✅ À retenir

Un entier n > 1 est **premier** s'il admet exactement deux diviseurs : 1 et lui-même.
Tout entier n \geq 2 se décompose de façon unique en **produit de facteurs premiers**.
**PGCD** (Plus Grand Commun Diviseur) : plus grand entier divisant deux nombres.
Algorithme d'Euclide : \text{PGCD}(a,b) = \text{PGCD}(b, a \mod b) jusqu'à reste nul.
Une fraction \dfrac{a}{b} est irréductible si \text{PGCD}(a,b) = 1.

📖 Définition — Algorithme d'Euclide

Pour calculer $\text{PGCD}(a, b)$ avec $a > b$ :

Diviser $a$ par $b$ : $a = b \times q + r$ .
Si $r = 0$ : $\text{PGCD}(a,b) = b$ .
Sinon recommencer avec $b$ et $r$ : $\text{PGCD}(a,b) = \text{PGCD}(b,r)$ .

🔢 Méthode — Décomposer en facteurs premiers

Tester la divisibilité par les premiers : 2, 3, 5, 7, 11, 13…
Diviser par le plus petit premier qui divise, répéter.
S'arrêter quand le quotient est 1.
Exemple : $360 = 2^3 \times 3^2 \times 5$.

🔢 Méthode — Calculer le PGCD par Euclide

Écrire la division euclidienne : $a = b \times q + r$.
Remplacer $(a, b)$ par $(b, r)$ et répéter.
Quand le reste est $0$ : le PGCD est le dernier diviseur non nul.
Exemple : $\text{PGCD}(252, 168)$.

✏️ Exemple — PGCD(252, 168)

⚠️

$1$ n'est pas un nombre premier (il n'a qu'un seul diviseur : lui-même). Le plus petit nombre premier est $2$ .

Ne pas confondre PGCD et PPCM (Plus Petit Commun Multiple). $\text{PPCM}(a,b) = \dfrac{a \times b}{\text{PGCD}(a,b)}$ .

L'algorithme d'Euclide date de 300 av. J.-C. et c'est l'un des plus anciens algorithmes de l'humanité ! Il est utilisé encore aujourd'hui dans la cryptographie pour sécuriser vos paiements en ligne.

🎯 Mini-quiz

1. PGCD(48, 36) = ?

2. La décomposition de 60 en facteurs premiers est :

3. Parmi ces nombres, lequel est premier ?