Cette ressource comporte quatre exercices guidés sur le début de l'arithmétique dans Z : division euclidienne, recherche du pgcd par l'algorithme d'Euclide et identité de Bézout.
Prérequis indispensables :
Le théorème de la division euclidienne, l'existence de l'algorithme d'Euclide à partir du deuxième exercice, l'identité de Bézout à partir du troisième exercice et le théorème de Gauss pour le quatrième exercice.
Objectifs :
Comprendre le théorème de la division euclidienne, savoir trouver le pgcd de deux nombres, quand les diviseurs communs ne sont pas immédiats, et trouver une et toutes les relations existant entre deux nombres et leur pgcd.
Temps de travail prévu : 60 minutes
Il est conseillé de faire le troisième exercice avant le quatrième.
Sommaire :
Enoncé
Déterminer, dans chacun des cas suivants, le quotient et le reste de la division euclidienne de l'entier a par l'entier b :
Durée : 10 minutes
Aide de lecture
Le théorème de la division euclidienne dans Z est :
« Pour tout couple d'entiers a et b de Z, 
, il existe un couple unique 
d'entiers de Z tels que :
q est le quotient et r le reste de la division euclidienne de a par b. »
Attention, dans une division euclidienne, le reste doit être positif.
Aide de méthodologie
Remarquer que lorsqu'un nombre s vérifie les inégalités 
, alors le nombre 
vérifie les inégalités 
.
Le couple d'entiers de Z vérifiant les conditions 
étant unique, il suffit de trouver (par un moyen mathématiquement correct) un couple d'entiers de Z satisfaisant à ces conditions, pour être sûr d'avoir trouvé le quotient et le reste cherchés.
Solution
et 
.On effectue la division de 2341 par 432 :
Donc 
, comme 
, on en déduit : 
.
et 
.
On a aussi 
.
Or, le couple d'entiers de Z vérifiant les conditions étant unique, il suffit de trouver (par un moyen mathématiquement correct) un couple d'entiers de Z satisfaisant à ces conditions, pour être sûr d'avoir trouver le quotient et le reste cherchés.
Donc, comme 
, on déduit du calcul précédent : 
.
et .
On remarque que :
mais le reste 
ne convient pas car il est négatif.
Or, si un nombre s vérifie les inégalités , alors le nombre vérifie les inégalités .
Par conséquent, en ajoutant et retranchant 432, on obtient :
Comme 
, on en déduit : 
.
et .
On a aussi 
.
Donc 
.
Enoncé
Durée : 7 minutes
Aide de lecture
Lorsque les diviseurs de a et b ne sont pas commodes à calculer, il vaut mieux utiliser l'algorithme d'Euclide.
Aide de méthodologie
Si , l'ensemble des diviseurs de a et b est égal à l'ensemble des diviseurs de b et r, par conséquent le pgcd de a et b est égal au pgcd de b et r.
L'algorithme d'Euclide consiste à effectuer des divisions euclidiennes pour calculer les quotients et les restes successifs jusqu'à ce que l'on trouve un reste nul.
Aide supplémentaire
Par exemple 
, donc le pgcd de a et b est égal au pgcd de b et 
; on recommence alors en effectuant la division euclidienne de 
par .
Solution
On a donc :
Or 
.
Donc 
.
|
Remarques :
|
Enoncé
Calculer le pgcd d des nombres a et b, 
, 
, et un couple d'entiers 
tel que 
.
Durée : 18 minutes
Aide de méthodologie
Le calcul du pgcd de a et b par l'algorithme d'Euclide permet de trouver un couple d'entiers : en effet il suffit de remarquer que chaque reste s'écrit comme une « combinaison linéaire » à coefficients entiers des deux restes précédents et donc va s'écrire comme une « combinaison linéaire » à coefficients entiers de a et b.
Faire les calculs en utilisant les lettres « a » et « b » et non leurs valeurs.
Aide supplémentaire
Par exemple pour et , on a : 
, donc 
.
Comme 
, on déduit :
,
et ainsi de suite.
Solution
En effectuant des divisions euclidiennes, on calcule les quotients et les restes successifs jusqu'à ce que l'on trouve un reste nul :
Le dernier reste non nul est 7, donc 7 est le pgcd de et :
Pour trouver u et v, il suffit de remarquer que chaque reste s'écrit comme une « combinaison linéaire » à coefficients entiers des deux restes précédents et donc va s'écrire comme une « combinaison linéaire » à coefficients entiers de a et b :
D'après l'égalité (1) on a : 
. En utilisant les notations a et b (, ), on donc 
. (1bis)
De même (2) donne : 
, donc, en utilisant (1bis), il vient : 
, d'où 
. (2bis)
D'après l'égalité (3) : 
, donc, en utilisant (1bis) et (2bis), il vient : 
, d'où 
. (3bis)
D'après l'égalité (4) : 
, donc, en utilisant (2bis) et (3bis), il vient : 
, d'où 
. (4bis)
Enfin, d'après l'égalité (5) : 
, donc, en utilisant (3bis) et (4bis), il vient : 
, d'où 
.
|
Le couple |
Enoncé
Calculer le pgcd d des nombres a et b, 
, 
, et tous les couples d'entiers tel que
(Il est conseillé de faire auparavant l'exercice guidé précédent : « Recherche d'une relation de Bézout entre deux entiers »).
Durée : 25 minutes
Aide de lecture
Dans l'exercice guidé précédent, on apprend à trouver un couple vérifiant l'identité de Bézout : 
.
Dans cet exercice, on recherche tous les couples ayant cette propriété : on cherche les solutions dans Z de l'équation , où a, b et d sont des entiers de Z.
L'équation est un exemple d'équation diophantienne. (Une équation diophantienne est une équation polynomiale à coefficients dans Z ou Q, dont on cherche les solutions dans Z ou Q).
Aide de méthodologie
On cherche d'abord un couple 
vérifiant 
. On remarque qu'un autre couple sera tel que 
.
Chercher alors les propriétés que vérifie le nombre 
en utilisant le théorème de Gauss : si x, y et z sont des entiers relatifs tels que x divise le produit 
et si x et y sont premiers entre eux, alors x divise z.
Aide supplémentaire
Remarquer que lorsque les nombres u, v, 
et 
sont tels que 
, on peut « simplifier » les deux membres de l'égalité par le pgcd de a et b pour obtenir une égalité de type 
, avec 
et 
premiers entre eux.
Solution
En effectuant des divisions euclidiennes, on calcule les quotients et les restes successifs jusqu'à ce que l'on trouve un reste nul :
,
,
,
.
Le dernier reste non nul est 23, donc 23 est le pgcd de et :
.
On cherche d'abord un couple tel que : en conservant les notations a et b avec , , on a 
.
Puis 
, soit 
, donc 
.
, soit 
, donc 
.
On a donc trouvé un couple 
tel que 
.
On cherche maintenant tous les couples tels que 
.
S'il existe un autre couple tel que , alors on aura , donc .
On peut alors « simplifier » les deux membres de l'égalité par le pgcd de a et b pour obtenir une égalité de type , avec et premiers entre eux.
Le pgcd de et est 23 ; on a : 
, 
, et les nombres 
et 
sont premiers entre eux.
De l'égalité , on déduit : 
. 
Donc divise le produit d'entiers 
.
Mais est premier à ; par conséquent, d'après le théorème de Gauss, il divise le nombre .
Donc il existe 
tel que 
et on déduit de que 
.
Donc s'il existe un couple tel que , il est de la forme : 
, .
Réciproquement, tout couple tel que 
et vérifie l'égalité , donc l'égalité , donc 
.
Conclusion : L'ensemble des couples 
tels que 
est l'ensemble 
.
et 
.
vérifie l'identité 
.