Extended Euclidean GCD Calculator
The extended Euclidean algorithm finds the greatest common divisor of two integers and, at the same time, the two whole-number coefficients that express that divisor as a combination of the inputs. For integers a and b it returns the greatest common divisor g together with x and y such that a times x plus b times y equals g, a relationship known as Bezout's identity. This calculator takes the two integers and returns the divisor and both coefficients. It runs the ordinary Euclidean algorithm, repeatedly replacing the larger number by the remainder when divided by the smaller, while carrying along the coefficients so that the identity holds at every step. The coefficients are essential in number theory and cryptography, where they give modular inverses used in RSA and other schemes. They can be negative, which is normal, since one term usually subtracts from the other. Mathematicians, computer scientists and students use this routine to solve linear Diophantine equations and to invert numbers modulo another. Enter the two integers to get the divisor and the coefficients immediately. Every figure here is computed deterministically from the algorithm shown below, with a worked example that reconciles exactly to the calculator so you can follow it.
The extended algorithm gives the gcd and x, y with ax + by = gcd. For a = 240, b = 46, the gcd is 2 with x = -9, y = 47.
Extended Euclidean GCD formula
find g, x, y with a x + b y = g
g = gcd(a, b)
run Euclid: replace (a, b) with (b, a mod b)
carry coefficients back at each step
x and y may be negative
The algorithm runs the Euclidean division repeatedly while tracking how each remainder is built from the originals, so that at the end the divisor is written as a whole-number combination of the two inputs.
Worked example
Find the gcd of 240 and 46 along with the Bezout coefficients.
- 240 = 5 x 46 + 10; 46 = 4 x 10 + 6; 10 = 1 x 6 + 4; 6 = 1 x 4 + 2; 4 = 2 x 2 + 0, so gcd = 2
- Back-substitute to express 2 from the originals
- Result: 2 = (-9) x 240 + 47 x 46, so x = -9, y = 47
The gcd is 2 with coefficients x = -9 and y = 47, since -9 times 240 plus 47 times 46 equals 2. These are the calculator's default inputs, so the result above matches the widget exactly.
GCD and coefficients for sample pairs
a x + b y = gcd.
| a, b | gcd | x, y |
|---|---|---|
| 240, 46 | 2 | -9, 47 |
| 12, 8 | 4 | 1, -1 |
| 35, 15 | 5 | 1, -2 |
| 17, 5 | 1 | -2, 7 |
| 99, 78 | 3 | -11, 14 |
Number-theory and cryptography reference: US National Institute of Standards and Technology (NIST).
Extended Euclidean GCD Calculator: frequently asked questions
What is the extended Euclidean algorithm?
It is an extension of the Euclidean algorithm that finds the greatest common divisor of two integers and also the coefficients x and y satisfying a times x plus b times y equals the divisor. The ordinary algorithm finds only the divisor; the extended version tracks how it is built from the inputs.
What is Bezout's identity?
Bezout's identity states that for any two integers there exist whole numbers x and y such that a times x plus b times y equals their greatest common divisor. The extended Euclidean algorithm computes a valid pair of these coefficients, which are not unique but always exist.
Why can the coefficients be negative?
Because the divisor is usually a difference of multiples of the two inputs, one coefficient is typically negative. That is expected and correct. For 240 and 46 the coefficients are minus nine and forty-seven, and minus nine times 240 plus forty-seven times 46 equals two.
Where is this used in cryptography?
It computes modular inverses, which are central to public-key systems like RSA. To invert a number modulo another, you run the extended algorithm; when the divisor is one, the coefficient of the number is its modular inverse. This makes the algorithm a building block of modern encryption.
What does the algorithm return for 240 and 46?
The greatest common divisor is 2, with coefficients x equal to minus nine and y equal to forty-seven. You can verify it: minus nine times 240 is minus 2,160, forty-seven times 46 is 2,162, and the difference is 2.
Official sources
- Mathematical functions and integer-sequence reference data (Digital Library of Mathematical Functions): US National Institute of Standards and Technology (NIST). As at 25 June 2026.
Reviewed by the CalculatorHub team, edited by James Graham, 25 June 2026. See our methodology. This is general information, not financial, tax, legal or investment advice.