Euclid's algorithm: computing GCD in O(log n)

GCD (greatest common divisor) and LCM (least common multiple) are middle-school concepts, but computing them efficiently calls for a classic algorithm — Euclid’s method. This article walks through how it works and how to implement it.

GCD and LCM: definitions and the relationship

• GCD — the largest positive integer that divides both inputs.
• LCM — the smallest positive integer that is a multiple of both inputs.

They satisfy:

GCD(a, b) × LCM(a, b) = a × b

So if you can compute GCD efficiently, LCM is one division away. Computing GCD efficiently is the core problem.

Why not factor first?

“Factor both numbers and take common primes” is mathematically natural but expensive. Factoring large integers is hard (RSA security depends on it). For practical computation, you need a different approach.

Euclid’s algorithm

Described in Euclid’s Elements around 300 BC — one of the oldest algorithms still in active use.

Key fact:

GCD(a, b) = GCD(b, a mod b)   (when b ≠ 0)
GCD(a, 0) = a

Replacing one operand with the remainder doesn’t change the GCD. Apply repeatedly until you reach (g, 0).

Example: GCD(48, 36)

GCD(48, 36)
= GCD(36, 48 mod 36) = GCD(36, 12)
= GCD(12, 36 mod 12) = GCD(12, 0)
= 12

Three steps.

Example: GCD(1071, 462)

GCD(1071, 462)
= GCD(462, 147)
= GCD(147, 21)
= GCD(21, 0)
= 21

Four steps. Even with larger numbers, the iteration count stays small.

Complexity: O(log n)

Iterations grow logarithmically with the input magnitude:

• O(log min(a, b)) iterations.
• Each iteration: one modulo, ~O(1) for fixed-width ints (O((log n)²) for arbitrary-precision).

Worst case is consecutive Fibonacci numbers: GCD(F(n+1), F(n)) takes exactly n iterations (Lamé’s theorem).

Recursive implementation

function gcd(a, b) {
	if (b === 0) return a;
	return gcd(b, a % b);
}

Stack depth is O(log n), so recursion stays safe.

Iterative implementation

function gcd(a, b) {
	while (b !== 0) {
		[a, b] = [b, a % b];
	}
	return a;
}

Use this in languages without tail-call optimization.

LCM from GCD

function lcm(a, b) {
	return (a / gcd(a, b)) * b;
}

Compute a / gcd first to keep the intermediate value smaller and avoid overflow.

Extended Euclidean algorithm

Returns x, y such that a × x + b × y = gcd(a, b). Used in RSA key generation and modular inverse.

function extendedGcd(a, b) {
	if (b === 0) return { g: a, x: 1, y: 0 };
	const { g, x: x1, y: y1 } = extendedGcd(b, a % b);
	return { g, x: y1, y: x1 - Math.floor(a / b) * y1 };
}

More than two arguments

GCD is associative:

GCD(a, b, c) = GCD(GCD(a, b), c)

Reduce over an array:

function gcdAll(arr) {
	return arr.reduce(gcd);
}

Where this shows up

• Reducing fractions — divide numerator and denominator by their GCD.
• Cryptography — RSA key generation uses the extended version.
• Ratios — “12:18” simplifies to “2:3”.
• Aspect ratios — 1920×1080 reduces to 16:9 (GCD = 120).
• Modular arithmetic — solving congruences.

Pitfalls

• Negative inputs — -12 % 5 differs by language. GCD is defined for non-negative integers; take absolute values.
• Both zero — GCD(0, 0) is mathematically undefined; many implementations return 0 by convention.
• Big numbers — use BigInt or an arbitrary-precision library.

Summary

• Euclid’s algorithm is one of the oldest algorithms still relevant.
• GCD(a, b) = GCD(b, a mod b) repeatedly converges fast.
• O(log n) iterations.
• LCM falls out of GCD.
• The extended version is essential in RSA and modular inverses.

For quick GCD/LCM computation across multiple inputs, the GCD/LCM tool on this site does both.