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

L'algorithme par divisions encore appelé algorithme d'Euclide repose sur la propriété suivante :

« a et b étant deux nombres entiers positifs tels que$a> b$, on a PGCD (a ; b) = PGCD(b ; reste de a : b) »

Nous allons donc appliquer cette propriété pas à pas et présenter les résultats dans un tableau.

On effectue successivement les divisions euclidiennes et on note les restes successifs .

De la propriété ci-dessus appliquée 6 fois successivement on déduit que :

PGCD (12818 ; 7830) = PGCD(696 ; 58) = 58

Remarque : $696 = 58 \times 12 + 0$

Le PGCD(1281 ; 7830) est le dernier reste non nul obtenu dans l'algorithme d'Euclide donc

PGCD(7830 ; 1281) = 58