Comment calculer le PGCD de deux nombres ?

L'algorithme d'Euclide pour calculer le PGCD

L'algorithme d'Euclide fonctionne par divisions successives jusqu'à obtenir un reste nul. Le dernier diviseur non nul est le PGCD.

Méthode étape par étape

Soit $a$ et $b$ deux entiers positifs avec $a\ge b$ :

1. Diviser $a$ par $b$ : $a=b{q}_1+r_1$ avec $0\le r_1<b$
2. Si $r_1=0$, alors $\text{PGCD}(a,b)=b$
3. Sinon, diviser $b$ par $r_1$ : $b=r_1{q}_2+r_2$ avec $0\le r_2<r_1$
4. Si $r_2=0$, alors $\text{PGCD}(a,b)=r_1$
5. Continuer jusqu'à obtenir un reste nul

Exemple avec PGCD(48, 18)

1. $48=18\times 2+12$ (reste $r_1=12$)
2. $18=12\times 1+6$ (reste $r_2=6$)
3. $12=6\times 2+0$ (reste $r_3=0$)

Le dernier reste non nul est $6$, donc $\text{PGCD}(48,18)=6$.

Vérification

$48=6\times 8$ et $18=6\times 3$, donc $6$ divise bien $48$ et $18$.