What is the greatest common divisor?

The largest whole number that divides every one of the given numbers with nothing left over. For 12 and 18 it is 6, since 6 divides both while nothing bigger does. It is also called the highest common factor, and the two names mean exactly the same thing — British textbooks tend to use one and American ones the other.

How does Euclid’s algorithm work?

Divide the larger number by the smaller, keep the remainder, and repeat with the smaller number and that remainder. Stop when the remainder is zero; the previous remainder is the gcd. The reason it is safe is that any number dividing a and b also divides a − qb, and conversely — so the pair (a, b) and the pair (b, a mod b) share exactly the same divisors. Nothing is lost at any step, and the numbers shrink quickly.

Why not just factorise both numbers?

Because factorising is enormously harder. Trial division needs roughly √n steps, so a sixteen-digit number takes about 10⁸ divisions — while Euclid finishes the same pair in around six. The gap widens with size: Euclid is logarithmic in the inputs and factoring is not. This is why the gcd of two numbers far too large to factor can still be computed instantly, which matters a great deal in cryptography.

How do I find the gcd of three or more numbers?

Take the gcd of the first two, then the gcd of that with the third, and so on. The order makes no difference to the result — folding a list pairwise in any sequence gives the same answer, which was confirmed here across twenty thousand random quadruples in three different orders with no disagreements. The same folding works for the lcm.

When does gcd × lcm = the product fail?

As soon as you have more than two numbers, unless they happen to be pairwise coprime. For two it is always exact. For three, gcd(2,3,4) × lcm(2,3,4) is 1 × 12 = 12, while 2 × 3 × 4 is 24. Across forty thousand random triples the identity held precisely when the three were pairwise coprime and failed otherwise, with no exceptions either way. The rule that does generalise is messier: lcm(a,b,c) = abc·gcd(a,b,c) ÷ (gcd(a,b)·gcd(b,c)·gcd(a,c)).

What is Bézout’s identity?

That the gcd of two numbers can always be written as ax + by with x and y whole numbers, possibly negative. For 1071 and 462 it is 1071(−3) + 462(7) = 21. The coefficients come out of running Euclid’s divisions backwards, substituting each remainder in terms of the two numbers above it. The practical payoff is modular inverses: when the gcd is 1, the coefficient of a is the inverse of a modulo b, which is the step RSA decryption depends on.

What does it mean for numbers to be coprime?

Their gcd is 1 — they share no factor above 1, though neither need be prime itself. 8 and 15 are coprime despite both being composite. When two numbers are coprime their lcm is simply their product, and a fraction with coprime numerator and denominator is already in lowest terms. Note that a set can be coprime overall while some pair within it is not: 6, 10 and 15 have gcd 1, yet every pair shares a factor.

What is the gcd of a number and zero?

The number itself. Every whole number divides zero exactly — zero divided by anything is zero with no remainder — so zero contributes no restriction, and the largest common divisor is whatever the other number allows. This makes gcd(a, 0) = a, which is precisely the stopping condition Euclid’s algorithm reaches. The single exception is gcd(0, 0), which has no value at all, since every number divides both and there is no largest.

How do I use the gcd to simplify a fraction?

Divide the numerator and denominator by it, once. That gives lowest terms immediately, without repeatedly cancelling small factors and hoping you have finished. For 462/1071 the gcd is 21, so it becomes 22/51 — and 22 and 51 are coprime, which is what guarantees nothing more can be cancelled. Any remaining common factor would have been part of the gcd already.

GCD Calculator

The greatest common divisor is the largest whole number dividing all of them, and the way to find it is not to factorise. Euclid's method is to divide, keep the remainder, and repeat. When the remainder reaches zero, the previous one is the answer. It works because any number dividing both a and b ...

Euclid’s algorithm does not need the factors. Divide, keep the remainder, repeat — the last non-zero remainder is the answer. Two sixteen-digit numbers resolve in about six steps, where factorising either one would take tens of millions of divisions. It is the oldest algorithm still in everyday use, and nothing has improved on it.

THE NUMBERS

GCD OF 1,071, 462

gcd

lcm

23,562

Every one of them is a whole number of 21s: 51, 22 respectively. Nothing larger divides them all. Euclid took 3 steps.

Step	Division	Remainder
1	1,071 = 2 × 462 + 147	147
2	462 = 3 × 147 + 21	21
3	147 = 7 × 21 + 0	0 — stop

3 steps against a bound of 15. Lamé proved in 1844 that the count never exceeds five times the number of digits in the smaller input, which here is 3 digits. The worst cases for any given size are consecutive Fibonacci numbers — gcd(75025, 46368) needs 23 steps, more than any random pair of that size manages. That bound is why Euclid stays fast on numbers far too large to factor.

