Bezout's Identity

The Bachet-Bezout identity is defined as : if $ a $ and $ b $ are two integers and $ d $ is their GCD (greatest common divisor), then it exists $ u $ and $ v $, two integers such as $ au + bv = d $.

Example: $ a=12 $ and $ b=30 $, gcd $ (12, 30) = 6 $. There are multiple solutions to $ u $ and $ v $ such as $ 12u + 30v = 6 $, such as : $$ 12 \times -2 + 30 \times 1 = 6 $$

The dCode Bezout coefficients calculator gives only one solution.

The Bézouts coefficients are the values $ u $ and $ v $.

The dCode program uses the extended GCD algorithm. $ a $ and $ b $ are two non-zero positive integers.

The algorithm of dCode consists of a sequence of Euclidean divisions for finding the Bezout coefficients (and also the GCD).

A source code for the identity of Bezout would be similar to this pseudo-code:

Initialization r = a, r' = b, u = 1, v = 0, u' = 0 and v' = 1
While (r' != 0)
q = (int) 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'
End While
Return (r, u, v)