Identité de Bézout

L'identité de 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 $$

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)