Objectifs

\n
• Comprendre le concept de divisibilité et le rôle du PGCD dans l'arithmétique exacte.
\n
• Savoir appliquer l'algorithme d'Euclide pour calculer le PGCD de deux entiers.
\n
• Savoir utiliser le PGCD pour simplifier des fractions et résoudre des problèmes simples.
\n

Rappel : divisibilité et PGCD

Définitions rapides :

\n
• On dit que a est divisible par b ssi il existe un entier q tel que a = b q.
\n
• On appelle PGCD (plus grand commun diviseur) de deux entiers a et b le plus grand entier qui divise à la fois a et b.
\n

Algorithme d'Euclide pour le PGCD

Principe : on remplace le problème (a, b) par (b, a mod b) jusqu'à ce que le reste soit 0. Le dernier reste non nul est le PGCD.

Formulation pratique :

\n
1. Tant que b ≠ 0, on calcule le reste r = a mod b, puis on pose a := b et b := r.
\n
2. Le PGCD est alors a (à la fin de la boucle).
\n

Remarques :

\n
• L'opération mod correspond au reste de la division euclidienne.
\n
• Le PGCD est unique et positif.
\n

Exemple chiffré :

L’algorithme d’Euclide étendu (aperçu)

Objectif : trouver des entiers x et y tels que ax + by = gcd(a,b). Utile pour résoudre des équations diophantiennes simples et trouver des coefficients de simplification de fractions.

Idée générale (pas nécessaire de tout coder à la main) :

\n
• On suit le même déroulement que l’Euclid, tout en conservant les combinaisons linéaires : à chaque étape, on exprime le reste r comme a combination de a et b, et on met à jour les coefficients.
\n

Exemple rapide : gcd(198, 156) = 6 peut s’écrire sous forme 198x + 156y = 6; les coefficients peuvent être trouvés via l’algorithme étendu, sans se soucier du detail ici.

Applications et usages

\n
• Simplification de fractions: gcd sert à réduire une fraction à sa forme irréductible.
\n
• Trouver un multiple commun et vérifier des propriétés de divisibilité dans des suites numériques.
\n
• Résoudre des problèmes de partition, de synchronisation, etc., en utilisant le PGCD comme outil de comparaison des grandeurs.
\n

Exercices (avec corrigé rapide)

\n
1. Calculer PGCD(270, 192) en utilisant l’algorithme d’Euclide et donner le PGCD.
\n
2. Simplifier la fraction 84/144 en utilisant le PGCD.
\n
3. Vérifier que 15 et 28 sont premiers entre eux en calculant leur PGCD.
\n

Corrigés :

\n
1. 270 = 192 × 1 + 78; 192 = 78 × 2 + 36; 78 = 36 × 2 + 6; 36 = 6 × 6 + 0 → PGCD = 6.
\n
2. 84/144 : gcd = 12 → fraction réduite = 7/12.
\n
3. PGCD(15, 28) : 28 = 15 × 1 + 13; 15 = 13 × 1 + 2; 13 = 2 × 6 + 1; 2 = 1 × 2 + 0 → PGCD = 1, donc premiers entre eux.
\n

Récapitulatif

\n
• Le PGCD est le plus grand commun diviseur de deux entiers.
\n
• L’algorithme d’Euclide calcule le PGCD par divisions successives (a mod b).
\n
• L’algorithme étendu permet aussi d’exprimer le PGCD comme combinaison linéaire des deux nombres et sert à trouver des coefficients pour simplifier des fractions et résoudre des équations.
\n