Home › Calculators › Extended Euclidean Algorithm Calculator
Extended Euclidean Algorithm Calculator
Enter two integers to get their greatest common divisor and the Bézout coefficients x and y with a·x + b·y = gcd(a, b). Every division, quotient and coefficient is shown in a table you can follow by hand or download.
Last updated:
Whole number, can be negative or very large
Leave blank to skip the linear Diophantine equation
Enter your values to see the result.
Advertisement
Advertisement
How to use the Extended Euclidean Algorithm Calculator
Enter a and b, the two integers you want to work with. Commas and spaces in long numbers are ignored.
Optionally enter c to solve the equation a·x + b·y = c in whole numbers.
Press Calculate (results also update as you type) to see the gcd, x, y and the check a·x + b·y = gcd.
Follow the table: each row shows the quotient, the remainder and the running coefficients s and t.
Copy or download the answer, or the step table as a CSV file for homework or notes.
How the extended Euclidean algorithm works
The Euclidean algorithm rests on one fact: gcd(a, b) = gcd(b, a mod b). You divide the larger number by the smaller, keep the remainder, and repeat with the divisor and the remainder until the remainder is 0. The last non-zero remainder is the gcd.
The extended version also writes every remainder as a combination of the original numbers, ri = si·a + ti·b. It starts with two rows, r0 = a (s = 1, t = 0) and r1 = b (s = 0, t = 1), and then applies the same update to all three columns:
When the remainder reaches 0, the row above it holds the gcd together with its coefficients x = s and y = t.
Worked example: gcd(240, 46)
i
Division
q
r
s
t
0
start
240
1
0
1
start
5
46
0
1
2
240 = 5·46 + 10
4
10
1
−5
3
46 = 4·10 + 6
1
6
−4
21
4
10 = 1·6 + 4
1
4
5
−26
5
6 = 1·4 + 2
2
2
−9
47
6
4 = 2·2 + 0
0
23
−120
The last non-zero remainder is 2, so gcd(240, 46) = 2 with x = −9 and y = 47. Check: 240 × (−9) + 46 × 47 = −2,160 + 2,162 = 2. The final row (23, −120) is a useful by-product: 240 × 23 − 46 × 120 = 0, and 23 = 46/2 and 120 = 240/2 are the steps of the general solution.
Where it is used
Modular inverses. If gcd(a, m) = 1, then a·x ≡ 1 (mod m). This is how the private exponent is computed in RSA key generation.
Linear Diophantine equations.a·x + b·y = c has whole-number solutions only when gcd(a, b) divides c; the coefficients give one solution directly.
Chinese remainder theorem. Combining congruences such as x ≡ 2 (mod 3) and x ≡ 3 (mod 5) needs inverses of one modulus modulo the other.
Fractions and ratios. Dividing by the gcd reduces a fraction to lowest terms.
Tip: the coefficients this method returns are the "minimal" ones, with |x| ≤ b/(2g) and |y| ≤ a/(2g) in most cases, so they rarely grow larger than the inputs.
Frequently asked questions
What does the extended Euclidean algorithm do?
It finds the greatest common divisor of two integers a and b and, at the same time, two integers x and y such that a·x + b·y = gcd(a, b). The ordinary Euclidean algorithm only gives the gcd; the extended version keeps track of how each remainder is built from a and b.
What are Bézout coefficients?
They are the integers x and y in Bézout's identity a·x + b·y = gcd(a, b). They always exist when a and b are not both zero, but they are not unique: if (x, y) works, so does (x + k·b/g, y − k·a/g) for any integer k, where g is the gcd.
How do I find a modular inverse with this calculator?
Enter the number as a and the modulus as b. If gcd(a, b) = 1, the coefficient x satisfies a·x ≡ 1 (mod b), so x reduced modulo b is the inverse. For example, the inverse of 17 modulo 3120 is 2753, because 17 × 2753 = 46,801 = 15 × 3120 + 1. If the gcd is larger than 1, no inverse exists.
Why is one of my coefficients negative?
For positive a and b, one of x and y is almost always negative (or zero), because a·x + b·y has to come out as small as the gcd. That is expected. Adding b/g to x and subtracting a/g from y gives another valid pair if you prefer a positive x.
When does a·x + b·y = c have integer solutions?
Exactly when gcd(a, b) divides c. Then you multiply the Bézout coefficients by c / gcd(a, b) to get one solution, and the general solution adds multiples of b/g to x and subtracts the same multiples of a/g from y. If the gcd does not divide c, there are no whole-number solutions.
How many steps does the Euclidean algorithm take?
Very few. By Lamé's theorem the number of division steps is at most about five times the number of digits of the smaller number. The worst case is two consecutive Fibonacci numbers, such as 89 and 55, where every quotient is 1.
Can I use negative numbers or huge numbers?
Yes. The calculator works with exact integer arithmetic of any length up to 400 digits. With negative inputs it runs the algorithm on the absolute values and then flips the sign of the matching coefficient, so a·x + b·y = gcd still holds. The gcd itself is always reported as a non-negative number.
Are all the tools on FreeToolCabin tested for quality and accuracy?
Yes! Every tool on our site undergoes automated Q/A testing in real browser environments to ensure high precision, correct output, and zero errors. If you happen to spot a bug or have a suggestion, please contact us at [email protected] and our team will review it right away.