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

Au collège, tu trouvais le PGCD de deux entiers en les décomposant en facteurs premiers et en gardant les facteurs communs. Ça marche pour $252$ et $180$ ; ça ne marche plus quand les nombres ont vingt chiffres, parce que factoriser est difficile — 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 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$.

Le couple n'est pas unique — et c'est une famille, pas un désordre. 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$, à résoudre dans $\mathbb{Z}^2$. Soit $d = \mathrm{pgcd}(a\,;\,b)$.

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 au programme : on te demandera de la refaire.

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$. 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, retiens que chercher un inverse, c'est faire une remontée d'Euclide.

Énoncé. On considère $a = 95$ et $b = 42$.

1. Calculer $\mathrm{pgcd}(95\,;\,42)$ par l'algorithme d'Euclide.
2. En déduire un couple $(u\,;\,v)$ d'entiers tel que $95u + 42v = 1$.
3. Décrire tous les couples $(u\,;\,v)$ vérifiant cette identité, et déterminer l'unique couple dont le premier coefficient vérifie $0 \le u < 42$.
4. En déduire l'inverse de $95$ modulo $42$.

---

1. Euclide. On divise, on décale, on recommence :

Le dernier reste non nul est $1$ : $\mathrm{pgcd}(95\,;\,42) = 1$. Les deux entiers sont premiers entre eux. (Le PGCD n'est pas $0$ : le reste nul signale la fin, il n'est pas le résultat.)

2. Remontée. On part de la dernière ligne à reste non nul et l'on remplace chaque reste par son expression, en gardant les parenthèses :

Donc $95 \times (-19) + 42 \times 43 = 1$. Contrôle : $43 \times 42 = 1806$ et $19 \times 95 = 1805$ ; $1806 - 1805 = 1$. $\checkmark$ Un couple de Bézout est $(u\,;\,v) = (-19\,;\,43)$.

3. Tous les couples, puis le bon. Ici $d = 1$, donc $\dfrac{b}{d} = 42$ et $\dfrac{a}{d} = 95$ :

