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 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 'Extended GCD Algorithm' tool for free! Thank you!

# Extended GCD Algorithm

## Extended GCD Calculator

### What is Extended GCD algorithm? (Definition)

The extended Euclidean algorithm is a modification of the classical GCD algorithm allowing to find a linear combination. 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 to find the linear combination gcd(a,b) = a.u+b.v: function extended_gcd(a, b) {// a, b natural integers a < b r1 = b, r2 = a, u1 = 0, v1 = 1, u2 = 1, v2 = 0 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 "Extended GCD Algorithm" source code. Except explicit open source licence (indicated Creative Commons / free), the "Extended GCD Algorithm" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Extended GCD Algorithm" 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 "Extended GCD Algorithm" 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 "Extended GCD Algorithm" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Extended GCD Algorithm on dCode.fr [online website], retrieved on 2024-07-18, https://www.dcode.fr/extended-gcd

## Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!