Theˊoreˋme de BeˊzoutDeux entiers relatifs a et b sont premiers entre eux si et seulement si, il existe deux entiers relatifs u et v tels que : au+bv=1 Il faut commencer par démontrer que les entiers relatifs
17 et
5 sont premiers entre eux. Pour cela, il faut calculer le
PGCD(17;5).
On vérifie facilement que
PGCD(17;5)=1Il en résulte donc que les entiers relatifs
17 et
5 sont premiers entre eux.
D’après le
Theˊoreˋme de Beˊzout, on peut déduire qu’il existe un couple d’entiers relatifs
(u;v) tel que
17u+5v=1.
On cherche un tel couple en utilisant l’algorithme d’Euclide et on isole les restes non nuls obtenus. Il vient alors que :
17=5×3+2 2=17−5×35=2×2+1 1=5−2×22=1×2+0Maintenant nous allons remonter l'algorithme d'Euclide en partant du dernier reste non nul :
1=5−2×21=5−(17−5×3)×2 ( on va à l'étape suivante en réduisant les expressions disposant de la valeur
25 ) .
On obtient alors :
1=5−17×2+5×3×21=5−17×2+5×61=17×(−2)+5×7Il en résulte qu'un couple d'entiers relatifs
(u;v) tel que
17u+5v=1 est le couple
(−2;7)