Dernière mise à jour : 2026-05-13

Deux relations fondamentales entre entiers

Toute paire d'entiers positifs possède deux nombres privilégiés : le plus grand entier qui divise les deux exactement (le plus grand commun diviseur, PGCD) et le plus petit entier qui est multiple des deux (le plus petit commun multiple, PPCM). Ensemble, ils caractérisent la relation arithmétique entre ces deux nombres.

Prenons l'exemple de 12 et 8 :

• Les diviseurs communs de 12 et 8 sont 1, 2 et 4. Le plus grand est 4.
• Les multiples communs de 12 et 8 sont 24, 48, 72, … Le plus petit est 24.

Calcul du PGCD par l'algorithme d'Euclide

La méthode la plus ancienne — et toujours la plus rapide en pratique — pour trouver le PGCD est l'algorithme d'Euclide, décrit dans ses Éléments vers 300 av. J.-C. La propriété fondamentale est :

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

où $a \bmod b$ est le reste de la division euclidienne de $a$ par $b$. On itère jusqu'à obtenir un reste nul ; le dernier reste non nul est le PGCD.

Exemple : PGCD(48, 18)

Étape	$a$	$b$	$a \bmod b$
1	48	18	12
2	18	12	6
3	12	6	0

Le dernier reste non nul est 6, donc PGCD(48, 18) = 6.

Cet algorithme est remarquablement efficace : le nombre d'étapes ne dépasse jamais cinq fois le nombre de chiffres du plus petit des deux entiers.

L'identité PGCD–PPCM

Une fois le PGCD connu, le PPCM s'en déduit par une formule unique :

$\text{PPCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$

Ce n'est pas un hasard : c'est un théorème qui découle de la décomposition unique en facteurs premiers. En représentant chaque entier comme produit de puissances de nombres premiers, le PGCD prend l'exposant minimum de chaque premier et le PPCM l'exposant maximum. Leur produit reconstruit toujours $a \times b$.

Exemple : PPCM(12, 8)

$\gcd(12, 8) = 4, \quad \text{PPCM}(12, 8) = \frac{12 \times 8}{4} = 24$

Vérification : $4 \times 24 = 96 = 12 \times 8$. ✓

Applications courantes

Réduire une fraction

Pour simplifier $\dfrac{a}{b}$ à sa forme irréductible, on divise numérateur et dénominateur par $\gcd(a, b)$. Ainsi, $\dfrac{12}{8}$ devient $\dfrac{3}{2}$ car $\gcd(12, 8) = 4$.

Additionner des fractions

Pour calculer $\dfrac{1}{12} + \dfrac{1}{8}$, il faut le dénominateur commun le plus petit — c'est $\text{PPCM}(12, 8) = 24$ :

$\frac{1}{12} + \frac{1}{8} = \frac{2}{24} + \frac{3}{24} = \frac{5}{24}$

Cycles et périodes

Si deux événements se répètent tous les $a$ jours et tous les $b$ jours, ils coïncident à nouveau dans $\text{PPCM}(a, b)$ jours. C'est pourquoi le PPCM intervient dans les rapports de transmission, les motifs périodiques de carrelage et les problèmes de calendrier (quand deux cycles célestes s'alignent-ils à nouveau ?).

Cryptographie

L'algorithme d'Euclide est une brique fondamentale du chiffrement RSA : le PGCD sert à vérifier que l'exposant de clé choisi est premier avec l'indicateur d'Euler du modulo.

Cas particuliers

• PGCD(a, 0) = a pour tout entier positif $a$ : c'est le cas de base de l'algorithme d'Euclide, qui découle naturellement de la définition.
• Entiers premiers entre eux : PGCD = 1 et PPCM = a × b. Par exemple PGCD(7, 13) = 1, PPCM(7, 13) = 91.
• Nombres égaux : PGCD(n, n) = n et PPCM(n, n) = n.

Aide-mémoire

Propriété	Formule
Algorithme d'Euclide	$\gcd(a, b) = \gcd(b,\ a \bmod b)$
PPCM à partir du PGCD	$\text{PPCM}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$
Identité	$\gcd(a,b) \times \text{PPCM}(a,b) = a \times b$
Réduire une fraction	diviser numérateur et dénominateur par le PGCD
Dénominateur commun	prendre le PPCM des deux dénominateurs

Questions fréquentes (FAQ)

Qu'est-ce que le plus grand commun diviseur ?

Le plus grand commun diviseur (PGCD) de deux entiers est le plus grand entier positif qui divise les deux sans reste. Par exemple, PGCD(12, 8) = 4, car 4 est le plus grand nombre qui divise exactement 12 et 8.

Qu'est-ce que le plus petit commun multiple ?

Le plus petit commun multiple (PPCM) de deux entiers est le plus petit entier positif divisible par les deux. Par exemple, PPCM(12, 8) = 24, car 24 est le plus petit nombre qui est à la fois multiple de 12 et de 8.

Quelle est la relation entre le PGCD et le PPCM ?

Pour deux entiers positifs quelconques a et b : PGCD(a, b) × PPCM(a, b) = a × b. Cela signifie que l'on peut trouver l'un à partir de l'autre : PPCM = a × b ÷ PGCD. C'est pourquoi ces deux valeurs sont souvent calculées ensemble.