Euclid’s algorithm finds the greatest common divisor (GCD) of two integers without factoring either one. Described in Book VII of Euclid’s Elements around 300 BCE, it is one of the oldest algorithms still in everyday use: it runs inside fraction libraries, cryptography software and computer algebra systems. This calculator lays out every division step in a table and, with the extended option, finds the Bézout coefficients and modular inverse that number theory and RSA encryption rely on.
How to use the Euclid’s algorithm calculator
- Enter two whole numbers, up to 40 digits each. Negative numbers and zero are allowed (but not both zero).
- Leave extended algorithm ticked to see the coefficients x and y with a·x + b·y = gcd(a, b).
- Read the GCD on the tape, then follow the division steps below it. The table lists each dividend, divisor, quotient and remainder.
The algorithm
Each step uses the division identity, dividend = quotient × divisor + remainder:
Repeat with (b, r) until the remainder is 0. The divisor at that moment is the GCD.
Worked example: gcd(1071, 462)
1,071 = 2 × 462 + 147
462 = 3 × 147 + 21
147 = 7 × 21 + 0
Last non-zero remainder: gcd(1071, 462) = 21
Check: 1,071 = 21 × 51 and 462 = 21 × 22, and 51 and 22 share no common factor.
Extended version: working backward
Rewrite each step to isolate the remainder, then substitute upward:
21 = 462 − 3 × 147
147 = 1,071 − 2 × 462, so 21 = 462 − 3 × (1,071 − 2 × 462)
21 = 7 × 462 − 3 × 1,071
Bézout coefficients: x = −3 (for 1,071), y = 7 (for 462)
The calculator computes the same coefficients going forward, keeping a running pair of multipliers next to each remainder, which avoids the back-substitution.
Why it’s so fast
Every two steps at least halve the remainder, so the number of steps grows with the number of digits, not with the size of the number. Gabriel Lamé proved in 1844 that the step count never exceeds five times the number of decimal digits of the smaller input. The worst case is a pair of consecutive Fibonacci numbers, where every quotient is 1:
| Pair | Steps |
|---|---|
| 21, 13 | 6 |
| 144, 89 | 10 |
| 832,040, 514,229 | 28 |
Even 40-digit inputs finish in under 200 steps, which is why this method beats factoring by an enormous margin. Explore the sequence itself with the Fibonacci calculator.
Uses of the Euclidean algorithm
- Simplifying fractions and ratios: divide by the GCD. The GCF calculator applies the algorithm to longer lists of numbers.
- Least common multiple: LCM(a, b) = a × b ÷ gcd(a, b) — see the LCM calculator.
- Modular inverses: solving 3x ≡ 1 (mod 11) gives x = 4. RSA key generation uses exactly this step. Pair it with the modulo calculator.
- Linear Diophantine equations: 1,071x + 462y = c has whole-number solutions only when 21 divides c.
The subtraction version
Euclid’s original description used repeated subtraction: replace the larger number by the difference until both are equal. It gives the same answer — 1,071 − 462 = 609, 609 − 462 = 147, and so on — but division compresses many subtractions into one step.
Frequently asked questions
How does the Euclidean algorithm work?
Divide the larger number by the smaller and keep the remainder. Replace the larger number with the smaller one and the smaller with the remainder, and repeat. When the remainder reaches 0, the last non-zero remainder is the GCD. For 1071 and 462 the remainders are 147, 21 and 0, so the GCD is 21.
Why does the Euclidean algorithm work?
Any number that divides both a and b also divides a − q·b, which is the remainder. So a and b have exactly the same common divisors as b and the remainder. The pair keeps shrinking but its GCD never changes, until one number is 0 and the other is the GCD.
What is the extended Euclidean algorithm?
A version that also finds integers x and y with a·x + b·y = gcd(a, b). For 1071 and 462, x = −3 and y = 7, because 1071 × (−3) + 462 × 7 = 21. Those x and y are called Bézout coefficients.
How do I find a modular inverse with Euclid's algorithm?
If gcd(a, m) = 1, the extended algorithm gives a·x + m·y = 1, so a·x ≡ 1 (mod m) and x (reduced mod m) is the inverse of a. For example, 3 × 4 = 12 ≡ 1 (mod 11), so 4 is the inverse of 3 modulo 11.
How many steps does the algorithm take?
Very few. The number of steps is at most about five times the number of digits in the smaller number. The slowest cases are consecutive Fibonacci numbers, such as 832,040 and 514,229, which need 28 steps.