Note liminaire : Tout ce qui suit est une fiction narrative. Les œuvres citées et les résultats mathématiques sont historiquement documentés. Seule la conversation est inventée.
Avec plaisir. Le problème est simple : étant donnés deux nombres entiers, trouver leur plus grande commune mesure — ce que vous appelez aujourd’hui le PGCD. Par exemple : quelle est la plus grande quantité qui divise à la fois 252 et 168 ?
On pourrait essayer tous les diviseurs un par un. Mais ce serait interminable pour de grands nombres. Ma méthode est bien plus rapide : je divise le plus grand par le plus petit, je garde le reste, et je recommence.
Voyons l’exemple. Je cherche la commune mesure de 252 et 168.
Le dernier reste non nul est 84. C’est la plus grande commune mesure de 252 et 168.
Deux divisions seulement ! Essayez de faire mieux.
Ce qui est remarquable, Euclide, c’est que votre méthode fonctionne pour n’importe quelle paire de nombres, aussi grands soient-ils. Quand j’ai traduit vos Éléments en arabe à la Maison de la Sagesse, c’est cette universalité qui m’a frappé. Ce n’est pas une recette pour un cas particulier — c’est une procédure générale qui termine toujours et donne toujours le bon résultat.
Note historique : L’algorithme d’Euclide figure dans les Éléments, livre VII, propositions 1 et 2 (vers 300 av. J.-C.). Donald Knuth le qualifie de « plus vieil algorithme non trivial encore en usage » (The Art of Computer Programming, vol. 2, §4.5.2). Thābit ibn Qurra (826–901) traduit les Éléments en arabe à Bagdad dans le cadre du mouvement de traduction parrainé par les califes abbassides.
Entrée : deux entiers \(a\) et \(b\) avec \(a \geq b > 0\).
Règle : tant que \(b \neq 0\), remplacer \((a, b)\) par \((b, \;a \mod b)\).
Sortie : quand \(b = 0\), le PGCD est la valeur de \(a\).
Exemple plus long — \(\text{pgcd}(1071, 462)\) :
| Étape | Division | Reste |
|---|---|---|
| 1 | \(1071 = 462 \times 2 + 147\) | 147 |
| 2 | \(462 = 147 \times 3 + 21\) | 21 |
| 3 | \(147 = 21 \times 7 + 0\) | 0 |
Donc \(\text{pgcd}(1071, 462) = 21\).
Exactement ! C’est pourquoi j’ai démontré ma méthode, pas simplement illustrée. L’argument repose sur une seule observation :
Si \(a = bq + r\), alors tout nombre qui divise à la fois \(a\) et \(b\) divise aussi \(r\), et inversement. Donc les diviseurs communs de \((a, b)\) sont exactement les mêmes que ceux de \((b, r)\). En particulier, le plus grand d’entre eux est le même.
Comme le reste \(r\) est strictement plus petit que \(b\), la suite des restes est strictement décroissante. Elle atteint zéro en un nombre fini d'étapes. L’algorithme termine toujours.
Ce qui me fascine, c’est cette double exigence : une méthode qui fonctionne (correction) et qui s’arrête (terminaison). Euclide ne dit pas « faites ceci et voyez ce qui se passe ». Il dit « voici pourquoi cela donne toujours la bonne réponse ». C’est la différence entre une recette de cuisine et un théorème.
Note historique : La distinction entre un procédé empirique et un algorithme démontré est au cœur de la démarche euclidienne. Les Éléments ne contiennent aucune méthode sans justification — chaque proposition est suivie de sa preuve.
Théorème : Si \(a = bq + r\), alors \(\text{pgcd}(a, b) = \text{pgcd}(b, r)\).
Preuve :
Les ensembles de diviseurs communs sont identiques, donc leurs maximums sont égaux. ∎
Terminaison : La suite des restes \(r_0 > r_1 > r_2 > \cdots \geq 0\) est une suite d’entiers naturels strictement décroissante. Elle atteint donc 0 en au plus \(b\) étapes (en pratique, beaucoup moins).
Je suis né à Harrān, en Haute-Mésopotamie, dans une communauté sabéenne — héritière des anciennes traditions astrologiques. Le grand mathématicien Muḥammad ibn Mūsā m’a remarqué et invité à Bagdad. Là, j’ai rejoint le cercle des traducteurs de la Maison de la Sagesse (Bayt al-Ḥikma).
Le calife al-Mutawakkil et ses successeurs finançaient la traduction systématique des œuvres grecques — Euclide, Archimède, Apollonius, Ptolémée. Ce n'était pas un acte de conservation passive : nous corrigions, nous complétions, nous étendions ces textes.
J’ai traduit et commenté les Éléments d’Euclide, mais aussi les Données, les Coniques d’Apollonius, et l'Almageste de Ptolémée. Pour l’algorithme du PGCD, j’ai ajouté des commentaires et des exemples numériques. Mes successeurs — al-Khwārizmī, al-Karajī — sont allés plus loin : ils ont développé la théorie des congruences et l’algèbre des polynômes en s’appuyant sur la même idée de division avec reste.
Douze siècles entre mon époque et la vôtre, Thābit. Et mon algorithme a traversé cette distance sans une ride. C’est peut-être la plus belle preuve de sa solidité.
Note historique : Thābit ibn Qurra (826–901), né à Harrān (Turquie actuelle), est l’un des plus grands traducteurs et mathématiciens de l'ère abbasside. Il traduit les Éléments, les Données d’Euclide, et de nombreuses œuvres d’Archimède. Il découvre également une règle pour générer des nombres amiables et généralise le théorème de Pythagore aux triangles quelconques.
Source : Roshdi Rashed, Thābit ibn Qurra: Science and Philosophy in Ninth-Century Baghdad, De Gruyter, 2009.
Oui, et c’est peut-être le plus beau. En « remontant » les étapes du calcul, on peut écrire le PGCD comme combinaison linéaire des deux nombres de départ. Autrement dit : il existe des entiers \(u\) et \(v\) tels que
C’est ce que le XVIIIe siècle appellera le « théorème de Bézout », mais l’idée est déjà dans mes Éléments.
Reprenons \(\text{pgcd}(1071, 462) = 21\). On a trouvé :
On remonte : en remplaçant 147 dans la deuxième ligne :
Vérification : \(1071 \times (-3) + 462 \times 7 = -3213 + 3234 = 21\) ✓
C’est cette remontée qui a fasciné les mathématiciens arabes. Elle ouvre la porte aux équations diophantiennes — les équations en nombres entiers. Chercher les entiers \(x, y\) tels que \(1071x + 462y = 21\), c’est exactement résoudre une équation diophantienne. Et votre algorithme étendu fournit une solution en un nombre fini d'étapes.
Al-Karajī, un siècle après moi, poussera plus loin en développant les congruences — l’arithmétique des restes — qui sont elles aussi filles de votre division euclidienne.
On cherche \(u, v\) tels que \(\text{pgcd}(a, b) = au + bv\).
Méthode : on effectue l’algorithme d’Euclide, puis on « remonte » chaque étape en exprimant le reste comme combinaison des deux nombres précédents.
| Étape | Division | Remontée |
|---|---|---|
| 1 | \(1071 = 462 \times 2 + 147\) | \(147 = 1071 - 462 \times 2\) |
| 2 | \(462 = 147 \times 3 + 21\) | \(21 = 462 - 147 \times 3\) |
Substitution :
Donc \(u = -3\), \(v = 7\), et \(1071 \times (-3) + 462 \times 7 = 21\). ✓
Conséquence (théorème de Bézout) : \(a\) et \(b\) sont premiers entre eux si et seulement s’il existe \(u, v \in \mathbb{Z}\) tels que \(au + bv = 1\).
Internet ? Je ne connais pas ce mot, mais je vous écoute.
Quand vous achetez en ligne ou envoyez un message sécurisé, votre ordinateur utilise un protocole appelé RSA (1977). Son principe : on choisit deux grands nombres premiers \(p\) et \(q\), on calcule \(n = pq\), et on chiffre avec un exposant \(e\). Pour déchiffrer, il faut trouver l'inverse modulaire de \(e\) modulo \((p-1)(q-1)\).
Et comment calcule-t-on cet inverse modulaire ? Par l'algorithme d’Euclide étendu. Exactement la remontée que vous venez de décrire.
Ainsi, l’algorithme du livre VII des Éléments protège vos secrets. La division avec reste, vieille de vingt-trois siècles, est au cœur de votre sécurité.
Je ne suis pas surpris. Un bon algorithme ne vieillit pas — il attend qu’on lui trouve de nouveaux usages.
Note historique : L’algorithme RSA, inventé par Rivest, Shamir et Adleman en 1977, repose sur la difficulté de factoriser le produit de deux grands nombres premiers. Le calcul de la clé privée nécessite l’inverse modulaire, obtenu par l’algorithme d’Euclide étendu. C’est l’une des applications les plus célèbres de l’arithmétique élémentaire.
| Date | Auteur | Contribution |
|---|---|---|
| vers –300 | Euclide (Alexandrie) | Algorithme du PGCD (Éléments VII), preuve de correction et de terminaison |
| IXe s. | Thābit ibn Qurra (Bagdad) | Traduction arabe des Éléments, commentaires, nombres amiables |
| Xe s. | Al-Karajī (Bagdad) | Congruences, extension de l’arithmétique euclidienne |
| XIIe s. | Al-Samawʾal (Bagdad) | Formalise la récurrence, démontre le binôme |
| 1202 | Fibonacci (Pise) | Transmet l’arithmétique arabe en Europe via le Liber Abaci |
| 1730 | Bézout (France) | Formalise l’identité \(au + bv = \text{pgcd}(a,b)\) |
| 1977 | Rivest, Shamir, Adleman | RSA : l’algorithme d’Euclide étendu au cœur de la cryptographie |
Idée centrale : L’algorithme d’Euclide est bien plus qu’une méthode de calcul du PGCD. C’est une idée — remplacer un problème par un problème plus petit, encore et encore, jusqu'à ce que la réponse soit évidente. Cette idée, née à Alexandrie, transmise à Bagdad, puis à l’Europe, protège aujourd’hui vos mots de passe.