Médaille
N°1 pour apprendre & réviser du collège au lycée.
Démonstration du théorème de Bézout
Démonstration

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 :

aa et bb sont deux entiers naturels non nuls. Dire « aa et bb sont premiers entre eux » équivaut à dire « il existe deux entiers relatifs uu et vv tels que au+bv=1au+bv = 1 ».

Démonstration

Supposons qu’il existe deux entiers uu et vv tels que au+bv=1au+bv=1 et prouvons que aa et bb sont premiers entre eux.

On note d=PGCD (a ;b)d=\text{PGCD }(a\ ;b). dd divise aa et bb donc dd divise au+bvau+bv.

Comme au+bv=1au+bv=1, d=1d=1 et aa et bb sont premiers entre eux.

Supposons aa et bb premiers entre eux et démontrons que 11 s’écrit sous la forme au+bvau+bv. Soit ε\varepsilon l’ensemble des nombres de la forme au+bvau+bv, avec uZu ∈\mathbb Z et vZv ∈\mathbb Z.

L’ensemble ε\varepsilon n’est pas vide car pour u=1u = 1 et v=0v = 0, ∈ ε\varepsilon. Il en est de même pour bb.

Ainsi ε\varepsilon contient des entiers strictement positifs et, parmi eux, un plus petit que tous les autres.

Notons m=au1+bv1m = au1+bv1 ce plus petit élément. La division euclidienne de aa par mm s’écrit a=mq+ra=mq+r avec 0r<m0 ≤ r < m

soit r=amq=a(au1+bv1)q=a(1u1q)+b(v1q)\begin{aligned}r&=a-mq\&=a-(au1+bv1)q\&=a(1-u1q)+b(-v1q)\end{aligned}

Ainsi r ∈ ε\varepsilon.

Or mm est le plus petit entier strictement positif de ε\varepsilon donc r=0r=0. Ainsi mm divise aa. On montre de même que mm divise bb.

Comme aa et bb sont premiers entre eux, m=1m = 1 et au1+bv1=1au1+bv1=1.

En pratique, pour trouver uu et vv, 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.