Soient a et b deux entiers relatifs non nuls.
On dit que a et b sont premiers entre eux lorsque leurs seuls diviseurs communs sont 1 et -1. Autrement dit, a et b sont premiers entre eux lorsque \operatorname{PGCD}(a\:; b)=1.

Deux nombres premiers distincts sont premiers entre eux.

Soient d^{\prime}=\operatorname{PGCD}\left(a^{\prime} ; b^{\prime}\right) et k_1 et k_2 les entiers tels que a^{\prime}=d' k_{1} et b^{\prime}=d^{\prime} k_2.
On doit montrer que d = 1.
En effet, a=d d^{\prime} k_{1} et b=d d^{\prime} k_{2} donc d d^{\prime} est un diviseur commun à a et b. Comme d=\operatorname{PGCD}(a\:; b), on a nécessairement d d^{\prime} \leqslant d donc, puisque d>0, d^{\prime}=1.
Réciproquement, \operatorname{PGCD}(a \:; b) =\operatorname{PGCD}\left(d a^{\prime} ; d b^{\prime}\right) =d \operatorname{PGCD}\left(a^{\prime} ; b^{\prime}\right) = d car a' et b' sont premiers entre eux.

36=12 \times 3 et 60=12 \times 5. Puisque 3 et 5 sont premiers entre eux, alors \operatorname{PGCD}(60\:; 36)=12.

Déterminer l'ensemble des couples (a \:; b) \in \mathbb{N}^{2} tels que \left\{\begin{array}{l}a b=300 \\ \operatorname{PGCD}(a \:; b)=5\end{array}\right..

• Introduire les entiers a' et b' premiers entre eux tels que \left\{\begin{array}{l}a=5 a^{\prime} \\ b=5 b^{\prime}\end{array}\right..
• Écrire une équation vérifiée par le produit a'b' et lister les couples d'entiers premiers entre eux vérifiant cette équation.
• En déduire les valeurs possibles pour a et b.

Puisque \operatorname{PGCD}(a \:; b)=5, il existe deux entiers a' et b' premiers entre eux tels que \left\{\begin{array}{l}a=5 a^{\prime} \\ b=5 b^{\prime }\end{array}\right..
On a alors a b=25 a^{\prime} b^{\prime} donc 25 a^{\prime} b^{\prime}=300 et ainsi a^{\prime} b^{\prime}=12.
Or 12=1 \times 12=2 \times 6=3 \times 4.
Comme a' et b' doivent être premiers entre eux, les couples possibles sont (1\:; 12),(12\:; 1),(3\:; 4) et (4\:; 3) ce qui donne pour (a\:; b) les couples (5\:; 60),(60\:; 5),(15\:; 20) et (20\:; 15).
Réciproquement, chacun de ces couples est solution du système.

Exercices

33

et

34

p. 132.

Tout sous-ensemble non vide de \N admet un plus petit élément.

Le théorème de Bézout donne l'existence d'entiers u et v mais ne donne pas de méthode pour en déterminer.

Soit (a\:; b) un couple d'entiers relatifs non nuls.
Alors a et b sont premiers entre eux si, et seulement si, il existe deux entiers relatifs u et v tels que a u+b v=1.

Il n'y a pas unicité des entiers u et v tels que au + bv = 1.

• On commence par justifier qu'il existe bien un couple d'entiers (u\:; v) tel que 29 u+12 v=1.
• On applique l'algorithme d'Euclide pour connaître tous les restes successifs jusqu'au reste égal à 1.
• On utilise les divisions euclidiennes obtenues en « remontant » l'algorithme d'Euclide pour déterminer u et v.

Puisque 29 est un nombre premier, 29 et 12 sont premiers entre eux.
Il existe donc deux entiers u et v tels que 29u + 12v = 1.
D'après l'algorithme d'Euclide, on a les égalités suivantes :
29=12 \times 2+5\left(\mathrm{E}_{1}\right) ; 12=5 \times 2+2\left(\mathrm{E}_{2}\right) et 5=2 \times 2+1\left(\mathrm{E}_{3}\right).
D'après \left(\mathrm{E}_{3}\right), on a 1=5-2 \times 2 et, d'après \left(\mathrm{E}_{2}\right), on a 2=12-5 \times 2.
Donc, 1=5-2 \times(12-5 \times 2)=5 \times 5-2 \times 12.
D'après \left(\mathrm{E}_{1}\right), on a 5=29-2 \times 12 d'où 1=5 \times(29-2 \times 12)-2 \times 12 soit finalement 1=29 \times 5+12 \times(-12).
On a donc trouvé u = 5 et v = -12.

Exercices

43

et

44

p. 133.

Pour tout couple (a\:; b) \in \mathbb{Z}^{* 2}, il existe (u\:; v) \in \mathbb{Z}^{2} tel que a u+b v=\operatorname{PGCD}(a\:; b).

Le couple (u\:; v) n'est pas unique.

Soient a et b deux entiers relatifs non nuls et on pose d=\operatorname{PGCD}(a\:; b).
Il existe deux entiers a' et b' tels que a=a^{\prime} d et b=b^{\prime} d et tels que \operatorname{PGCD}\left(a^{\prime} ; b^{\prime}\right)=1.
D'après le théorème de Bézout, il existe (u\:; v) \in \mathbb{Z}^{2} tel que a^{\prime} u+b^{\prime} v=1.
On a alors a u+b v=a^{\prime} d u+b^{\prime} d v=d\left(a^{\prime} u+b^{\prime} v\right)=\operatorname{PGCD}(a\:; b).

L'identité de Bézout est en réalité vraie pour (a ; b) \in \mathbb{Z}^{2}.

Le \text{PGCD} de 84 et 18 est 6 donc il existe des entiers u et v tels que 84 u+18 v=6. Pour les déterminer, on peut se ramener à l'équation diophantienne 14 u+3 v=1 dont une solution est (-1\:; 5). On vérifie : -84+18 \times 5=-84+90=6.

On appelle équation diophantienne une équation à coefficients entiers, dont on cherche une solution entière (ou rationnelle).

Soient a, b et c trois entiers tels que a et b ne sont pas simultanément nuls.
L'équation a x+b y=c admet des couples d'entiers (x\:; y) solutions si, et seulement si, le nombre c est un multiple de \operatorname{PGCD}(a\:; b).

Voir exercice

88

p. 136.

Il existe a \in \mathbb{Z} tel que 30 a \equiv 1[23] si, et seulement si, il existe (a ; b) \in \mathbb{Z}^{2} tel que 30 a+23 b=1.

• Vérifier que cette équation admet une solution en écrivant l'algorithme d'Euclide pour déterminer le \text{PGCD} de 30 et 23.
• Remonter les lignes de l'algorithme d'Euclide en partant de l'avant-dernière (reste égal à 1) pour écrire 1 comme combinaison linéaire des deux derniers restes, puis des deux restes précédents, jusqu'à obtenir une combinaison linéaire de 30 et 23.

30 et 23 sont premiers entre eux donc, d'après le théorème de Bézout, il existe un couple d'entiers relatifs (a\:; b) tel que 30 a+23 b=1 donc il existe un entier a tel que 30a \equiv 1[23].
L'algorithme d'Euclide et sa remontée permettent d'obtenir 1=30 \times 10-23 \times 13.
On en déduit que (10\:;-13) est un couple solution et donc que 10 est un inverse de 30 modulo 23 :
30 \times 10 \equiv 1[23]

Exercices

48

et

49

p. 133.