GCD (Greatest Common Divisor) and LCM (Least Common Multiple) are simple concepts that are often used in questions involving divisibility, fractions, ratios, and number relationships.

They underpin solutions in problems about simplifying fractions, detecting cycles, periodic patterns, and divisibility constraints. The rest of this chapter covers their definitions, the Euclidean algorithm, the Extended Euclidean variant, and modular inverse as one of its main applications.

Greatest Common Divisor (GCD)

The GCD of two integers a and b is the largest positive integer that divides both a and b without leaving a remainder.

For example:

Least Common Multiple (LCM)

The LCM of two integers a and b is the smallest positive integer that is a multiple of both a and b.

For example:

The key relationship between GCD and LCM is:

This means once you can compute GCD efficiently, LCM comes for free.

The naive way to find GCD is to list all divisors of both numbers and pick the largest common one. That works, but it is slow. The Euclidean algorithm is dramatically faster, and the idea is elegant.

The Key Insight

The Euclidean algorithm is based on one simple observation:

In words: the GCD of two numbers is the same as the GCD of the smaller number and the remainder when you divide the larger by the smaller. You keep reducing until the remainder hits zero, at which point the other number is the GCD.

Why Does This Work?

Here is the intuition. Suppose d divides both a and b. Then a = d * p and b = d * q for some integers p and q. The remainder a % b = a - k * b for some integer k, which equals d * p - k * d * q = d * (p - k*q). So d also divides the remainder. This means every common divisor of a and b is also a common divisor of b and a % b. The argument works in reverse too, so the two pairs have exactly the same set of common divisors, and therefore the same GCD.

Let us trace gcd(48, 18) through the Euclidean algorithm:

Each step replaces the larger number with the remainder, shrinking the problem until it vanishes. When the remainder is 0, the answer is the non-zero value.

The standard Euclidean algorithm finds gcd(a, b). The extended version goes further: it finds integers x and y such that:

This is known as Bezout's Identity, and it guarantees that such x and y always exist.

Why is this useful? The extended GCD is the backbone of:

The algorithm works by tracking the coefficients as we recurse. At the base case, gcd(a, 0) = a, so x = 1, y = 0 (since a · 1 + 0 · 0 = a). As we unwind, suppose the recursive call returned gcd = b · x1 + (a mod b) · y1. We need to express the same gcd as a · x + b · y. Substitute a mod b = a − (a / b) · b (where a / b is integer division):

gcd = b · x1 + (a − (a / b) · b) · y1 = a · y1 + b · (x1 − (a / b) · y1)

Reading off the coefficients of a and b:

We can verify: 48 · (-1) + 18 · 3 = -48 + 54 = 6.

Modular Inverse via Extended GCD

The modular inverse of a modulo m is an integer x such that a · x ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1. Fermat's little theorem gives a clean formula when m is prime (a^(m-2) mod m), but when m is composite, Extended Euclidean is the standard way.

From Bezout's identity, if gcd(a, m) = 1 then there exist integers x, y with a · x + m · y = 1. Reducing modulo m, the m · y term vanishes and we get a · x ≡ 1 (mod m), so x mod m is the inverse. The x from extended GCD can be negative; normalize with ((x % m) + m) % m.

Quick check: the inverse of 3 mod 11 should satisfy 3x ≡ 1 (mod 11). Extended GCD on (3, 11) returns gcd = 1, x = 4, y = -1 because 3 · 4 + 11 · (-1) = 1. So the inverse is 4, and indeed 3 · 4 = 12 ≡ 1 (mod 11).

Use this version whenever the modulus is composite (for example, mod 2^32 for hash tables, or mod n for cyclic structures with n not prime). For prime moduli, power(a, m - 2, m) from the modular arithmetic chapter is shorter and easier to remember.

LCM via GCD

The formula lcm(a, b) = (a * b) / gcd(a, b) is straightforward, but there is an important implementation detail. If a and b are large, their product a * b can overflow even a 64-bit integer. The safe way to compute it is:

By dividing first, you keep the intermediate value small. Since gcd(a, b) always divides a, the division is exact (no truncation issues).

GCD of an Array

To find the GCD of more than two numbers, use the property that GCD is associative:

This means you can fold (reduce) across an array, applying pairwise GCD:

The same pattern works for LCM of an array: lcm(a, b, c) = lcm(lcm(a, b), c).

The regular GCD trace is already shown in the diagram above. The extended version is worth tracing once because the backward pass is where the update rule earns its complexity. Goal: find x, y such that 48x + 18y = 6.

Below are complete implementations. Each includes: iterative GCD, recursive GCD, LCM, extended GCD, and GCD of an array.

Time Complexity

The Euclidean algorithm runs in O(log(min(a, b))) time.

Why? At each step, the remainder a % b is strictly less than b, and it can be shown that after two consecutive steps, the value of b is reduced by at least half. This means the number of steps is at most 2 * log2(min(a, b)), which is O(log(min(a, b))).

More precisely, the worst case occurs when a and b are consecutive Fibonacci numbers (for example, gcd(89, 55) takes the maximum number of steps for inputs of that size). This is because Fibonacci numbers produce the smallest possible remainders at each step, making the algorithm work the hardest.

Space Complexity

LCM Complexity

LCM is one GCD call plus constant-time arithmetic, so it is also O(log(min(a, b))).

GCD of Array

For an array of n elements, computing GCD requires n - 1 pairwise GCD calls. If the maximum element is M, the total time is O(n * log(M)).