Tool to compute Bezout coefficients. The Bezout Identity proves that there exists solutions to the equation a.u + b.v = PGCD(a,b).
Bezout's Identity - dCode
Tag(s) : Arithmetics
dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!
Example: $ a=12 $ and $ b=30 $, gcd $ (12, 30) = 6 $, then, it exists $ u $ and $ v $ such as $ 12u + 30v = 6 $, like: $$ 12 \times -2 + 30 \times 1 = 6 $$
The dCode Bezout coefficients calculator gives only one solution, there is an infinity of them.
The Bézouts coefficients are the values $ u $ and $ v $.
Automatic method: Use the dCode form above, enter the non-zero relative integers $ a $ and $ b $ and click on Calculate.
By initializing $ u = 1 $, $ v = 0 $, $ u' = 0 $ and $ v' = 1 $, from 2 relative integers $ a $ and $ b $, calculate the quotient $ q $ and the remainder $ r $ of the euclidean division of $ a $ by $ b $
While $ r \neq 0 $, calculate the new values $ u' \leftarrow u \times q - u' $ and $ u \leftarrow u' $ and change the values $ a \leftarrow b $ and $ b \leftarrow r $.
When $ r = 0 $ the last value of $ b $ is the GCD and the values $ u $ and $ v $ are the Bézout coefficients.
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'
Return (r, u, v)