On veut $0 \le -19 + 42k < 42$, soit $19 \le 42k < 61$, soit $k = 1$ (le seul entier de $\left[\tfrac{19}{42}\,;\,\tfrac{61}{42}\right[$). Le couple normalisé est

Contrôle direct : $95 \times 23 = 2185$, $42 \times 52 = 2184$, et $2185 - 2184 = 1$. $\checkmark$

4. L'inverse. L'identité $95 \times 23 + 42 \times (-52) = 1$ se lit modulo $42$ : $95 \times 23 \equiv 1\ [42]$. L'inverse de $95$ modulo $42$ est $23$ — et c'est le même nombre que le représentant normalisé de la question 3, ce qui n'est pas un hasard : « premier coefficient dans $[0\,;\,42[$ » et « inverse parmi les restes modulo $42$ » sont deux noms de la même unicité. Remarque que $95 \equiv 11\ [42]$ : l'inverse de $11$ modulo $42$ est donc aussi $23$, et $11 \times 23 = 253 = 6 \times 42 + 1$. $\checkmark$

Lecture. Quatre divisions ont suffi pour deux nombres à deux chiffres. Le couple $(-19\,;\,43)$ sorti de la remontée n'est pas « le » couple de Bézout : c'est un représentant d'une famille infinie, et l'énoncé qui veut une réponse unique doit imposer un encadrement.

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 :

Imagine les mêmes échelles pour deux entiers de trente chiffres : les colonnes de gauche et de droite seraient impossibles à écrire (il faudrait connaître les facteurs premiers), 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.

La remontée, mécaniquement. On écrit la dernière division à reste non nul sous la forme $r_{k} = r_{k - 2} - q_k\,r_{k - 1}$, puis on remplace $r_{k - 1}$ par son expression, en gardant $r_{k - 2}$ et $r_{k - 3}$ entre parenthèses, et l'on remonte jusqu'à $a$ et $b$. Tant qu'on n'a pas recalculé $au + bv$ avec les valeurs trouvées, le résultat n'est pas acquis.

Ce qui n'est pas dans cette leçon. L'anneau $\mathbb{Z}/n\mathbb{Z}$ et ses propriétés, le petit théorème de Fermat, le théorème des restes chinois, l'arithmétique des polynômes, la complexité exacte de l'algorithme (théorème de Lamé), et toute application au chiffrement.

1. Répondre $0$ comme PGCD. L'algorithme s'arrête quand le reste est nul, mais le PGCD est le dernier reste non nul, la ligne d'avant. Pour $252$ et $180$, c'est $36$, pas le $0$ de $72 = 2 \times 36 + 0$.
2. Écrire $au + bv = 1$ quand le PGCD vaut $d > 1$. La forme « $= 1$ » caractérise les entiers premiers entre eux. Pour $252$ et $180$, aucun couple ne donne $1$ : le membre de gauche est un multiple de $36$. La bonne identité est $252u + 180v = 36$.
3. Perdre un signe dans la remontée. L'erreur type : remplacer $14$ par $35 - 21$ sans parenthèses, et écrire $21 - 35 - 21$ au lieu de $21 - (35 - 21) = 2 \times 21 - 35$. Le remède est mécanique — parenthèses, puis développement — et le contrôle final $au + bv = d$ est obligatoire.
4. Croire le couple de Bézout unique. Il y en a une infinité : $\left(u_0 + k\,\tfrac{b}{d}\ ;\ v_0 - k\,\tfrac{a}{d}\right)$. Deux étudiants qui trouvent $(-19\,;\,43)$ et $(23\,;\,-52)$ ont tous les deux raison. Quand un énoncé veut UNE réponse, il impose un encadrement — et c'est celui-là qu'il faut lire.
5. Croiser les pas. Le premier coefficient (celui de $a$) avance de $\dfrac{b}{d}$, le second (celui de $b$) recule de $\dfrac{a}{d}$. Inverser les deux donne des couples qui ne vérifient plus l'identité : $a \cdot \tfrac{b}{d} - b \cdot \tfrac{a}{d} = 0$, mais $a \cdot \tfrac{a}{d} - b \cdot \tfrac{b}{d} \ne 0$ en général.
6. Déclarer $ax + by = c$ sans solution après quelques essais. La seule question qui décide : $d$ divise-t-il $c$ ? $91x + 35y = 20$ n'a aucune solution ($7$ ne divise pas $20$) ; $91x + 35y = 21$ en a une infinité. Les essais ne prouvent rien dans un sens ni dans l'autre.
7. Confondre Gauss et Bézout, ou oublier l'hypothèse de Gauss. « $a$ divise $bc$ » n'implique « $a$ divise $c$ » que si $a$ est premier avec $b$. Sans cela, $6$ divise $4 \times 3$ mais $6$ ne divise pas $3$. Dans la résolution de $ax + by = c$, c'est la division par $d$ qui fabrique l'hypothèse ($\tfrac{a}{d}$ et $\tfrac{b}{d}$ premiers entre eux) : ne pas la sauter.
8. Chercher un inverse modulo $n$ sans vérifier $\mathrm{pgcd}(a\,;\,n) = 1$. $6$ n'a pas d'inverse modulo $30$ : $6u \equiv 1\ [30]$ demanderait $6u + 30v = 1$, impossible puisque $6$ divise le membre de gauche. La remontée d'Euclide ne « trouvera » rien — elle s'arrêtera sur un PGCD égal à $6$, ce qui est la réponse : pas d'inverse.

Le modèle d'entraînement. L'exercice associé à cette leçon ne demande jamais « le PGCD » — il se lit en trois divisions et n'est pas de niveau licence. Il demande, selon la variante, l'unique coefficient $u$ de Bézout tel que $0 \le u < \dfrac{b}{d}$, l'inverse d'un entier modulo $n$ après avoir justifié qu'il existe, ou la plus petite solution positive d'une congruence $ax \equiv c\ [n]$ dont le PGCD n'est pas toujours $1$. Toutes les réponses sont des entiers, sans tolérance. Un modèle voisin, à choix multiples, propose quatre couples bâtis sur les mêmes nombres, à l'ordre et aux signes près, et demande lequel vérifie $au + bv = d$.

Énoncé type. Soit $a = 95$ et $b = 42$. On note $d$ leur PGCD. Déterminer l'unique entier $u$ tel que $0 \le u < \dfrac{b}{d}$ et qu'il existe un entier $v$ vérifiant $95u + 42v = d$. Donner $u$.

Corrigé complet.

1. Euclide, pour $d$. $95 = 2 \times 42 + 11$ ; $42 = 3 \times 11 + 9$ ; $11 = 1 \times 9 + 2$ ; $9 = 4 \times 2 + 1$ ; $2 = 2 \times 1 + 0$. Dernier reste non nul : $d = 1$. L'encadrement demandé est donc $0 \le u < 42$.

2. Remontée, pour un premier couple.

Contrôle : $1806 - 1805 = 1$. $\checkmark$ Un couple est $(u_0\,;\,v_0) = (-19\,;\,43)$.

3. Toute la famille, puis le représentant. Les couples sont $(-19 + 42k\,;\,43 - 95k)$, $k \in \mathbb{Z}$. La condition $0 \le -19 + 42k < 42$ équivaut à $19 \le 42k < 61$, soit $k = 1$. D'où $u = 23$ et $v = -52$.

4. Contrôle final, sur les valeurs. $95 \times 23 = 2185$ et $42 \times (-52) = -2184$ ; somme $1 = d$. $\checkmark$ Et $0 \le 23 < 42$. $\checkmark$

Réponse : $u = 23$ (avec $v = -52$).

Auto-contrôle. Ai-je pris le dernier reste non nul comme PGCD ? Ai-je gardé les parenthèses à chaque substitution de la remontée ? Ai-je recalculé $au + bv$ avec mes valeurs finales, et non seulement avec le couple intermédiaire ? Mon $u$ est-il dans $[0\,;\,\tfrac{b}{d}[$, et ai-je translaté de $\tfrac{b}{d}$ (ici $42$) et non de $\tfrac{a}{d}$ ?