Euclidean Algorithm Calculator
Enter two whole numbers to find the greatest common factor, and see the work. The calculator divides repeatedly until the remainder reaches 0, then runs the chain backwards for the Bézout coefficients x and y in ax + by = gcd(a, b) — and the modular inverse when the pair is coprime.
- Every division shown
- Bézout coefficients included
Euclidean Algorithm
LiveThe gcd, the Bézout coefficients and the inverse.
- Divisions needed
- —
- Coprime?
- —
- Bézout x
- —
- Bézout y
- —
Euclid's chain, step by step
The forward table shrinks the pair until a remainder hits 0. The back-substitution then rebuilds the greatest common divisor out of the two numbers you started with.
Forward: the divisions
Backward: building ax + by = gcd
What Is the Euclidean Algorithm?
The Euclidean algorithm is a method for finding the greatest common factor of two whole numbers by repeated division. Divide the larger number by the smaller, keep the remainder, and repeat with the divisor and that remainder. The moment a remainder reaches 0, the divisor used in that division is the answer.
Euclid recorded the method in the Elements, Book VII, around 300 BC, which makes it one of the oldest algorithms still in daily use. Modern cryptography runs it billions of times a day inside RSA key generation, unchanged in structure from the version Euclid wrote down.
The pair of numbers shrinks at every step, and the greatest common factor stays fixed all the way down:
Greatest common factor (GCF), greatest common divisor (GCD) and highest common factor (HCF) are 3 names for one number. The Euclidean algorithm produces that number whichever term a textbook uses.
Euclid's original version subtracts rather than divides, which is where the method started. Subtracting the smaller number from the larger and repeating reaches the same answer, and takes far longer: 1071 and 462 need 12 subtractions against 3 divisions. Division compresses a run of identical subtractions into a single quotient, and the sum of the quotients — 2 + 3 + 7 — gives back the subtraction count exactly.
How to Use the Euclidean Algorithm Calculator
To use the Euclidean algorithm calculator, enter the 2 whole numbers and read the greatest common factor. The answer and the full working appear together in 4 steps:
- Enter a in the first field. The order carries no weight — the calculator swaps the pair internally when b is larger.
- Enter b in the second field. Negative values are accepted and reduced to their magnitudes, since a greatest common divisor is always positive.
- Read the GCD in the headline, along with the number of divisions the chain needed and whether the pair is coprime.
- Open the working panel for the forward division table and the back-substitution table that produces x and y.
The calculator reports 6 results for every pair: the greatest common factor, the count of divisions, a coprime verdict, the Bézout coefficients x and y, the modular inverse when one exists, and the equation ax + by = gcd written out with your numbers substituted in. Numbers up to 60 digits are handled exactly, since the arithmetic runs in arbitrary-precision integers rather than floating point.
The tool works on whole numbers. The Euclidean algorithm extends to polynomials, where polynomial division replaces integer division and the degree falls at every step instead of the value — the polynomial remainder theorem calculator covers that case. For the greatest common factor of 3 or more numbers at once, the greatest common divisor of several numbers tool chains the operation across a list.
Euclidean Algorithm Formula
The Euclidean algorithm formula is gcd(a, b) = gcd(b, a mod b), applied until the second number reaches 0. The base case gcd(g, 0) = g ends the recursion and hands back the answer.
gcd(a, b) = gcd(b, a mod b) while b ≠ 0 gcd(g, 0) = g the stopping case each step writes a = q × b + r with 0 ≤ r < bThe formula holds for 1 reason: any number d that divides both a and b divides a − qb as well, and a − qb is exactly the remainder r. Every common divisor of (a, b) is therefore a common divisor of (b, r), and the argument runs in reverse too. The 2 pairs share an identical set of common divisors, so the largest member of that set survives every step untouched.
Termination follows from the remainder rule. Each remainder is smaller than the divisor that produced it and never drops below 0, so the sequence strictly decreases and has to reach 0 in a finite number of steps.
The extended Euclidean algorithm tracks 2 extra columns while the divisions run, and ends with the coefficients of Bézout's identity:
ax + by = gcd(a, b) Bézout's identity 1071(−3) + 462(7) = 21 for a = 1071, b = 462Those coefficients answer 3 further questions. Modular inverses fall straight out: reading ax + ny = 1 modulo n leaves ax ≡ 1 (mod n), so x inverts a whenever the pair is coprime. Linear Diophantine equations of the form ax + by = c have whole-number solutions exactly when gcd(a, b) divides c, and Bézout supplies the first one. The least common multiple comes from the same number: lcm(a, b) = a ÷ gcd(a, b) × b, which puts lcm(1071, 462) at 23562.
Speed is what keeps the algorithm in production code. Lamé's theorem caps the division count at roughly 5 times the digit count of the smaller input, so a 3-digit number such as 462 can never need more than about 15 divisions — and 1071 with 462 finishes in 3. The worst case is a pair of consecutive Fibonacci numbers, where every quotient comes out as 1 and no step removes more than it has to: 6765 and 4181 take 18 divisions. Factoring both numbers to compare their primes would be hopeless at cryptographic sizes, while the Euclidean algorithm on 2 thousand-digit numbers finishes in a few thousand divisions.
Every major language ships the algorithm.
Python has math.gcd(1071, 462),
C++ has std::gcd in
<numeric> since C++17,
Java has BigInteger.gcd,
and JavaScript takes 1 line:
Euclidean Algorithm Example
Finding the GCF of 1071 and 462 using the Euclidean algorithm takes 3 divisions and returns 21. Each line hands its divisor and remainder down to the line below, and the colours track where every number goes:
1071 = 2 × 462 + 147 462 becomes the dividend, 147 becomes the divisor 462 = 3 × 147 + 21 147 becomes the dividend, 21 becomes the divisor 147 = 7 × 21 + 0 remainder 0 — stop, and the divisor 21 is the GCF Reading the 4 steps in words: divide 1071 by 462 to get 2 remainder 147, replace the pair with 462 and 147, repeat until the remainder is 0, and take the last divisor. GCF(1071, 462) = 21, which checks out as 1071 = 21 × 51 and 462 = 21 × 22.
Running the chain backwards produces the Bézout coefficients. Start from the second-to-last line and substitute upwards, keeping 1071 and 462 intact rather than multiplying anything out:
The calculator carries those coefficients forward while the divisions run, which produces the same x and y without a separate backward pass.
| Pair | Divisions | GCF | Bézout identity |
|---|---|---|---|
| 1071, 462 | 3 | 21 | 1071(−3) + 462(7) = 21 |
| 240, 46 | 5 | 2 | 240(−9) + 46(47) = 2 |
| 270, 192 | 4 | 6 | 270(5) + 192(−7) = 6 |
| 3, 26 | 4 | 1 | 3(9) + 26(−1) = 1 |
| 17, 3120 | 5 | 1 | 17(−367) + 3120(2) = 1 |
| 6765, 4181 | 18 | 1 | Fibonacci pair — every quotient is 1 |
The 17 and 3120 row is the textbook RSA setup. A public exponent of 17 against a totient of 3120 gives gcd 1, so an inverse exists. The algorithm returns x = −367, and reducing that into the range 0 to 3119 gives the private exponent: −367 + 3120 = 2753, verified by 17 × 2753 = 46801 = 15 × 3120 + 1. Bézout coefficients are never unique — adding 3120 to x and subtracting 17 from y produces another valid pair, which is why the identity and the modular inverse are reported separately.
Common Euclidean Algorithm Mistakes
There are 5 common Euclidean algorithm mistakes, and 4 of them show up the moment the answer is checked against both original numbers.
Take the divisor from the line where the remainder is 0. The last remainder is 0 itself, which divides nothing — the number sitting in the divisor position is the greatest common factor.
147 = 7 × 21 + 0 GCF = 0
147 = 7 × 21 + 0 GCF = 21
Move the divisor into the dividend slot and the remainder into the divisor slot. Keeping the original dividend restarts the chain and loops forever rather than shrinking.
1071 = 2 × 462 + 147 1071 = 7 × 147 + 42 ← 1071 reused
1071 = 2 × 462 + 147 462 = 3 × 147 + 21 ← 462 moves up
Continue until the remainder is 0, and report 1 as the answer when the final divisor is 1. A remainder of 1 means one more division remains, and the pair turns out coprime.
Keep 1071 and 462 as symbols while substituting upwards. Multiplying 1071 − 2 × 462 into 147 collapses the expression back to a plain number and loses the coefficients the extended algorithm exists to find.
21 = 462 − 3 × 147 = 462 − 441 = 21 ← true, and useless
21 = 462 − 3 × (1071 − 2 × 462) = 7 × 462 − 3 × 1071 → x = −3, y = 7
Drop the signs before starting. gcd(−1071, 462) equals 21 rather than −21, since a greatest common divisor is defined as positive. The Bézout coefficients absorb the sign instead, which keeps ax + by = gcd correct.
Check any Euclidean algorithm answer in 2 divisions: divide each original number by the result and confirm both leave a remainder of 0. 1071 ÷ 21 = 51 and 462 ÷ 21 = 22 both come out exact, so 21 is a common divisor — and the algorithm guarantees no larger one exists. The remainder calculator runs either check on its own, and the divisibility rule checker confirms the same fact from the digits.