PGCD, théorème de Bézout et applications
1. Plus Grand Commun Diviseur (PGCD)
PGCD : Soient a et b deux entiers relatifs non tous deux nuls. Le Plus Grand Commun Diviseur de a et b, noté PGCD(a, b) ou a ∧ b, est le plus grand entier positif qui divise à la fois a et b.
Par convention, on pose PGCD(0, 0) = 0.
Exemples :
- PGCD(12, 18) = 6 (les diviseurs communs sont 1, 2, 3, 6)
- PGCD(15, 25) = 5
- PGCD(7, 11) = 1 (nombres premiers entre eux)
- PGCD(a, 0) = |a| si a ≠ 0
Propriétés du PGCD : Pour tous a, b, c ∈ ℤ :
- PGCD(a, b) = PGCD(b, a) (commutativité)
- PGCD(a, b) = PGCD(|a|, |b|)
- PGCD(a, b) = PGCD(a, b + ka) pour tout k ∈ ℤ
- Si a | b et b ≠ 0, alors PGCD(a, b) = |a|
- PGCD(ca, cb) = |c| × PGCD(a, b) pour c ≠ 0
2. Algorithme d'Euclide
Algorithme d'Euclide : Pour calculer PGCD(a, b) avec a, b ∈ ℕ^* et a ≥ b :
- Effectuer la division euclidienne : a = bq + r avec 0 ≤ r < b
- Si r = 0, alors PGCD(a, b) = b
- Sinon, recommencer avec PGCD(b, r)
L'algorithme s'arrête car la suite des restes est strictement décroissante.
Exemple détaillé : Calculer PGCD(252, 198).
- 252 = 198 × 1 + 54 → PGCD(252, 198) = PGCD(198, 54)
- 198 = 54 × 3 + 36 → PGCD(198, 54) = PGCD(54, 36)
- 54 = 36 × 1 + 18 → PGCD(54, 36) = PGCD(36, 18)
- 36 = 18 × 2 + 0 → PGCD(36, 18) = 18
Donc PGCD(252, 198) = 18.
Algorithme d'Euclide étendu : L'algorithme d'Euclide permet aussi de trouver des coefficients de Bézout (voir section suivante) en "remontant" les divisions euclidiennes.
3. Nombres premiers entre eux
Nombres premiers entre eux : Deux entiers a et b sont dits premiers entre eux (ou copremiers) si PGCD(a, b) = 1.
Exemples :
- 15 et 28 sont premiers entre eux car PGCD(15, 28) = 1
- 12 et 18 ne sont pas premiers entre eux car PGCD(12, 18) = 6 ≠ 1
- Deux nombres premiers distincts sont toujours premiers entre eux
Lemme de Gauss : Si a | bc et PGCD(a, b) = 1, alors a | c.
En particulier, si un nombre premier p divise un produit ab et ne divise pas a, alors p | b.
Exemple : Montrer que si n est un entier tel que 7 | n², alors 7 | n.
Si 7 | n² et 7 est premier, alors par le lemme de Gauss (car PGCD(7, n) divise 7, donc vaut 1 ou 7), on a 7 | n.
4. Théorème de Bézout
Théorème de Bézout : Soient a et b deux entiers relatifs non tous deux nuls. Il existe des entiers u et v tels que :
au + bv = PGCD(a, b)
De plus, PGCD(a, b) est le plus petit entier strictement positif qui peut s'écrire sous la forme au + bv avec u, v ∈ ℤ.
Caractérisation : Deux entiers a et b sont premiers entre eux si et seulement si il existe u, v ∈ ℤ tels que :
au + bv = 1
C'est l'identité de Bézout.
Algorithme d'Euclide étendu : Pour trouver des coefficients de Bézout u et v tels que au + bv = PGCD(a, b) :
- Appliquer l'algorithme d'Euclide en notant chaque division : rᵢ = rᵢ₋₂ - qᵢ rᵢ₋₁
- Remonter les égalités en exprimant chaque reste en fonction de a et b
- Le dernier reste non nul donne le PGCD et son expression en fonction de a et b donne les coefficients
Exemple : Trouver des entiers u et v tels que 252u + 198v = PGCD(252, 198) = 18.
On remonte les divisions euclidiennes :
- 54 = 252 - 198 × 1
- 36 = 198 - 54 × 3 = 198 - 3(252 - 198) = -3 × 252 + 4 × 198
- 18 = 54 - 36 × 1 = (252 - 198) - (-3 × 252 + 4 × 198) = 4 × 252 - 5 × 198
Donc u = 4 et v = -5 : 252 × 4 + 198 × (-5) = 18.
5. Théorème de Bézout (réciproque)
Théorème de Bézout (réciproque) : Si d = au + bv avec u, v ∈ ℤ, alors PGCD(a, b) | d.
En particulier, si au + bv = 1, alors PGCD(a, b) = 1.
Exemple : Montrer que PGCD(n, n+1) = 1 pour tout n ∈ ℤ.
On a 1 × (n+1) + (-1) × n = 1, donc par le théorème de Bézout, PGCD(n, n+1) = 1.
6. PPCM (Plus Petit Commun Multiple)
PPCM : Soient a et b deux entiers relatifs non nuls. Le Plus Petit Commun Multiple de a et b, noté PPCM(a, b) ou a ∨ b, est le plus petit entier strictement positif qui est multiple à la fois de a et de b.
Relation PGCD-PPCM : Pour tous a, b ∈ ℤ^* :
PGCD(a, b) × PPCM(a, b) = |ab|
Exemple : PGCD(12, 18) = 6 et PPCM(12, 18) = 36. Vérification : 6 × 36 = 216 = 12 × 18.
7. Applications
7.1 Résolution d'équations diophantiennes
Équation diophantienne : Une équation diophantienne est une équation de la forme ax + by = c où a, b, c ∈ ℤ et où l'on cherche les solutions (x, y) ∈ ℤ².
Condition d'existence : L'équation ax + by = c admet des solutions entières si et seulement si PGCD(a, b) | c.
Résolution : Si PGCD(a, b) | c :
- Trouver une solution particulière (x₀, y₀) en utilisant l'algorithme d'Euclide étendu
- Les solutions générales sont de la forme : x = x₀ + k b/d, y = y₀ - k a/d où d = PGCD(a, b) et k ∈ ℤ
Exemple : Résoudre dans ℤ² : 252x + 198y = 18.
On a vu que 252 × 4 + 198 × (-5) = 18, donc (x₀, y₀) = (4, -5) est une solution particulière.
Comme PGCD(252, 198) = 18, les solutions sont : x = 4 + k × 198/18 = 4 + 11k, y = -5 - k × 252/18 = -5 - 14k pour k ∈ ℤ.
7.2 Fractions irréductibles
Fraction irréductible : Une fraction a/b avec b ≠ 0 est dite irréductible si PGCD(a, b) = 1.
Rendre une fraction irréductible : Pour rendre a/b irréductible, on divise numérateur et dénominateur par leur PGCD :
a/b = (a/d)/(b/d) où d = PGCD(a, b)
Exemple : Rendre 252/198 irréductible.
PGCD(252, 198) = 18, donc 252/198 = (252/18)/(198/18) = 14/11.
8. Applications avancées
Théorème chinois des restes (cas simple) : Si PGCD(m, n) = 1, alors le système : x ≡ a (mod m) | x ≡ b (mod n) admet une unique solution modulo mn.
On peut trouver cette solution en utilisant l'identité de Bézout mu + nv = 1.
Inverses modulo n : Un entier a admet un inverse modulo n (i.e. il existe b tel que ab ≡ 1 (mod n)) si et seulement si PGCD(a, n) = 1.
Cet inverse peut être trouvé via l'algorithme d'Euclide étendu.
À retenir
Résumé :
PGCD : plus grand diviseur commun, calculable par l'algorithme d'Euclide
Nombres premiers entre eux : PGCD(a, b) = 1
Théorème de Bézout : PGCD(a, b) = au + bv pour certains u, v ∈ ℤ
Lemme de Gauss : si a | bc et PGCD(a, b) = 1, alors a | c
PPCM : PGCD(a, b) × PPCM(a, b) = |ab|
Équations diophantiennes : ax + by = c a des solutions ssi PGCD(a, b) | c