Admis

Accueil / Terminale C / Mathématiques / Leçon 11

PGCD et PPCM de deux entiers relatifs

Thème : arithmétique (Terminale C).

Situation de départ

Deux bus quittent la gare d'Abobo en même temps : l'un revient toutes les 12 minutes, l'autre toutes les 18 minutes. Dans combien de temps se retrouveront-ils ensemble ? Et deux planches de 252 cm et 180 cm doivent être découpées en morceaux égaux les plus longs possibles : quelle longueur ? On utilise le PPCM et le PGCD.

I. PGCD

  • Le PGCD de a et b (non tous deux nuls) est le plus grand entier positif qui divise a et b. On le note a ∧ b.
  • Algorithme d'Euclide : a = bq + r ; PGCD(a, b) = PGCD(b, r) ; on répète jusqu'à un reste nul : le dernier reste non nul est le PGCD.
  • Les diviseurs communs de a et b sont les diviseurs de leur PGCD.
  • Deux entiers sont premiers entre eux si leur PGCD vaut 1.

PGCD(252, 180) : 252 = 180×1 + 72 ; 180 = 72×2 + 36 ; 72 = 36×2 + 0. PGCD = 36. Les planches sont coupées en morceaux de 36 cm (7 et 5 morceaux).

II. Théorèmes de Bézout et de Gauss

  • Bézout : a et b sont premiers entre eux ⇔ il existe u et v entiers tels que au + bv = 1. Plus généralement, PGCD(a, b) = d ⇒ il existe u, v avec au + bv = d.
  • Gauss : si a | bc et PGCD(a, b) = 1, alors a | c.
  • Si a | c et b | c avec PGCD(a, b) = 1, alors ab | c.

Résoudre 7x + 5y = 1 dans ℤ² : 7×3 + 5×(−4) = 1, donc (3 ; −4) est une solution particulière ; les solutions sont (3 + 5k ; −4 − 7k), k ∈ ℤ.

III. PPCM

  • Le PPCM de a et b est le plus petit multiple commun strictement positif. On a : PGCD(a, b) × PPCM(a, b) = |ab|.
  • Avec les décompositions en facteurs premiers : PGCD = produit des facteurs communs avec le plus petit exposant ; PPCM = produit de tous les facteurs avec le plus grand exposant.

PPCM(12, 18) : 12 = 2² × 3 ; 18 = 2 × 3². PPCM = 2² × 3² = 36. Les bus se retrouvent après 36 minutes.

Pour résoudre ax + by = c, il faut d'abord que PGCD(a, b) divise c ; sinon, il n'y a pas de solution entière.

À retenir

  • Euclide : dernier reste non nul = PGCD.
  • Bézout : premiers entre eux ⇔ au + bv = 1 ; Gauss : a | bc et a ∧ b = 1 ⇒ a | c.
  • PGCD × PPCM = produit.

Exercices de fixation

Exercice 1. PGCD(84, 126).

Voir la correction

126 = 84 + 42 ; 84 = 2×42. PGCD = 42.

Exercice 2. PPCM(84, 126).

Voir la correction

84 × 126 / 42 = 252.

Exercice 3. Résous 3x + 4y = 1 dans ℤ².

Voir la correction

(−1 ; 1) est solution (−3 + 4 = 1). Solutions : (−1 + 4k ; 1 − 3k).

Exercice 4. 6x + 9y = 4 a-t-il des solutions entières ?

Voir la correction

Non : PGCD(6, 9) = 3 ne divise pas 4.

Situation complexe

Un marchand dispose de 252 sacs de riz et de 180 sacs de maïs. Il veut former des lots identiques, sans reste, avec le plus grand nombre de lots possible. Combien de lots, et que contient chaque lot ?

Voir la correction

Le nombre de lots divise 252 et 180 ; le maximum est PGCD(252, 180) = 36. Chaque lot contient 252/36 = 7 sacs de riz et 180/36 = 5 sacs de maïs.

Poser une question au profsur cette leçon

Il te reste 5 questions aujourd'hui. Le prof peut se tromper : vérifie avec ton cours.

Faire une interro de Mathématiques

Donner mon avis