Extended Euclidean Algorithm Calculator: Reading GCD and Bézout Coefficients Off One Table
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
An extended Euclidean algorithm calculator gives you three numbers instead of one. Feed it 240 and 46 and it returns gcd(240, 46) = 2, plus the pair x = −9 and y = 47 that makes 240(−9) + 46(47) = 2 true. Check it by hand: −2,160 + 2,162 = 2. The plain Euclidean algorithm would have stopped at the 2.
Those two extra numbers are the whole point. They are what turn a gcd into a modular inverse, an RSA private exponent, or a solution to 6x + 15y = 21. Below: what the extra columns actually compute, a sign pattern that catches arithmetic slips for free, why the coefficients your calculator prints may differ from your textbook’s and both still be right, how to aim the identity at any target c, and the two facts about running time that most treatments skip.
What the Two Extra Columns Carry
Ordinary Euclid keeps one column: the remainders, shrinking until one of them is 0. The extended version keeps three, and the two new ones answer a different question — not “what is left over?” but “how do I rebuild this remainder out of the two numbers I started with?”
Every row of the table stands for one true statement of the form r = s·a + t·b. Row 0 is a itself, so it starts at s = 1, t = 0. Row 1 is b, so it starts at s = 0, t = 1. After that each row is built from the two above it using the quotient q of that division, and the same recurrence applies to all three columns at once:
r(i) = r(i−2) − q × r(i−1)
s(i) = s(i−2) − q × s(i−1)
t(i) = t(i−2) − q × t(i−1)
That is why the coefficients are effectively free. You are not running a second algorithm; you are applying the identical subtraction to two more columns while the remainders do what they were going to do anyway. When the remainder finally hits 0, the row above it holds the gcd — and the s and t sitting on that row are your answer. Compare this with the plain greatest common factor calculator, which runs the same divisions and throws the bookkeeping away.
The Signs Alternate, and That’s a Free Error Check
Here is the s and t column for 240 and 46, in order:
| Division | Remainder | s (× 240) | t (× 46) |
|---|---|---|---|
| start | 240 | 1 | 0 |
| start | 46 | 0 | 1 |
| 240 = 5 × 46 + 10 | 10 | 1 | −5 |
| 46 = 4 × 10 + 6 | 6 | −4 | 21 |
| 10 = 1 × 6 + 4 | 4 | 5 | −26 |
| 6 = 1 × 4 + 2 | 2 | −9 | 47 |
Look down the s column: 1, 0, 1, −4, 5, −9. Now the t column: 0, 1, −5, 21, −26, 47. From the third row on, both columns flip sign on every single step, and the magnitudes never shrink. That isn’t a coincidence of this example — it holds for every input, and it falls straight out of the recurrence, because each row subtracts a positive multiple of a value with the opposite sign.
Use it. If you are working the table by hand and two consecutive s values share a sign, or a magnitude goes down instead of up, you have an arithmetic error in that row and you can stop and fix it rather than discovering it six rows later. The two columns also stay opposite to each other throughout, which is the second half of the same check.
Why Your Answer and the Textbook’s Answer Both Check Out
Students lose a lot of time to this: the calculator says x = −9, the worked solution in the book says x = 14, and neither is wrong. The Bézout coefficients are not unique. If (x₀, y₀) works, so does every pair of the form
x = x₀ + k × (b ÷ g)
y = y₀ − k × (a ÷ g)
for any integer k, where g is the gcd. The reason is short: you have added k(ab/g) to one product and subtracted the same k(ab/g) from the other, so the total cannot move. With a = 240, b = 46 and g = 2 the steps are 46 ÷ 2 = 23 and 240 ÷ 2 = 120:
| k | x | y | 240x + 46y |
|---|---|---|---|
| −1 | −32 | 167 | −7,680 + 7,682 = 2 |
| 0 | −9 | 47 | −2,160 + 2,162 = 2 |
| 1 | 14 | −73 | 3,360 − 3,358 = 2 |
| 2 | 37 | −193 | 8,880 − 8,878 = 2 |
The algorithm hands back one row of that infinite list — conventionally the one with the smallest magnitudes, which is what makes it the useful starting point. Which row you actually want depends on the job. Modular arithmetic wants the representative in the range 0 to n − 1, so you add the modulus until the coefficient is positive; that single adjustment is the whole difference between −367 and 2753 in the RSA example the modular inverse calculator walks through. Counting problems want the smallest non-negative x, which the k-stepper above finds directly.
Hitting a Target That Isn’t the GCD
Linear Diophantine equations ask for integer solutions to ax + by = c, and the extended Euclidean algorithm settles them completely in two moves. First, the existence test: a solution exists exactly when gcd(a, b) divides c. Nothing else matters. No search, no case analysis. Every value of ax + by is a multiple of the gcd, so a target that isn’t a multiple is simply unreachable.
Second, if it does divide, scale. Run the algorithm to get ax₀ + by₀ = g, then multiply both coefficients by c ÷ g. Take 240x + 46y = 18. Since g = 2 divides 18, multiply x₀ = −9 and y₀ = 47 by 9: x = −81, y = 423. Check: 240(−81) = −19,440 and 46(423) = 19,458, and 19,458 − 19,440 = 18. Try 240x + 46y = 7 instead and there is nothing to compute — the left side is always even and 7 isn’t.
The everyday version is a coin or packaging problem. Suppose you sell items in 6-unit and 15-unit packs and a customer wants exactly 21 units. gcd(6, 15) = 3, and 3 divides 21, so it is possible. The algorithm gives 6(−2) + 15(1) = 3; scaling by 7 gives x = −14, y = 7. A negative pack count is meaningless, so step k until x turns non-negative: the family is x = −14 + 5k, y = 7 − 2k, and k = 3 gives x = 1, y = 1. One pack of each. Notice how the divisibility test did the real work — this is the same criterion the divisibility calculator checks, applied to c and the gcd.
One warning about scaling. Multiplying x₀ and y₀ by c ÷ g inflates the coefficients, and for a large c that inflation is real: with c = 10⁶ the coefficients above become x = −4,500,000 and y = 23,500,000. They are still correct, but if the answer needs to be small, reduce with the k family afterwards rather than accepting whatever the scaling produced.
Lamé’s Theorem: The Slowest Inputs Are Always Fibonacci
In 1844 Gabriel Lamé proved the first non-trivial running-time bound in the history of algorithms: the Euclidean algorithm needs at most five times as many divisions as the smaller number has decimal digits. Two-digit inputs never take more than 10 steps. Four-digit inputs never take more than 20.
What makes the result memorable is which inputs actually reach the bound. They are always consecutive Fibonacci numbers, because those are precisely the pairs where every quotient comes out as 1 — the division removes as little as it possibly can, so the remainders shrink as slowly as arithmetic allows.
| Worst-case pair | Digits in the smaller | Divisions taken | Lamé’s bound |
|---|---|---|---|
| 13, 8 | 1 | 5 | 5 |
| 89, 55 | 2 | 9 | 10 |
| 987, 610 | 3 | 14 | 15 |
| 10946, 6765 | 4 | 19 | 20 |
The bound is close but never tight past a single digit, and real inputs are nowhere near it. The average number of divisions over random pairs grows like 0.843 × ln(n) + 1.47, which for four-digit numbers is about 9 — less than half the worst case, and the gap widens as the numbers grow. Run 240 and 46 through the calculator and you get 5 divisions against a bound of 10.
There is a small bonus in the Fibonacci case that is worth seeing once. Run the algorithm on 2584 and 1597 and the coefficients come back as 610 and −987 — Fibonacci numbers themselves, four places down the sequence. The structure is that self-similar. If you want to generate the pairs to test this, the Fibonacci calculator lists them directly.
The Quotient Column Is a Continued Fraction in Disguise
Take the quotients from the 240 and 46 run in order — 5, 4, 1, 1, 2 — and write them as a continued fraction. You get 240/46 = [5; 4, 1, 1, 2], meaning 5 + 1/(4 + 1/(1 + 1/(1 + 1/2))), which evaluates to 5.2173913…, exactly 240 ÷ 46. This is not a curiosity bolted on afterwards. The Euclidean algorithm is the continued fraction expansion; the quotients are the expansion’s terms by definition.
The payoff comes from the convergents — the fractions you get by truncating the expansion early. For [5; 4, 1, 1, 2] they are 5/1, 21/4, 26/5, 47/9, and 120/23. The last one is 240/46 in lowest terms, which is expected. The interesting one is the second-to-last: 47/9. Compare it with the coefficients the algorithm produced, x = −9 and y = 47. The denominator is |x| and the numerator is |y|, and that correspondence holds for every input, not just this one.
This is why the Bézout coefficients are as small as they are — they are the numerator and denominator of the best rational approximation to a/b with a denominator below b/g, which is a genuinely strong optimality property. It also gives you a second, independent way to compute them: build the convergents forward from the quotients and read off the penultimate one. The calculator above shows both, and highlights the convergent that matches. For the plain remainder arithmetic driving every quotient in that list, the modulo calculator is the simpler tool.
Zeros, Negatives, and the Cases an Extended Euclidean Algorithm Calculator Must Handle
Four inputs break naive code, and all four have clean answers:
- b = 0. gcd(a, 0) = |a|, and the identity is a(1) + 0(0) = |a| for positive a. The table never runs a division; row 0 is already the answer. Any implementation that divides before testing crashes here.
- Both zero. gcd(0, 0) = 0 by convention, and there is no meaningful coefficient pair — 0x + 0y is 0 whatever you choose. Treat it as a special case rather than a bug.
- Negative inputs. The gcd is defined on magnitudes, so gcd(−1234, 4321) = gcd(1234, 4321) = 1. Run the table on |a| and |b|, then flip the sign of x if a was negative and of y if b was negative. The identity survives untouched, because you flipped both the number and its multiplier.
- a smaller than b. Nothing special happens: the first quotient comes out as 0 and that row simply swaps the two values. It costs one wasted division and no library bothers to pre-sort for it. You can see it live by entering 17 and 3120.
Beyond those, the one substantive mistake is treating a coefficient as if it were a residue. The x that comes out of the table can be large and negative — for 17 and 3120 it is −367 — and it is a perfectly correct Bézout coefficient in that form. It only becomes a modular inverse after you reduce it into range. Mixing the two conventions is what produces answers that verify in one context and fail in another; the standard formulation of the algorithm returns the raw coefficient and leaves the reduction to you.
Once you are comfortable with the identity, most of number theory opens up from it. Coprimality becomes a one-line test, modular inverses become a sign fix-up, the Chinese Remainder Theorem calculator merges congruences by calling this algorithm once per pair, and lcm(a, b) = |ab| ÷ gcd(a, b) drops out of the same run — the least common multiple calculator is doing exactly that underneath. One table, five divisions, and a surprising amount of arithmetic falls out of it.
