S'abonner
decoration
decorationdecoration

Méthode : PGCD avec l'algorithme d'Euclide et les soustractions successives

Propriété

Calculs de PGCD avec l'algorithme d'Euclide (divisions successives)

C’est un algorithme itératif qui consiste à faire des divisions euclidiennes successives. Il repose sur la propriété suivante :

Soient aa et bb deux entiers naturels non nuls avec a>ba>b et rrest le reste de la division euclidienne de aa par bb. On a :

PGCD(a;b)=PGCD(b;r).PGCD(a;b)=PGCD(b;r).

Algorithme

Dans la 1ère division, on divise aa (le plus grand) par bb (le plus petit) et dans la 2ème division, on prend bb le diviseur de la 1ère, comme dividende et le reste de la 1ère division comme diviseur et ainsi de suite jusqu’à obtenir un reste nul. Le dernier reste non nul est PGCD(a;b)PGCD(a ; b).

Revenir au chapitre
Commentaires