Introduction
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.
Prérequis
Afin de démontrer cet algorithme nous avons besoin du théorème suivant :
et sont deux entiers naturels non nuls tels que la division euclidienne de par se traduit par avec compris entre et tous deux exclus .
Alors l’ensemble des diviseurs commun à et est identique à ceux communs à et ce qui amène à .
Démonstration
- Démontrons que si divise et , alors divise et : Si divise et , divise toute combinaison linéaire de et , donc en particulier , soit . Il en résulte que l’ensemble des diviseurs de et sont inclus dans les diviseurs de et :
- Démontrons que si divise et , alors divise et . Si divise et , divise toute combinaison linéaire de et , donc en particulier , soit . Il en résulte que l’ensemble des diviseurs de et figurent parmi les diviseurs de et :
La double inclusion équivaut donc à dire que l’ensemble des diviseurs à et sont communs à ceux de et . Ces deux ensembles étant identiques, ils ont le même plus grand élément donc :
Lorsque ne divise pas , le de et est le dernier reste non nul dans la succession des divisions de l’algorithme d’Euclide.