Qu'est-ce que le PGCD ?
Le PGCD (Plus Grand Commun Diviseur) de deux entiers a et b est le plus grand entier qui divise a la fois a et b. Notation : PGCD(a, b). Exemples : PGCD(12, 18) = 6 car 6 divise 12 (12/6 = 2) et 18 (18/6 = 3), et aucun entier plus grand ne divise les deux. Le PGCD intervient dans la simplification des fractions, la resolution de problemes de partage et la cryptographie (algorithme RSA).
Methode 1 — Decomposition en facteurs premiers :
PGCD(a, b) = produit des facteurs premiers communs avec le plus petit exposant
Methode 2 — Algorithme d'Euclide :
PGCD(a, b) = PGCD(b, r) ou r = reste de la division de a par b
On repete jusqu'a r = 0 ; le dernier diviseur non nul est le PGCD
Proprietes :
PGCD(a, 0) = a | PGCD(a, a) = a | PGCD(a, 1) = 1
Tableau de reference : PGCD de paires courantes
| a | b | PGCD(a, b) | Fraction simplifiee |
|---|---|---|---|
| 12 | 18 | 6 | 12/18 → 2/3 |
| 24 | 36 | 12 | 24/36 → 2/3 |
| 15 | 25 | 5 | 15/25 → 3/5 |
| 48 | 64 | 16 | 48/64 → 3/4 |
| 100 | 75 | 25 | 100/75 → 4/3 |
| 7 | 13 | 1 | premiers entre eux |
Algorithme d'Euclide : methode pas a pas
L'algorithme d'Euclide est la methode la plus efficace pour les grands nombres. On effectue des divisions euclidiennes successives : a = b × q + r, puis on remplace a par b et b par r, jusqu'a obtenir un reste nul.
Exemple 1 — PGCD(252, 105) :
252 = 105 × 2 + 42
105 = 42 × 2 + 21
42 = 21 × 2 + 0 → PGCD = 21
Verification : 252/21 = 12 ; 105/21 = 5. Fraction 252/105 se simplifie en 12/5.
Exemple 2 — PGCD(1071, 462) :
1071 = 462 × 2 + 147
462 = 147 × 3 + 21
147 = 21 × 7 + 0 → PGCD = 21
Exemple 3 — PGCD(84, 36) par decomposition en facteurs premiers :
84 = 2² × 3 × 7 | 36 = 2² × 3²
Facteurs communs : 2² × 3 = 4 × 3 = PGCD = 12
PGCD et PPCM : le lien fondamental
Le PPCM (Plus Petit Commun Multiple) est lie au PGCD par la relation : PGCD(a, b) × PPCM(a, b) = a × b. Exemple : PGCD(12, 18) = 6 et PPCM(12, 18) = 36. Verification : 6 × 36 = 216 = 12 × 18. Cette relation permet de calculer le PPCM a partir du PGCD, ou inversement. Le PPCM est indispensable pour additionner des fractions de denominateurs differents.
Erreur 1 — Confondre PGCD et PPCM : Le PGCD est toujours inferieur ou egal au plus petit des deux nombres. Le PPCM est toujours superieur ou egal au plus grand. PGCD(4, 6) = 2 (petit) ; PPCM(4, 6) = 12 (grand). Pour simplifier une fraction, on utilise le PGCD ; pour trouver un denominateur commun, on utilise le PPCM.
Erreur 2 — Oublier de verifier que la fraction est completement simplifiee : Diviser numerateur et denominateur par n'importe quel diviseur commun ne suffit pas si ce n'est pas le PGCD. 18/24 divise par 2 donne 9/12, pas encore simplifiee. Il faut diviser par le PGCD (6) pour obtenir 3/4 (forme irreductible).
Erreur 3 — Appliquer l'algorithme d'Euclide dans le mauvais sens : On doit toujours diviser le plus grand par le plus petit. PGCD(18, 30) commence par 30 = 18 × 1 + 12, pas par 18 = 30 × 0 + 18 (ce qui est correct mais rallonge inutilement le calcul). Toujours commencer avec a ≥ b.
Applications concretes du PGCD
Le PGCD resout des problemes concrets de partage optimal. Exemple classique : on dispose de 48 chocolats et 36 bonbons a repartir en lots identiques sans reste. Le nombre maximum de lots est PGCD(48, 36) = 12. Chaque lot contiendra 4 chocolats (48/12) et 3 bonbons (36/12). En menuiserie, si l'on veut paver un rectangle de 252 cm × 105 cm avec des carres identiques sans coupe, le cote maximum du carre est PGCD(252, 105) = 21 cm.
FAQ — PGCD
Comment calculer le PGCD de trois nombres ou plus ?
On calcule iterativement. PGCD(a, b, c) = PGCD(PGCD(a, b), c). Exemple : PGCD(12, 18, 30). D'abord PGCD(12, 18) = 6, puis PGCD(6, 30) = 6. Donc PGCD(12, 18, 30) = 6. L'algorithme d'Euclide s'applique a chaque etape de la meme facon qu'avec deux nombres.
Que signifie "nombres premiers entre eux" ?
Deux nombres sont premiers entre eux (ou coprimes) si leur PGCD est 1. Cela ne signifie pas que les nombres sont premiers ! Par exemple, PGCD(8, 9) = 1 : 8 et 9 sont premiers entre eux, mais ni 8 ni 9 n'est premier. En cryptographie RSA, on choisit des nombres premiers entre eux pour construire les cles de chiffrement.
Comment simplifier une fraction avec le PGCD ?
Calculer le PGCD du numerateur et du denominateur, puis diviser les deux par ce PGCD. Exemple : simplifier 84/126. PGCD(84, 126) : 126 = 84 × 1 + 42 ; 84 = 42 × 2 + 0. PGCD = 42. Donc 84/126 = (84÷42)/(126÷42) = 2/3. La fraction 2/3 est irreductible car PGCD(2, 3) = 1.
L'algorithme d'Euclide fonctionne-t-il avec les decimaux ?
L'algorithme d'Euclide classique s'applique aux entiers. Pour des nombres decimaux, on les convertit d'abord en fractions, puis on calcule le PGCD des numerateurs et le PPCM des denominateurs. Alternativement, on peut multiplier tous les nombres par une puissance de 10 pour les rendre entiers, calculer le PGCD, puis diviser.
Quelle est la complexite algorithmique de l'algorithme d'Euclide ?
L'algorithme d'Euclide a une complexite O(log(min(a, b))). Il est tres rapide meme pour de tres grands nombres. Le theoreme de Lame prouve que le nombre d'etapes ne depasse jamais 5 fois le nombre de chiffres du plus petit des deux entiers. Pour des nombres a 10 chiffres, au plus 50 divisions suffisent. C'est pourquoi cet algorithme, connu depuis l'Antiquite, reste utilise en cryptographie moderne.
Quel est le PGCD de deux nombres consecutifs ?
Le PGCD de deux entiers consecutifs est toujours 1. En effet, si d divise a et divise a+1, alors d divise leur difference (a+1) - a = 1. Donc d = 1. Cela signifie que deux entiers consecutifs sont toujours premiers entre eux : PGCD(7, 8) = 1, PGCD(99, 100) = 1, PGCD(1000, 1001) = 1.
Comment le PGCD intervient-il dans le theoreme de Bezout ?
Le theoreme de Bezout affirme qu'il existe des entiers relatifs u et v tels que a × u + b × v = PGCD(a, b). Ces entiers s'appellent les coefficients de Bezout. Exemple : PGCD(12, 8) = 4 et on peut verifier que 12 × (-1) + 8 × 2 = -12 + 16 = 4. L'algorithme d'Euclide etendu calcule ces coefficients, utiles en cryptographie et en resolution d'equations diophantiennes.
Comment calculer le PGCD par decomposition en facteurs premiers ?
Decomposer chaque nombre en produit de facteurs premiers, puis garder chaque facteur premier avec le plus petit exposant commun. Exemple : PGCD(120, 180). 120 = 2³ × 3 × 5 ; 180 = 2² × 3² × 5. Facteurs communs : 2² (min de 3 et 2) × 3¹ (min de 1 et 2) × 5¹ (min de 1 et 1) = 4 × 3 × 5 = 60. Verification : 120/60 = 2 ; 180/60 = 3.
