Search for a tool
Extended GCD Algorithm

Tool to apply the extended GCD algorithm (Euclidean method) in order to find the values of the Bezout coefficients and the value of the GCD of 2 numbers.

Results

Extended GCD Algorithm -

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 Extended GCD Algorithm tool. Thank you.

dCode is now secured over HTTPS, thank you for reporting any issue

# Extended GCD Algorithm

This script has been updated, please report any problems.

## Extended GCD Calculator

Tool to apply the extended GCD algorithm (Euclidean method) in order to find the values of the Bezout coefficients and the value of the GCD of 2 numbers.

### What is Extended GCD algorithm?

The extended Euclidean algorithm is a modification of the classical GCD algorithm. From 2 natural inegers a and b, its steps allow to calculate their GCD and their Bézout coefficients (see the identity of Bezout).

Example: $$a=12$$ and $$b=30$$, thus $$\mbox{pgcd}(12, 30) = 6$$

$$12 \times -10 + 30 \times 3 = 6 \\ 12 \times -3 + 30 \times 1 = 6 \\ 12 \times 4 + 30 \times -1 = 6 \\ 12 \times 11 + 30 \times -3 = 6 \\ 12 \times 18 + 30 \times -5 = 6 \ 12 \times −2+30 \times 1 = 6$$

### How to code the Extended GCD algorithm?

Here is an implementation of the pseudo-code algorithm: function extended_gcd(a, b) {// a, b natural integers r1 = a, r2 = b, u1 = 1, v1 = 0, u2 = 0, v2 = 1 while (r2! = 0) do q = r1 ÷ r2 (integer division) r3 = r1, u3 = u1, v3 = v1, r1 = r2, u1 = u2, v1 = v2, r2 = r3 - q * r2, u2 = u3 - q * u2, v2 = v3 - q * v2 end while return (r1, u1, v1) (r1 natural integer and u1, v1 rational integers)

The values are such that r1 = pgcd(a, b) = a * u1 + b * v1