Bézout: 1,071(−3) + 462(7) = 21. The gcd of any two numbers can always be written as a whole multiple of one plus a whole multiple of the other, and running the same divisions backwards produces the coefficients. It is what makes modular inverses computable, and so what makes RSA decryption possible at all.

THE ALGORITHM

Why it works. Any number dividing both a and b also divides their remainder, and any number dividing b and the remainder also divides a. So the pair (a, b) and the pair (b, a mod b) have exactly the same common divisors — replacing one with the other loses nothing while making the numbers smaller. Repeat and the smaller number reaches zero, at which point the other is the answer.

Euclid’s algorithm · exact for any size of input

Created with❤️byeaglecalculator.com

HOW TO USE

1
Enter two or more whole numbers. Signs are ignored, because divisibility does not care about them — if 3 divides 12 it divides −12 equally.
2
Read the division chain rather than just the answer. Each line is one step of the algorithm, and the last non-zero remainder is the result.
3
Compare the step count with the bound shown. Euclid finishes in at most five times the digit count of the smaller number, which is what keeps it fast on very large inputs.
4
With exactly two numbers you also get the Bézout coefficients — the whole multiples of each that add to the gcd. They are what modular inverses are built from.

REFERENCE FORMULAS

Rule	Formula	What it is for
Euclid’s algorithm	gcd(a, b) = gcd(b, a mod b)	Repeat until the remainder is zero. The last non-zero remainder is the answer.
Base case	gcd(a, 0) = a	Everything divides zero, so the other number is the largest common divisor.
Two numbers	gcd(a,b) × lcm(a,b) = a × b	Always true for exactly two. Do not extend it to three — see below.
Three numbers	gcd·lcm = abc only if pairwise coprime	gcd(2,3,4) × lcm(2,3,4) = 12, not 24. The two-number identity does not generalise.
Correct triple identity	lcm(a,b,c) = abc·gcd(a,b,c) ÷ (gcd(a,b)gcd(b,c)gcd(a,c))	Inclusion–exclusion on the exponents. Verified over 40,000 triples.
Several numbers	gcd(a,b,c) = gcd(gcd(a,b), c)	Fold pairwise. The order makes no difference to the result.
Bézout’s identity	gcd(a,b) = ax + by	Integers x and y always exist. The extended algorithm finds them.
Coprime	gcd(a, b) = 1	No common factor above 1. Then lcm is simply the product.
Scaling	gcd(ka, kb) = k · gcd(a, b)	A common factor pulled out of both stays a common factor.
Reducing a fraction	a/b ÷ gcd(a,b) on both	Dividing through by the gcd gives lowest terms in one step.
Lamé’s bound	steps ≤ 5 × digits of the smaller	Proved in 1844. Verified here across 200,000 random pairs with no violations.
Worst case	consecutive Fibonacci numbers	gcd(75025, 46368) needs 23 steps — more than any random pair of that size.
Against factoring	Euclid is logarithmic; factoring is not	A 16-digit pair resolves in about six steps rather than 10⁷ divisions.
Negatives and zero	gcd(−a, b) = gcd(a, b); gcd(0,0) undefined	Sign is irrelevant. Two zeros have no greatest common divisor at all.

FREQUENTLY ASKED QUESTIONS

RELATED CALCULATORS

5 to the Power of 2

Calculate instantly →

6 to the Power of 2

Calculate instantly →

6 to the Power of 9

Calculate instantly →

10 to the Power of 5

Calculate instantly →

MORE ALGEBRA CALCULATORS

24 Times Table

Calculate instantly →

Quadratic Equation Solver

Calculate instantly →

Logarithm Calculator

Calculate instantly →

Fraction Calculator

Calculate instantly →

Fraction Simplifier

Calculate instantly →

Linear Equation Solver

Calculate instantly →

25 Times Table

Calculate instantly →

26 Times Table

Calculate instantly →

27 Times Table

Calculate instantly →

Simultaneous Equations Solver (2×2)

Calculate instantly →

28 Times Table

Calculate instantly →

Exponent Calculator

Calculate instantly →

29 Times Table

Calculate instantly →

30 Times Table

Calculate instantly →

Times Tables Mega Calculator

Calculate instantly →

Square Root of 10

Calculate instantly →

Square Root of 1

Calculate instantly →

Square Root Mega

Calculate instantly →

Square Root of 2

Calculate instantly →

23 Times Table

Calculate instantly →

Was this calculator helpful?

Last updated: August 4, 2026 · Euclid’s algorithm with Bézout coefficients · gcd × lcm = ab holds for two numbers, not for three.