Mathématiques > Arithmétique (Terminale - Spécialité) > Divisibilité et Nombres Premiers > Divisibilité dans Z

PGCD dans Z : Définition, Propriétés et Algorithme d'Euclide

Étude approfondie du Plus Grand Commun Diviseur (PGCD) dans l'ensemble des entiers relatifs (Z). Ce cours couvre les définitions, les propriétés et l'algorithme d'Euclide, essentiels pour la spécialité Mathématiques en Terminale.

Définition du PGCD dans Z

Le Plus Grand Commun Diviseur (PGCD) de deux entiers relatifs a et b, noté PGCD(a, b) ou parfois gcd(a, b), est le plus grand entier positif qui divise à la fois a et b.

Note Importante : Le PGCD est toujours positif, même si a ou b sont négatifs. On prend en compte tous les diviseurs, qu'ils soient positifs ou négatifs, mais on retient le plus grand diviseur positif commun.

Exemples :

  • PGCD(12, 18) = 6
  • PGCD(-12, 18) = 6
  • PGCD(-12, -18) = 6
  • PGCD(0, 8) = 8 (Par convention, le PGCD(0, a) = |a| pour a non nul)
  • PGCD(0, 0) n'est pas défini (par convention, on peut considérer PGCD(0,0) = 0)

Propriétés du PGCD

Le PGCD possède plusieurs propriétés importantes :

1. Symétrie : PGCD(a, b) = PGCD(b, a)

Explication : L'ensemble des diviseurs communs à a et b est le même que l'ensemble des diviseurs communs à b et a.

2. PGCD et signe : PGCD(a, b) = PGCD(|a|, |b|)

Explication : Les diviseurs de a sont les mêmes que les diviseurs de |a|, à un signe près. Comme on cherche le plus grand diviseur positif, le signe n'affecte pas le résultat.

3. Divisibilité : Si c divise a et c divise b, alors c divise PGCD(a, b).

Explication : Le PGCD(a, b) est le plus grand diviseur commun à a et b. Donc tout diviseur commun à a et b divise aussi le PGCD.

4. PGCD et combinaison linéaire : PGCD(a, b) = PGCD(a, b + ka) pour tout entier k.

Démonstration :
Soit d = PGCD(a, b). Alors, d | a et d | b.
Donc, d | (b + ka) (puisque d divise toute combinaison linéaire de a et b).
Ainsi, d est un diviseur commun de a et b + ka.
Réciproquement, soit d' = PGCD(a, b + ka). Alors, d' | a et d' | (b + ka).
Donc, d' | (b + ka - ka), ce qui implique d' | b.
Ainsi, d' est un diviseur commun de a et b.
Puisque d est le plus grand diviseur commun de a et b, on a d' ≤ d. Réciproquement, d ≤ d'.
Donc, d = d', et PGCD(a, b) = PGCD(a, b + ka).

Algorithme d'Euclide

L'algorithme d'Euclide est une méthode efficace pour calculer le PGCD de deux entiers.

Principe : On effectue des divisions euclidiennes successives jusqu'à obtenir un reste nul. Le PGCD est alors le dernier reste non nul.

Étapes :

  1. Soient a et b deux entiers dont on cherche le PGCD. On suppose a ≥ b ≥ 0 (on peut toujours prendre les valeurs absolues).
  2. On effectue la division euclidienne de a par b : a = bq1 + r1, où 0 ≤ r1 < b.
  3. Si r1 = 0, alors PGCD(a, b) = b.
  4. Sinon, on effectue la division euclidienne de b par r1 : b = r1q2 + r2, où 0 ≤ r2 < r1.
  5. On continue ainsi jusqu'à obtenir un reste nul : rn-1 = rnqn+1 + 0.
  6. Le PGCD(a, b) est alors rn, le dernier reste non nul.

Exemple : Calculer PGCD(1071, 462).
  1. 1071 = 462 * 2 + 147
  2. 462 = 147 * 3 + 21
  3. 147 = 21 * 7 + 0
Donc, PGCD(1071, 462) = 21.

Nombres premiers entre eux

Deux entiers a et b sont dits premiers entre eux (ou relativement premiers) si leur PGCD est égal à 1, c'est-à-dire PGCD(a, b) = 1.

Exemple : 8 et 15 sont premiers entre eux car PGCD(8, 15) = 1.

Théorème de Bézout : Deux entiers a et b sont premiers entre eux si et seulement s'il existe des entiers u et v tels que au + bv = 1.

Les entiers u et v sont appelés coefficients de Bézout. L'algorithme d'Euclide étendu permet de trouver ces coefficients.

Ce qu'il faut retenir

  • Définition du PGCD : Le plus grand entier positif divisant à la fois a et b.
  • Propriétés : PGCD(a, b) = PGCD(b, a), PGCD(a, b) = PGCD(|a|, |b|), PGCD(a, b) = PGCD(a, b + ka).
  • Algorithme d'Euclide : Une méthode efficace pour calculer le PGCD.
  • Nombres premiers entre eux : PGCD(a, b) = 1.
  • Théorème de Bézout : a et b sont premiers entre eux <=> il existe u et v tels que au + bv = 1.

← Les Nombres Premiers : Fondations de l'Arithmétique PGCD et PPCM : Maîtriser les fondations de l'arithmétique →

FAQ

  • Le PGCD de deux nombres négatifs est-il négatif ?

    Non, le PGCD est toujours positif. On prend en compte tous les diviseurs (positifs et négatifs), mais on choisit le plus grand diviseur positif commun.
  • Comment trouver les coefficients de Bézout ?

    On peut utiliser l'algorithme d'Euclide étendu. Cet algorithme permet de déterminer les coefficients u et v tels que au + bv = PGCD(a, b). Si PGCD(a, b) = 1, alors a et b sont premiers entre eux.
  • Pourquoi l'algorithme d'Euclide fonctionne-t-il ?

    L'algorithme d'Euclide est basé sur la propriété que PGCD(a, b) = PGCD(b, r), où r est le reste de la division euclidienne de a par b. En répétant ce processus, on réduit progressivement les nombres jusqu'à obtenir un reste nul. Le dernier reste non nul est alors le PGCD.