Algorithme d'Euclide : méthode (Maths expertes)
Algorithme d'Euclide
Pour calculer $\mathrm{PGCD}(a, b)$ avec $a \geqslant b > 0$ :
- On effectue la division euclidienne de $a$ par $b$ : $a = bq_1 + r_1$.
- Si $r_1 = 0$, le PGCD est $b$. Sinon, on recommence avec le couple $(b, r_1)$, puis $(r_1, r_2)$, etc.
- Les restes forment une suite d'entiers naturels strictement décroissante, donc on atteint un reste nul après un nombre fini d'étapes.
- Le PGCD est le dernier reste non nul.
En effet, par la propriété précédente : $\mathrm{PGCD}(a,b) = \mathrm{PGCD}(b, r_1) = \mathrm{PGCD}(r_1, r_2) = \dots = \mathrm{PGCD}(r_k, 0) = r_k$.
Calcul de PGCD(1071, 462)
$$\begin{aligned} 1071 &= 2 \times 462 + 147 \\ 462 &= 3 \times 147 + 21 \\ 147 &= 7 \times 21 + 0 \end{aligned}$$ Le dernier reste non nul est $21$, donc $\mathrm{PGCD}(1071, 462) = 21$.
Programmation
L'algorithme d'Euclide se programme en quelques lignes en Python (l'opérateur % donne le reste de la division euclidienne) :
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return a
PGCD de deux expressions en n
Soit $n \in \mathbb{N}$. On cherche $\mathrm{PGCD}(2n+3, n+1)$.
Par la propriété 4 avec $q = 2$ : $\mathrm{PGCD}(2n+3, n+1) = \mathrm{PGCD}(n+1, (2n+3) - 2(n+1)) = \mathrm{PGCD}(n+1, 1) = 1$.
Donc $2n+3$ et $n+1$ sont premiers entre eux pour tout $n$. De même, deux entiers consécutifs $n$ et $n+1$ sont toujours premiers entre eux.