Algorithme d'Euclide, Bézout et l'équation ax + by = c

Dans les leçons précédentes, vous trouviez le PGCD de deux entiers en les décomposant en facteurs premiers et en gardant les facteurs communs. Ça marche pour $252$ et $180$ ; la factorisation peut devenir coûteuse pour de grands entiers, même si certains grands nombres se factorisent facilement — c'est même sur cette difficulté que repose une partie de la cryptographie. L'algorithme d'Euclide, lui, ne factorise rien : il divise.

La division euclidienne. Pour $a\in\mathbb Z$ et $b\in\mathbb N^*$, il existe un unique couple $(q\,;\,r)$ d'entiers tel que

Le point clé, qui fait tout l'algorithme : les diviseurs communs de $a$ et $b$ sont exactement les diviseurs communs de $b$ et $r$. En effet, si $d$ divise $a$ et $b$, il divise $a - bq = r$ ; et si $d$ divise $b$ et $r$, il divise $bq + r = a$. Donc $\mathrm{pgcd}(a\,;\,b) = \mathrm{pgcd}(b\,;\,r)$.

Algorithme d’Euclide. On part de $a\geqslant0$ et $b>0$ (pour des entiers signés, on utilise leurs valeurs absolues et on échange si nécessaire). Si le second entier est nul, le PGCD vaut directement $|a|$. On remplace le couple $(a\,;\,b)$ par $(b\,;\,r)$, puis on recommence, jusqu'à obtenir un reste nul. Le PGCD est le dernier reste non nul.

Sur $252$ et $180$ :

Le dernier reste non nul est $36$ : $\mathrm{pgcd}(252\,;\,180) = 36$. Trois divisions, aucune factorisation, et le même résultat que les arbres de facteurs. L'algorithme se termine toujours, parce que les restes forment une suite d'entiers naturels strictement décroissante ($0 \le r < b$) — elle ne peut pas descendre indéfiniment.

Remonter l'algorithme. Chaque ligne exprime un reste à partir des deux nombres précédents ; en remontant, on exprime le PGCD à partir de $a$ et de $b$ :

Ainsi $252 \times (-2) + 180 \times 3 = 36$. On a trouvé un couple de Bézout : deux entiers $u$ et $v$ tels que $au + bv = \mathrm{pgcd}(a\,;\,b)$. Contrôle obligatoire : $-504 + 540 = 36$. $\checkmark$

Théorème de Bézout. Pour tous entiers $a$ et $b$ non tous nuls, de PGCD $d$, il existe des entiers $u$ et $v$ tels que $au + bv = d$. En particulier, $a$ et $b$ sont premiers entre eux si et seulement s'il existe $u$ et $v$ tels que $au + bv = 1$.

Attention au sens : $au + bv = 1$ caractérise les entiers premiers entre eux ; dans le cas général, le second membre est $d$, pas $1$. Écrire « $252u + 180v = 1$ » n'a pas de solution — le membre de gauche est toujours multiple de $36$.

La famille, avec ses domaines. Dans les formules de normalisation qui suivent, on suppose $a\in\mathbb Z$, $b>0$ et $d=\mathrm{pgcd}(a;b)>0$. Le théorème de Bézout précédent reste valable pour deux entiers non tous nuls ; si $b=0$, la normalisation $0\leqslant u<b/d$ ne s’applique pas. Le couple n’est pas unique. Si $(u_0\,;\,v_0)$ convient, alors pour tout entier $k$,

