Plus grand commun diviseur

Définition intuitive

Soient $a$ et $b$ deux entiers. Le plus grand commun diviseur est un diviseur commun de $a$ et $b$ et le plus grand possible.

Définition formelle

Soient $a$ et $b$ deux entiers relatifs. On note $\mathcal{D}_{a}$ et $\mathcal{D}_{b}$ respectivement l’ensemble des diviseurs dans $\mathbb Z$ de $a$ et de $b$. Le plus grand commun diviseur aussi appelé plus simplement PGCD est défini de la manière suivante :
$$\mathrm{pgcd}(a,b) = \left\{ \begin{array}{l} \max(\mathcal{D}_{a} \cap \mathcal{D}_{b}) , \mathrm{si}~ a \ne 0 ~ \mathrm{ou} ~ b\ne 0&\\ 0, \mathrm{si} ~ a = b=0 \end{array} \right.$$

Exemples

• $\mathrm{pgcd}(9,6) = 3$ , en effet : $3$ est un diviseur commun à $6$ et à $9$ : $3 | 6$ et $3|9$ , de plus il n’existe pas de nombres strictement plus grand que $3$ divisant à la fois $6$ et $9$.
• $\mathrm{pgcd}(1,a) = 1$ pour tout $a$ entier
• $\mathrm{pgcd}(0,a) = |a|$ pour tout