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 $, alors il existe $ 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, il en existe une infinité.

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

Méthode automatique : Utiliser le programme dCode ci-dessus, entrer les entiers $ a $ et $ b $ relatifs non nuls et cliquer sur Calculer.

Méthode manuelle : utiliser l'algorithme d'euclide étendu, qui est une suite de divisions euclidiennes qui permet de trouver les coefficients de Bezout (ainsi que le PGCD).

En initialisant $ u = 1 $, $ v = 0 $, $ u' = 0 $ et $ v' = 1 $, à partir de 2 entiers relatifs $ a $ et $ b $, calculer le quotient $ q $ et le reste $ r $ de la division euclidienne de $ a $ par $ b $

Tant que $ r \neq 0 $, calculer les nouvelle valeurs $ u' \leftarrow u \times q - u' $ et $ u \leftarrow u' $ et changer les valeurs $ a \leftarrow b $ et $ b \leftarrow r $.

Lorsque $ r = 0 $ la dernière valeur de $ b $ est le PGCD et les valeurs $ u $ et $ v $ sont les coefficients de Bézout.

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)