Matières › 📐 Mathématiques › Collège › Arithmétique
🔢

Arithmétique

PGCD, nombres premiers, décomposition

Deux roues dentées sont engrenées l'une dans l'autre : la petite a 1212 dents, la grande en a 1818. Sur chacune, une dent est marquée d'un trait rouge, et au départ les deux traits sont exactement face à face.

Tu fais tourner le mécanisme. Les traits se séparent aussitôt. Question : au bout de combien de dents défilées les deux traits se retrouveront-ils face à face ?

La réponse spontanée est « au bout de 1818 », puisque la grande roue est la plus lente. Mais après 1818 dents, la petite roue a fait un tour et demi : son trait pointe à l'opposé. Compter, essayer, tâtonner ne mène nulle part — il faut un nombre qui soit à la fois un multiple de 1212 et un multiple de 1818. Le premier est 3636 : la petite roue fait alors trois tours, la grande en fait deux, et les deux traits se rejoignent.

Ce nombre 3636 a un nom : c'est le PPCM de 1212 et 1818, le Plus Petit Commun Multiple. Il donne le premier instant où deux cycles se synchronisent — engrenages, feux de circulation, éclipses, rythmes de rotation des planètes.

Son jumeau répond à la question inverse. Tu dois répartir 1212 bonbons et 1818 caramels en sachets tous identiques, sans rien laisser de côté : combien de sachets au maximum ? Pas 1212, pas 1818 — il faut un nombre qui divise les deux, et le plus grand est 66. Ce 66 est le PGCD, le Plus Grand Commun Diviseur : il donne la part équitable la plus fine possible.

D'où viennent ces nombres ? De la structure profonde des entiers. Tout entier n≥2n \geq 2 admet une décomposition en facteurs premiers unique, à l'ordre près : c'est le théorème fondamental de l'arithmétique. Cette décomposition est le « code-barres » du nombre — elle révèle d'un coup tous ses diviseurs, son PGCD et son PPCM.

L'algorithme d'Euclide calcule le PGCD en quelques divisions successives, sans décomposer en facteurs premiers — très pratique pour les grands nombres, et vieux de vingt-trois siècles.

Relation clé : a×b=PGCD(a,b)×PPCM(a,b)a \times b = \text{PGCD}(a,b) \times \text{PPCM}(a,b) — connaître l'un permet de calculer l'autre.

📖 Vocabulaire clé

Nombre premier : Entier n≥2n \geq 2 qui n'a que deux diviseurs distincts : 11 et lui-même.

Exemples : 2,3,5,7,11,13…2, 3, 5, 7, 11, 13\ldots Le nombre 11 n'est pas premier.
PGCD : Plus Grand Commun Diviseur de deux entiers aa et bb : c'est le plus grand entier qui divise à la fois aa et bb.

Exemple : PGCD(12,18)=6\text{PGCD}(12, 18) = 6.
PPCM : Plus Petit Commun Multiple de deux entiers aa et bb : c'est le plus petit entier strictement positif qui est multiple de aa et de bb simultanément.

Exemple : PPCM(4,6)=12\text{PPCM}(4, 6) = 12.
Algorithme d'Euclide : Méthode de calcul du PGCD par divisions euclidiennes successives : PGCD(a,b)=PGCD(b,amod  b)\text{PGCD}(a, b) = \text{PGCD}(b, a \mod b), jusqu'à obtenir un reste nul. Le dernier diviseur non nul est le PGCD.

