PGCD, théorème de Bézout et applications

Arithmétique — Terminale Maths Expertes

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 Z :

  1. PGCD(a, b) = PGCD(b, a) (commutativité)
  2. PGCD(a, b) = PGCD(|a|, |b|)
  3. PGCD(a, b) = PGCD(a, b + ka) pour tout k Z
  4. Si a b et b 0, alors PGCD(a, b) = |a|
  5. 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 N^* et a b :

  1. Effectuer la division euclidienne : a = bq + r avec 0 r < b
  2. Si r = 0, alors PGCD(a, b) = b
  3. 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^2, alors 7 n.

Si 7 n^2 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 :

[formule]

De plus, PGCD(a, b) est le plus petit entier strictement positif qui peut s'écrire sous la forme au + bv avec u, v Z.

Caractérisation : Deux entiers a et b sont premiers entre eux si et seulement si il existe u, v Z tels que :

[formule]

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) :

  1. Appliquer l'algorithme d'Euclide en notant chaque division : r_i = r_{i-2} - q_i r_{i-1}
  2. Remonter les égalités en exprimant chaque reste en fonction de a et b
  3. 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 Z, 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 Z.

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 Z^* :

[formule]

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 Z et où l'on cherche les solutions (x, y) Z^2.

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 :

  1. Trouver une solution particulière (x_0, y_0) en utilisant l'algorithme d'Euclide étendu
  2. Les solutions générales sont de la forme : [formule] où d = PGCD(a, b) et k Z

Exemple : Résoudre dans Z^2 : 252x + 198y = 18.

On a vu que 252 4 + 198 (-5) = 18, donc (x_0, y_0) = (4, -5) est une solution particulière.

Comme PGCD(252, 198) = 18, les solutions sont : [formule] pour k Z.

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 :

[formule]

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 : [formule] 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 n) si et seulement si PGCD(a, n) = 1.

Cet inverse peut être trouvé via l'algorithme d'Euclide étendu.

À retenir

Résumé :

  1. PGCD : plus grand diviseur commun, calculable par l'algorithme d'Euclide

  2. Nombres premiers entre eux : PGCD(a, b) = 1

  3. Théorème de Bézout : PGCD(a, b) = au + bv pour certains u, v Z

  4. Lemme de Gauss : si a bc et PGCD(a, b) = 1, alors a c

  5. PPCM : PGCD(a, b) PPCM(a, b) = |ab|

  6. Équations diophantiennes : ax + by = c a des solutions ssi PGCD(a, b) c