Deux entiers peuvent avoir des diviseurs en commun : le plus grand d’entre eux, le PGCD, se calcule très vite grâce à l’algorithme d’Euclide. Deux théorèmes, ceux de Bézout et de Gauss, permettent ensuite de résoudre des équations en nombres entiers comme 5x + 3y = 1.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Calculer un PGCD avec l’algorithme d’Euclide
- Reconnaître deux entiers premiers entre eux
- Énoncer et utiliser les théorèmes de Bézout et de Gauss
- Résoudre une équation diophantienne ax + by = c
1. PGCD et algorithme d’Euclide
PGCD : Soit a et b deux entiers non tous deux nuls. Le PGCD de a et b est le plus grand entier naturel qui divise à la fois a et b. On le note PGCD(a ; b).
Propriété clé : si a = bq + r, alors PGCD(a ; b) = PGCD(b ; r). On répète les divisions euclidiennes ; le PGCD est le dernier reste non nul.
PGCD(1 071 ; 462)
- 1 071 = 462 × 2 + 147
- 462 = 147 × 3 + 21
- 147 = 21 × 7 + 0
Le dernier reste non nul est 21 : PGCD(1 071 ; 462) = 21.
- Les diviseurs communs à a et b sont exactement les diviseurs de leur PGCD.
- PGCD(ka ; kb) = k PGCD(a ; b) pour k entier naturel non nul.
- Si d = PGCD(a ; b), alors et sont premiers entre eux.
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return a2. Théorème de Bézout
Entiers premiers entre eux : a et b sont premiers entre eux si PGCD(a ; b) = 1 : leur seul diviseur positif commun est 1.
Plus généralement (identité de Bézout), il existe toujours u et v tels que au + bv = PGCD(a ; b). On les obtient en « remontant » l’algorithme d’Euclide.
Montrer que 2n + 1 et n sont premiers entre eux
- (2n + 1) × 1 + n × (−2) = 1
Par Bézout, PGCD(2n + 1 ; n) = 1 pour tout entier n.
3. Théorème de Gauss
- Corollaire : si a et b sont premiers entre eux et divisent tous deux c, alors ab divise c.
- Attention : 4 divise 2 × 6 mais ne divise ni 2 ni 6. L’hypothèse « premier avec » est indispensable.
4. Équations ax + by = c
L’équation ax + by = c a des solutions entières si et seulement si PGCD(a ; b) divise c.
Résoudre 5x + 3y = 1 dans ℤ²
- Solution particulière : 5 × 2 + 3 × (−3) = 1, donc (2 ; −3).
- Par soustraction : 5(x − 2) = −3(y + 3).
- 3 divise 5(x − 2) et PGCD(3 ; 5) = 1 : par Gauss, 3 divise x − 2, donc x = 2 + 3k.
- En remplaçant : 15k = −3(y + 3), donc y = −3 − 5k.
- Réciproquement, ces couples conviennent : 5(2 + 3k) + 3(−3 − 5k) = 1.
Les solutions sont les couples (2 + 3k ; −3 − 5k), k ∈ ℤ.
À retenir
- PGCD(a ; b) = PGCD(b ; r) : le PGCD est le dernier reste non nul de l’algorithme d’Euclide.
- Bézout : PGCD(a ; b) = 1 ⟺ il existe u, v avec au + bv = 1.
- Gauss : a | bc et PGCD(a ; b) = 1 ⟹ a | c.
- ax + by = c a des solutions ⟺ PGCD(a ; b) divise c ; méthode : solution particulière, puis Gauss.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.