convient aussi, puisque $a \cdot k\frac{b}{d} - b \cdot k\frac{a}{d} = 0$. Et ce sont tous les couples (on le démontre au bloc suivant avec le théorème de Gauss). Pour $252$ et $180$ : $\dfrac{b}{d} = 5$, $\dfrac{a}{d} = 7$, donc les couples sont $(-2 + 5k\,;\,3 - 7k)$. Parmi eux, un seul a son premier coefficient dans $[0\,;\,5[$ : pour $k = 1$, le couple $(3\,;\,-4)$, et l'on vérifie $756 - 720 = 36$. $\checkmark$ C'est ce représentant normalisé que les exercices demandent, précisément parce qu'il est unique.

Le théorème de Gauss est la conséquence la plus utile de Bézout :

Si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

Démonstration. Par Bézout, il existe $u$, $v$ avec $au + bv = 1$. En multipliant par $c$ : $acu + bcv = c$. Or $a$ divise $acu$ (évident) et $a$ divise $bcv$ (par hypothèse, $a$ divise $bc$). Donc $a$ divise leur somme, $c$. Fin de la démonstration. Sans l'hypothèse « $a$ premier avec $b$ », c'est faux : $6$ divise $4 \times 3 = 12$, mais $6$ ne divise ni $4$ ni $3$.

L’équation diophantienne $ax+by=c$, avec $a\in\mathbb Z$, $b>0$, $c\in\mathbb Z$, à résoudre dans $\mathbb Z^2$. Soit $d=\mathrm{pgcd}(a;b)>0$.

Existence. Le membre de gauche est toujours multiple de $d$. Donc : il y a des solutions si et seulement si $d$ divise $c$. C'est la seule condition ; aucune quantité d'essais infructueux ne la remplace. Si $d$ divise $c$, on écrit $c = d\,c'$, on prend un couple de Bézout $au_0 + bv_0 = d$, et $(x_0\,;\,y_0) = (c'u_0\,;\,c'v_0)$ est une solution particulière.

Toutes les solutions. Soit $(x\,;\,y)$ une autre solution. En soustrayant, $a(x - x_0) + b(y - y_0) = 0$, soit, après division par $d$ :

Ainsi $b'$ divise $a'(x - x_0)$ et $b'$ est premier avec $a'$ : par Gauss, $b'$ divise $x - x_0$, d'où $x = x_0 + k\,b'$. En reportant, $y = y_0 - k\,a'$. Réciproquement, tout couple de cette forme convient.

$$\mathcal{S} = \left\{\, \left(x_0 + k\,\frac{b}{d}\ ;\ y_0 - k\,\frac{a}{d}\right),\ k \in \mathbb{Z} \,\right\}.$$

C'est exactement la famille des couples de Bézout du bloc précédent, avec $c = d$. La démonstration est courte et elle est étudiée dans ce parcours ; il faut pouvoir justifier la famille et sa réciproque.

Exemple complet. Résoudre $91x + 35y = 21$.

• Euclide : $91 = 2 \times 35 + 21$ ; $35 = 1 \times 21 + 14$ ; $21 = 1 \times 14 + 7$ ; $14 = 2 \times 7 + 0$. Donc $d = 7$.
• $7$ divise $21$ : il y a des solutions, et $c' = 3$.
• Remontée : $7 = 21 - 14 = 21 - (35 - 21) = 2 \times 21 - 35 = 2 \times (91 - 2 \times 35) - 35 = 2 \times 91 - 5 \times 35$. Contrôle : $182 - 175 = 7$. $\checkmark$
• Solution particulière : $(x_0\,;\,y_0) = (3 \times 2\,;\,3 \times (-5)) = (6\,;\,-15)$. Contrôle : $546 - 525 = 21$. $\checkmark$
• Toutes les solutions, avec $\dfrac{b}{d} = 5$ et $\dfrac{a}{d} = 13$ :

Pour $k = 1$ : $(11\,;\,-28)$, et $1001 - 980 = 21$. $\checkmark$

Une application : l'inverse modulo $n$. Pour un module entier $n\geqslant2$, dire que $a$ est premier avec $n$, c'est dire qu'il existe $u$, $v$ avec $au + nv = 1$, c'est-à-dire $au \equiv 1\ [n]$ : $u$ est un inverse de $a$ modulo $n$. Il est unique parmi les restes $0, 1, \dots, n - 1$. Par exemple, $7$ et $30$ sont premiers entre eux : $30 = 4 \times 7 + 2$, $7 = 3 \times 2 + 1$, donc $1 = 7 - 3 \times 2 = 7 - 3 \times (30 - 4 \times 7) = 13 \times 7 - 3 \times 30$. L'inverse de $7$ modulo $30$ est $13$ : en effet $7 \times 13 = 91 = 3 \times 30 + 1$. La structure des congruences est la fiche suivante ; ici, retenez que chercher un inverse, c'est faire une remontée d'Euclide.

Énoncé fictif. Une réserve doit fournir exactement78 unités, avec des lots de12 et de18 unités. On cherche les nombres de lots $x,y$ entiers positifs ou nuls, puis on impose au plus cinq lots en tout.

Condition arithmétique. $18=12+6$, puis $12=2\times6$ : le PGCD vaut6 et divise78. De $6=18-12$, on déduit $78=13\times18-13\times12$, donc une solution entière $(-13;13)$.

Famille entière. Toutes les solutions de $12x+18y=78$ sont

La condition $x\geqslant0$ donne $k\geqslant5$ ; $y\geqslant0$ donne $k\leqslant6$. Il reste $(2;3)$ et $(5;1)$ : les sommes sont bien24+54=78 et60+18=78.

Ajouter la contrainte sans changer l’équation. Les totaux de lots sont respectivement5 et6. Avec au plus cinq lots, seule la paire $(2;3)$ convient. L’existence de solutions entières donnée par le PGCD ne garantissait ni leur positivité ni la contrainte logistique : ces étapes doivent être traitées séparément.

Figure (fig.math.prime-factor-tree, figure programmatique de la leçon de troisième sur les nombres premiers, relue ici avec les yeux de la licence) : deux échelles de division, côte à côte.

• À gauche, $252$ est divisé successivement par $2$, $2$, $3$, $3$, $7$ : les nombres $252$, $126$, $63$, $21$, $7$, $1$ descendent le long d'une barre verticale, chaque diviseur dans une petite boîte à droite. Bilan : $252 = 2^2 \times 3^2 \times 7$.
• À droite, $180$ est divisé par $2$, $2$, $3$, $3$, $5$ : $180$, $90$, $45$, $15$, $5$, $1$. Bilan : $180 = 2^2 \times 3^2 \times 5$.
• Les facteurs communs $2$, $2$, $3$, $3$ portent un fond hachuré ; les facteurs propres $7$ et $5$ un cadre à trait épais — le codage double la couleur, et une légende l'écrit. Une ligne encadrée conclut : « facteurs communs : $2^2 \times 3^2 = 36$ ». En bas, la fraction $\dfrac{252}{180}$ est simplifiée en $\dfrac{36 \times 7}{36 \times 5} = \dfrac{7}{5}$.

Ce qu'il faut y lire pour cette leçon. La figure obtient $\mathrm{pgcd}(252\,;\,180) = 36$ par les factorisations : dix divisions par des nombres premiers qu'il a fallu deviner. L'algorithme d'Euclide obtient le même $36$ par trois divisions euclidiennes sans deviner quoi que ce soit :

Imaginez les mêmes échelles pour deux entiers de trente chiffres : les colonnes pourraient être difficiles à établir si les facteurs premiers sont inconnus, tandis que la suite des restes d'Euclide resterait courte — elle est au plus proportionnelle au nombre de chiffres. C'est pourquoi on apprend Euclide après avoir appris les arbres de facteurs.

Ce que la figure montre aussi, sans le dire. Les cofacteurs $7$ et $5$ — ce qui reste de chaque nombre une fois le PGCD retiré — sont précisément $\dfrac{a}{d}$ et $\dfrac{b}{d}$, premiers entre eux. Ce sont eux qui paramètrent la famille des couples de Bézout : $(-2 + 5k\,;\,3 - 7k)$. Le $5$ de la boîte à trait épais, à droite, est le pas du premier coefficient ; le $7$ de gauche, celui du second. La fraction irréductible $\dfrac{7}{5}$ du bas et le théorème de Gauss disent la même chose : une fois le PGCD ôté, plus rien de commun.