Extended Euclidean algorithm calculator
Enter two integers a and b. The calculator runs the extended Euclidean algorithm and returns the gcd, the coefficients x and y with a·x + b·y = gcd(a, b), every step of the table and, when it exists, the inverse of a modulo b.
Runs in your browser: nothing you enter is sent anywhere.
How to use it
- Type a and b.
- Read the gcd and the identity a·x + b·y = gcd. Open the table to see every division step. The last two lines give modular inverses where they exist.
How it works
Rows start as (r, s, t) = (a, 1, 0) and (b, 0, 1). Each new row subtracts q times the row before it, where q is the integer quotient of the two previous remainders. When the remainder reaches 0 the row above is the answer. Numbers are big integers, so 60-digit inputs stay exact. Related: GCD and LCM calculator, modulo calculator, Euler’s totient.
Worked example
a = 240, b = 46:
| q |
r |
s |
t |
| – |
240 |
1 |
0 |
| – |
46 |
0 |
1 |
| 5 |
10 |
1 |
−5 |
| 4 |
6 |
−4 |
21 |
| 1 |
4 |
5 |
−26 |
| 1 |
2 |
−9 |
47 |
| 2 |
0 |
|
|
The gcd is 2 and 240·(−9) + 46·47 = −2160 + 2162 = 2.
Tips
Frequently asked questions
What is Bézout's identity?
For any integers a and b, not both 0, there are integers x and y with a·x + b·y = gcd(a, b). The extended Euclidean algorithm finds one such pair. For 240 and 46 it gives 240·(−9) + 46·47 = 2.
How does the algorithm work?
It runs the ordinary Euclidean division steps r = prev − q·current and carries two more columns along, s and t, updated with the same quotients, starting from (1, 0) and (0, 1). In every row r = a·s + b·t, and when the remainder reaches 0 the previous row holds the gcd and the coefficients.
How do I find a modular inverse?
The inverse of a modulo m exists only if gcd(a, m) = 1. Then a·x + m·y = 1, so a·x ≡ 1 (mod m), and x reduced to 0…m−1 is the inverse. For 3 and 7: 3·5 = 15 = 2·7 + 1, so the inverse of 3 mod 7 is 5.
Are the coefficients unique?
No. If (x, y) works, so does (x + k·b/g, y − k·a/g) for any integer k. The tool shows the pair the standard algorithm produces.
Can I use negative numbers?
Yes. The identity then holds with the signs given, and the modular inverse uses the size of the modulus. Inverses are returned in the range 0…m−1.