L’algorithme d’Euclide

Ce que dit la formule

Pour tous entiers naturels $a$ et $b$ avec $b \neq 0$ :

• $\operatorname{pgcd}(a, b)$ : le plus grand commun diviseur de $a$ et $b$, c’est-à-dire le plus grand entier qui divise à la fois $a$ et $b$.
• $a \bmod b$ : le reste de la division euclidienne de $a$ par $b$. C’est l’unique entier $r$ tel que $a = qb + r$ avec $q$ entier et $0 \leq r < b$ ; $q$ est le quotient.
• La condition $b \neq 0$ est indispensable : on ne divise pas par zéro.

L’algorithme. On remplace le couple $(a, b)$ par $(b, r)$, puis on recommence. Le reste diminue strictement à chaque étape, donc il finit par valoir $0$. On s’arrête alors grâce à la règle $\operatorname{pgcd}(a, 0) = a$ (tout entier divise $0$) : le PGCD est le dernier reste non nul.

Si $a < b$, la première division donne $q = 0$ et $r = a$ : l’algorithme commence simplement par échanger les deux nombres.

Un exemple

Calculer $\operatorname{pgcd}(1071, 462)$, l’exemple classique de l’article de Wikipédia en anglais.

1. $1071 = 2 \times 462 + 147$ : le reste est 147, donc $\operatorname{pgcd}(1071, 462) = \operatorname{pgcd}(462, 147)$.
2. $462 = 3 \times 147 + 21$ : $\operatorname{pgcd}(462, 147) = \operatorname{pgcd}(147, 21)$.
3. $147 = 7 \times 21 + 0$ : le reste est nul, donc $\operatorname{pgcd}(147, 21) = \operatorname{pgcd}(21, 0) = 21$.

Le PGCD vaut 21. Vérification : $1071 = 21 \times 51$ et $462 = 21 \times 22$, et 51 et 22 n’ont aucun diviseur commun autre que 1. On en déduit la fraction irréductible $\frac{462}{1071} = \frac{22}{51}$.

En remontant les calculs (algorithme d’Euclide étendu), on écrit le PGCD comme combinaison des deux nombres : $21 = 462 - 3 \times 147 = 462 - 3 \times (1071 - 2 \times 462) = 7 \times 462 - 3 \times 1071$. En effet $7 \times 462 = 3\,234$ et $3 \times 1071 = 3\,213$. C’est l’identité de Bézout, utile pour résoudre les équations $ax + by = c$ en nombres entiers.

Pourquoi c’est vrai

Écrivons $a = qb + r$. Si un entier $d$ divise $a$ et $b$, il divise $a - qb = r$ ; il divise donc $b$ et $r$. Inversement, si $d$ divise $b$ et $r$, il divise $qb + r = a$ ; il divise donc $a$ et $b$. Les couples $(a, b)$ et $(b, r)$ ont ainsi exactement les mêmes diviseurs communs, donc le même plus grand diviseur commun.

L’algorithme s’arrête toujours, car les restes forment une suite d’entiers positifs strictement décroissante : $b > r_1 > r_2 > \cdots \geq 0$. Une telle suite ne peut pas descendre indéfiniment, elle atteint $0$ en au plus $b$ étapes. En réalité, il en faut beaucoup moins : Gabriel Lamé a démontré en 1844 que le nombre de divisions ne dépasse jamais cinq fois le nombre de chiffres du plus petit des deux nombres. Le cas le plus lent est celui de deux termes consécutifs de la suite de Fibonacci, où tous les quotients valent 1 sauf le dernier : $\operatorname{pgcd}(89, 55)$ demande 9 divisions pour aboutir à 1.

Les programmes de l’atelier vérifient l’égalité en comparant les listes complètes de diviseurs communs de $(a, b)$ et de $(b, a \bmod b)$ sur 3 000 couples, comparent le résultat de l’algorithme au plus grand diviseur commun cherché un par un sur 20 000 couples, contrôlent l’identité de Bézout sur 2 000 couples d’entiers de 60 chiffres au plus, et la borne de Lamé sur 100 000 couples d’entiers jusqu’à un milliard.

Un peu d’histoire

L’algorithme figure dans les Éléments d’Euclide, vers 300 avant notre ère : au livre VII, propositions 1 et 2, pour les nombres entiers, et au livre X, propositions 2 et 3, pour les longueurs. Euclide le présente par soustractions successives : on retire le plus petit nombre du plus grand tant que c’est possible, ce qui revient à une division euclidienne. Il n’en est probablement pas l’inventeur ; les historiens pensent qu’il était connu avant lui, peut-être d’Eudoxe de Cnide.

Il a été redécouvert ailleurs : en Inde, Aryabhata le décrit à la fin du Ve siècle pour résoudre des équations en nombres entiers, sous le nom de « pulvérisateur ». En Europe, Claude-Gaspard Bachet de Méziriac le présente sous forme numérique dans la seconde édition de ses Problèmes plaisants et délectables (1624). L’analyse de sa rapidité par Lamé, en 1844, est souvent citée comme l’un des premiers résultats de la théorie de la complexité des algorithmes. Il est encore utilisé chaque jour, par exemple en cryptographie, et il est souvent présenté comme l’un des plus anciens algorithmes toujours en usage.

Ce que montre l’affiche

Le dessin est la version géométrique de l’algorithme : un rectangle de $1071 \times 462$ est rempli de carrés aussi grands que possible. On y place d’abord 2 carrés de côté 462, puis, dans la bande restante, 3 carrés de côté 147, puis 7 carrés de côté 21 qui remplissent exactement le dernier morceau. Les nombres de carrés sont les quotients 2, 3 et 7, et le côté des plus petits carrés est le PGCD, 21 ; sous le rectangle, les trois divisions sont écrites, chacune précédée d’un carré de la couleur de son étape. Le pavage est calculé par le programme de l’atelier, et l’affiche existe en quatre styles : Papier, Nuit, Bauhaus et Tableau noir.

Pour aller plus loin

• Les nombres premiers : deux entiers sont premiers entre eux quand leur PGCD vaut 1.
• La suite de Fibonacci, qui donne le cas le plus lent de l’algorithme.
• Le nombre d’or, lié aux quotients tous égaux à 1 des nombres de Fibonacci.
• L’équation du second degré, autre méthode de résolution très ancienne.

Sources : Algorithme d’Euclide (Wikipédia) (nouvel onglet), Euclidean algorithm (Wikipedia) (nouvel onglet), Euclidean Algorithm (MathWorld) (nouvel onglet), Euclide, Éléments, livre VII, proposition 2 (D. E. Joyce, Clark University) (nouvel onglet), Lamé’s theorem (Wikipedia) (nouvel onglet).