Le PGCD et le PPCM (on rencontre souvent aussi « PGCD et PPCM ») sont deux notions d’arithmétique incontournables au collège et au lycée : elles servent à simplifier des fractions, trouver un dénominateur commun et résoudre des problèmes de périodicité (événements qui se répètent).
Dans cette page, tu vas apprendre à les calculer avec des méthodes fiables (factorisation, algorithme, tableau), puis t’entraîner avec des exercices corrigés.
Objectif : On te donne une méthode claire et rigoureuse, et on te montre surtout comment choisir la méthode la plus efficace selon les valeurs.
Pour revoir les bases sur les entiers : cours « Nombres entiers ». Et pour les négatifs : entiers relatifs.
Définitions et premières propriétés
Avant de calculer le PGCD et le PPCM, il est essentiel de comprendre précisément ce que ces notions représentent et comment elles s’articulent.
Qu’est-ce que le PGCD (Plus Grand Commun Diviseur) ?
Définition
Soient \(a\) et \(b\) deux entiers naturels non nuls. Le PGCD de \(a\) et \(b\), noté \(\text{PGCD}(a, b)\), est le plus grand entier qui divise à la fois \(a\) et \(b\).
Autrement dit, c’est le plus grand diviseur commun à \(a\) et \(b\).
Exemple : Calculons le PGCD de 12 et 18.
- Les diviseurs de 12 sont : 1, 2, 3, 4, 6, 12
- Les diviseurs de 18 sont : 1, 2, 3, 6, 9, 18
- Ceux en commun sont : 1, 2, 3, 6
- Le plus grand est 6
Donc \(\text{PGCD}(12, 18) = 6\).
Qu’est-ce que le PPCM (Plus Petit Commun Multiple) ?
Définition du PPCM
Soient \(a\) et \(b\) deux entiers strictement positifs. Le PPCM de \(a\) et \(b\), noté \(\text{PPCM}(a, b)\) ou parfois \([a, b]\), est le plus petit entier strictement positif qui est multiple à la fois de \(a\) et de \(b\).
Autrement dit, c’est le plus petit commun strictement positif de \(a\) et \(b\).
Exemple : Calculons-le pour 12 et 18.
- Les multiples de 12 sont : 12, 24, 36, 48, 60, 72…
- Ceux de 18 sont : 18, 36, 54, 72, 90…
- En commun : 36, 72, 108…
- Le plus petit est 36
Donc \(\text{PPCM}(12, 18) = 36\).
Relation fondamentale entre PGCD et PPCM
Théorème fondamental
Pour tous entiers strictement positifs \(a\) et \(b\) :
\(a \times b = \text{PGCD}(a, b) \times \text{PPCM}(a, b)\)
Cette formule signifie que le produit des deux valeurs égale celui de ces deux notions.
Vérification avec notre exemple :
- \(12 \times 18 = 216\)
- \(6 \times 36 = 216\)
La relation est bien vérifiée.
Piège. \(\mathrm{PPCM}(a,b)=a\times b\) uniquement si \(\mathrm{PGCD}(a,b)=1\) (on dit alors que \(a\) et \(b\) sont premiers entre eux).
Comment les calculer ? (choisir la bonne méthode)
Il existe plusieurs méthodes. Le bon réflexe : ne pas appliquer une seule méthode « par habitude », mais choisir celle qui est la plus efficace selon les valeurs.
| Situation | Méthode conseillée | Pourquoi |
|---|---|---|
| Petites valeurs (ex. \(12\) et \(18\)) | Listes | Rapide mentalement |
| Valeurs « factorisables » (ex. \(60\) et \(84\)) | Factorisation | Méthode robuste, sûre |
| À trouver vite (ex. \(625\) et \(360\)) | Algorithme d’Euclide | Très efficace sans factorisation |
| Tu veux le second une fois le premier trouvé | Formule | Un calcul direct |
| Plus de 2 valeurs (3 ou plus) | Factorisation / tableau | Lisible et systématique |
Règle simple.
- Tu dois réduire / simplifier / découper au plus grand → pense PGCD.
- Tu dois aligner / synchroniser / mettre au même dénominateur → pense PPCM.
Erreur classique
Oublier des éléments pour le PPCM
Certains élèves ne prennent que ceux en commun, comme pour le PGCD.
Rappel : Le PPCM prend tous ceux présents dans au moins un des deux entiers.
Exemple de l’erreur : Pour \(20 = 2^2 \times 5\) et \(12 = 2^2 \times 3\)
❌ Erreur : \(\text{PPCM}(20, 12) = 2^2 = 4\) (seulement les communs)
✓ Correct : \(\text{PPCM}(20, 12) = 2^2 \times 3 \times 5 = 60\) (tous)
Méthode 1 : Décomposition en facteurs premiers (méthode de référence)
La factorisation est la méthode de référence enseignée au collège et au lycée. Elle repose sur l’écriture unique de tout entier comme multiplication de valeurs premières.
Principe :
- Factoriser chaque entier
- Pour le PGCD : prendre ceux communs avec les exposants minimaux
- Pour le PPCM : prendre tous ceux présents (communs ou non) avec les exposants maximaux
Exemple détaillé : calculer pour 60 et 84
Étape 1 : Décompositions en facteurs
- \(60 = 2 \times 30 = 2 \times 2 \times 15 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5\)
- \(84 = 2 \times 42 = 2 \times 2 \times 21 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7\)
Étape 2 : Détermination du premier
Ceux en commun : \(2\) et \(3\)
- Pour \(2\) : exposants 2 et 2 → on prend le minimum = 2
- Pour \(3\) : exposants 1 et 1 → on prend le minimum = 1
- \(5\) n’est que dans 60 → on ne le prend pas
- \(7\) n’est que dans 84 → on ne le prend pas
Donc \(\text{PGCD}(60, 84) = 2^2 \times 3 = 4 \times 3 = 12\)
Étape 3 : Détermination du second
Tous ceux présents : \(2\), \(3\), \(5\), \(7\)
- Pour \(2\) : exposants 2 et 2 → on prend le maximum = 2
- Pour \(3\) : exposants 1 et 1 → on prend le maximum = 1
- Pour \(5\) : exposant 1 (uniquement dans 60) → on prend 1
- Pour \(7\) : exposant 1 (uniquement dans 84) → on prend 1
Donc \(\text{PPCM}(60, 84) = 2^2 \times 3 \times 5 \times 7 = 4 \times 3 \times 5 \times 7 = 420\)
Vérification : \(60 \times 84 = 5040\) et \(12 \times 420 = 5040\) ✓
Méthode 2 : Tableau de divisions successives (méthode simultanée)
Cette méthode permet de trouver les deux en même temps à l’aide d’un tableau de divisions successives. Elle est particulièrement efficace quand on cherche les deux résultats simultanément.
Principe :
- Tracer un tableau avec une colonne « Diviseurs » et une colonne pour chaque entier
- Diviser simultanément par des valeurs en ordre croissant (2, 3, 5, 7…)
- Si un entier n’est pas divisible, mettre un trait (-) et le recopier
- Continuer jusqu’à obtenir 1 dans toutes les colonnes
- Premier = multiplication des diviseurs des lignes sans trait (lignes pleines)
- Second = multiplication de tous les diviseurs de la colonne
Exemple : calculer pour 40 et 48
| Diviseurs | 40 | 48 |
|---|---|---|
| 2 | 20 | 24 |
| 2 | 10 | 12 |
| 2 | 5 | 6 |
| 2 | – | 3 |
| 3 | – | 1 |
| 5 | 1 | – |
Résultat premier :
On multiplie ceux des lignes pleines (sans trait) = lignes accentuées
\(\text{PGCD}(40, 48) = 2 \times 2 \times 2 = 8\)Résultat second :
On multiplie tous ceux de la colonne
\(\text{PPCM}(40, 48) = 2 \times 2 \times 2 \times 2 \times 3 \times 5 = 240\)Vérification : \(40 \times 48 = 1920\) et \(8 \times 240 = 1920\) ✓
Consultez si besoin notre page sur les critères de divisibilité
Méthode 3 : Algorithme d’Euclide (puis calcul du second)
L’Algorithme d’Euclide est très efficace pour trouver le premier de deux entiers, surtout quand ils sont grands. Il repose sur la division euclidienne et des divisions successives.
Principe :
- Effectuer la division du plus grand par le plus petit
- Remplacer le plus grand par le reste obtenu
- Recommencer jusqu’à obtenir un reste nul
- Le premier est le dernier reste non nul
- Une fois trouvé, obtenir le second avec la formule : \(\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}\)
Exemple : calculer pour 60 et 168 avec l’algorithme
Étape 1 : Divisions successives
- \(168 = 60 \times 2 + 48\)
- \(60 = 48 \times 1 + 12\)
- \(48 = 12 \times 4 + 0\)
Le reste est nul, donc on s’arrête. Le dernier non nul est 12.
Donc \(\text{PGCD}(60, 168) = 12\)
Étape 2 : Second avec la formule
\(\text{PPCM}(60, 168) = \frac{60 \times 168}{12} = \frac{10080}{12} = 840\)Vérification : \(60 \times 168 = 10080\) et \(12 \times 840 = 10080\) ✓
Méthode rapide pour les grandes valeurs !
Cette méthode est particulièrement efficace pour trouver le premier sans avoir à factoriser. C’est celle privilégiée en classes préparatoires et dans les calculs informatiques.
(Option prépa) Identité de Bézout en bonus
Option prépa : identité de Bézout (à connaître)
Si \(a\) et \(b\) sont deux entiers strictement positifs et si \(d=\mathrm{PGCD}(a,b)\), alors il existe des entiers relatifs \(u\) et \(v\) tels que :
\(au+bv=d\)
Exemple (avec l’exercice ci-dessus). On a \(\mathrm{PGCD}(60,168)=12\). En remontant les divisions ligne par ligne :
\(12=60-48\) et \(48=168-60\times 2\), donc
\(12=60\times 3-168\times 1\)
Une relation de Bézout est donc \(60\times 3+168\times (-1)=12\).
Applications (fractions & périodicité)
Ces deux notions ne sont pas seulement des définitions : ce sont des outils très pratiques pour travailler avec les fractions et résoudre des problèmes de synchronisation.
PGCD : simplifier une fraction
Principe. Si \(\text{PGCD}(a,b)=d\), alors :
\(\frac{a}{b}=\frac{a\div d}{b\div d}\)Exemple. Simplifier \(\frac{84}{60}\).
\(\text{PGCD}(84,60)=12\), donc :
\(\frac{84}{60}=\frac{84\div 12}{60\div 12}=\frac{7}{5}\)PPCM : mettre au même dénominateur
Principe. Pour additionner \(\frac{a}{b}+\frac{c}{d}\), on prend le dénominateur commun le plus simple :
\(m=\text{PPCM}(b,d)\)Exemple. Calculer \(\frac{3}{14}+\frac{3}{35}\).
\(\text{PPCM}(14,35)=70\). Donc :
\(\frac{3}{14}=\frac{15}{70}\quad \text{et}\quad \frac{3}{35}=\frac{6}{70}\) \(\frac{3}{14}+\frac{3}{35}=\frac{15}{70}+\frac{6}{70}=\frac{21}{70}\)On simplifie avec le premier : \(\text{PGCD}(21,70)=7\), donc \(\frac{21}{70}=\frac{3}{10}\).
Astuce. Évite de prendre \(14\times 35\) : c’est un dénominateur commun, mais pas le plus simple. Le second te donne des opérations plus propres.
PPCM : synchroniser deux cycles
Quand deux événements se répètent toutes les \(12\) minutes et toutes les \(18\) minutes, ils se recroisent toutes les \(\text{PPCM}(12,18)\) minutes.
Exemple. Deux bus passent toutes les 12 min et 18 min, ensemble à 8h00. Quand se retrouvent-ils ?
\(\text{PPCM}(12,18)=36\). Ils se retrouvent donc 36 minutes après : à 8h36.
Vers le cocon « Fractions ». Ces deux réflexes (simplifier avec le premier, trouver un dénominateur commun avec le second) sont au cœur du chapitre fractions. Cours complet à venir : Fractions : cours et exercices.
Exercices corrigés
Testez vos connaissances avec ces exercices progressifs du collège au lycée. Chaque exercice est accompagné de sa correction détaillée.
Exercices niveau collège (3ème) — Calculs directs
Exercice 1 : Calculer pour 24 et 36
Voir la correction
Méthode : factorisation
Étape 1 : Factorisation
- \(24 = 2 \times 12 = 2 \times 2 \times 6 = 2 \times 2 \times 2 \times 3 = 2^3 \times 3\)
- \(36 = 2 \times 18 = 2 \times 2 \times 9 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2\)
Étape 2 : Premier (communs, exposants minimaux)
Ceux en commun : \(2\) et \(3\)
- Pour \(2\) : min(3, 2) = 2
- Pour \(3\) : min(1, 2) = 1
Étape 3 : Second (tous, exposants maximaux)
Ceux présents : \(2\) et \(3\)
- Pour \(2\) : max(3, 2) = 3
- Pour \(3\) : max(1, 2) = 2
Vérification : \(24 \times 36 = 864\) et \(12 \times 72 = 864\) ✓
Exercice 2 : Calculer pour 48 et 180
Voir la correction
Méthode : factorisation
Étape 1 : Factorisation
- \(48 = 2^4 \times 3\)
- \(180 = 2^2 \times 3^2 \times 5\)
Étape 2 : Premier (communs, exposants minimaux)
Ceux en commun : \(2\) et \(3\)
- Pour \(2\) : min(4, 2) = 2
- Pour \(3\) : min(1, 2) = 1
Étape 3 : Second (tous, exposants maximaux)
Ceux présents : \(2\), \(3\), \(5\)
- Pour \(2\) : max(4, 2) = 4
- Pour \(3\) : max(1, 2) = 2
- Pour \(5\) : max(0, 1) = 1
Vérification : \(48 \times 180 = 8640\) et \(12 \times 720 = 8640\) ✓
Exercice 3 : Simplifier la fraction \(\frac{126}{84}\)
Voir la correction
Méthode : trouver le premier puis diviser
Étape 1 : Factorisation
- \(126 = 2 \times 3^2 \times 7\)
- \(84 = 2^2 \times 3 \times 7\)
Étape 2 : Premier
Ceux en commun : \(2\), \(3\), \(7\)
- Pour \(2\) : min(1, 2) = 1
- Pour \(3\) : min(2, 1) = 1
- Pour \(7\) : min(1, 1) = 1
Étape 3 : Simplification
\(\frac{126}{84} = \frac{126 \div 42}{84 \div 42} = \frac{3}{2}\)Réponse : La fraction simplifiée est \(\frac{3}{2}\)
Exercice 4 : Calculer \(\frac{5}{12} + \frac{7}{18}\)
Voir la correction
Méthode : utiliser le second comme dénominateur commun
Étape 1 : Trouver le second pour (12, 18)
- \(12 = 2^2 \times 3\)
- \(18 = 2 \times 3^2\)
- \(\text{PPCM}(12, 18) = 2^2 \times 3^2 = 4 \times 9 = 36\)
Étape 2 : Mettre au même dénominateur
- \(\frac{5}{12} = \frac{5 \times 3}{12 \times 3} = \frac{15}{36}\)
- \(\frac{7}{18} = \frac{7 \times 2}{18 \times 2} = \frac{14}{36}\)
Étape 3 : Additionner
\(\frac{5}{12} + \frac{7}{18} = \frac{15}{36} + \frac{14}{36} = \frac{29}{36}\)Étape 4 : Vérifier si on peut simplifier
29 est un nombre premier et ne divise pas 36, donc la fraction est déjà irréductible.
Réponse : \(\frac{5}{12} + \frac{7}{18} = \frac{29}{36}\)
Exercices niveau lycée — Applications et problèmes
Exercice 5 : Problème de pavage
Énoncé : On veut paver une salle rectangulaire de 450 cm sur 300 cm avec des carreaux carrés identiques, le plus grands possible, sans découpe. Quelle doit être la dimension des carreaux ?
Voir la correction
Méthode : le côté du carreau doit diviser les deux dimensions
Pour que les carreaux s’ajustent parfaitement sans découpe, leur côté doit être commun aux deux. Pour qu’ils soient les plus grands possible, on cherche le premier.
Étape 1 : Trouver pour (450, 300)
- \(450 = 2 \times 3^2 \times 5^2\)
- \(300 = 2^2 \times 3 \times 5^2\)
Ceux en commun : \(2\), \(3\), \(5\)
- Pour \(2\) : min(1, 2) = 1
- Pour \(3\) : min(2, 1) = 1
- Pour \(5\) : min(2, 2) = 2
Vérification :
- Longueur : \(450 \div 150 = 3\) carreaux
- Largeur : \(300 \div 150 = 2\) carreaux
Réponse : Les carreaux doivent mesurer 150 cm de côté.
Exercice 6 : Synchronisation de feux tricolores
Énoncé : À un carrefour, deux feux tricolores passent au vert toutes les 48 secondes pour le premier et toutes les 72 secondes pour le second. S’ils sont simultanément au vert à 14h00, à quelle heure repasseront-ils ensemble au vert pour la première fois ?
Voir la correction
Méthode : trouver le second des périodes
Étape 1 : Calcul
- \(48 = 2^4 \times 3\)
- \(72 = 2^3 \times 3^2\)
Tous avec exposants maximaux :
- Pour \(2\) : max(4, 3) = 4
- Pour \(3\) : max(1, 2) = 2
Étape 2 : Convertir en minutes
\(144\) secondes \(= 144 \div 60 = 2\) minutes et \(24\) secondes
Réponse : Les deux feux repasseront ensemble au vert à 14h02min24s.
Exercice 7 : Démonstration
Énoncé : Démontrer que si \(\text{PGCD}(a, b) = 1\), alors \(\text{PPCM}(a, b) = a \times b\)
Voir la correction
Méthode : utiliser la relation fondamentale
On sait que pour tous entiers strictement positifs \(a\) et \(b\) :
\(a \times b = \text{PGCD}(a, b) \times \text{PPCM}(a, b)\)
Hypothèse : \(\text{PGCD}(a, b) = 1\)
En remplaçant dans la formule :
\(a \times b = 1 \times \text{PPCM}(a, b)\)Donc :
\(\text{PPCM}(a, b) = a \times b\)
Conclusion : Lorsque deux entiers sont premiers entre eux (le premier = 1), leur second est égal à leur multiplication.
Exemple numérique : \(\text{PGCD}(7, 11) = 1\) car 7 et 11 sont premiers, donc \(\text{PPCM}(7, 11) = 7 \times 11 = 77\)
Exercice avancé : retrouver deux nombres connaissant leurs valeurs
Voici un exercice original qui inverse le problème habituel : au lieu de calculer ces deux notions, on vous les donne et vous devez retrouver les valeurs de départ. Cette technique peu connue est très utile !
Méthode générale :
- Calculer : \(\frac{\text{PPCM}}{\text{PGCD}}\) = multiplication de deux valeurs premières entre elles
- Décomposer ce quotient comme multiplication de deux éléments premiers entre eux
- Multiplier chaque élément par le premier pour obtenir les deux entiers
Exercice 8 : Premier = 14 et Second = 84. Trouver les deux nombres.
Voir la correction
Étape 1 : Calculer le quotient
\(\frac{84}{14} = 6\)Étape 2 : Décomposer 6 comme multiplication de deux valeurs premières entre elles
\(6 = 2 \times 3\)On vérifie : \(\text{PGCD}(2, 3) = 1\) ✓ (2 et 3 sont bien premiers entre eux)
Étape 3 : Multiplier par 14
- Premier nombre : \(2 \times 14 = 28\)
- Deuxième nombre : \(3 \times 14 = 42\)
Vérification :
- \(28 = 2^2 \times 7\) et \(42 = 2 \times 3 \times 7\)
- \(\text{PGCD}(28, 42) = 2 \times 7 = 14\) ✓
- \(\text{PPCM}(28, 42) = 2^2 \times 3 \times 7 = 84\) ✓
Réponse : Les deux entiers sont 28 et 42.
Exercice 9 : Premier = 8 et Second = 144. Trouver les deux nombres.
Voir la correction
Étape 1 : Calculer le quotient
\(\frac{144}{8} = 18\)Étape 2 : Décomposer 18 comme multiplication de deux valeurs premières entre elles
\(18 = 2 \times 9\)On vérifie : \(\text{PGCD}(2, 9) = 1\) ✓ (2 et 9 sont bien premiers entre eux)
Remarque : \(18 = 3 \times 6\) ne convient pas car \(\text{PGCD}(3, 6) = 3 \neq 1\)
Étape 3 : Multiplier par 8
- Premier nombre : \(2 \times 8 = 16\)
- Deuxième nombre : \(9 \times 8 = 72\)
Vérification :
- \(16 = 2^4\) et \(72 = 2^3 \times 3^2\)
- \(\text{PGCD}(16, 72) = 2^3 = 8\) ✓
- \(\text{PPCM}(16, 72) = 2^4 \times 3^2 = 144\) ✓
Réponse : Les deux entiers sont 16 et 72.
📥 Envie d’aller plus loin ? Retrouvez 20 exercices interactifs corrigés supplémentaires dans notre page d’exercices sur les nombres entiers.
FAQ : Questions fréquentes
Comment les trouver ?
Il existe trois méthodes principales :
- Factorisation (méthode de référence) :
- Factoriser chaque entier
- Premier : ceux en commun avec exposants minimaux
- Second : tous ceux présents avec exposants maximaux
- Tableau de divisions : permet de les trouver simultanément en divisant successivement
- Algorithme (pour le premier) : divisions successives jusqu’à reste nul, puis second avec la formule \(\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}\)
Consultez la section « Comment les calculer ? Les 3 méthodes » pour des explications détaillées.
Quelle est la différence ?
La différence fondamentale est :
- PGCD (Plus Grand Commun Diviseur) : le plus grand qui divise à la fois les deux entiers. On l’utilise pour simplifier une fraction.
- PPCM (Plus Petit Commun Multiple) : le plus petit qui en est un des deux. On l’utilise pour mettre des fractions au même dénominateur.
Pour la factorisation :
- Premier : ceux communs uniquement, exposants minimaux
- Second : tous présents, exposants maximaux
Consultez le tableau comparatif en début de page pour une synthèse visuelle complète.
Quel est le PPCM de 24 et 16 ?
Calculons \(\text{PPCM}(24, 16)\) :
Factorisation :
- \(24 = 2^3 \times 3\)
- \(16 = 2^4\)
Second (tous, exposants maximaux) :
- Pour \(2\) : max(3, 4) = 4
- Pour \(3\) : max(1, 0) = 1
\(\text{PPCM}(24, 16) = 2^4 \times 3 = 16 \times 3 = 48\)
Réponse : 48
Quel est le PGCD de 24 et de 36 ?
Calculons \(\text{PGCD}(24, 36)\) :
Factorisation :
- \(24 = 2^3 \times 3\)
- \(36 = 2^2 \times 3^2\)
Premier (communs, exposants minimaux) :
- Pour \(2\) : min(3, 2) = 2
- Pour \(3\) : min(1, 2) = 1
\(\text{PGCD}(24, 36) = 2^2 \times 3 = 4 \times 3 = 12\)
Réponse : 12
Quel est le PPCM de 18 et 24 ?
Calculons \(\text{PPCM}(18, 24)\) :
Factorisation :
- \(18 = 2 \times 3^2\)
- \(24 = 2^3 \times 3\)
Second (tous, exposants maximaux) :
- Pour \(2\) : max(1, 3) = 3
- Pour \(3\) : max(2, 1) = 2
\(\text{PPCM}(18, 24) = 2^3 \times 3^2 = 8 \times 9 = 72\)
Réponse : 72
À quoi servent-ils en pratique ?
Ils ont de nombreuses applications pratiques :
PGCD :
- Simplifier des fractions (diviser numérateur et dénominateur)
- Problèmes de partage équitable ou de découpage optimal
- Problèmes de pavage (taille maximale des carreaux)
PPCM :
- Additionner ou soustraire des fractions (dénominateur commun minimal)
- Problèmes de synchronisation (rendez-vous périodiques, feux tricolores, bus…)
- Problèmes d’alignement ou de répétition cyclique
Consultez la section « Applications concrètes » pour des exemples détaillés.
Quelle est la relation entre eux ?
Ils sont liés par une formule fondamentale :
\(a \times b = \text{PGCD}(a, b) \times \text{PPCM}(a, b)\)
Cette formule permet de trouver rapidement le second si on connaît le premier :
\(\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}\)
Ou inversement de trouver le premier si on connaît le second :
\(\text{PGCD}(a, b) = \frac{a \times b}{\text{PPCM}(a, b)}\)
Que faire si deux nombres sont premiers entre eux ?
Deux entiers \(a\) et \(b\) sont premiers entre eux si \(\text{PGCD}(a, b) = 1\).
Dans ce cas particulier :
- Le premier est 1
- Le second est égal à leur multiplication : \(\text{PPCM}(a, b) = a \times b\)
Exemples :
- \(\text{PGCD}(7, 11) = 1\) donc \(\text{PPCM}(7, 11) = 77\)
- \(\text{PGCD}(15, 28) = 1\) donc \(\text{PPCM}(15, 28) = 420\)
Cette propriété est très utile pour simplifier les opérations.
Comment calculer rapidement pour de grands nombres ?
Pour les grandes valeurs, l’algorithme est le plus rapide. Il ne nécessite pas de factorisation.
Principe :
- Effectuer la division du plus grand par le plus petit
- Remplacer le plus grand par le reste obtenu
- Recommencer jusqu’à obtenir un reste nul
- Le premier est le dernier reste non nul
Exemple : \(\text{PGCD}(1071, 462)\)
- \(1071 = 462 \times 2 + 147\)
- \(462 = 147 \times 3 + 21\)
- \(147 = 21 \times 7 + 0\)
Donc \(\text{PGCD}(1071, 462) = 21\)
Cette méthode est utilisée en cryptographie et en programmation pour sa rapidité.
Peut-on calculer pour plus de deux nombres ?
Oui, absolument ! On peut les trouver pour 3, 4, ou plus de valeurs.
Méthode par itération :
- \(\text{PGCD}(a, b, c) = \text{PGCD}(\text{PGCD}(a, b), c)\)
- \(\text{PPCM}(a, b, c) = \text{PPCM}(\text{PPCM}(a, b), c)\)
Exemple avec 3 valeurs : Calculons \(\text{PGCD}(12, 18, 24)\)
- \(\text{PGCD}(12, 18) = 6\)
- \(\text{PGCD}(6, 24) = 6\)
Donc \(\text{PGCD}(12, 18, 24) = 6\)
Avec la factorisation :
- \(12 = 2^2 \times 3\)
- \(18 = 2 \times 3^2\)
- \(24 = 2^3 \times 3\)
- Premier : communs aux trois, exposants minimaux → \(2^1 \times 3^1 = 6\)
- Second : tous présents, exposants maximaux → \(2^3 \times 3^2 = 72\)
Pour approfondir l’arithmétique en mathématiques :
