Search for a tool
Bezout's Identity

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

Results

Bezout's Identity -

Tag(s) : Mathematics

dCode and you

dCode is free and its tools are a valuable help in games, puzzles and problems to solve every day!
You have a problem, an idea for a project, a specific need and dCode can not (yet) help you? You need custom development? Contact-me!

Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best Bezout's Identity tool. Thank you.

# Bezout's Identity

## Bezout Identity Calculator

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

### What is Bezout Identity?

The Bezout identity is defined as : if $$a$$ and $$b$$ are two integers and $$d$$ is their GCD, 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$$

### What are Bezout coefficients?

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

### How to calculate values for Bézout Identity?

The dCode program uses the gcd" target="_blank">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).

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