Introduction
Dans cette fiche, nous allons nous intéresser à la démonstration du théorème de Bézout, 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 de Bézout :
et sont deux entiers naturels non nuls. Dire « et sont premiers entre eux » équivaut à dire « il existe deux entiers relatifs et tels que ».
Démonstration
Supposons qu’il existe deux entiers et tels que et prouvons que et sont premiers entre eux.
On note . divise et donc divise .
Comme , et et sont premiers entre eux.
Supposons et premiers entre eux et démontrons que s’écrit sous la forme . Soit l’ensemble des nombres de la forme , avec et .
L’ensemble n’est pas vide car pour et , ∈ . Il en est de même pour .
Ainsi contient des entiers strictement positifs et, parmi eux, un plus petit que tous les autres.
Notons ce plus petit élément. La division euclidienne de par s’écrit avec
soit
Ainsi r ∈ .
Or est le plus petit entier strictement positif de donc . Ainsi divise . On montre de même que divise .
Comme et sont premiers entre eux, et .
En pratique, pour trouver et , on utilise l’algorithme d’Euclide pour démontrer que les deux nombres sont premiers entre eux. Puis, on reprend chaque division euclidienne pour exprimer chaque reste au fur et à mesure. On trouve ainsi le couple solution.