Division euclidienne
Pour $a$ un entier relatif et b un entier naturel non nul, Il existe un unique couple $(q, r)$ d’entiers respectivement relatif et naturel qui vérifient :
$a = bq + r$ et $0 \leq r < b$.
$q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.
PGCD de deux nombres
Pour $a$ et $b$ deux entiers relatifs non nuls, le PGCD de $a$ et de $b$ qui est noté $\mathrm{PGCD} (a, b)$, est le plus grand des diviseurs communs à $a$ et à $b$.
On peut le calculer avec l’algorithme d’Euclide ou la décomposition en produit de facteurs premiers de $a$ et de $b$.
Algorithme d’Euclide
Si la division euclidienne de $a$ par $b$ ($a$ et $b$ deux entiers naturels) est $a = b × q + r$ avec $0 \leq r < b$, on a $\mathrm{PGCD}(a~ ;~ b) = \mathrm{PGCD}(b~ ;~ r)$.
On détermine le $\rm PGCD$ de deux nombres à l’aide de divisions euclidiennes successives.
Exemple : Calcul du $\rm PGCD$ de $252$ et $144$
$252 = 1 \times 144 + 108$ $\rm PGCD(252~ ;~ 144) = PGCD(144~ ; ~108)$
$144 = 1 \times 108 + 36$ $\rm PGCD(144~ ; ~108) = PGCD(108~ ; ~36)$
$108 = 3 \times 36 + 0$ $\rm PGCD(108~ ;~ 36) = 36$ car $36$ divise $108$
$\rm PGCD(252~ ; ~108) = 36$ qui est le dernier reste non nul.
Nombres premiers entre eux
Deux nombres sont dits premiers entre eux si leur $\rm PGCD$ est égal à $1$.
Pour $a$ et $b$ deux entiers relatifs non nuls, $a$ et $b$ sont premiers entre eux est équivalent à $\displaystyle\frac{a}{b}$ est une fraction irréductible.