Extended Euclidean Calculator Form
Formula Used
Core Identity
ax + by = gcd(a, b)
Division Step
ri-2 = qiri-1 + ri, where 0 ≤ ri < ri-1
Coefficient Update
si = si-2 - qisi-1
ti = ti-2 - qiti-1
The algorithm repeatedly divides and updates coefficients until the remainder becomes zero. The final nonzero remainder is the gcd, and the matching coefficients provide one Bézout solution.
How to Use This Calculator
- Enter two whole numbers in the input fields.
- Pick a preset if you want a fast example.
- Select the graph view you want to see.
- Add a custom report label for downloads if needed.
- Press the calculate button.
- Review the gcd, coefficients, identity check, and inverses.
- Study the step table to follow each quotient and remainder.
- Download the CSV or PDF report for later use.
Example Data Table
| Input a | Input b | gcd(a, b) | x | y | Identity | Inverse Note |
|---|---|---|---|---|---|---|
| 252 | 198 | 18 | 4 | -5 | 252×4 + 198×-5 = 18 | No inverse |
| 101 | 23 | 1 | -5 | 22 | 101×-5 + 23×22 = 1 | 101⁻¹ mod 23 = 18 |
| 84 | 33 | 3 | 2 | -5 | 84×2 + 33×-5 = 3 | No inverse |
Frequently Asked Questions
1. What does the extended Euclidean algorithm find?
It finds the greatest common divisor of two integers and also returns coefficients x and y such that ax + by equals the gcd.
2. Why are Bézout coefficients useful?
They help solve linear Diophantine equations, verify gcd relationships, and compute modular inverses in number theory and cryptography.
3. When does a modular inverse exist?
A modular inverse exists only when the two numbers are coprime, meaning their gcd is exactly 1.
4. Can this calculator handle negative integers?
Yes. The gcd is reported as a positive value, while the coefficients are adjusted so the identity still matches the original signed inputs.
5. What happens if one value is zero?
The gcd becomes the absolute value of the nonzero number. The coefficients are still produced so the Bézout identity remains valid.
6. Why does the step table matter?
It shows every quotient, remainder, and coefficient update. This makes the algorithm easier to learn, verify, and teach.
7. What does the verification box confirm?
It confirms that the returned coefficients satisfy ax + by = gcd(a, b). This is the key correctness check.
8. Where is this algorithm commonly applied?
It is used in modular arithmetic, RSA-style cryptography, coding theory, equation solving, and many number theory exercises.