1. Plus Grand Commun Diviseur (PGCD)
Définition du PGCD
Le PGCD de deux entiers naturels non nuls a et b, noté PGCD(a, b), est le plus grand entier positif qui divise à la fois a et b.
Théorème : Existence et unicité du PGCD
Pour tout couple d'entiers naturels non nuls (a, b), il existe un unique PGCD(a, b).
Méthodes de calcul du PGCD
- Décomposition en facteurs premiers
- Algorithme d'Euclide
- Algorithme d'Euclide étendu
Exemple : Calcul du PGCD avec l'algorithme d'Euclide
Calculons PGCD(48, 18) :
48 = 2 × 18 + 12
18 = 1 × 12 + 6
12 = 2 × 6 + 0
Donc, PGCD(48, 18) = 6
2. Plus Petit Commun Multiple (PPCM)
Définition du PPCM
Le PPCM de deux entiers naturels non nuls a et b, noté PPCM(a, b), est le plus petit entier positif qui est multiple à la fois de a et de b.
Théorème : Relation entre PGCD et PPCM
Pour tout couple d'entiers naturels non nuls (a, b) :
PGCD(a, b) × PPCM(a, b) = a × b
Démonstration
La preuve de ce théorème repose sur la décomposition en facteurs premiers des nombres a et b.
Méthodes de calcul du PPCM
- Décomposition en facteurs premiers
- Utilisation de la relation avec le PGCD
Exemple : Calcul du PPCM
Calculons PPCM(12, 18) :
PGCD(12, 18) = 6
PPCM(12, 18) = (12 × 18) / PGCD(12, 18) = 216 / 6 = 36
3. Applications
- Simplification de fractions
- Résolution d'équations diophantiennes
- Problèmes de calendriers et de cycles