Cours Terminale S PGCD et PPCM 1. Plus grand commun diviseur 1.1 Diviseurs communs à deux entiers positifs Pour tout entier naturel n, on note D(n) l'ensemble des diviseurs de n. On note D(a; b) l'ensemble des diviseurs communs à a et b, c'est-à-dire D(a; b) = D(a) D(b). Le plus grand élément de D(a; b) est appelé PGCD de a et b , noté PGCD(a; b). Exemple: Le PGCD de 24 et 36 est 12; celui de 25 et 12 est 1. Propriétés: Pour tout entier naturel n, D(n; 0) = D(n). En effet, D(n; 0) = D(n) = D(n). PGCD(a; b) a et PGCD(a; b) b. En effet, les diviseurs de a sont inférieurs à a , de même pour b. Si b divise a, alors PGCD(a; b) = b. En effet, Si b divise a, b D(a; b). PGCD(a; b) = PGCD(b; a). PGCD(a; 1) = 1. PGCD(a; a) = a. Pour tout k entier naturel non nul, PGCD(ka; kb) = k ×PGCD(a; b). Démonstration à l'aide de l'algorithme d'Euclide, vu juste après. 1.2 Recherche du PGCD : Algorithme d'Euclide: a) Propriété : Soit a = bq + r la division euclidienne de a par b . Alors D(a; b) = D(b; r) . Si r = 0, alors PGCD(a; b) = b. Si r 0, alors PGCD(a; b) = PGCD(b; r). Démonstration : Soit c un diviseur commun de a et de b. Il existe deux entiers a' et b' tels que a = ca' et b = cb'. Si a = bq + r est la division euclidienne de a par b , alors r = a – bq = ca' – cb'q = c(a' – b'q), et c divise r, donc est un diviseur commun de b et de r. Ainsi D(a; b) D(b; r).