PGCD et PPCM
Deux naturels non nuls peuvent avoir des facteurs en commun dans leur décomposition en un produit de facteurs premiers. Le plus grand commun diviseur (PGCD) de deux naturels non nuls $a$ et $b$ est leur plus grand facteur commun; on le note $pgcd(a, b)$. Leur plus petit commun multiple (PPCM) est le plus petit nombre à la fois multiple de $a$ et de $b$; on le note $ppcm(a, b)$.
L'algorithme d'Euclide permet de trouver le PGCD de deux nombres naturels non nuls $a$ et $b$ en se basant sur les trois observations suivantes :
- $pgcd(a, a) = a$ ;
- $pgcd(a, b) = pgcd(a - b, b)$ si $a > b$ ;
- $pgcd(a, b) = pgcd(a, b - a)$ si $b > a$.
Quelques propriétés font intervenir le PGCD et le PPCM :
- Les PGCD et PPCM de $a, b \in \mathbb{N}_0$ sont liés par : $$pgcd(a, b) = \frac{ab}{ppcm(a, b)}.$$
- Deux nombres naturels sont premiers entre eux (ou copremier) si leur PGCD vaut $1$, c'est-à-dire qu'ils n'ont aucun facteur premier commun.