Démonstration de l'algorithme d'Euclide

Dans cette fiche, nous allons nous intéresser au théorème algorithme d’Euclide, qui permet de déterminer si des nombres sont premiers entre eux.

Afin de démontrer cet algorithme nous avons besoin du théorème suivant :

$a$ et $b$ sont deux entiers naturels non nuls tels que la division euclidienne de $a$ par $b$ se traduit par $a=bq+r$ avec $r$ compris entre $0$ et $b$ tous deux exclus $0 < r < b$.

Alors l’ensemble des diviseurs commun à $a$ et $b$ est identique à ceux communs à $b$ et $r$ $\text D(a\ ;b)=\text D(b\ ;r)$ ce qui amène à $\text{PGCD }(a\ ;b)=\text{PGCD }(b\ ;r)$.

• Démontrons que si $d$ divise $a$ et $b$, alors $d$ divise $b$ et $r$ : Si $d$ divise $a$ et $b$, $d$ divise toute combinaison linéaire de $a$ et $b$, donc en particulier $a-bq$, soit $r$. Il en résulte que l’ensemble des diviseurs de $a$ et $b$ sont inclus dans les diviseurs de $b$ et $r$ : $$\text D(a\ ;b)⊂\text D(b\ ;r)$$
• Démontrons que si $δ$ divise $b$ et $r$, alors $δ$ divise $a$ et $b$. Si $δ$ divise $b$ et $r$, $δ$ divise toute combinaison linéaire de $b$ et $r$, donc en particulier $bq+r$, soit $a$. Il en résulte que l’ensemble des diviseurs de $b$ et $r$ figurent parmi les diviseurs de $a$ et $b$ : $$\text D(b\ ;r)⊂\text D(a\ ;b)$$

La double inclusion équivaut donc à dire que l’ensemble des diviseurs à $a$ et $b$ sont communs à ceux de $b$ et $r$ $\text D(a\ ;b)=\text D(b\ ;r)$. Ces deux ensembles étant identiques, ils ont le même plus grand élément donc : $$\text{PGCD }(a\ ;b)=\text{PGCD}(b\ ;r)$$

Lorsque $b$ ne divise pas $a$, le $\text{PGCD}$ de $a$ et $b$ est le dernier reste non nul dans la succession des divisions de l’algorithme d’Euclide.