PGCD et algorithme d'Euclide

3.1 Définition

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls. Leurs diviseurs communs sont en nombre fini, et $1$ en fait partie.

Définition. Le plus grand commun diviseur de $a$ et $b$ est le plus grand de leurs diviseurs communs. On le note $\mathrm{PGCD}(a\,;b)$, ou $a \wedge b$.

Exemple 15. Les diviseurs positifs de $24$ sont $1$, $2$, $3$, $4$, $6$, $8$, $12$, $24$ ; ceux de $36$ sont $1$, $2$, $3$, $4$, $6$, $9$, $12$, $18$, $36$. Les diviseurs communs positifs sont $1$, $2$, $3$, $4$, $6$, $12$, donc $\mathrm{PGCD}(24\,;36) = 12$.

Propriétés immédiates.

• $\mathrm{PGCD}(a\,;b) \geq 1$, $\mathrm{PGCD}(a\,;b) = \mathrm{PGCD}(b\,;a)$ et $\mathrm{PGCD}(a\,;b) = \mathrm{PGCD}(|a|\,;|b|)$ : on peut toujours se ramener à des entiers naturels.
• Si $a \neq 0$, $\mathrm{PGCD}(a\,;0) = |a|$.
• Si $b \neq 0$ et $b \mid a$, alors $\mathrm{PGCD}(a\,;b) = |b|$.

3.2 Le lemme d'Euclide

Propriété. Si $a = b\,q + r$ (avec $a$, $b$, $q$, $r$ entiers), alors $a$ et $b$ ont les mêmes diviseurs communs que $b$ et $r$. En particulier $\mathrm{PGCD}(a\,;b) = \mathrm{PGCD}(b\,;r).$

Démonstration. Si $d$ divise $a$ et $b$, il divise $r = a - bq$ (combinaison). Si $d$ divise $b$ et $r$, il divise $a = bq + r$. Les deux couples ont donc exactement les mêmes diviseurs communs, donc le même plus grand.

3.3 L'algorithme d'Euclide

Soit $a$ et $b$ deux entiers naturels avec $b \neq 0$. On effectue la division euclidienne de $a$ par $b$, puis celle de $b$ par le reste, puis celle du premier reste par le deuxième, et ainsi de suite. Les restes sont des entiers naturels strictement décroissants : on finit par obtenir un reste nul.

Théorème. Le PGCD de $a$ et $b$ est le dernier reste non nul de l'algorithme d'Euclide.

En effet, d'après le lemme d'Euclide, le PGCD ne change pas d'une ligne à la suivante, et à la dernière ligne, $\mathrm{PGCD}(r\,;0) = r$.

Exemple 16. Calcul de $\mathrm{PGCD}(924\,;360)$.

Division	Reste
$924 = 360 \times 2 + 204$	$204$
$360 = 204 \times 1 + 156$	$156$
$204 = 156 \times 1 + 48$	$48$
$156 = 48 \times 3 + 12$	$\mathbf{12}$
$48 = 12 \times 4 + 0$	$0$

Le dernier reste non nul est $12$ : $\mathrm{PGCD}(924\,;360) = 12$.

Conséquences.

• Les diviseurs communs de $a$ et $b$ sont exactement les diviseurs de leur PGCD (ils sont conservés d'une ligne à l'autre de l'algorithme, et à la fin ce sont les diviseurs de $r$).
• Pour tout entier naturel non nul $k$ : $\mathrm{PGCD}(ka\,;kb) = k\,\mathrm{PGCD}(a\,;b)$ (on multiplie par $k$ toutes les lignes de l'algorithme).

Exemple 17 (partage, situation simplifiée). Une association veut répartir $924$ cahiers et $360$ stylos en lots identiques, en utilisant tout le matériel, avec le plus grand nombre de lots possible. Le nombre de lots divise $924$ et $360$ : le plus grand possible est $\mathrm{PGCD}(924\,;360) = 12$. Chaque lot contient $924 : 12 = 77$ cahiers et $360 : 12 = 30$ stylos.

3.4 Entiers premiers entre eux

Définition. Deux entiers sont premiers entre eux si leur PGCD est égal à $1$ : leurs seuls diviseurs communs sont $1$ et $-1$.

Exemple 18. $35 = 5 \times 7$ et $18 = 2 \times 3^2$ sont premiers entre eux. $77$ et $30$ aussi.

Propriété. Si $d = \mathrm{PGCD}(a\,;b)$, avec $a$ et $b$ non nuls, alors $a = d\,a'$ et $b = d\,b'$, où $a'$ et $b'$ sont premiers entre eux.

Démonstration. $d = \mathrm{PGCD}(d\,a'\,;d\,b') = d\,\mathrm{PGCD}(a'\,;b')$, donc $\mathrm{PGCD}(a'\,;b') = 1$.

Application aux fractions. Une fraction $\dfrac{a}{b}$ est irréductible si $a$ et $b$ sont premiers entre eux. Pour la rendre irréductible, on divise $a$ et $b$ par leur PGCD : $\dfrac{924}{360} = \dfrac{12 \times 77}{12 \times 30} = \dfrac{77}{30}$.

3.5 PGCD de plusieurs entiers

Le PGCD de plusieurs entiers est le plus grand de leurs diviseurs communs. On le calcule de proche en proche : $\mathrm{PGCD}(a\,;b\,;c) = \mathrm{PGCD}\big(\mathrm{PGCD}(a\,;b)\,;c\big).$

Exemple 19. $\mathrm{PGCD}(924\,;360\,;150) = \mathrm{PGCD}(12\,;150) = 6$, car $150 = 12 \times 12 + 6$ et $12 = 6 \times 2$.