Lorsqu’on doit trouver le plus grand commun diviseur de deux entiers on pense spontanément à utiliser le théorème fondamental de l’arithmétique, soit la factorisation de chaque entier en facteurs premiers. Pourtant, cette méthode est complètement inefficace numériquement puisqu’un ordinateur ne peut pas factoriser de très grands entiers en un temps raisonnable, ce qui est à la base de protocoles de cryptographie¹. Une méthode extrêmement efficace numériquement remonte à 300 ans av. J.-C. : elle est donnée par l’algorithme d’Euclide. Et cette méthode a de nombreuses applications pratiques modernes

Euclide
vers -300

Prenons deux entiers positifs a et b dont on veut trouver le plus grand commun diviseur, appelé PGCD de a et b. La méthode proposée par Euclide repose sur la division euclidienne.

La divison euclidienne

Étant donné deux entiers positifs c et d, il existe des entiers q et r tels que
\[c = dq + r, 0 \leq r < d.\] Si \(c = 112\) et \(d = 29\), cela nous donne \[112 = 29 \times 3 + 25.\] Regardons maintenant comment Euclide propose d’itérer ce processus pour trouver le PGCD de \(a = 112\) et \(b =29\). \[ \begin {array} {l r} 112 = 29 \times 3 + 25, &(e_1)\\ 29 = 25 \times 1 + 4, &(e_2)\\25 = 4 \times 6 + 1, &(e_3) \\ 4 = 1 \times 4 + 0. &(e_4)\end{array}\] Qu’a-t-on fait ? À la deuxième étape on a divisé b par le reste. À la troisième étape, on a divisé le premier reste par le deuxième reste. À la quatrième étape on a divisé le deuxième reste par le troisième reste. Le quatrième reste est nul. Donc on ne peut continuer. L’affirmation d’Euclide est que le dernier reste non nul, ici 1, est le PGCD de a et b.

Cela peut sembler plus compliqué que de décomposer a et b en facteurs premiers. Pour nous, oui ! Mais pas pour un ordinateur. Malgré de la recherche intensive pour améliorer les algorithmes de factorisation, la décomposition en facteurs premiers demeure très gourmande en temps et impossible à réaliser en un temps raisonnable si a et b sont grands. Alors que la division euclidienne et l’algorithme d’Euclide sont très efficaces numériquement ! C’est donc l’algorithme d’Euclide qui est préprogrammé dans les logiciels calculant le PGCD de deux nombres.

Le cas général de l’algorithme d’Euclide apparaît dans l’encadré.

Exploiter l’algorithme

Cet algorithme a beaucoup plus à nous offrir que de trouver le PGCD de a et b. Revenons à notre exemple et remontons les équations une à une à partir de l’avant dernière \((e_3)\), soit celle dont le reste est le PGCD de a et b. L’équation \((e_3)\) est équivalente à :
\[\begin{array}{r l r}1 = 25 – 4 \times 6.&&(1) \end{array}\]

L’équation \((e_2)\) nous donne

\[\begin{array}{r l r}4 = 29 – 25 \times 1. &&(2)\end{array}\]
Remplaçons (2) dans (1) :
\[\begin{array}{r l r}1 &= 25 – (29 – 25 \times 1) \times 6 \\ &= 25 \times 7 – 29 \times 6. &(3)\end{array}\]
L’équation \((e_1)\) nous donne
\[\begin{array}{r l r}25 = 112 – 29 \times 3. &&(4)\end{array}\]
Remplaçons (4) dans (3) :
\[\begin{array}{r l r}1& = (112 – 29 \times 3) \times 7 – 29 \times 6 \\&= 112 \times 7 – 29 \times 27. &(5)\end{array}\]
C’est cette dernière expression qui nous intéresse : on a écrit le PGCD de 112 et 29 sous la forme
\[1 = 112 \times 7 + 29 \times (–27).\]
soit sous la forme :
\[\begin{array}{r l r}PGCD(a, b) = ac + bd, &&(^*)\end{array}\]

Étienne Bezout
1730-1783

où c et d sont deux entiers relatifs. Cette dernière relation, tout à fait générale, est appelée théorème de Bezout. C’est elle qui est utilisée dans les applications pratiques, le plus souvent quand a et b sont relativement premiers, et donc quand PGCD(a, b) = 1. Une de ces applications se trouve dans l’article « Ne léser aucun héritier » de ce numéro.

Le fait que la factorisation d’un grand nombre entier est difficile est à la base du protocole de cryptographie RSA utilisé dans beaucoup de transactions où on doit fournir un NIP secret : ce NIP est crypté lors de la transmission et lisible seulement par le récepteur. Récupérer le NIP utilise une manipulation basée sur le théorème de Bezout.

PDF