Search for a tool
Bezout's Identity

Tool to compute Bezout coefficients. The Bezout Identity proves that there exists solutions to the equation a.u + b.v = PGCD(a,b).

Results

Bezout's Identity -

Tag(s) : Arithmetics

Share
Share
dCode and more

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!


Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!


Thanks to your feedback and relevant comments, dCode has developed the best 'Bezout's Identity' tool, so feel free to write! Thank you!

Bezout's Identity

Bezout Identity Calculator




Answers to Questions (FAQ)

What is Bezout Identity? (Definition)

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.

What are Bezout coefficients?

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

How to calculate values for Bézout Identity?

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.

How to code Bézout Identity in pseudo-code?

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)

Source code

dCode retains ownership of the online "Bezout's Identity" source code. Except explicit open source licence (indicated CC / 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, copy-paste, or API access for "Bezout's Identity" are not public, same for offline use on PC, tablet, iPhone or Android ! Remainder : dCode is free to use.

Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Questions / Comments

Thanks to your feedback and relevant comments, dCode has developed the best 'Bezout's Identity' tool, so feel free to write! Thank you!


Source : https://www.dcode.fr/bezout-identity
© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.
Feedback