Calculer le PGCD de Deux Nombres

Algorithme d'Euclide : PGCD(a,b) = PGCD(b, a mod b) jusqu'a b=0.

PGCD — definition, methodes de calcul et applications

Le PGCD (Plus Grand Commun Diviseur), aussi note gcd(a,b) en anglais, est le plus grand entier positif qui divise simultanement les deux entiers a et b sans reste. C'est un concept fondamental en arithmetique, etudie au college et indispensable pour simplifier les fractions, resoudre les equations diophantiennes et comprendre la cryptographie RSA.

Methode 1 — Algorithme d'Euclide (le plus efficace)

PGCD(a, b) = PGCD(b, a mod b) jusqu'a ce que b = 0
Resultat = a (quand b = 0)

Complexite : O(log(min(a,b))) — extremement rapide meme pour de tres grands nombres.

3 exemples detailles pas a pas

Exemple 1 — PGCD(48, 36) :

PGCD(48, 36) → reste = 48 mod 36 = 12
PGCD(36, 12) → reste = 36 mod 12 = 0
PGCD(12, 0) → resultat = 12

Verification : 48 = 12×4 ✓ et 36 = 12×3 ✓. Fraction 48/36 simplifiee : 4/3.

Exemple 2 — PGCD(252, 105) :

PGCD(252, 105) → 252 mod 105 = 42
PGCD(105, 42) → 105 mod 42 = 21
PGCD(42, 21) → 42 mod 21 = 0
PGCD = 21

Fraction 105/252 = 5/12. Application : partager 252 et 105 objets en groupes identiques → max 21 groupes.

Exemple 3 — PGCD(1071, 462) (grands nombres) :

PGCD(1071, 462) → 1071 mod 462 = 147
PGCD(462, 147) → 462 mod 147 = 21
PGCD(147, 21) → 147 mod 21 = 0
PGCD = 21

Methode 2 — Decomposition en facteurs premiers

Decomposer a et b, puis prendre les facteurs communs avec les plus petits exposants.

Exemple PGCD(360, 840) :

• 360 = 2³ × 3² × 5¹
• 840 = 2³ × 3¹ × 5¹ × 7¹
• Facteurs communs : 2^min(3,3) × 3^min(2,1) × 5^min(1,1) = 2³ × 3¹ × 5¹ = 8×3×5 = 120

Tableau comparatif PGCD, PPCM et relation fondamentale

Relation fondamentale : PGCD(a,b) × PPCM(a,b) = a × b

Identite de Bezout et applications avancees

L'identite de Bezout stipule : il existe des entiers u et v tels que a × u + b × v = PGCD(a, b). Cette propriete est la base de l'algorithme d'Euclide etendu, utilise notamment pour :

• Cryptographie RSA : Calculer l'inverse modulaire (cle de dechiffrement) via PGCD etendu
• Equations diophantiennes : ax + by = c a une solution entiere si et seulement si PGCD(a,b) | c
• Codes correcteurs d'erreurs : Calcul de l'inverse dans Z/nZ

Approfondissement — PGCD, algorithmes et applications

Algorithme d'Euclide étendu — calcul de l'inverse modulaire

L'algorithme d'Euclide étendu calcule simultanément PGCD(a,b) et les coefficients de Bézout u et v tels que a×u + b×v = PGCD(a,b). Méthode pour PGCD(35, 13) :

Remontée : 1 = 9 − 2×4 = 9 − 2×(13−9) = 3×9 − 2×13 = 3×(35−2×13) − 2×13 = 3×35 − 8×13. Donc 35×3 ≡ 1 (mod 13) → l'inverse de 35 modulo 13 est 3. Vérification : 35×3 = 105 = 8×13 + 1 ✓

PGCD et fractions irréductibles — simplification systématique

Une fraction p/q est irréductible si et seulement si PGCD(p,q) = 1. Pour simplifier 252/360 :

• PGCD(252, 360) : 360 = 1×252 + 108 → 252 = 2×108 + 36 → 108 = 3×36 + 0 → PGCD = 36
• 252/360 = (252÷36)/(360÷36) = 7/10
• Vérification : PGCD(7,10) = 1 ✓ (la fraction est irréductible)
• Application : 252 secondes sur 360 = 7/10 d'un tour = 70% du temps

PGCD en algorithmique — complexité et variantes

PGCD en musique — intervalles harmoniques

En acoustique musicale, deux notes de fréquences f₁ et f₂ sont en rapport simple (consonance) si leur rapport se réduit à une petite fraction. La quinte parfaite correspond à f₂/f₁ = 3/2. PGCD(3,2) = 1 : la fraction est déjà irréductible. La quarte = 4/3, la tierce majeure = 5/4. Le tempérament égal moderne (12 demi-tons) utilise la fréquence de base 2^(1/12) — un irrationnel. La raison pour laquelle certains intervalles sonnent "juste" et d'autres "faux" est directement liée au PGCD des numérateurs et dénominateurs de leurs rapports de fréquence.

PGCD et ordonnancement de tâches — application pratique en informatique

Le PGCD intervient directement dans les problèmes de synchronisation cyclique. Si une tâche A s'exécute toutes les a millisecondes et une tâche B toutes les b ms, elles se synchronisent toutes les PPCM(a,b) ms. Réduire la granularité du tick système au PGCD(a,b) minimise le nombre d'interruptions à gérer. En architecture CPU, les caches L1/L2/L3 ont des tailles qui sont des puissances de 2 précisément pour simplifier les calculs de PGCD et garantir que les alignements mémoire sont des diviseurs exacts des blocs de données. La règle d'or : PGCD(taille_donnée, taille_cache_ligne) doit être maximal — idéalement égal à la taille de la ligne de cache (64 octets) — pour éviter le faux partage (false sharing) entre cœurs.

Décomposition en facteurs premiers et PGCD — méthode alternative

La méthode des facteurs premiers donne une vision structurelle du PGCD. Pour PGCD(360, 252) :

• 360 = 2³ × 3² × 5¹
• 252 = 2² × 3² × 7¹
• PGCD = 2^min(3,2) × 3^min(2,2) × 5^min(1,0) × 7^min(0,1) = 2² × 3² = 4 × 9 = 36
• PPCM = 2^max(3,2) × 3^max(2,2) × 5^max(1,0) × 7^max(0,1) = 2³ × 3² × 5 × 7 = 8 × 9 × 5 × 7 = 2520
• Vérification : 36 × 2520 = 90 720 = 360 × 252 ✓

Cette méthode est plus intuitive pour comprendre la structure, mais l'algorithme d'Euclide reste plus rapide en pratique car la factorisation en nombres premiers est coûteuse pour les grands entiers.

4 erreurs classiques sur le PGCD

• Confondre PGCD et PPCM : Le PGCD est ≤ min(a,b) ; le PPCM est ≥ max(a,b). PGCD(12,8)=4, PPCM(12,8)=24 — pas l'inverse.
• PGCD de nombres premiers entre eux : Si PGCD(a,b)=1, les deux nombres n'ont aucun facteur commun. Ce n'est pas une erreur mais une propriete : 14 et 15 sont premiers entre eux.
• Appliquer la formule PGCD×PPCM=a×b a trois nombres : Cette relation ne se generalise pas directement. Pour 3 nombres, il faut calculer les PGCD deux a deux.
• Arret premature de l'algorithme d'Euclide : Continuer jusqu'a ce que le reste soit exactement 0, pas jusqu'au premier reste "petit". PGCD(35,14) : 35 mod 14 = 7, puis 14 mod 7 = 0 → PGCD = 7, pas 14.