Find the greatest common divisor of two numbers with Euclid’s 2,300-year-old algorithm — enter any two integers and see every division step. Free, fast, and mobile-friendly.
Home » Math Calculators » Euclid’s Algorithm Calculator
Over 2,300 years ago, Euclid wrote down a method for finding the greatest common divisor of two numbers that is still the fastest practical way to do it. No factoring, no prime lists, no trial division — just repeated division with remainders until one appears. Our free Euclid’s Algorithm Calculator runs that ancient procedure instantly: enter any two integers and it shows every division step plus the GCD, so you can watch two millennia of mathematics work in a fraction of a second.
The greatest common divisor (GCD) is the largest number that divides both inputs evenly. It sits at the heart of fraction simplification, modular arithmetic, cryptography, and scheduling problems. Finding it by factoring both numbers works for small values but collapses for large ones — try factoring a 12-digit number by hand. Euclid’s algorithm sidesteps factoring entirely, which is why it remains the standard method in every computer algebra system and cryptography library on earth.
The calculator accepts positive and negative integers (signs are ignored, since divisibility does not depend on them) and handles edge cases like zero explicitly. Each run displays the numbered division steps in the classic form a = b × q + r, ending with the last non-zero remainder — the GCD. Whether you are simplifying fractions, studying number theory, or implementing RSA key generation, this is the tool that shows the work behind the answer.
The algorithm rests on one beautiful fact: gcd(a, b) = gcd(b, r), where r is the remainder when a is divided by b. Any common divisor of a and b must also divide the remainder r = a − bq, and any common divisor of b and r must divide a = bq + r. The two pairs therefore share exactly the same common divisors — and the same greatest one. Each step replaces the pair (a, b) with the smaller pair (b, r), shrinking the problem while preserving the answer.
Because remainders keep getting strictly smaller, the process must terminate: eventually a remainder of zero appears, and at that point the divisor is the GCD. This is not an approximation or a heuristic — it is a proof by infinite descent that always finishes. Euclid presented it geometrically, as repeated subtraction of the smaller segment from the larger; the division version simply performs many subtractions at once via the quotient.
The efficiency is stunning. The number of steps never exceeds five times the number of digits of the smaller input — a result related to Fibonacci numbers (consecutive Fibonacci numbers are the slowest possible inputs). Two 100-digit numbers resolve in at most 500 quick divisions, while factoring either one would take longer than the age of the universe. This gap between division and factoring is literally what keeps RSA encryption secure.
That security connection is worth understanding. RSA key generation needs the GCD of huge numbers to equal 1 (the numbers must be coprime), and Euclid’s algorithm performs that check in milliseconds. Meanwhile, breaking RSA requires factoring a huge product — a problem with no known shortcut. The same humble remainder loop thus both builds modern cryptography and guards its locks, which is why every programmer meets Euclid in their first algorithms course.
gcd(a, b) = gcd(b, a mod b), repeating until the remainder is 0 — the last non-zero remainder is the GCD
Write each step as a = b × q + r. When r = 0, the current divisor b is the greatest common divisor.
Step 1: 1071 = 462 × 2 + 147. Step 2: 462 = 147 × 3 + 21. Step 3: 147 = 21 × 7 + 0. The last non-zero remainder is 21, so gcd(1071, 462) = 21. Three divisions replaced what would have been a tedious factoring job (1071 = 3 × 3 × 7 × 17 and 462 = 2 × 3 × 7 × 11, sharing 3 × 7 = 21).
Reduce 84/126. Run Euclid: 126 = 84 × 1 + 42; 84 = 42 × 2 + 0. GCD is 42. Divide top and bottom: 84/126 = 2/3. Two divisions and the fraction is in lowest terms — this is exactly what the calculator’s step display shows.
Find gcd(35, 64). Steps: 64 = 35 × 1 + 29; 35 = 29 × 1 + 6; 29 = 6 × 4 + 5; 6 = 5 × 1 + 1; 5 = 1 × 5 + 0. The GCD is 1, so 35 and 64 are coprime. Notice how the remainders shrink unevenly — the algorithm adapts to whatever the numbers give it.
Find gcd(0, 25). By definition, every number divides 0, so the greatest common divisor is simply 25. The calculator reports this directly without looping. (GCD(0, 0) is undefined and is flagged as an error.)
When generating RSA keys, software must verify that the public exponent e and φ(n) are coprime — that gcd(e, φ(n)) = 1. With φ(n) often hundreds of digits long, factoring is impossible, but Euclid’s algorithm confirms coprimality in a few hundred divisions. Every secure web connection you have ever made depended on this remainder loop running correctly in milliseconds.
A factory runs two machines on cycles of 48 and 180 minutes and wants both idle for maintenance at the same time. The cycles realign every lcm(48, 180) minutes, and lcm(a, b) = a × b / gcd(a, b). Euclid gives gcd(48, 180): 180 = 48 × 3 + 36; 48 = 36 × 1 + 12; 36 = 12 × 3 + 0, so GCD = 12 and LCM = 48 × 180 / 12 = 720 minutes (12 hours). Maintenance windows fall every 12 hours — computed with three divisions.
Tile layers use the same math physically. To tile a 1071 × 462 cm floor with the largest possible square tiles and no cutting, the tile side must divide both dimensions — the GCD, 21 cm. Euclid’s answer from Example 1 becomes a shopping list: 21 cm tiles, 51 along one wall and 22 along the other. Ancient geometry, modern hardware store.
Which inputs make Euclid’s algorithm work the hardest? The answer is consecutive Fibonacci numbers, like 89 and 55 or 233 and 144. Because each Fibonacci number is the sum of the two before it, every division step yields quotient 1 and the remainders descend exactly through the Fibonacci sequence — the slowest possible shrinkage. Lamé proved in 1844 that the number of steps never exceeds five times the number of decimal digits of the smaller number, and Fibonacci pairs are what attain that bound.
This worst case is still wonderfully fast: a 100-digit input needs at most 500 steps. Compare that with trial division, which might need 10^50 operations for the same input. The Fibonacci analysis was one of the first complexity results in the history of computing — an 1844 theorem about a 300 BCE algorithm that now describes software performance.
The connection runs even deeper. The quotients in Euclid’s steps are exactly the terms of the continued fraction expansion of a/b. For the golden ratio’s convergents (ratios of Fibonacci numbers), all quotients are 1 — the simplest infinite continued fraction, which is why the golden ratio is the “most irrational” number and Fibonacci pairs are Euclid’s hardest case. One algorithm ties together divisibility, continued fractions, and the golden ratio.
270 = 192 × 1 + 78; 192 = 78 × 2 + 36; 78 = 36 × 2 + 6; 36 = 6 × 6 + 0. GCD = 6. Check: 270 = 6 × 45 and 192 = 6 × 32, and 45 and 32 are coprime. Four quick divisions.
54321 = 12345 × 4 + 4941; 12345 = 4941 × 2 + 2463; 4941 = 2463 × 2 + 15; 2463 = 15 × 164 + 3; 15 = 3 × 5 + 0. GCD = 3. Factoring either number would have been far more work than these five divisions.
31 = 17 × 1 + 14; 17 = 14 × 1 + 3; 14 = 3 × 4 + 2; 3 = 2 × 1 + 1; 2 = 1 × 2 + 0. GCD = 1 — coprime, as expected for two distinct primes. Euclid never needed to know they were prime.
The extended Euclidean algorithm goes one step further: it finds integers x and y with ax + by = gcd(a, b) (Bézout’s identity). Working the steps of Example 1 backwards from 21 = 462 − 147 × 3, substituting 147 = 1071 − 462 × 2, yields 21 = 1071 × (−3) + 462 × 7. That “7” is the modular inverse of 462 modulo 1071 — the exact operation RSA key generation performs on hundred-digit numbers. The ordinary algorithm finds the GCD; the extended version finds the keys.
Use Euclid’s algorithm on (48, 18). Solution: 48 = 18 × 2 + 12; 18 = 12 × 1 + 6; 12 = 6 × 2 + 0. GCD = 6. Then reduce 18/48 to 3/8 using the GCD.
Use Euclid’s algorithm on (100, 75). Solution: 100 = 75 × 1 + 25; 75 = 25 × 3 + 0. GCD = 25. The LCM is 100 × 75 / 25 = 300.
Are 91 and 143 coprime? Solution: 143 = 91 × 1 + 52; 91 = 52 × 1 + 39; 52 = 39 × 1 + 13; 39 = 13 × 3 + 0. GCD = 13, so no — they share 13 (91 = 7 × 13, 143 = 11 × 13). Euclid caught the hidden factor without any factoring.
When Alice’s laptop generates an RSA key pair, it picks two large primes p and q, computes n = pq and φ(n) = (p−1)(q−1) — a number with 600+ digits — then chooses a public exponent e (often 65537) and must confirm gcd(e, φ(n)) = 1. Factoring φ(n) to check this is out of the question; instead, the library runs Euclid’s algorithm, which finishes in under a millisecond with a few hundred remainder steps.
If the GCD came back larger than 1, the key would be weak and the software would pick a new e. In practice it never happens with e = 65537 (a prime that rarely divides φ(n)), but the check is mandatory — and it is Euclid, unchanged for 23 centuries, doing the checking. The calculator above runs the identical loop on your inputs; only the digit count differs.
Euclid’s Algorithm Calculator computes the greatest common divisor of two integers by repeated division with remainder: replace (a, b) with (b, a mod b) until the remainder is zero; the last non-zero remainder is the GCD. It displays every step in a = b × q + r form, flags coprime pairs, and handles zero inputs by definition. The method needs no factoring and runs in at most five steps per digit of the smaller input.
Euclid’s algorithm finds the greatest common divisor (GCD) of two numbers by repeated division with remainder: replace the pair (a, b) with (b, a mod b) until the remainder is zero. The last non-zero remainder is the GCD. It needs no factoring and dates to around 300 BCE.
It uses the identity gcd(a, b) = gcd(b, r), where r is the remainder of a ÷ b. Since every common divisor of a and b also divides r, the GCD is preserved while the numbers shrink. Repeating until a zero remainder appears leaves the GCD as the final divisor.
21. The steps: 1071 = 462 × 2 + 147; 462 = 147 × 3 + 21; 147 = 21 × 7 + 0. The last non-zero remainder is 21, so gcd(1071, 462) = 21.
Factoring a large number requires trial division up to its square root, while Euclid needs at most five division steps per digit of the smaller input. For 100-digit numbers, that is a few hundred divisions versus up to 10^50 trial divisions — the gap that makes RSA encryption practical to build but infeasible to break.
Two numbers are coprime (relatively prime) if their GCD is 1 — they share no common factor greater than 1. Examples: 35 and 64, 17 and 31. Euclid’s algorithm detects coprimality the moment the remainders descend to 1.
It equals a (for a ≠ 0), because every number divides 0, so the greatest divisor of both is a itself. Only gcd(0, 0) is undefined. The calculator applies this definition directly.
It extends the basic algorithm to find integers x and y satisfying ax + by = gcd(a, b) (Bézout’s identity), by working the remainder steps backwards. The coefficient it produces is a modular inverse — the operation at the heart of RSA key generation.
Consecutive Fibonacci numbers, like 89 and 55: every quotient is 1, so the remainders shrink as slowly as possible. Even then, Lamé’s theorem guarantees at most five steps per digit of the smaller number — still extremely fast.
Cite this page as: Euclid’s Algorithm Calculator. Sigma Calculator. Retrieved October 9, 2026, from https://sigmacalculator.net/math-calculators/euclids-algorithm-calculator/
Last updated: October 9, 2026