Algorithme d'Euclide : méthode (MPSI)

Pour calculer $a \wedge b$ avec $a, b \in \mathbb{N}$ et $b \neq 0$ :

1. Poser $r_0 = a$, $r_1 = b$.
2. Tant que $r_k \neq 0$, effectuer la division euclidienne $r_{k-1} = q_k r_k + r_{k+1}$ avec $0 \leqslant r_{k+1} < r_k$.
3. Le PGCD est le dernier reste non nul.

Justification : la suite des restes est une suite strictement décroissante d'entiers naturels, donc elle atteint $0$ en un nombre fini d'étapes. Par le lemme, $r_{k-1} \wedge r_k = r_k \wedge r_{k+1}$ à chaque étape ; si $r_N \neq 0$ et $r_{N+1} = 0$, alors $a \wedge b = r_N \wedge 0 = r_N$.