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) : Arithmetics

Share dCode and you

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 community Discord for help requests!

Thanks to your feedback and relevant comments, dCode has developped the best Extended GCD Algorithm tool, so feel free to write! Thank you !

# Extended GCD Algorithm

## 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 $gcd(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 eGCD 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

### How does Extended GCD algorithm work with negative numbers?

Using the absolute values for a and b, the rest of the calculation is identical thanks to the property: $$a(\text{sign}(a)\cdot x)+b(\text{sign}(b)\cdot y)=1$$

## Source code

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

## Need Help ?

Please, check our community Discord for help requests!