L’essentiel : D’après le théorème de Bézout, deux entiers relatifs \(a\) et \(b\) sont premiers entre eux si et seulement s’il existe des entiers \(u\) et \(v\) tels que \(au+bv=1\). Plus généralement, le PGCD de \(a\) et \(b\) est le plus petit entier strictement positif de la forme \(au+bv\). On trouve \(u\) et \(v\) en remontant l’algorithme d’Euclide.
I.Enoncé du théorème de Bézout :
Soient a et b sont deux entiers naturels non nuls.
Dire que a et b sont premiers entre eux équivaut à dire il existe deux entiers relatifs u et v tels que 
.
Démonstration :
1.Supposons qu’il existe deux entiers u et v tels que au + bv = 1 et prouvons que a et b sont premiers entre eux.
On note 
divise a et b donc divise au + bv.
Comme au + bv = 1, = 1 et a et b sont premiers entre eux.
2.Supposons que a et b premiers entre eux et démontrons que 1 s’écrit sous la forme au + bv.
Soit 
l’ensemble des nombres sous la forme au + bv avec 
et 
.
L’ensemble n’est pas vide car pour u = 1 et v = 0, 
.Il en est de même pour b.
Ainsi contient des entiers strictement positive, et, parmi eux, un plus petit que tous les autres.
Notons 
ce plus petit élément.
La division euclidienne de a par m s’écrit 
avec 
soit 
.
Ainsi 
.Or m est le plus petit entier strictement positif de donc r = 0.
Ainsi m divise a.On montre de même que m divise b.
Comme a et b sont premiers entre eux, m=1 et 
.
En pratique, comment trouver u et v ?
Pour déterminer les coefficient, on utilise l’algorithme d’Euclide.
Donnons un exemple.
On cherche un couple (x;y) d’entiers relatifs tels que 89x+41y=1 (1).
89 et 41 sont premiers entre eux donc il existe deux entiers relatifs x et y vérifiant (1).
On pose a=89 et b=41.
donc 
.
donc 
.
donc 
.
Soit 
.
Ainsi 
est solution de (1).
II.Une nouvelle caractérisation du PGCD
a et b sont deux entiers naturels non nuls.Dire que est le 
équivaut à dire que est un diviseur de a et b et il existe deux entiers relatifs u et v tels que 
.
