|
|
|
|
|
|
|
|
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) :
 |
 |
C. Grospellier |