Calculator Inputs
Example Data Table
| a | b | gcd(a, b) | x | y | Verification | Inverse of a mod b |
|---|---|---|---|---|---|---|
| 240 | 46 | 2 | -9 | 47 | 240(-9) + 46(47) = 2 | Not available |
| 35 | 12 | 1 | -1 | 3 | 35(-1) + 12(3) = 1 | 11 |
| 99 | 78 | 3 | -11 | 14 | 99(-11) + 78(14) = 3 | Not available |
| 17 | 43 | 1 | -5 | 2 | 17(-5) + 43(2) = 1 | 38 |
Formula Used
Euclidean recurrence:
ri-2 = qi ri-1 + ri
The process repeats until the final non-zero remainder is the greatest common divisor.
Coefficient recurrence:
snew = sold - q × s
tnew = told - q × t
The last stable coefficients satisfy ax + by = gcd(a, b).
Modular inverse condition:
If gcd(a, m) = 1, then the coefficient of a is an inverse modulo m.
Normalized inverse = ((x % m) + m) % m.
How to Use This Calculator
- Enter the first integer a and second integer b.
- Optionally add a custom modulus when you need the inverse of a under another modulus.
- Choose whether to normalize inverses into positive residues.
- Keep the step-table option enabled if you want a full quotient and remainder trace.
- Submit the form to display results directly below the header and above the form.
- Review the gcd, Bézout coefficients, identity check, lcm, and inverse availability.
- Export the summary and steps using the CSV or PDF buttons.
Frequently Asked Questions
1) What does the extended Euclidean algorithm find?
It finds the greatest common divisor of two integers and coefficients x and y that satisfy ax + by = gcd(a, b).
2) Why are the coefficients useful?
They prove the Bézout identity and help solve modular inverse problems, linear Diophantine equations, and number theory exercises.
3) When does a modular inverse exist?
An inverse exists only when the number and modulus are coprime. That means their gcd must equal exactly one.
4) Why can an inverse be negative before normalization?
The algorithm returns a valid coefficient. Negative values still work mathematically, but normalization converts them into the usual positive residue form.
5) Does the calculator work with negative integers?
Yes. It accepts negative whole numbers and still returns coefficients that verify the identity correctly.
6) What happens if both inputs are zero?
That case is invalid here because the gcd is not meaningful for two simultaneous zero inputs. The calculator blocks it.
7) Why is the lcm shown with the result?
The least common multiple is closely related to gcd through the product rule, so it is often helpful for verification and coursework.
8) What does the step table show?
It records each division, quotient, remainder, and coefficient update, making the full algorithm easy to audit, teach, and verify.