Nombres et calculs · 1re Bac SM
Division euclidienne, pgcd, ppcm et nombres premiers
Deux entiers partagent toujours un plus grand diviseur : l'algorithme d'Euclide le trouve en quelques lignes, sans décomposer.
Le vocabulaire à connaître
- division euclidienne
- Pour a et b entiers (b non nul), il existe un unique couple (q ; r) tel que a = bq + r et 0 ≤ r ≤ |b| − 1.
- pgcd, ppcm
- Le plus grand diviseur commun et le plus petit multiple commun strictement positif de deux entiers.
- premiers entre eux
- Deux entiers dont le pgcd vaut 1.
Ce qu'on sait
- Si a = bq + r, alors pgcd(a ; b) = pgcd(b ; r) : c'est le moteur de l'algorithme d'Euclide.
- Le pgcd est le dernier reste non nul de la suite des divisions.
- pgcd(a ; b) × ppcm(a ; b) = a × b, et un entier divise a et b si et seulement s'il divise leur pgcd.
La méthode, étape par étape
1.Je divise le plus grand par le plus petit et je note le reste.
2.Je recommence avec le diviseur et le reste, jusqu'à obtenir un reste nul.
3.Le dernier reste non nul est le pgcd.
4.Je déduis le ppcm par ppcm = a × b / pgcd.
Le pgcd est le dernier reste non nul de l'algorithme d'Euclide ; le ppcm s'en déduit par pgcd × ppcm = a × b.
C.Q.F.D.
L'exemple au propre
1.Cherchons pgcd(252 ; 198).
2.252 = 198 × 1 + 54 puis 198 = 54 × 3 + 36.
3.54 = 36 × 1 + 18 puis 36 = 18 × 2 + 0.
4.Le dernier reste non nul est 18 : pgcd(252 ; 198) = 18.
5.Le ppcm vaut 252 × 198 / 18 = 2 772.