6eme 5eme 4eme 3eme
Sommaire Liens Atelier Maths Forum

Programme JavaScript

Recherche de PGCD par l'algorithme d'Euclide


Soit a et b deux entiers naturels non nuls.

Ecrivons la division euclidienne de a par b : a = bq + r.

Si d est un diviseur commun à a et b, d divise b donc bq, et par suite d divise a - bq = r.

Par conséquent, d est un diviseur commun à b et r.

Si d' est un diviseur commun à b et r, d' divise b donc bq, et par suite bq + r = a.

Par conséquent, d' est un diviseur commun à a et b.

Ainsi, les diviseurs communs de a et b sont les diviseurs communs de b et r. C'est aussi vrai pour le plus grand d'entre eux, d'où :

pgcd (a,b) = pgcd (b,r)

On peut continuer ce raisonnement et on obtient l'algorithme ci-contre avec :

pgcd (a,b) = pgcd (b,r0) = pgcd (r0,r1) = pgcd (r1,r2) = ...

Les restes sont des entiers naturels de plus en plus petits. Par conséquent, cette suite de divisions euclidiennes va finir par s'arrêter avec un dernier reste égale à 0 (sinon on pourrait encore faire une division euclidienne).

si R est le dernier reste non nul, on a :

pgcd (a,b) = pgcd (b,r0) = pgcd (r0,r1) = ... = pgcd (R,0)

Or le plus grand diviseur commun à R et 0 est R (0 est divisible par tous les entiers non nuls).

Le pgcd est donc le dernier reste non nul.

 

Calcul du pgcd de deux nombres (programme écrit en JavaScript) :

a =

b =


Document made with Nvu C. Grospellier