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≥b, et r le reste de la division euclidienne de a par b.
Si r=0 alors a∧b=b sinon a∧b=r∧b.
Démonstration
On a a=bq+r.
Si r=0, alors a est un multiple de b et donc a∧b=b.
Si 1≤r<b, a∧b divise a et b, et par suite a∧b divise a−bq=r.
Par conséquent, il divise aussi r∧b.
De même r∧b divise r et b donc il divise a=bq+r.
Divisant a et b, il divise a∧b.
Puisque a∧b∣r∧b et r∧b∣a∧b alors a∧b=r∧b, avec r<b≤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 :
4505=4×1054+289 donc 4505∧1054=1054∧289.
Appliquons de nouveau le théorème en effectuant la division euclidienne de 1054 par 289. Or 1054=3×289+187.
On a r=187 qui n’est pas nul donc 1054∧289=289∧187.
En réitérant la même procédure, on a 289=1×187+85.
Donc 289∧187=187∧85, puis 187=2×85+17.
Donc 187∧85=85∧17 et enfin 85=5×17. Dans cette dernière division euclidienne, le reste est nul donc 85∧17=17.
Finalement 4505∧1084=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 :
Dividende | 4505 | 1054 | 289 | 187 | 85 | 17 |
|---|---|---|---|---|---|---|
Diviseur | 1054 | 289 | 187 | 85 | 17 | 0 |
Reste | 289 | 187 | 85 | 17 | 0 | |
Quotient | 4 | 3 | 1 | 2 | 5 |
Le dernier reste non nul est 17.
4505∧1084=17