📋 Méthode en 3 étapes

  1. 1 Étape 1 : Décomposer chaque nombre en produit de facteurs premiers (diviser successivement par 22, 33, 55, 77, 11…11\ldots jusqu'à 11).
  2. 2 Étape 2 : PGCD — prendre les facteurs premiers communs avec le plus petit exposant.
  3. 3 Étape 3 : PPCM — prendre tous les facteurs premiers (communs ou non) avec le plus grand exposant.

✅ Exemple résolu

Énoncé : Trouver le PGCD de 8484 et 5656 par l'algorithme d'Euclide.
Démarche :
  1. 1re division : 84=56×1+2884 = 56 \times 1 + 28. Le reste est 28≠028 \neq 0, on continue avec PGCD(56,28)\text{PGCD}(56, 28).
  2. 2e division : 56=28×2+056 = 28 \times 2 + 0. Le reste est 00, on s'arrête.
  3. Conclusion : le dernier reste non nul est 2828, donc PGCD(84,56)=28\text{PGCD}(84, 56) = 28. Vérification : 84=28×384 = 28 \times 3 et 56=28×256 = 28 \times 2 ✓
Réponse : PGCD(84,56)=28\text{PGCD}(84, 56) = 28.

📐 Formules clés

PGCD × PPCM =a×b= a \times b
Fraction irréductible : diviser numérateur et dénominateur par le PGCD
Algorithme d'Euclide : PGCD(a,b)=PGCD(b,amod  b)\text{PGCD}(a, b) = \text{PGCD}(b, a \mod b)

🎨 Illustrations

Décomposition en facteurs premiers
Un arbre pour décomposer 180 en facteurs premiers

Chaque nombre composé se sépare en deux facteurs jusqu'à n'obtenir que des nombres premiers, en bout de branche.

Arbre de decomposition en facteurs premiers de 180 Le schema montre 180 se separant en 4 et 45, puis 4 en 2 et 2, 45 en 9 et 5, et 9 en 3 et 3, jusqu'a n'obtenir que des nombres premiers. Nombre compose : on continue Nombre premier : on s'arrete 180 4 45 2 2 9 5 3 3 180 = 2² × 3² × 5
  • 1 Peu importe la paire de facteurs choisie au départ (ici 4 et 45) : on retombe toujours sur la même décomposition finale. C'est le théorème fondamental de l'arithmétique.
  • 2 Les cercles bordés (180, 4, 45, 9) sont des nombres composés : on continue à les décomposer. Les cercles pleins (2, 2, 3, 3, 5) sont des nombres premiers : la branche s'arrête.
  • 3 On regroupe ensuite les facteurs identiques avec des exposants : 180=22×32×5180 = 2^2 \times 3^2 \times 5.
Ce qu'il faut lire : Un arbre de décomposition se lit de haut en bas : à chaque nœud composé, on choisit deux facteurs dont le produit redonne le nombre, jusqu'à n'obtenir que des nombres premiers.
Décomposition de 180180 en produit de facteurs premiers : 180=22×32×5180 = 2^2 \times 3^2 \times 5.
Piège
Le PGCD se loge sous les deux nombres, le PPCM au-dessus

Les deux noms se ressemblent, et c'est là tout le problème. Mais leurs places ne se ressemblent pas : un diviseur commun est forcément plus petit que les deux nombres, un multiple commun forcément plus grand. Sur 1212 et 1818, le PGCD vaut 66 et le PPCM vaut 3636.

Position du PGCD et du PPCM par rapport aux deux nombres Une echelle verticale de valeurs croissantes du bas vers le haut. Tout en bas figure le nombre six, designe comme le plus grand commun diviseur de douze et de dix-huit ; a cote de lui sont rappeles les autres diviseurs communs, un, deux et trois, tous plus petits que six. Au milieu figurent les deux nombres de depart, douze et dix-huit. Tout en haut figure le nombre trente-six, designe comme le plus petit commun multiple de douze et de dix-huit ; a cote de lui sont rappeles les multiples communs suivants, soixante-douze et cent huit, tous plus grands que trente-six. Le plus grand commun diviseur est donc situe en dessous des deux nombres de depart, et le plus petit commun multiple au-dessus : les diviseurs communs sont plus petits que les nombres, les multiples communs plus grands. grand petit PPCM de 12 et 18 : 36 puis 72, puis 108 le plus petit des multiples communs 12 18 les deux nombres PGCD de 12 et 18 : 6 apres 1, 2 et 3 le plus grand des diviseurs communs un diviseur est plus petit, un multiple est plus grand
  • 1 Un diviseur de 1212 ne peut pas dépasser 1212. Donc un diviseur commun à 1212 et à 1818 est plus petit que les deux, et le PGCD se trouve nécessairement en dessous.
  • 2 Un multiple de 1212 vaut au moins 1212. Donc un multiple commun est plus grand que les deux, et le PPCM se trouve nécessairement au-dessus.
  • 3 Les diviseurs communs de 1212 et 1818 sont 11, 22, 33 et 66 : on prend le plus grand, d'où PGCD=6\text{PGCD} = 6. Les multiples communs sont 3636, 7272, 108108… : on prend le plus petit, d'où PPCM=36\text{PPCM} = 36.
  • 4 Le mot « grand » dans PGCD et le mot « petit » dans PPCM ne parlent donc pas du résultat final, mais du choix dans la liste. C'est exactement ce qui trompe.
  • 5 Le contrôle qui sauve : 6×36=2166 \times 36 = 216 et 12×18=21612 \times 18 = 216. Si ton PGCD multiplié par ton PPCM ne redonne pas le produit des deux nombres de départ, l'un des deux est faux.
Ce qu'il faut lire : Ne retiens pas les deux noms, retiens les deux hauteurs. Ce qui divise est en bas, ce qui est multiple est en haut, et les deux nombres de départ sont toujours entre les deux.
Positions relatives du PGCD et du PPCM de 1212 et 1818 : le PGCD (66) sous les deux nombres, le PPCM (3636) au-dessus.

❌ Une erreur, une suggestion

❌ L'erreur fréquente

11 n'est PAS un nombre premier (il faut exactement deux diviseurs distincts).

✅ La suggestion

Le plus petit nombre premier est 22. Et 22 est le seul nombre premier pair.

💡 À retenir

  • Théorème fondamental : tout entier ≥2\geq 2 se décompose de manière unique en produit de nombres premiers.
  • Relation PGCD-PPCM : PGCD(a,b)×PPCM(a,b)=a×b\text{PGCD}(a, b) \times \text{PPCM}(a, b) = a \times b. Connaître l'un permet de calculer l'autre.
  • 11 n'est pas premier : un nombre premier a exactement deux diviseurs distincts. 11 n'en a qu'un.
  • Algorithme d'Euclide : méthode rapide pour calculer le PGCD sans décomposer en facteurs premiers — idéal pour les grands nombres.
← Théorème de Thalès 40 / 49 → Identités remarquables