Extended Euclidean Algorithm Calculator
Find GCD and Bézout coefficients for two integers with step-by-step division table, back-substitution, and modular inverse when coprime.
What Is the Extended Euclidean Algorithm?
The extended Euclidean algorithm computes the greatest common divisor (GCD) of two integers and finds Bézout coefficients $s$ and $t$ such that $\gcd(a,b) = s \cdot a + t \cdot b$. It extends Euclid's classic GCD method with extra columns that track linear combinations.
Bézout's Identity
$$\gcd(a, b) = s \cdot a + t \cdot b$$Coefficients $s$ and $t$ may be negative. The step table shows each division: quotient, remainder, and updated $(s, t)$ pairs until the remainder reaches zero.
Applications
- Modular inverse for RSA and cryptography when $\gcd(a, m) = 1$
- Solving linear Diophantine equations
- Simplifying fractions by dividing numerator and denominator by GCD
- Competitive programming number theory problems
For basic GCD only, try the GCF Calculator or LCM Calculator.
Frequently Asked Questions
What is a modular inverse?
If $\gcd(a, m) = 1$, the modular inverse $x$ satisfies $a \cdot x \equiv 1 \pmod{m}$. The Bézout coefficient $s$ gives this inverse modulo $m$.
Do negative inputs work?
Yes. The algorithm uses absolute values internally, then adjusts Bézout coefficients to match the signs of the original integers.
What does it mean when GCD is 1?
GCD equal to 1 means the numbers are coprime (relatively prime). A modular inverse of $a$ modulo $b$ exists only in this case.
How is this different from the basic Euclidean algorithm?
The basic algorithm returns only GCD. The extended version also tracks how each remainder is built from the original inputs, producing Bézout coefficients.
Related Tools
Webp To Jpg Converter
CSS Background Image Generator
Reverse Binary Numbers
0-60 Quarter Mile Calculator
Golden Rectangle Calculator
Anagram Generator
Refine Image Edges
MD2 Hash Generator
Image Color Extractor
Argon2 Hash Generator
Convert List to Columns
Certificate of Deposit Calculator
Percent to Fraction Calculator
Extract JSON Keys
HTML Table Generator
Vigenere Cipher
Derivative Calculator
Upside Down Text
Blood Type Calculator
Fake Tweet Generator