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*!

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 $, 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ézout coefficients are the values $ u $ and $ v $ found.

Automatic method: Use the dCode form above, enter the non-zero relative integers $ a $ and $ b $ and click on Calculate.

Manual method: use the extended euclidean algorithm, which is a series of Euclidean divisions which allows to find the Bezout coefficients (as well as the GCD).

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'

r₂ = r, u₂ = u, v₂ = v,

r = r', u = u', v = v',

r' = r₂ - q*r', u' = u₂ - q*u', v' = v₂ - q*v'

End While

Return (r, u, v)

dCode retains ownership of the "Bezout's Identity" source code. Except explicit open source licence (indicated Creative Commons / free), the "Bezout's Identity" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or the "Bezout's Identity" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Bezout's Identity" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!

Reminder : dCode is free to use.

The copy-paste of the page "Bezout's Identity" or any of its results, is allowed as long as you cite dCode!

Cite as source (bibliography):

*Bezout's Identity* on dCode.fr [online website], retrieved on 2022-09-29,

bezout,identity,bachet,lemma,au,bv,gcd,coefficient,divisor,euclidean,algorithm,extended,calculator

https://www.dcode.fr/bezout-identity

© 2022 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback