Déterminer les coefficients dans l'égalité de Bezout

Soit a et b deux entiers naturels non nuls ; d est leur PGCD.

D'après le théorème de Bezout il existe deux entiers relatifs u et v tels que : .

Le but est de donner un algorithme permettant de déterminer u et v.

On met en œuvre l'algorithme d'Euclide et on calcule les restes successifs en fonction de a et b.Le dernier reste non nul est le PGCD. On développe alors les calculs de façon à faire apparaître à chaque étape une écriture du reste de la forme .

Exemple : déterminons des entiers relatifs u et v tels que : .

  et .

  soit donc ,
  soit donc ,
  soit donc ,
  soit donc ,
 .

Par conséquent, on a :  ; et .