GCD Calculator with Euclidean Algorithm Steps
Find the greatest common divisor with every Euclidean algorithm step, Bézout coefficients x and y, the LCM and the modular inverse when it exists.
This GCD calculator finds the greatest common divisor of two integers with the Euclidean algorithm and shows every division step, set out the way number theory and programming courses present it. It also runs the extended algorithm to give the Bézout coefficients x and y with ax + by = gcd(a, b), and the modular inverse when the numbers are coprime. Add more integers to reduce a whole list.
How to use this tool
- Enter the two integers a and b.
- Optionally list more integers to include in the GCD and LCM.
- Read the GCD, then follow the Euclidean steps in the table.
- Use the Bézout coefficients or the modular inverse for Diophantine equations and cryptography exercises.
Formula
gcd(a, b) = gcd(b, a mod b), repeated until the remainder is 0
Each step replaces the larger number with the remainder left after dividing it by the smaller one, and the last non-zero remainder is the GCD. Working the steps backwards gives integers x and y with a·x + b·y = gcd(a, b) — Bézout’s identity — and lcm(a, b) = |a × b| ÷ gcd(a, b).
Example
For a = 1071 and b = 462: 1071 = 2 × 462 + 147, then 462 = 3 × 147 + 21, then 147 = 7 × 21 + 0. The last non-zero remainder gives gcd = 21. Back-substituting gives 21 = 1071 × (−3) + 462 × 7, so x = −3 and y = 7, and the LCM is 1071 × 462 ÷ 21 = 23,562.
Frequently asked questions
Why is the Euclidean algorithm so fast?
The remainder at least halves every two steps, so the number of steps grows with the number of digits rather than the size of the numbers. Even 15-digit inputs finish in well under 100 steps.
What does coprime mean?
Two integers are coprime, or relatively prime, when their GCD is 1, as with 8 and 15. Only then does a have an inverse modulo b.
How do I get a modular inverse from this?
When gcd(a, b) = 1, the coefficient x satisfies a·x ≡ 1 (mod b). For a = 3 and b = 11 the inverse is 4, since 3 × 4 = 12 = 11 + 1.
Does the sign of the numbers matter?
The GCD of a nonzero list is positive, so gcd(−12, 18) = 6. The Bézout coefficients are adjusted so the identity still holds with the signs you entered.
Last updated: 2026-10-30