Algorithme d'Euclide et calcul du PGCD

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Si a = bq + r, alors PGCD(a, b) = PGCD(b, r). • Plus généralement, PGCD(a, b) = PGCD(b, a - kb) pour tout entier k. • Le PGCD est le dernier reste non nul de l'algorithme d'Euclide. • Les diviseurs communs à a et b sont exactement les diviseurs de leur PGCD.

Le cours

1. Lemme d'Euclide Si a = bq + r (avec a, b, q, r entiers), les diviseurs communs à a et b sont exactement les diviseurs communs à b et r : un diviseur de a et b divise r = a - bq, et un diviseur de b et r divise a = bq + r. Donc : PGCD(a, b) = PGCD(b, r) Plus généralement, PGCD(a, b) = PGCD(b, a - kb) pour tout entier relatif k. 2. Algorithme d'Euclide 1. Effectuer la division euclidienne de a par b : a = bq_1 + r_1. 2. Remplacer le couple (a, b) par (b, r_1) et recommencer. 3. Les restes diminuent strictement, donc on finit par obtenir un reste nul : le PGCD est le dernier reste non nul. Exemple : 252 = 105 2 + 42, 105 = 42 2 + 21, 42 = 21 2 + 0, donc PGCD(252, 105) = 21. 3. Conséquences Les diviseurs communs à a et b sont exactement les diviseurs de PGCD(a, b). Deux entiers a et b sont dits premiers entre eux si et seulement si PGCD(a, b) = 1. Pour des entiers relatifs, PGCD(a, b) = PGCD(|a|, |b|). 4. Attention Le PGCD est le dernier reste non nul : ce n'est ni le reste 0 qui arrête l'algorithme, ni le dernier quotient.

Dans ce chapitre