🎯 PGCD, PPCM et Décomposition en Facteurs Premiers

Dans cette leçon, nous allons explorer des outils puissants pour manipuler les nombres entiers : l’algorithme d’Euclide, le PGCD, le PPCM et la décomposition en facteurs premiers. Ces concepts sont fondamentaux en arithmétique. 🔢

📚 Définitions Fondamentales

PGCD (Plus Grand Commun Diviseur)

Le PGCD de deux entiers a et b (non tous deux nuls) est le plus grand entier qui divise à la fois a et b. On le note PGCD(a, b) ou simplement (a ∧ b).

Exemple : PGCD(12, 18) = 6 car les diviseurs communs sont 1, 2, 3, 6.

PPCM (Plus Petit Commun Multiple)

Le PPCM de deux entiers a et b est le plus petit entier strictement positif qui est multiple à la fois de a et de b. On le note PPCM(a, b) ou (a ∨ b).

Exemple : PPCM(4, 6) = 12 car les multiples communs sont 12, 24, 36…

🔍 Algorithme d’Euclide

L’algorithme d’Euclide est une méthode efficace pour calculer le PGCD de deux nombres. Il repose sur la propriété suivante :

\[ PGCD(a, b) = PGCD(b, r) \]

où r est le reste de la division euclidienne de a par b.

Étapes de l’Algorithme

1. On effectue la division euclidienne de a par b : a = b × q + r
2. Si r = 0, alors PGCD(a, b) = b
3. Sinon, on recommence avec PGCD(b, r)

📝 Exemple Détaillé

Calculons PGCD(252, 198) :

Étape 1 : 252 = 198 × 1 + 54

Étape 2 : 198 = 54 × 3 + 36

Étape 3 : 54 = 36 × 1 + 18

Étape 4 : 36 = 18 × 2 + 0

Le dernier reste non nul est 18, donc PGCD(252, 198) = 18. ✅

🎨 Représentation de l’Algorithme

Voici une représentation schématique de l’algorithme d’Euclide :

\begin{tikzpicture}[scale=0.7]
\node[draw, circle] (a) at (0,0) {a, b};
\node[draw, rectangle] (div) at (0,-2) {Division euclidienne};
\node[draw, diamond] (test) at (0,-4) {r = 0 ?};
\node[draw, circle] (result) at (3,-4) {PGCD = b};
\node[draw, circle] (recurse) at (-3,-4) {a=b, b=r};
\draw[->] (a) — (div);
\draw[->] (div) — (test);
\draw[->] (test) — node[above] {Oui} (result);
\draw[->] (test) — node[above] {Non} (recurse);
\draw[->] (recurse) — (-3,-2) — (0,-2);
\end{tikzpicture}

🔢 Décomposition en Facteurs Premiers

Tout entier n ≥ 2 peut s’écrire de manière unique comme un produit de nombres premiers :

\[ n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times … \times p_k^{\alpha_k} \]

où les pᵢ sont des nombres premiers distincts et les αᵢ sont des entiers naturels non nuls.

Exemple de Décomposition

Décomposons 360 en facteurs premiers :

360 ÷ 2 = 180

180 ÷ 2 = 90

90 ÷ 2 = 45

45 ÷ 3 = 15

15 ÷ 3 = 5

5 ÷ 5 = 1

Donc : 360 = 2³ × 3² × 5¹

🧮 Calcul du PGCD et PPCM par Décomposition

À partir de la décomposition en facteurs premiers, on peut calculer facilement le PGCD et le PPCM :

Soient a = 2³ × 3² × 5 et b = 2² × 3³ × 7

PGCD(a, b) = 2^min(3,2) × 3^min(2,3) = 2² × 3² = 36

PPCM(a, b) = 2^max(3,2) × 3^max(2,3) × 5 × 7 = 2³ × 3³ × 5 × 7 = 7560

📊 Relation entre PGCD et PPCM

Il existe une relation fondamentale entre le PGCD et le PPCM :

\[ PGCD(a, b) \times PPCM(a, b) = |a \times b| \]

Vérification : Avec a = 12 et b = 18 :

PGCD(12, 18) × PPCM(12, 18) = 6 × 36 = 216 = 12 × 18 ✅

💡 Application Pratique

Problème : Un jardinier veut paver une surface rectangulaire de 24 m sur 36 m avec des carreaux carrés identiques. Quel est le plus grand côté possible pour les carreaux ?

Solution : On cherche PGCD(24, 36) = 12. Les carreaux peuvent avoir 12 m de côté maximum.

🎓 Astuce Mnémotechnique

Pour retenir la relation PGCD-PPCM : « PGCD fois PPCM égale produit » 🧠

Ces outils sont extrêmement puissants et vous seront utiles dans de nombreux domaines des mathématiques !