Tool to compute Bezout coefficients. The Bezout Identity proves that it 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 $. 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)

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

Please, check our dCode Discord community for help requests!

NB: for encrypted messages, test our automatic cipher identifier!

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

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

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

Feedback

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