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!


Feedback and suggestions are welcome so that dCode offers the best 'Bezout's Identity' tool for free! 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ézout coefficients are the values $ u $ and $ v $ found.

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'
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)

Source code

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, breaker, 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.

Cite dCode

The copy-paste of the page "Bezout's Identity" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Bezout's Identity on dCode.fr [online website], retrieved on 2024-06-24, https://www.dcode.fr/bezout-identity

Need Help ?

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

Questions / Comments

Feedback and suggestions are welcome so that dCode offers the best 'Bezout's Identity' tool for free! Thank you!


https://www.dcode.fr/bezout-identity
© 2024 dCode — El 'kit de herramientas' definitivo para resolver todos los juegos/acertijos/geocaching/CTF.
 
Feedback