Au programme de ce chapitre
- I. PGCD et algorithme d'Euclide
- II. Théorème de Bézout
- III. Théorème de Gauss et équations diophantiennes
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Soient a et b deux entiers naturels non tous deux nuls. Le plus grand diviseur commun à a et b est appelé PGCD de a et b, noté PGCD(a;b), ou a∧b.
Un exemple corrigé
Exemple Calculons PGCD(252;198). 252 = 198×1+54 ; 198 = 54×3+36 ; 54 = 36×1+18 ; 36 = 18×2+0. Le dernier reste non nul est 18, donc PGCD(252;198) = 18.
Extrait du cours
Démonstration. Puisque a et b sont premiers entre eux, le théorème de Bézout fournit des entiers u, v tels que au + bv = 1. En multipliant par c : auc + bvc = c, soit a(uc) + (bc)v = c. Or a divise bc par hypothèse, et a divise évidemment a(uc) : donc a divise la somme a(uc) + (bc)v, c'est-à-dire a divise c. ∎
Les erreurs fréquentes à éviter
Piège. « Premiers entre eux » ne veut pas dire « tous les deux premiers ». 8 et 9 sont premiers entre eux alors que ni l'un ni l'autre n'est premier.
L'astuce du prof
Astuce. Pour trouver un couple de Bézout, remonte l'algorithme d'Euclide (algorithme d'Euclide étendu) : exprime chaque reste puis substitue.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Calculer pgcd(48, 36) par l'algorithme d'Euclide.
Voir la correction
48 = 36×1 + 12 ; 36 = 12×3 + 0. Le dernier reste non nul est 12 : pgcd(48,36) = 12.
Exercice 2
Les nombres 7 et 5 sont-ils premiers entre eux ? Donner un couple de Bézout.
Voir la correction
pgcd(7,5) = 1, donc oui. On cherche u, v : 7×3 + 5×(−4) = 21 − 20 = 1. Couple : (u,v) = (3, −4).