Identité de Bézout

L'identité de Bachet-Bezout est définie ainsi : si $ a $ et $ b $ sont deux entiers relatifs et $ d $ est leur PGCD (plus grand commun diviseur), alors il existe $ u $ et $ v $, deux autres entiers relatifs tels que $ au + bv = d $.

Exemple : $ a=12 $ et $ b=30 $, pgcd $ (12, 30) = 6 $. Il existe plusieurs solutions à $ u $ et $ v $ tels que $ 12u + 30v = 6 $, comme $$ 12 \times -2 + 30 \times 1 = 6 $$

La calculatrice des coefficients de Bezout de dCode ne donne qu'une seule solution.

Les coefficients de Bézouts sont les valeurs $ u $ et $ v $ trouvées.

Le programme dCode utilise l'algorithme d'euclide étendu. $ a $ et $ b $ sont forcément des entiers positifs non nuls.

L'algorithme consiste en une suite de divisions euclidiennes qui permet de trouver les coefficients de Bezout (ainsi que le PGCD).

Un code source pour l'identité de Bezout serait similaire à ce pseudo-code:

Initialisation r = a, r' = b, u = 1, v = 0, u' = 0 et v' = 1
Tant que (r' != 0)
q = (entier) r/r'
rs = r, us = u, vs = v,
r = r', u = u', v = v',
r' = rs - q*r', u' = us - q*u', v' = vs - q*v'
Fin tant que
Retourner (r, u, v)