Quatre façons de trouver le PGCD de deux nombres — et pourquoi celle d'Euclide gagne toujours.
Le PGCD de deux entiers est le plus grand nombre qui les divise tous les deux. On peut le chercher
en dressant la liste des diviseurs, ce qui est sûr mais interminable ; en retranchant sans cesse le plus petit du
plus grand, ce qui est la méthode des Grecs ; ou en remplaçant ces soustractions par des divisions, ce qui est
l'algorithme d'Euclide et reste, vingt-trois siècles plus tard, la meilleure méthode connue. Tout se calcule ici
sur les deux nombres de travail ci-dessous.
Planche 1 Ce que « diviser les deux » veut dire
Un diviseur commun d est une règle qui mesure exactement les deux longueurs : reportée bout à bout, elle
doit tomber juste sur a et sur b. Déplacez d, ou lancez le balayage : les règles qui tombent juste
s'inscrivent sur la bande du bas.
a ÷ d
—
b ÷ d
—
verdict
—
diviseurs communs
—
PGCD
—
reports entiers de dreste : d ne convient pasdiviseur commun sur la bande
Les listes de diviseurs
diviseurs de a :
diviseurs de b :
La méthode est irréprochable et parfaitement inutilisable dès que les nombres grandissent :
dresser la liste des diviseurs d'un nombre, c'est le factoriser, et personne ne sait le faire vite. Les trois
planches suivantes obtiennent le même résultat sans jamais chercher un seul diviseur.
Planche 2 La méthode des Grecs : retrancher
Si d mesure a et b, il mesure aussi leur différence. On peut donc remplacer le plus grand des deux nombres
par a − b sans changer le PGCD, et recommencer. Les deux barres finissent par s'égaliser : leur valeur commune
est le PGCD.
état courant
—
dernière opération
—
soustractions faites
0
soustractions nécessaires
—
résultat
—
—
Planche 3 Le rectangle carrelé
Voici la même idée, en géométrie. Dans un rectangle a × b, découpons le plus grand carré possible, puis
recommençons dans ce qui reste. Le côté du dernier carré est le PGCD — et le nombre de carrés de
chaque taille donne la fraction continue de a / b.
carrés posés
0
côté du carré courant
—
rectangle restant
—
côté du dernier carré
—
fraction continue de a / b
—
contrôle : fraction reconstruite
—
Le carrelage s'arrête toujours, car les côtés décroissent strictement dans les entiers. C'est
exactement l'anthyphérèse des Grecs. Sur un rectangle dont le rapport des côtés est irrationnel — un
rectangle d'or, par exemple — le découpage ne s'arrête jamais : c'est la définition même de
l'incommensurabilité, et le PGCD n'existe pas.
Planche 4 L'algorithme d'Euclide, et les coefficients de Bézout
Retrancher b un grand nombre de fois, c'est faire une division. On remplace donc toute une rafale de
soustractions par une seule opération : a = b·q + r, puis on recommence avec (b, r). Le dernier reste non nul
est le PGCD.
étape
dividende
diviseur
quotient
reste
nombre de divisions
—
contre les soustractions
—
contrôle rk+2 < rk / 2
—
PGCD
—
Remonter la chaîne : l'identité de Bézout
En repartant du bas vers le haut, chaque reste s'écrit a·u + b·v. Le dernier donne le PGCD sous cette forme.
reste r
u
v
a·u + b·v
écart
identité de Bézout
—
écart maximal sur toutes les lignes
—
a·u + b·v décrit…
—
L'algorithme rend donc davantage que le PGCD : il fournit deux entiers u et v tels que
a·u + b·v = PGCD(a, b). C'est de là que sortent l'inverse modulaire, la résolution des équations
diophantiennes ax + by = c, et le chiffrement RSA.
Planche 5 — signature Tous les couples à la fois
A. La carte des PGCD
Colorions le point (a, b) selon PGCD(a, b). Les couples premiers entre eux restent clairs, les autres
s'assombrissent — et le plan se remplit de droites passant par l'origine, une par valeur du PGCD.
couples examinés
—
premiers entre eux
—
proportion
—
PGCD maximal rencontré
—
B. La proportion tend vers 6 / π²
Deux entiers pris au hasard sont premiers entre eux avec la probabilité 6 / π² = 0,607927… Faisons croître
le carré et suivons la proportion mesurée.
proportion mesurée
—
6 / π²
—
écart
—
π retrouvé par √(6 / proportion)
—
La proportion mesurée sert de mesure de π : c'est un calcul d'arithmétique pure, sans le
moindre cercle. La raison en est que la probabilité qu'aucun premier p ne divise les deux nombres vaut
∏ (1 − 1/p²) = 1 / ζ(2), et que ζ(2) = π² / 6.
C. Le pire cas est celui de Fibonacci
Cherchons, par force brute, le couple qui fait le plus travailler l'algorithme. Le vainqueur est toujours
un couple de nombres de Fibonacci consécutifs : c'est le théorème de Lamé (1844), première analyse de
complexité de l'histoire.
pire couple trouvé
—
divisions nécessaires
—
sont-ils deux Fibonacci consécutifs ?
—
borne de Lamé : 5 × (chiffres de b)
—
quotients de la chaîne
—
Tous les quotients valent 1 : le pire cas de l'algorithme d'Euclide est celui où chaque
division ne retranche qu'une seule fois le diviseur — autrement dit, celui où les divisions ne sont pas plus
efficaces que les soustractions. Comme les nombres de Fibonacci croissent comme φⁿ, le nombre d'étapes ne
dépasse jamais logφ du plus petit nombre, soit environ 4,785 divisions par chiffre décimal.
Pour deux nombres de mille chiffres, c'est moins de cinq mille divisions : c'est pourquoi l'algorithme
d'Euclide, seul, tient encore debout au cœur de la cryptographie moderne.