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

### 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 cite 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 2023-12-03, 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!