Euclidean divisions
240 = 5 × 46 + 10
46 = 4 × 10 + 6
10 = 1 × 6 + 4
6 = 1 × 4 + 2
4 = 2 × 2 + 0
The last nonzero remainder is 2, so gcd(240, 46) = 2.
Extended Euclidean Algorithm Calculator with Bézout Coefficients
Enter two integers
Up to 500 digits each. Commas, spaces, or underscores may group digits in sets of three. At least one input must be nonzero.
Result and working
Your result will appear here.
With the starting values 240 and 46, select Calculate to get gcd = 2 and the identity 240(−9) + 46(47) = 2.
Advertisement
What does the extended Euclidean algorithm find?
The ordinary Euclidean algorithm repeatedly divides and keeps the remainder until it reaches zero. The last nonzero remainder is gcd(a, b). The extended version simultaneously tracks two coefficients for every remainder, producing integers x and y such that:
ax + by = gcd(a,b)
This equation is Bézout’s identity. The calculator always reports a non-negative GCD, including when one or both inputs are negative.
If a and b are coprime, their GCD is 1. In that case, x is an inverse of a modulo |b| when |b| > 1, after reducing x to the standard residue from 0 through |b| − 1.
How the coefficient recurrence works
- Start with remainders r0 = |a| and r1 = |b|.
- Start coefficient pairs at (1, 0) and (0, 1), so each initial remainder is already a linear combination.
- For each quotient q, update all three sequences with new = old − q × current.
- When the current remainder is zero, the preceding remainder and coefficient pair give the GCD identity.
- Adjust coefficient signs to match the original signed inputs.
Maintained invariant
ri = |a|si + |b|ti
For quotient qi:
ri+1 = ri−1 − qiri
si+1 = si−1 − qisi
ti+1 = ti−1 − qiti
Worked example: 240 and 46
Bézout identity
Tracking the coefficient recurrences gives x = −9 and y = 47:
240(−9) + 46(47)
= −2,160 + 2,162
= 2
The pair is not unique; it is one compact solution returned by the algorithm.
Signs, zeros, and all coefficient solutions
| Input case | Calculator convention |
|---|---|
| Negative input | Compute with absolute values, then change coefficient signs so the displayed identity uses the original inputs. |
| Exactly one zero | gcd(a, 0) = |a| and gcd(0, b) = |b|, with a direct valid coefficient pair. |
| Both inputs zero | Rejected as undefined for this tool. |
| All solutions | If (x0, y0) is shown and d = gcd(a, b), then x = x0 + k(b/d) and y = y0 − k(a/d) for any integer k. |
Extended Euclidean algorithm FAQ
What are Bézout coefficients?
They are integers x and y that express the GCD as ax + by. The algorithm returns one valid pair; infinitely many pairs exist whenever a and b are not both zero.
Are Bézout coefficients unique?
No. Starting from one pair (x0, y0), add k(b/d) to x and subtract k(a/d) from y, where d is the GCD and k is any integer.
When can I use a coefficient as a modular inverse?
If gcd(a, m) = 1 and |m| > 1, the coefficient multiplying a in ax + my = 1 is an inverse of a modulo |m|. The result panel shows its least non-negative residue.
Can the inputs be negative or zero?
Yes. Either input can be negative or zero, and the GCD remains non-negative. At least one integer must be nonzero.
Why might another calculator give different coefficients?
Bézout coefficient pairs are not unique. Different division conventions or equivalent solution shifts can produce different x and y while still satisfying the same identity.
How large can the inputs be?
Each signed integer may contain up to 500 digits after grouping separators are removed. Exact BigInt arithmetic avoids floating-point rounding. Very long step tables are abbreviated on screen while the GCD and coefficients remain exact.
Are my inputs private?
Yes. The calculator performs validation and arithmetic entirely in your browser and does not upload, store, or place the integers in the page URL.