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.
Extended GCD Algorithm - dCode
Tag(s) : Arithmetics
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!
Extended GCD Algorithm
Extended GCD Calculator
Answers to Questions (FAQ)
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. Any algorithm for the "Extended GCD Algorithm" algorithm, applet or snippet or script (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or any "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.) or any database download or API access for "Extended GCD Algorithm" or any other element are not public (except explicit open source licence like Creative Commons). Same with the download for offline use on PC, mobile, tablet, iPhone or Android app.
Reminder: dCode is an educational and teaching resource, accessible online for free and for everyone.
Cite dCode
The content of the page "Extended GCD Algorithm" and its results may be freely copied and reused, including for commercial purposes, provided that dCode.fr is cited as the source.
Exporting the results is free and can be done simply by clicking on the export icons ⤓ (.csv or .txt format) or ⧉ (copy and paste).
To cite dCode.fr on another website, use the link:
In a scientific article or book, the recommended bibliographic citation is: Extended GCD Algorithm on dCode.fr [online website], retrieved on 2025-04-12,
