PGCD, théorèmes de Bézout et de Gauss

Un artisan dispose d'une plaque rectangulaire de $119$ cm sur $51$ cm.

Il découpe le plus grand carré possible, puis le plus grand carré possible dans le rectangle restant, et ainsi de suite jusqu'à ce qu'il ne reste rien. Décrire les découpes successives.
Il veut maintenant couvrir toute la plaque avec des carrés tous de même taille, posés côte à côte en lignes et en colonnes, dont le côté est un nombre entier de centimètres, le plus grand possible. Quel est leur côté ?

Dans la plaque de $119 \times 51$, il découpe un carré de $51 \times 51$ : il reste un rectangle de $68 \times 51$. Un second carré de $51 \times 51$ laisse un rectangle de $17 \times 51$, que trois carrés de $17 \times 17$ épuisent, car $51 = 3 \times 17$.
Les carrés forment des lignes et des colonnes, donc un nombre entier de côtés remplit chaque dimension de la plaque : leur côté $c$ divise $119$ et $51$. Découper un carré ne change pas les diviseurs communs des deux dimensions :
- comme $68 = 119 - 51$ et $119 = 68 + 51$, l'entier $c$ divise $119$ et $51$ exactement lorsqu'il divise $68$ et $51$ ;
- comme $17 = 68 - 51$ et $68 = 17 + 51$, cela se produit exactement lorsque $c$ divise $17$ et $51$, c'est-à-dire, puisque $17$ divise $51$, lorsque $c$ divise $17$.
Le plus grand côté possible est $17$ cm, et $7 \times 3 = 21$ carrés couvrent la plaque, car $119 = 7 \times 17$.

Les découpes successives sont les divisions euclidiennes $119 = 51 \times 2 + 17$ et $51 = 17 \times 3 + 0$. Le côté $17$ est le plus grand commun diviseur de $119$ et de $51$ : les découpes successives l'ont trouvé sans lister aucun diviseur. C'est l'idée de l'algorithme d'Euclide.

Proposition — Existence du PGCD

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls. L'ensemble des diviseurs communs à $a$ et $b$ admet un plus grand élément.

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls.

