Euclidean algorithm
Reduce a greatest-common-divisor problem to smaller remainders.
Euclidean algorithm is one of 2 number theory formulas in the discrete math section of this library, and it is used at high school · university level.
Why euclidean algorithm works
Any number that divides both a and b also divides what is left after you subtract copies of b from a, which is the remainder. So the pair (b, a mod b) has exactly the same common divisors as the original pair, but the numbers are smaller. Repeating shrinks them fast without ever losing the answer.
What each symbol means
$a,b$ are integers, not both zero.
Euclidean algorithm: when it holds
Repeat until the remainder is zero; the last nonzero remainder is the positive gcd.
When it stops applying
The gcd of 0 and 0 is undefined, since every number divides zero and there is no greatest one. Every other pair is fine, including negatives once you take absolute values first, because divisibility does not care about sign.
Euclidean algorithm: a worked example
$\gcd(48,18)=\gcd(18,12)=\gcd(12,6)=6$.
The mistake to avoid
What people do: Students carry the quotient forward instead of the remainder.
Why it goes wrong: The quotient tells you how many times one number fits into the other, which throws away the very leftover that the method depends on.
Do this instead: Keep only the remainder each round. For 48 and 18: 48 leaves 12, then 18 leaves 6, then 12 leaves 0, so the answer is the last nonzero remainder, 6.
Euclidean algorithm: step by step
- Name the unknown, and the unit the answer has to come out in.
- Match the symbols to your values. $a,b$ are integers, not both zero.
- Check the conditions before substituting. Repeat until the remainder is zero; the last nonzero remainder is the positive gcd.
- Substitute, keep exact values to the last line, then test the sign, size, and unit against a rough estimate — the check that catches most discrete math slips.
Where this formula fits
- Subject
- Discrete Math formulas — 11 entries in this library
- Topic
- Number theory
- Level
- High school · University
Formulas are easiest to keep when they sit inside a method rather than on a list. Use the links below to see where euclidean algorithm comes from, to check a calculation against a tool, and to practise it until you can recall it without looking.
- Discrete Math Calculator — check your substitution and the value it produces.
- Study discrete math — the subject guide that explains the ideas these formulas compress.
- Discrete Math Practice — questions that make you retrieve the formula instead of recognising it.
- All 11 discrete math formulas — the full grouped reference, or the complete formula library.
Questions about euclidean algorithm
Is the answer the last remainder or the last nonzero one?
The last nonzero one. When a remainder of 0 appears, the number you were dividing by at that moment is the gcd, so the zero is the stop signal rather than the result.
How do I get the least common multiple from this?
Multiply the two numbers and divide by the gcd. For 48 and 18 that is 864 divided by 6, which is 144, and it saves you from factoring either number.
What is gcd(a, 0)?
It is a itself, since every number divides 0 evenly and a is the largest divisor of a. That case is what makes the recursion stop.
How many steps can the algorithm take?
Remarkably few. The remainders shrink at least as fast as the Fibonacci numbers grow, so even numbers with hundreds of digits finish in a few hundred steps, which is why the method underpins modern cryptography.