Introduction : Au-delà du PGCD
L’algorithme d’Euclide est l’une des plus anciennes et des plus célèbres procédures mathématiques, utilisée pour trouver le plus grand commun diviseur (PGCD) de deux entiers. Cependant, une version « étendue » de cet algorithme permet de faire bien plus : elle fournit une méthode constructive pour exprimer le PGCD comme une combinaison linéaire des deux nombres de départ.
Ce résultat, connu sous le nom de théorème de Bézout, n’est pas seulement une curiosité théorique. L’algorithme d’Euclide étendu est un outil essentiel en arithmétique modulaire, qui permet de calculer efficacement des inverses modulaires. Cette opération est elle-même un rouage indispensable de nombreux algorithmes cryptographiques, notamment le célèbre RSA. L’algorithme étendu transforme ainsi une simple recherche de PGCD en une puissante machine à résoudre des équations diophantiennes et à forger les outils de la sécurité informatique.
Étant donnés deux entiers $a$ et $b$, l’algorithme d’Euclide étendu a pour but de trouver non seulement leur PGCD, noté $d = \text{pgcd}(a, b)$, mais aussi deux entiers $u$ et $v$ (appelés coefficients de Bézout) tels que : $$ au + bv = d $$
Rappel : L’Algorithme d’Euclide Simple
L’algorithme d’Euclide repose sur le principe que $\text{pgcd}(a, b) = \text{pgcd}(b, r)$, où $r$ est le reste de la division de $a$ par $b$. On effectue une série de divisions euclidiennes jusqu’à obtenir un reste nul. Le dernier reste non nul est le PGCD.
Pour $a=252$ et $b=198$ :
- $252 = 1 \cdot 198 + 54$
- $198 = 3 \cdot 54 + 36$
- $54 = 1 \cdot 36 + 18$
- $36 = 2 \cdot 18 + 0$
Le dernier reste non nul est 18, donc $\text{pgcd}(252, 198) = 18$.
L’Algorithme Étendu : La Méthode de la Remontée
Pour trouver les coefficients $u$ et $v$, on part de l’avant-dernière équation de l’algorithme simple et on « remonte » en substituant les restes successifs.
- On exprime le PGCD à partir de la 3ème ligne : $18 = 54 – 1 \cdot 36$.
- On exprime le reste précédent (36) à partir de la 2ème ligne : $36 = 198 – 3 \cdot 54$. On substitue : $$ 18 = 54 – 1 \cdot (198 – 3 \cdot 54) = 54 – 198 + 3 \cdot 54 = 4 \cdot 54 – 1 \cdot 198 $$
- On exprime le reste précédent (54) à partir de la 1ère ligne : $54 = 252 – 1 \cdot 198$. On substitue : $$ 18 = 4 \cdot (252 – 1 \cdot 198) – 1 \cdot 198 = 4 \cdot 252 – 4 \cdot 198 – 1 \cdot 198 = 4 \cdot 252 – 5 \cdot 198 $$
On a trouvé la relation : $4 \cdot 252 + (-5) \cdot 198 = 18$. Les coefficients de Bézout sont donc $u=4$ et $v=-5$.
Une Méthode Tabulaire Plus Efficace
La méthode de la remontée peut être fastidieuse. Une approche plus systématique consiste à maintenir à chaque étape les coefficients de Bézout pour chaque reste. On cherche des suites $(u_k)$ et $(v_k)$ telles que $r_k = u_k a + v_k b$. Elles obéissent aux relations de récurrence :
$u_{k+1} = u_{k-1} – q_k u_k$ et $v_{k+1} = v_{k-1} – q_k v_k$, avec les initialisations suivantes :
$r_0=a$, $u_0=1$, $v_0=0$
$r_1=b$, $u_1=0$, $v_1=1$
Appliquons cela à notre exemple avec $a=252$ et $b=198$.
| k | $r_k$ (Reste) | $q_k$ (Quotient) | $u_k$ | $v_k$ |
|---|---|---|---|---|
| 0 | 252 | – | 1 | 0 |
| 1 | 198 | – | 0 | 1 |
| 2 | 54 ($=r_0 – 1 \cdot r_1$) | 1 | $1 – 1 \cdot 0 = 1$ | $0 – 1 \cdot 1 = -1$ |
| 3 | 36 ($=r_1 – 3 \cdot r_2$) | 3 | $0 – 3 \cdot 1 = -3$ | $1 – 3 \cdot (-1) = 4$ |
| 4 | 18 ($=r_2 – 1 \cdot r_3$) | 1 | $1 – 1 \cdot (-3) = 4$ | $-1 – 1 \cdot 4 = -5$ |
| 5 | 0 ($=r_3 – 2 \cdot r_4$) | 2 |
On retrouve bien que le PGCD est 18 (le dernier reste non nul, à la ligne $k=4$), et que les coefficients correspondants sont $u_4=4$ et $v_4=-5$.
Application Majeure : Calcul de l’Inverse Modulaire
L’application la plus importante de l’algorithme d’Euclide étendu est le calcul de l’inverse d’un nombre dans une structure modulaire.
Soit un entier $a$ et un module $n$. L’inverse de $a$ modulo $n$, noté $a^{-1}$, est un entier $x$ tel que : $$ ax \equiv 1 \pmod n $$ Cet inverse existe si et seulement si $a$ et $n$ sont premiers entre eux, c’est-à-dire $\text{pgcd}(a, n) = 1$.
Si $\text{pgcd}(a, n) = 1$, l’algorithme d’Euclide étendu nous donne des entiers $u$ et $v$ tels que : $$ au + nv = 1 $$ En regardant cette équation modulo $n$, le terme $nv$ devient 0, et il reste : $$ au \equiv 1 \pmod n $$ Le coefficient $u$ est donc l’inverse de $a$ modulo $n$.
Exemple : Trouver l’inverse de 7 modulo 26
On cherche $x$ tel que $7x \equiv 1 \pmod{26}$. On applique l’algorithme d’Euclide étendu à $a=26$ et $b=7$.
| k | $r_k$ | $q_k$ | $u_k$ | $v_k$ |
|---|---|---|---|---|
| 0 | 26 | – | 1 | 0 |
| 1 | 7 | – | 0 | 1 |
| 2 | 5 ($=26 – 3 \cdot 7$) | 3 | 1 | -3 |
| 3 | 2 ($=7 – 1 \cdot 5$) | 1 | -1 | 4 |
| 4 | 1 ($=5 – 2 \cdot 2$) | 2 | 3 | -11 |
| 5 | 0 | 2 |
Le PGCD est 1, donc l’inverse existe. La dernière ligne non nulle nous donne la relation :
$$ (3) \cdot 26 + (-11) \cdot 7 = 1 $$
En regardant modulo 26, on obtient $(-11) \cdot 7 \equiv 1 \pmod{26}$.
L’inverse est donc $-11 \pmod{26}$. Pour obtenir un représentant positif, on ajoute 26 : $-11 + 26 = 15$.
L’inverse de 7 modulo 26 est 15.
Vérification : $7 \times 15 = 105$. Et $105 = 4 \times 26 + 1$, donc $105 \equiv 1 \pmod{26}$.