Demandez à un élève de terminale le PGCD de 4 991 et de 1 219. Il cherchera les décompositions en facteurs premiers, parce que c’est la méthode qu’on lui a montrée, et il y passera un long moment : aucun des deux nombres ne se laisse factoriser de tête. Il existe pourtant un procédé qui donne la réponse en cinq divisions, sans chercher un seul facteur premier. Il a plus de vingt-trois siècles. Dans cet article, nous exposons l’algorithme d’Euclide, nous démontrons le lemme qui le fait fonctionner, et nous établissons qu’il se termine toujours.

Cet article ouvre une série consacrée au PGCD, à l’identité de Bézout et au théorème de Gauss. Il prolonge nos précédentes contributions sur la numération et la division euclidienne et sur la résolution des équations diophantiennes à trois inconnues.

1. Un exemple qui résiste

Le PGCD de deux entiers est le plus grand de leurs diviseurs communs. La définition suggère une méthode : décomposer les deux nombres, puis retenir les facteurs communs. Sur 4 991 et 1 219, cette méthode demande de découvrir que

d’où . Le résultat est juste, mais le chemin est mauvais. Rien, dans l’écriture de 4 991, ne signale le facteur 7 ; et rien, ensuite, ne signale le facteur 23 de 713. Il faut essayer les nombres premiers un par un. Sur des entiers à quinze chiffres, la méthode devient impraticable — et c’est précisément sur cette difficulté que repose la cryptographie contemporaine.

2. L’algorithme

Divisons le plus grand par le plus petit, puis recommençons avec le diviseur et le reste :

Le dernier reste non nul est 23. C’est le PGCD. Cinq divisions, aucune factorisation.

3. Le lemme qui justifie tout

Proposition. Soient un entier relatif et un entier naturel non nul. Si , alors les couples et ont exactement les mêmes diviseurs communs. En particulier, .

Démonstration. Soit un diviseur commun de et de . De l’égalité et de la stabilité de la divisibilité par combinaison linéaire, nous tirons ; donc divise et .

Réciproquement, soit un diviseur commun de et de . De l’égalité , nous tirons ; donc divise et .

Les deux couples ont donc le même ensemble de diviseurs communs. Cet ensemble étant non vide et majoré, il admet un plus grand élément, et ce plus grand élément est le même pour les deux couples.

Remarquons ce que cette démonstration ne suppose pas : ni la primalité, ni l’existence d’une décomposition en facteurs premiers. Seule intervient la stabilité de la divisibilité par combinaison linéaire. C’est ce qui rend l’algorithme aussi robuste : il vaut dans tout anneau euclidien, et nous le retrouverons pour les polynômes.

4. Pourquoi l’algorithme se termine

À chaque étape, le nouveau reste est strictement inférieur au précédent, et tous les restes sont positifs ou nuls. La suite des restes est donc une suite strictement décroissante d’entiers naturels : elle est nécessairement finie. L’algorithme atteint un reste nul en un nombre fini d’étapes, et le dernier reste non nul est le PGCD cherché.

Ce raisonnement — une suite strictement décroissante d’entiers naturels est finie — est une forme du principe de bon ordre. Nous y reviendrons lorsque nous construirons .

5. Combien d’étapes ? La borne de Lamé

L’algorithme se termine : nous venons de le prouver. Mais en combien d’étapes ? La réponse date de 1844 et revient à Gabriel Lamé. Elle est souvent tenue pour le premier résultat de complexité algorithmique de l’histoire des mathématiques.

Théorème de Lamé (1844). Soient et deux entiers naturels non nuls tels que . Si s’écrit avec chiffres en base dix, alors l’algorithme d’Euclide appliqué au couple demande au plus divisions.

C’est cette majoration que nous appellerons la borne de Lamé. Sur notre exemple, 1 219 compte quatre chiffres : la borne annonce au plus vingt divisions, et il en a suffi de cinq. Elle est donc large — mais elle a le mérite d’être universelle, aucun couple d’entiers, si défavorable soit-il, ne pouvant la mettre en défaut.

Reste à savoir si cette borne est serrée. Le pire cas est fourni par deux termes consécutifs de la suite de Fibonacci : c’est alors, et seulement alors, que tous les quotients valent 1 et qu’aucune étape ne fait gagner de terrain. Le dernier exercice invite à le constater.

6. Note historique

L’algorithme figure au livre VII des Éléments d’Euclide, aux propositions 1 et 2, vers 300 avant notre ère. Euclide ne parle ni de division ni de reste : il raisonne sur des grandeurs et procède par soustractions répétées, un procédé que les Grecs nommaient anthyphérèse. Au livre X, la même méthode, appliquée à des grandeurs géométriques, sert à caractériser la commensurabilité : si le procédé ne s’arrête pas, les deux grandeurs sont incommensurables.

C’est probablement le plus ancien algorithme non trivial qui nous soit parvenu, et il reste, vingt-trois siècles plus tard, celui qu’utilisent les logiciels de calcul formel.

7. Exercices

1. Déterminer par l’algorithme d’Euclide, puis vérifier le résultat par décomposition en facteurs premiers.
2. Montrer que deux entiers naturels consécutifs sont toujours premiers entre eux.
3. Soit un entier naturel. Déterminer, selon les valeurs de , le PGCD de et de .
4. Combien de divisions l’algorithme demande-t-il pour ? Comparer à la borne de Lamé et commenter.

---

Cet article reprend et développe une partie du chapitre 3 de Mathématiques en terminales scientifiques, Tome 2 — Arithmétique : cours et exercices corrigés, où l’algorithme est accompagné de 134 exercices corrigés.