PGCD de deux entiers

Mathématiques Expertes · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

Définitions et théorèmes

Soit a et b deux entiers naturels non nuls. L'ensemble des diviseurs communs à a et b est fini et non vide (il contient 1). Le PGCD de a et b, noté \mathrm{PGCD}(a,b) ou a\wedge b, est le plus grand de ces diviseurs communs.

Propriété fondamentale : les diviseurs communs à a et b sont exactement les diviseurs de \mathrm{PGCD}(a,b).

On définit de même le PPCM (plus petit commun multiple), noté \mathrm{PPCM}(a,b) ou a\vee b, comme le plus petit entier strictement positif multiple commun de a et b.

Formules

- Décomposition en facteurs premiers : si a=\prod p_i^{\alpha_i} et b=\prod p_i^{\beta_i}, alors \mathrm{PGCD}(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)},\qquad \mathrm{PPCM}(a,b)=\prod p_i^{\max(\alpha_i,\beta_i)}. - Relation fondamentale : \mathrm{PGCD}(a,b)\times\mathrm{PPCM}(a,b)=a\times b. - Homogénéité : \mathrm{PGCD}(ka,kb)=k\,\mathrm{PGCD}(a,b). - Simplification : si d=\mathrm{PGCD}(a,b), alors \dfrac{a}{d} et \dfrac{b}{d} sont premiers entre eux.

Méthodes type bac

  • Calcul par décomposition : factoriser a et b en produits de nombres premiers, puis appliquer les règles min/max sur les exposants.
  • Calcul par l'algorithme d'Euclide (chapitre suivant) : plus rapide quand les nombres sont grands et difficiles à factoriser.
  • Vérification : utiliser \mathrm{PGCD}\times\mathrm{PPCM}=ab pour contrôler un résultat ou pour déduire l'un connaissant l'autre.
  • Problèmes concrets : le PGCD répond aux questions de partage en parts égales maximales (« quel est le plus grand carreau pavant une pièce de a par b ? ») ; le PPCM aux questions de coïncidence périodique (« dans combien de temps deux feux clignotant toutes les a et b secondes coïncident-ils ? »).

Pièges

  • Confondre \min et \max : PGCD = plus petit exposant, PPCM = plus grand exposant.
  • Pour le PGCD, ne garder que les facteurs communs ; pour le PPCM, garder tous les facteurs.
  • La relation \mathrm{PGCD}\times\mathrm{PPCM}=ab ne vaut que pour deux entiers (pas trois).
  • Oublier un facteur premier non commun dans le PPCM : tous les premiers apparaissant dans a ou dans b doivent y figurer.

Exemple détaillé

Pour 252=2^2\times3^2\times7 et 360=2^3\times3^2\times5 : les facteurs communs sont 2 et 3. Le PGCD prend les exposants minimaux : \min(2,3)=2 pour le 2 et \min(2,2)=2 pour le 3, soit \mathrm{PGCD}=2^2\times3^2=36. Le PPCM prend les exposants maximaux et tous les facteurs : \mathrm{PPCM}=2^3\times3^2\times5\times7=2520. On vérifie \mathrm{PGCD}\times\mathrm{PPCM}=36\times2520=90720=252\times360.

Pour l'épreuve

Sache calculer un PGCD de deux façons (décomposition en facteurs premiers et algorithme d'Euclide) et passer de l'une à l'autre selon la taille des nombres. La relation \mathrm{PGCD}\times\mathrm{PPCM}=ab est un grand classique de vérification, à utiliser pour contrôler tes résultats. Retiens que « diviseurs communs = diviseurs du PGCD » : cette caractérisation sert dans de nombreux raisonnements, notamment pour démontrer que deux quotients \dfrac{a}{d} et \dfrac{b}{d} sont premiers entre eux après simplification.