🔢

Arithmétique

PGCD, nombres premiers, décomposition

Tout entier $n \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 instantanément tous ses diviseurs, son PGCD et son PPCM.

Le PGCD (Plus Grand Commun Diviseur) donne la taille maximale d'une part équitable. Le PPCM (Plus Petit Commun Multiple) indique le premier moment où deux cycles se synchronisent.

L'algorithme d'Euclide calcule le PGCD en quelques divisions successives, sans décomposer en facteurs premiers — très pratique pour les grands nombres.

Relation clé : $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 \geq 2

qui n'a que deux diviseurs distincts :

1

et lui-même.

Exemples :

2, 3, 5, 7, 11, 13\ldots

Le nombre

1

n'est pas premier.

PGCD : Plus Grand Commun Diviseur de deux entiers

a

b

: c'est le plus grand entier qui divise à la fois

a

b

.

Exemple :

\text{PGCD}(12, 18) = 6

PPCM : Plus Petit Commun Multiple de deux entiers

a

b

: c'est le plus petit entier strictement positif qui est multiple de

a

et de

b

simultanément.

Exemple :

\text{PPCM}(4, 6) = 12

Algorithme d'Euclide : Méthode de calcul du PGCD par divisions euclidiennes successives :

\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 Étape 1 : Décomposer chaque nombre en produit de facteurs premiers (diviser successivement par $2$ , $3$ , $5$ , $7$ , $11\ldots$ jusqu'à $1$ ).
2 Étape 2 : PGCD — prendre les facteurs premiers communs avec le plus petit exposant.
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

84

56

par l'algorithme d'Euclide.

Démarche :

1ère division : $84 = 56 \times 1 + 28$ . Le reste est $28 \neq 0$ , on continue avec $\text{PGCD}(56, 28)$ .
2e division : $56 = 28 \times 2 + 0$ . Le reste est $0$ , on s'arrête.
Conclusion : le dernier reste non nul est $28$ , donc $\text{PGCD}(84, 56) = 28$ . Vérification : $84 = 28 \times 3$ et $56 = 28 \times 2$ ✓

Réponse :

\text{PGCD}(84, 56) = 28

📐 Formules clés

PGCD × PPCM

= a \times b

Fraction irréductible : diviser numérateur et dénominateur par le PGCD

Algorithme d'Euclide :

\text{PGCD}(a, b) = \text{PGCD}(b, a \mod b)

🎨 Illustration

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.

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 = 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

180

en produit de facteurs premiers :

180 = 2^2 \times 3^2 \times 5

❌ Une erreur, une suggestion

❌ L'erreur fréquente

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

✅ La suggestion

Le plus petit nombre premier est $2$ . Et $2$ est le seul nombre premier pair.

💡 À retenir

Théorème fondamental : tout entier $\geq 2$ se décompose de manière unique en produit de nombres premiers.
Relation PGCD-PPCM : $\text{PGCD}(a, b) \times \text{PPCM}(a, b) = a \times b$ . Connaître l'un permet de calculer l'autre.
$1$ n'est pas premier : un nombre premier a exactement deux diviseurs distincts. $1$ 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