L'algorithme d'Euclide pour déterminer le pgcd de deux entiers

La recherche du PGCD par la décomposition en facteurs premiers est souvent fastidieuse.
La division euclidienne permet une recherche algorithmique du PGCD, grâce au théorème suivant :

I. Théorème

Soient deux entiers non nuls $a$ et $b$, avec $a \geq b$, et $r$ le reste de la division euclidienne de $a$ par $b$.
Si $r = 0$ alors $a \wedge b = b$ sinon $a \wedge b = r \wedge b$.

Démonstration

On a $a = bq + r$.

Si $r = 0$, alors $a$ est un multiple de $b$ et donc $a \wedge b = b$.

Si $1 \leq r \lt b$, $a \wedge b$ divise $a$ et $b$, et par suite $a \wedge b$ divise $a - bq = r$.

Par conséquent, il divise aussi $r \wedge b$.

De même $r \wedge b$ divise $r$ et $b$ donc il divise $a = bq + r$.

Divisant $a$ et $b$, il divise $a \wedge b$.

Puisque $a \wedge b \mid r \wedge b$ et $r \wedge b \mid a \wedge b$ alors $a \wedge b = r \wedge b$, avec $r \lt b \leq a$.

Ce théorème permet d’obtenir un algorithme donnant le PGCD de deux nombres en un nombre fini d’opérations.

II. Un exemple de l'algorithme d'Euclide

Énoncé :

Déterminer le PGCD de 4505 et 1054.

Solution :

$4 505 = 4 \times 1 054 + 289$ donc $4 505 \wedge 1 054 = 1 054 \wedge 289$.

Appliquons de nouveau le théorème en effectuant la division euclidienne de $1 054$ par $289$. Or $1 054 = 3 \times 289 + 187$.

On a $r = 187$ qui n’est pas nul donc $1 054 \wedge 289 = 289 \wedge 187$.

En réitérant la même procédure, on a $289 = 1 \times 187 + 85$.

Donc $289 \wedge 187 = 187 \wedge 85$, puis $187 = 2 \times 85 + 17$.

Donc $187 \wedge 85 = 85 \wedge 17$ et enfin $85 = 5 \times 17$. Dans cette dernière division euclidienne, le reste est nul donc $85 \wedge 17 = 17$.

Finalement $4 505 \wedge 1 084 = 17$.

La procédure que nous venons d'appliquer s’appelle l’algorithme d’Euclide. Comme à chaque itération, l’un des deux nombres $a$ et $b$ diminue strictement, cet algorithme conduit au calcul du PGCD en un nombre fini d’opérations.

On peut présenter ces divisions dans un tableau où le diviseur et le reste d’une colonne deviennent respectivement le dividende et le diviseur de la colonne suivante :

Le dernier reste non nul est $17$.

$4 505 \wedge 1 084 = 17$