Engineering / Mathematics — Integer Algorithms
Euclid's Algorithm for Integer GCD
Euclid's algorithm for greatest common divisors, its correctness, and the Fibonacci worst case that bounds its iteration count.
Executive summary
Euclid's algorithm computes the gcd by repeatedly replacing the larger argument with its remainder modulo the smaller. It is among the oldest algorithms still in use and remains the method of choice.
Its efficiency is not obvious from the statement. The worst case is attained by consecutive Fibonacci numbers, and the iteration count is logarithmic in the operands.
Learning objectives
- State the algorithm and prove correctness from the gcd shift identity.
- Bound the number of iterations.
- Identify the Fibonacci worst case.
01The algorithm and its correctness
Euclidean algorithm
non-negative integers a, bgcd(a, b)- Given a ≥ b ≥ 0.
- While b ≠ 0:
- Compute r = a mod b.
- Set a = b, b = r.
- Return a.
O(len(a) · len(b)) bit operationsCorrectness
gcd(a, b) = gcd(b, a mod b).
Reason. Any common divisor of a and b divides a − qb = a mod b, and any common divisor of b and a mod b divides qb + (a mod b) = a. The two pairs have identical common divisors, hence the same greatest one.
Termination is immediate: the second argument strictly decreases and stays non-negative, so the loop cannot run forever. The remaining question is how fast it decreases.
02The iteration bound
Lamé's theorem
The number of division steps is at most about 4.8 · log₁₀(min(a,b)), and the worst case occurs when the inputs are consecutive Fibonacci numbers.
The mechanism is that each pair of consecutive steps at least halves the larger argument. If r = a mod b then either r < b/2 directly, or r ≥ b/2, in which case the next remainder is b mod r = b − r < b/2. Either way the value halves within two steps, giving a logarithmic bound.
03Variants
| Variant | Idea | When preferable |
|---|---|---|
| Classical | Division with remainder each step | Default; fewest iterations |
| Binary gcd | Remove factors of 2, subtract, halve | No division needed; good where division is costly |
| Lehmer | Operate on leading digits to batch several steps | Large multiprecision operands |
| Extended | Track Bezout coefficients alongside | When the coefficients are needed |
The binary variant replaces division with subtraction and shifting, which on some architectures is faster despite performing more iterations. Lehmer's variant is the standard choice for very large operands, batching many small-quotient steps using single-word arithmetic on the leading digits.
04Frequently asked questions
Why is the bit complexity quadratic rather than logarithmic?
Because there are O(len) iterations and each performs a division costing O(len²) in the worst case, but the total is O(len²) rather than O(len³) — the operands shrink, and summing the actual per-step costs telescopes. The careful analysis gives O(len(a) · len(b)).
Does the algorithm work for negative inputs?
After taking absolute values, yes. The gcd is defined to be non-negative, so the standard approach normalises signs on entry.
Is there anything asymptotically faster?
Yes. A divide-and-conquer variant based on the same idea as Lehmer's achieves essentially the cost of multiplication times a logarithmic factor, and is used in libraries for very large inputs. It is considerably more intricate.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 55-58.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.