L'ensemble des diviseurs d'un entier non nul est fini. Comme au moins l'un des deux entiers $a$ ou $b$ est non nul, au moins l'un des deux ensembles de diviseurs est fini, donc leur intersection (l'ensemble des diviseurs communs) est finie.
L'ensemble des diviseurs communs n'est pas vide car $1$ divise $a$ et $b$.
Or tout sous-ensemble fini non vide de $\mathbb{Z}$ admet un plus grand élément. Donc l'ensemble des diviseurs communs admet un plus grand élément.

Définition — Plus grand commun diviseur (PGCD)

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls. Le plus grand élément de l'ensemble des diviseurs communs positifs de $a$ et $b$ est appelé le plus grand commun diviseur. On le note $PGCD(a,b)$.

Exemple

$PGCD(24, 18) = 6$ : les diviseurs positifs de $24$ sont $1$, $2$, $3$, $4$, $6$, $8$, $12$ et $24$, ceux de $18$ sont $1$, $2$, $3$, $6$, $9$ et $18$, et le plus grand nombre commun aux deux listes est $6$. De même, $PGCD(-24, 18) = 6$, puisque $-24$ et $24$ ont les mêmes diviseurs.

Proposition — Propriétés du PGCD

Soient $a$ et $b$ des entiers relatifs non nuls.

Si $b$ divise $a$, alors $PGCD(a,b)=|b|$.
Pour tout entier relatif $k$, $PGCD(a,b)=PGCD(a-kb,b)$.
Si \(0

Soient $a$ et $b$ deux entiers relatifs non nuls.

Si $b$ divise $a$. L'entier strictement positif $|b|$ divise $a$ et $b$. Tout diviseur commun $d$ de $a$ et de $b$ divise l'entier non nul $b$, donc $d \le |b|$. Ainsi $PGCD(a, b) = |b|$.
$PGCD(a, b) = PGCD(a - kb, b)$ pour tout entier relatif $k$. Si $d$ divise $a$ et $b$, alors $d$ divise la combinaison linéaire $a - kb$ ; réciproquement, si $d$ divise $a - kb$ et $b$, alors $d$ divise $(a - kb) + kb = a$. Les couples $(a ; b)$ et $(a - kb ; b)$ ont les mêmes diviseurs communs, donc le même plus grand.
Le reste. Si $0 < b \le a$ et $a = bq + r$ avec $0 \le r < b$, le point précédent avec $k = q$ donne $PGCD(a, b) = PGCD(a - qb, b) = PGCD(r, b) = PGCD(b, r)$.

Compétences à pratiquer

Analyser les propriétés du PGCD

I.2 L'algorithme d'Euclide en pseudo-code

Définition — L'algorithme d'Euclide

Le plus grand commun diviseur de deux entiers naturels est le plus grand nombre qui les divise tous les deux. L'algorithme d'Euclide le calcule par les restes : tant que le second nombre n'est pas nul, remplacer le couple (a ; b) par le couple (b ; r), où r est le reste de a par b ; quand le second devient nul, le premier est la réponse. Les deux nombres sont des entiers naturels et l'un au moins n'est pas nul, puisqu'un couple de deux zéros n'a pas de plus grand commun diviseur : tout entier divise zéro.

Méthode — Justifier l'algorithme d'Euclide

Terminaison : le second nombre du couple est un entier naturel, et à chaque tour il devient le reste de la division de a par b, donc il est strictement plus petit que le b qu'il remplace, et un reste n'est jamais négatif. Un entier naturel ne peut pas décroître indéfiniment au-dessus de zéro, donc le second nombre atteint zéro.
Correction : écrire la division sous la forme $a = q \times b + r$. Un nombre qui divise a et b divise $a - q \times b$, c'est-à-dire r ; et un nombre qui divise b et r divise $q \times b + r$, c'est-à-dire a. Les deux couples ont donc exactement les mêmes diviseurs communs, et le plus grand d'entre eux voyage inchangé de tour en tour.
Lecture de la réponse : quand le second est nul, les diviseurs communs du couple sont les diviseurs du premier, dont le plus grand est le premier lui-même.
Désigner la colonne du tableau d'états qui porte l'argument : le second nombre, strictement décroissant, est le variant ; le plus grand commun diviseur, inchangé, est ce qui reste vrai à chaque tour.

Exemple

Exécuter à la main l'algorithme d'Euclide sur $1071$ et $462$, et donner la valeur qu'il affiche.

a ← 1071
b ← 462
Tant que b ≠ 0
    r ← reste de a par b
    a ← b
    b ← r
Fin Tant que
Afficher a

Instruction	$a$	$b$	$r$	$b \neq 0$	Affichage
départ	$1071$	$462$
tour 1	$462$	$147$	$147$	vrai
tour 2	$147$	$21$	$21$	vrai
tour 3	$21$	$0$	$0$	vrai
fin	$21$	$0$	$0$	faux
Afficher $a$	$21$	$0$	$0$		$21$

Il affiche 21. Trois tours, et la colonne $b$ porte les deux arguments à la fois : elle vaut $462$, $147$, $21$, $0$, strictement décroissante, ce pourquoi la boucle se termine ; et le plus grand commun diviseur du couple de chaque ligne vaut $21$ à toutes, ce pourquoi la dernière ligne se lit comme la réponse. Écrits comme des divisions, les trois tours sont $1071 = 2 \times 462 + 147$, puis $462 = 3 \times 147 + 21$, puis $147 = 7 \times 21 + 0$ : l'algorithme est la chaîne de ces divisions, et rien d'autre.

Compétences à pratiquer

Exécuter et justifier l'algorithme d'Euclide

I.3 Algorithme d'Euclide

Théorème — Le PGCD est le dernier reste non nul

Soient $a$ et $b$ deux entiers tels que $a \ge b > 0$. On effectue la division euclidienne de $a$ par $b$, puis celle du diviseur par le reste, et ainsi de suite tant que le reste n'est pas nul. Cette suite de divisions s'arrête après un nombre fini d'étapes, et :

si le premier reste est nul, alors $PGCD(a, b) = b$ ;
sinon, $PGCD(a, b)$ est le dernier reste non nul.

Plus généralement, soient $x$ et $y$ deux entiers relatifs non tous deux nuls. Si l'un d'eux est nul, leur PGCD est la valeur absolue de l'autre ; sinon, l'algorithme appliqué au plus grand et au plus petit des entiers $|x|$ et $|y|$ donne $PGCD(x, y)$.

On écrit les divisions successives : $a = bq_0 + r_0$ avec $0 \le r_0 < b$ ; si $r_0 \neq 0$, $b = r_0 q_1 + r_1$ avec $0 \le r_1 < r_0$ ; si $r_1 \neq 0$, $r_0 = r_1 q_2 + r_2$ avec $0 \le r_2 < r_1$ ; et ainsi de suite.

L'algorithme s'arrête. Les restes vérifient $b > r_0 > r_1 > r_2 > \dots \ge 0$ : ce sont des entiers naturels inférieurs à $b$ qui décroissent strictement, il y en a donc au plus $b$, et un reste nul est atteint.
Premier reste nul. Si $r_0 = 0$, alors $b$ divise $a$, et $PGCD(a, b) = b$ d'après les propriétés du PGCD.
Sinon. Soit $r_n$ le dernier reste non nul : la division suivante s'écrit $r_{n-1} = r_n q_{n+1} + 0$, où $r_{-1}$ désigne $b$ lorsque $n = 0$. D'après les propriétés du PGCD, chaque division conserve le PGCD : $$PGCD(a, b) = PGCD(b, r_0) = PGCD(r_0, r_1) = \dots = PGCD(r_{n-1}, r_n).$$ Comme $r_n$ divise $r_{n-1}$, $PGCD(r_{n-1}, r_n) = r_n$, donc $PGCD(a, b) = r_n$.
Deux entiers quelconques. Soient $x$ et $y$ deux entiers relatifs non tous deux nuls. Un entier divise $x$ si et seulement s'il divise $-x$, et les diviseurs communs de $x$ et de $y$ ne dépendent pas de leur ordre : les couples $(x ; y)$, $(y ; x)$ et $(|x| ; |y|)$ ont les mêmes diviseurs communs, donc le même PGCD. Si $y = 0$, tout entier divise $0$, donc les diviseurs communs de $x$ et de $0$ sont les diviseurs de $x$, dont le plus grand est $|x|$ ; le cas $x = 0$ est analogue. Sinon, l'algorithme s'applique au plus grand et au plus petit des entiers $|x|$ et $|y|$.

Méthode — Algorithme d'Euclide

Soient $a$ et $b$ deux entiers tels que $0 < b \leq a$. Alors, l'algorithme suivant permet de calculer, en un nombre fini d'étapes, le PGCD de $a$ et $b$ :

Calculer le reste $r$ dans la division euclidienne de $a$ par $b$.
Tant que $r \neq 0$ faire :
- $a \leftarrow b$,
- $b \leftarrow r$,
- calculer le nouveau reste $r$ de la division euclidienne de $a$ par $b$.
Fin du tant que
Renvoyer $b$ : c'est le PGCD des deux entiers de départ.

Exemple

Calculer $PGCD(1554,136)$ à l'aide de l'algorithme d'Euclide.

$$\begin{aligned}1554 &= 136\times 11 + 58,\\ 136 &= 58\times 2 + 20,\\ 58 &= 20\times 2 + 18,\\ 20 &= 18\times 1 + 2,\\ 18 &= 2\times 9 + 0.\end{aligned}$$ Le dernier reste non nul est $2$, donc $PGCD(1554,136)=2$.

Compétences à pratiquer

Calculer le PGCD par l'algorithme d'Euclide
Modéliser avec le PGCD

I.4 Nombres premiers entre eux

Définition — Nombres premiers entre eux

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls.
On dit que $a$ et $b$ sont premiers entre eux si $PGCD(a,b)=1$.

Exemple

$PGCD(15,8)=1$, donc $15$ et $8$ sont premiers entre eux.
Pour tout entier relatif $a$, $PGCD(a,1)=1$, donc $1$ est premier avec tout entier.

Remarques

Il ne faut pas confondre nombres premiers entre eux et nombres premiers. Les entiers $15$ et $8$ sont premiers entre eux mais ni l'un ni l'autre n'est premier. En revanche, deux nombres premiers distincts sont toujours premiers entre eux.
Une fraction irréductible $q$ s'écrit comme le rapport de deux entiers premiers entre eux : $$ q=\frac{a}{b} \quad \text{avec } a\in\mathbb{Z},\ b\in\mathbb{N}^*,\ \text{et } PGCD(a,b)=1. $$

Signaler une erreur

Proposition — Diviser par le PGCD

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls et $d = PGCD(a, b)$. Alors $a = da'$ et $b = db'$, où $a'$ et $b'$ sont des entiers relatifs premiers entre eux.

Comme $d$ divise $a$ et $b$, il existe des entiers relatifs $a'$ et $b'$ tels que $a = da'$ et $b = db'$ ; ils ne sont pas tous deux nuls, puisque $a$ et $b$ ne le sont pas. Soit $c$ un diviseur commun strictement positif de $a'$ et de $b'$. Alors $dc$ divise $da' = a$ et $db' = b$ : c'est un diviseur commun strictement positif de $a$ et de $b$, donc $dc \le d$ par définition du PGCD. Ainsi $c \le 1$, c'est-à-dire $c = 1$. Le seul diviseur commun strictement positif de $a'$ et de $b'$ est $1$, donc $PGCD(a', b') = 1$ : les entiers $a'$ et $b'$ sont premiers entre eux.

Compétences à pratiquer

Étudier si des entiers sont premiers entre eux
Résoudre des problèmes faisant intervenir le PGCD

II Théorème de Bézout

II.1 Identité et théorème de Bézout

Dans un jeu, la caisse et les joueurs n'utilisent que des jetons de $7~\Euro$ et des jetons de $11~\Euro$. Un joueur peut-il régler exactement $1~\Euro$, en donnant des jetons et en en recevant en retour ? Et si les seuls jetons valaient $6~\Euro$ et $9~\Euro$ ?

Avec des jetons de $7~\Euro$ et de $11~\Euro$, le joueur donne deux jetons de $11~\Euro$ et reçoit trois jetons de $7~\Euro$ : $2 \times 11 - 3 \times 7 = 22 - 21 = 1$. En général, si le joueur donne $u$ jetons de $11~\Euro$ et $v$ jetons de $7~\Euro$, un nombre négatif comptant des jetons reçus, le montant réglé vaut $11u + 7v$ ; ici $u = 2$ et $v = -3$.
Avec des jetons de $6~\Euro$ et de $9~\Euro$, tout montant échangé vaut $6u + 9v = 3(2u + 3v)$, un multiple de $3$ : régler exactement $1~\Euro$ est impossible. Le plus petit montant strictement positif est $3~\Euro$, par exemple $9 - 6$.
Dans les deux cas, les montants que l'on peut régler sont exactement les multiples du PGCD des deux valeurs. Avec des jetons de $6~\Euro$ et de $9~\Euro$, tout montant est un multiple de $3$, et en répétant l'échange $9 - 6 = 3$ on règle n'importe quel multiple de $3 = PGCD(6, 9)$. Avec des jetons de $7~\Euro$ et de $11~\Euro$, en répétant l'échange qui règle $1~\Euro$ on règle n'importe quel montant entier, c'est-à-dire n'importe quel multiple de $1 = PGCD(7, 11)$. L'identité de Bézout explique ce lien avec le PGCD.

Proposition — Identité de Bézout

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls et $d=PGCD(a,b)$.
Alors, il existe un couple d'entiers relatifs $(u ; v)$ tel que$$au+bv=d.$$

On considère l'ensemble $S$ des combinaisons linéaires strictement positives de $a$ et $b$ :$$S=\{am+bn \mid m,n\in\mathbb{Z}\ \text{et}\ am+bn>0\}.$$

$S$ est non vide : comme $a$ et $b$ ne sont pas tous deux nuls, l'un au moins des entiers $a,-a,b,-b$ est strictement positif et appartient à $S$.
$S$ étant une partie non vide de $\mathbb{N}^*$, elle admet un plus petit élément $d_0$. Il existe donc des entiers relatifs $u$ et $v$ tels que $d_0=au+bv$.
On montre que $d_0$ divise $a$. On effectue la division euclidienne de $a$ par $d_0$ : $$ a=d_0q+r \quad \text{avec } 0\le r0\), alors $r\in S$, mais \(r
Enfin, $d_0$ est bien le PGCD : si $d'$ est un diviseur commun de $a$ et $b$, alors $d'$ divise toute combinaison linéaire de $a$ et $b$, en particulier $d_0=au+bv$. Donc $d'\le d_0$, et ainsi $d_0=PGCD(a,b)$.

Proposition — Diviseurs communs et PGCD

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls.

Tout diviseur commun à $a$ et à $b$ divise $PGCD(a, b)$.
Pour tout entier relatif $k$ non nul, $PGCD(ka, kb) = |k| \, PGCD(a, b)$.

Soit $d = PGCD(a, b)$. D'après l'identité de Bézout, il existe des entiers relatifs $u$ et $v$ tels que $au + bv = d$.

Si $c$ divise $a$ et $b$, alors $c$ divise la combinaison linéaire $au + bv$, c'est-à-dire $d$.
Soient $k$ un entier relatif non nul et $D = PGCD(ka, kb)$, défini puisque $ka$ et $kb$ ne sont pas tous deux nuls. Comme $d$ divise $a$ et $b$, $|k|d$ divise $ka$ et $kb$ ; d'après le premier point, $|k|d$ divise $D$, donc $|k|d \le D$. Réciproquement, $D$ divise $ka$ et $kb$, donc la combinaison $ka \times u + kb \times v = kd$, qui n'est pas nulle, d'où $D \le |kd| = |k|d$. Ainsi $D = |k|d$.

Proposition — Théorème de Bézout

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls.
$PGCD(a,b)=1$ si et seulement s'il existe un couple d'entiers relatifs $(u ; v)$ tel que $au+bv=1$.

$(\Rightarrow)$ Si $PGCD(a,b)=1$, l'existence de $(u ; v)$ découle de l'identité de Bézout.
$(\Leftarrow)$ On suppose qu'il existe des entiers relatifs $u,v$ tels que $au+bv=1$. Soit $d=PGCD(a,b)$. Comme $d\mid a$ et $d\mid b$, on a $d\mid (au+bv)$, donc $d\mid 1$. Comme $d$ est un entier positif, on obtient $d=1$.

Exemple

Soit $n$ un entier relatif. Montrer que $5n + 4$ et $4n + 3$ sont premiers entre eux.

Soient $a = 5n + 4$ et $b = 4n + 3$ ; ils ne sont pas tous deux nuls, puisque $5n + 4 = 0$ n'a pas de solution entière. On cherche des coefficients entiers qui éliminent $n$ : comme $4 \times 5n = 5 \times 4n$, $$\begin{aligned} 4a - 5b &= 4(5n + 4) - 5(4n + 3)\\ &= 20n + 16 - 20n - 15\\ &= 1. \end{aligned}$$ Ainsi $a \times 4 + b \times (-5) = 1$ avec les entiers relatifs $4$ et $-5$ : d'après le théorème de Bézout, $PGCD(a, b) = 1$. Donc $5n + 4$ et $4n + 3$ sont premiers entre eux pour tout entier relatif $n$.

Compétences à pratiquer

Analyser le théorème et l'identité de Bézout
Démontrer par Bézout que des entiers sont premiers entre eux ou qu'une fraction est irréductible
Exploiter le PGCD de multiples

II.2 Coefficients de Bézout

Méthode — Trouver des coefficients de Bézout

Soient $a$ et $b$ deux entiers relatifs avec $b\neq 0$.

Appliquer l'algorithme d'Euclide à $(|a| ; |b|)$ pour obtenir $PGCD(a,b)$.
Remonter les égalités (algorithme d'Euclide étendu) pour écrire $PGCD(a,b)$ comme combinaison linéaire de $|a|$ et de $|b|$.
Si $a$ ou $b$ est négatif, ajuster les signes des coefficients en conséquence (remplacer $u$ par $-u$ si $a < 0$, et $v$ par $-v$ si $b < 0$).

Exemple

Déterminer des entiers relatifs $u$ et $v$ tels que $47u+39v=1$.

On commence par appliquer l'algorithme d'Euclide pour trouver le PGCD :

$47 = 39 \times 1 + 8\quad \textcircled{1}$
$39 = 8 \times 4 + 7 \quad \textcircled{2}$
$8 = 7 \times 1 + 1 \quad \textcircled{3}$

On exprime chaque reste à partir des égalités précédentes :

D'après $\textcircled{3}: 1 = 8 - 7 \times 1$
D'après $\textcircled{2}: 7 = 39 - 8 \times 4$
D'après $\textcircled{1}: 8 = 47 - 39 \times 1$

Enfin, on « remonte » les calculs pour exprimer $1$ en fonction de $47$ et $39$ :$$\begin{aligned}1 &= 8 - (39 - 8 \times 4) \times 1 && (\text{en substituant } 7 \text{ d'après } \textcircled{2}) \\ 1 &= 8 \times 5 - 39 && (\text{en simplifiant}) \\ 1 &= (47 - 39 \times 1) \times 5 - 39 && (\text{en substituant } 8 \text{ d'après } \textcircled{1}) \\ 1 &= 47 \times 5 - 39 \times 5 - 39 && (\text{en développant}) \\ 1 &= 47 \times 5 + 39 \times (-6) && (\text{forme finale})\end{aligned}$$ Ainsi, le couple $(u ; v) = (5 ; -6)$ est une solution. Vérification : $47 \times 5 + 39 \times (-6) = 235 - 234 = 1$.

Compétences à pratiquer

Déterminer des coefficients de Bézout

II.3 Inverse modulo $n$

Exemple

Montrer que $9$ est un inverse de $3$ modulo $26$.

On vérifie la relation de définition : $3 \times 9 = 27 = 26 + 1$, donc $3 \times 9 \equiv 1 \pmod{26}$. Par définition, $9$ est un inverse de $3$ modulo $26$.

Proposition — Inversibilité modulo $n$

Soient $n \ge 2$ un entier naturel et $a$ un entier relatif. Alors $a$ admet un inverse modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux.

On suppose que $PGCD(a, n) = 1$. Le théorème de Bézout donne des entiers relatifs $u$ et $v$ tels que $au + nv = 1$. Alors $au - 1 = -nv$ est un multiple de $n$ : $au \equiv 1 \pmod{n}$, et $u$ est un inverse de $a$ modulo $n$.
Réciproquement, on suppose que $a$ admet un inverse $u$ modulo $n$ : $au \equiv 1 \pmod{n}$, donc il existe un entier relatif $v$ tel que $au - 1 = nv$, c'est-à-dire $au + n(-v) = 1$. D'après le théorème de Bézout, $a$ et $n$ sont premiers entre eux.

Méthode — Inverse modulaire par Bézout

Pour déterminer un inverse de $a$ modulo $n$ (avec $n \ge 2$ et $PGCD(a, n) = 1$) :

D'après le théorème de Bézout, il existe des entiers $u, v$ tels que $au + nv = 1$.
En réduisant modulo $n$ : $au \equiv 1 \pmod{n}$, donc le coefficient $u$ (obtenu par la remontée de l'algorithme d'Euclide) est un inverse de $a$ modulo $n$.

Exemple

Déterminer un inverse de $7$ modulo $26$.

Algorithme d'Euclide pour $(26 ; 7)$ :

$26 = 7 \times 3 + 5 \quad \textcircled{1}$
$7 = 5 \times 1 + 2 \quad \textcircled{2}$
$5 = 2 \times 2 + 1 \quad \textcircled{3}$

En remontant : $$\begin{aligned} 1 &= 5 - 2 \times 2 &&(\text{d'après } \textcircled{3})\\ &= 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7 &&(\text{en substituant } 2 \text{ d'après } \textcircled{2})\\ &= 3 \times (26 - 3 \times 7) - 2 \times 7 &&(\text{en substituant } 5 \text{ d'après } \textcircled{1})\\ &= 3 \times 26 - 11 \times 7 &&(\text{forme finale}) \end{aligned}$$ Ainsi $7 \times (-11) \equiv 1 \pmod{26}$, et comme $-11 \equiv 15 \pmod{26}$, un inverse de $7$ modulo $26$ est $\boxed{15}$. (Vérification : $7 \times 15 = 105 = 4 \times 26 + 1$.)

Compétences à pratiquer

Déterminer un inverse modulo $n$

III Théorème de Gauss et applications

III.1 Théorème de Gauss

Soit $n$ un entier relatif.

Si $9$ divise $4n$, $9$ divise-t-il nécessairement $n$ ?
Si $9$ divise $6n$, $9$ divise-t-il nécessairement $n$ ?

Oui. Si $9$ divise $4n$, alors $9$ divise $7 \times 4n = 28n$ ; il divise aussi $3 \times 9n = 27n$, donc leur différence $28n - 27n = n$. Les multiplicateurs $7$ et $3$ viennent de la relation $7 \times 4 - 3 \times 9 = 1$ entre $4$ et $9$.
Non. Pour $n = 3$, $6n = 18$ est divisible par $9$, mais $3$ ne l'est pas. Ici, $6$ et $9$ ont le facteur $3$ en commun : toute combinaison $6u + 9v = 3(2u + 3v)$ est un multiple de $3$, donc aucune n'est égale à $1$.

Le théorème de Gauss énonce la règle générale : si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

Théorème — Théorème de Gauss

Soient $a$, $b$ et $c$ trois entiers relatifs.
Si $a$ divise le produit $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

On suppose que $a \mid bc$ et que $PGCD(a,b)=1$.

Puisque $a \mid bc$, il existe un entier relatif $k$ tel que $bc=ka$.
Puisque $PGCD(a,b)=1$, d'après le théorème de Bézout, il existe des entiers relatifs $u$ et $v$ tels que $$ au+bv=1. $$
En multipliant par $c$, on obtient $$ c(au+bv)=c \implies acu+bcv=c. $$
On réécrit $a(cu)+(bc)v=c$ et on remplace $bc$ par $ka$ : $$ a(cu)+(ka)v=c \implies a(cu+kv)=c. $$
Comme $(cu+kv)$ est un entier relatif, on en déduit que $a\mid c$.

Exemple

Déterminer tous les entiers naturels $n$ tels que $12$ divise $9n$.

On suppose $12 \mid 9n$ : il existe un entier $k$ tel que $9n = 12k$, soit $3n = 4k$ après division par $3$. Alors $4 \mid 3n$, et comme $PGCD(4, 3) = 1$, le théorème de Gauss donne $4 \mid n$.
Réciproquement, si $n = 4k'$, alors $9n = 36k' = 12 \times 3k'$ est divisible par $12$.
Les solutions sont exactement les multiples de $4$ : $n \in \{0 ; 4 ; 8 ; 12 ; \dots\}$. (Vérification : $9 \times 4 = 36 = 12 \times 3$.)

Compétences à pratiquer

Appliquer le théorème de Gauss

III.2 Corollaires du théorème de Gauss

Proposition — Corollaires du théorème de Gauss

Si un entier est divisible par des entiers $a$ et $b$ premiers entre eux, alors il est divisible par leur produit $ab$.
Si un nombre premier divise un produit $ab$, alors il divise au moins l'un des facteurs $a$ ou $b$.

On démontre les deux corollaires.

Premier corollaire. On suppose $a \mid m$ et $b \mid m$ avec $PGCD(a, b) = 1$. Comme $a \mid m$, il existe un entier $k$ tel que $m = ka$. Alors $b \mid ka$ avec $PGCD(a, b) = 1$, donc d'après le théorème de Gauss $b \mid k$ : il existe un entier $k'$ tel que $k = bk'$. Ainsi $$m = ka = (bk')a = (ab)k' \implies ab \mid m.$$
Deuxième corollaire (lemme d'Euclide). On suppose $p$ premier et $p \mid ab$. Si $p \mid a$, c'est terminé. Sinon, les seuls diviseurs positifs de $p$ étant $1$ et $p$, les diviseurs communs de $p$ et $a$ se réduisent à $1$ : $PGCD(p, a) = 1$. Le théorème de Gauss appliqué à $p \mid ab$ donne alors $p \mid b$.

Exemple

Soit $n$ un entier relatif. Montrer que $n(n + 1)(n + 2)(n + 3)$ est divisible par $24$.

Soit $P = n(n + 1)(n + 2)(n + 3)$.

Divisibilité par $3$. Les entiers $n$, $n + 1$ et $n + 2$ ont pour restes $0$, $1$ et $2$ modulo $3$ dans un certain ordre, donc l'un d'eux est un multiple de $3$, et $3$ divise $P$.
Divisibilité par $8$. Parmi quatre entiers consécutifs, deux sont des nombres pairs consécutifs, $2m$ et $2m + 2$ pour un entier relatif $m$. Leur produit vaut $2m(2m + 2) = 4m(m + 1)$, et $m(m + 1)$ est pair, comme produit de deux entiers consécutifs : donc $8$ divise $4m(m + 1)$, et $8$ divise $P$.
Divisibilité par $24$. Comme $8 = 3 \times 2 + 2$ et $3 = 2 \times 1 + 1$, $PGCD(3, 8) = 1$. L'entier $P$ est divisible par $3$ et par $8$, qui sont premiers entre eux : d'après le premier corollaire du théorème de Gauss, $P$ est divisible par $3 \times 8 = 24$.

Vérification : pour $n = 1$, $P = 1 \times 2 \times 3 \times 4 = 24$.

Compétences à pratiquer

Exploiter les corollaires du théorème de Gauss

III.3 Équations diophantiennes du premier degré

Un jeu n'utilise que des jetons de $7~\Euro$ et des jetons de $11~\Euro$. Un joueur règle exactement $1~\Euro$ en donnant deux jetons de $11~\Euro$ et en recevant trois jetons de $7~\Euro$. Existe-t-il d'autres façons de régler exactement $1~\Euro$, en donnant des jetons et en en recevant en retour ? Les décrire toutes.

Soient $x$ le nombre de jetons de $7~\Euro$ et $y$ le nombre de jetons de $11~\Euro$ donnés, un nombre négatif comptant des jetons reçus. Les façons de régler $1~\Euro$ sont les solutions entières de $7x + 11y = 1$, et $(x ; y) = (-3 ; 2)$ en est une.

On suppose que $(x ; y)$ est une solution. En soustrayant $7 \times (-3) + 11 \times 2 = 1$, on obtient $7(x + 3) = 11(2 - y)$. Donc $11$ divise $7(x + 3)$ ; comme $PGCD(11, 7) = 1$, le théorème de Gauss donne $11 \mid x + 3$ : on pose $x = -3 + 11k$ avec $k \in \mathbb{Z}$. Alors $7 \times 11k = 11(2 - y)$, d'où $y = 2 - 7k$.
Réciproquement, pour tout entier relatif $k$, $7(-3 + 11k) + 11(2 - 7k) = -21 + 77k + 22 - 77k = 1$.

Les façons de régler $1~\Euro$ sont exactement les couples $(x ; y) = (-3 + 11k ; 2 - 7k)$, $k \in \mathbb{Z}$. Pour $k = 1$, le joueur donne huit jetons de $7~\Euro$ et reçoit cinq jetons de $11~\Euro$, puisque $56 - 55 = 1$. Une solution et le théorème de Gauss donnent toutes les autres : c'est la méthode des équations $ax + by = c$.

Définition — Équation diophantienne

Une équation diophantienne est une équation polynomiale à coefficients entiers dont on cherche les solutions parmi les entiers. Une équation diophantienne du premier degré à deux inconnues est une équation $ax + by = c$, où $a$, $b$ et $c$ sont des entiers relatifs avec $(a ; b) \neq (0 ; 0)$, et dont les inconnues $x$ et $y$ sont des entiers relatifs. Ces équations doivent leur nom à Diophante d'Alexandrie.

Proposition — Solutions entières de $ax + by = c$

Soient $a$, $b$ et $c$ des entiers relatifs, avec $a$ et $b$ non tous deux nuls, et soit $d = PGCD(a, b)$. L'équation $ax + by = c$ admet des solutions entières $(x ; y)$ si et seulement si $d$ divise $c$.

On suppose que $(x ; y)$ est une solution entière. Comme $d$ divise $a$ et $b$, il divise la combinaison linéaire $ax + by$, c'est-à-dire $c$.
Réciproquement, si $d$ divise $c$, on écrit $c = dm$ avec $m$ entier relatif. D'après l'identité de Bézout, il existe des entiers relatifs $u$ et $v$ tels que $au + bv = d$ ; en multipliant par $m$, $a(um) + b(vm) = dm = c$, donc $(um ; vm)$ est une solution.

Méthode — Résoudre l'équation diophantienne $ax + by = c$

Pour déterminer tous les couples d'entiers $(x ; y)$ tels que $ax + by = c$, où $a$ et $b$ sont des entiers relatifs non nuls :

Existence. Calculer $d = PGCD(a, b)$. Des solutions existent si et seulement si $d \mid c$ (une combinaison de $a$ et $b$ est toujours un multiple de $d$ ; réciproquement, en multipliant un couple de Bézout par $c/d$, on atteint $c$).
Solution particulière. Trouver un couple $(x_0 ; y_0)$, par lecture directe ou par la remontée de l'algorithme d'Euclide (Bézout), ajusté pour que $ax_0 + by_0 = c$.
Solution générale. Soustraire : $a(x - x_0) = -b(y - y_0)$, simplifier par $d$ — les entiers $\frac{a}{d}$ et $\frac{b}{d}$ sont premiers entre eux, d'après la propriété de division par le PGCD —, puis appliquer le théorème de Gauss pour obtenir $$x = x_0 + \tfrac{b}{d}\,k, \qquad y = y_0 - \tfrac{a}{d}\,k, \qquad k \in \mathbb{Z}.$$
Vérifier en reportant la forme générale dans l'équation.

Exemple

Déterminer tous les couples d'entiers relatifs $(x ; y)$ tels que $17x + 33y = 1$.

Existence. Les divisions euclidiennes de l'étape suivante se terminent par le reste $1$, donc $PGCD(17, 33) = 1$, et $1$ divise $1$ : des solutions existent.
Solution particulière. Euclide : $33 = 17 \times 1 + 16$, puis $17 = 16 \times 1 + 1$. En remontant : $$\begin{aligned} 1 &= 17 - 16 &&\\ &= 17 - (33 - 17) &&\text{(en substituant } 16\text{)}\\ &= 2 \times 17 - 1 \times 33, && \end{aligned}$$ donc $(x_0 ; y_0) = (2 ; -1)$ convient.
Solution générale. En soustrayant $17x + 33y = 1$ et $17 \times 2 + 33 \times (-1) = 1$ : $$17(x - 2) = -33(y + 1).$$ Donc $17 \mid 33(y+1)$ ; comme $PGCD(17, 33) = 1$, le théorème de Gauss donne $17 \mid y + 1$ : on pose $y + 1 = 17k$, soit $y = -1 + 17k$. En reportant : $17(x - 2) = -33 \times 17k$, d'où $x = 2 - 33k$.
Vérification. $$17(2 - 33k) + 33(-1 + 17k) = 34 - 561k - 33 + 561k = 1. \checkmark$$

Les solutions sont les couples $(x ; y) = (2 - 33k ;\ -1 + 17k)$ pour $k \in \mathbb{Z}$.

Compétences à pratiquer

Résoudre une équation $ax + by \equal c$

III.4 Le plus petit commun multiple

Proposition — Existence du PPCM

Soient $a$ et $b$ deux entiers relatifs non nuls. L'ensemble des multiples communs strictement positifs de $a$ et $b$ est une partie non vide de $\mathbb{N}^*$ ; elle admet donc un plus petit élément.

Définition — Plus petit commun multiple

Soient $a$ et $b$ deux entiers relatifs non nuls. Le plus petit entier naturel strictement positif qui est un multiple commun à $a$ et $b$ est appelé le plus petit commun multiple.
On le note $PPCM(a, b)$.

Proposition — Relation entre PGCD et PPCM

Soient $a$ et $b$ deux entiers naturels non nuls. On a :$$ PGCD(a, b) \times PPCM(a, b) = a \times b $$ De manière plus générale, pour tous entiers relatifs non nuls $a, b \in \mathbb{Z}$ :$$ PGCD(a, b) \times PPCM(a, b) = |ab| $$