Arithmétique

L'algorithme d'Euclide consiste à remplacer le plus grand nombre par le reste de sa division par le plus petit, jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD.
Étape 1 : $126 = 90 \times 1 + 36$ (reste 36).
Étape 2 : on continue avec 90 et 36 : $90 = 36 \times 2 + 18$ (reste 18).
Étape 3 : on continue avec 36 et 18 : $36 = 18 \times 2 + 0$ (reste 0).
Le dernier reste non nul est 18.
$PGCD(126 \,;\, 90) = 18$.
Vérifions : $126 = 18 \times 7$ et $90 = 18 \times 5$, donc 18 divise bien les deux nombres.

Deux nombres sont premiers entre eux lorsque leur PGCD vaut 1, c'est-à-dire quand ils n'ont aucun facteur premier commun.
Étape 1 : on décompose.
$84 = 2 \times 42 = 2 \times 2 \times 21 = 2^{2} \times 3 \times 7$.
$55 = 5 \times 11$.
Étape 2 : on compare les facteurs premiers.
84 utilise les facteurs 2, 3 et 7 ; 55 utilise les facteurs 5 et 11.
Aucun facteur n'est commun aux deux nombres.
Donc $PGCD(84 \,;\, 55) = 1$ : les nombres 84 et 55 sont premiers entre eux.