Last updated: 2026-05-13

Greatest common divisor and least common multiple

The greatest common divisor (GCD) of two positive integers is the largest integer that divides both of them without a remainder. The least common multiple (LCM) is the smallest positive integer that is a multiple of both. Together they describe how two numbers are arithmetically related.

For example, consider 12 and 8:

• The common divisors of 12 and 8 are 1, 2, and 4. The greatest is 4.
• The common multiples of 12 and 8 are 24, 48, 72, …. The least is 24.

Euclid's algorithm

A common method for finding the GCD is Euclid's algorithm, described in the Elements around 300 BCE. It rests on the identity:

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

where $a \bmod b$ is the remainder when $a$ is divided by $b$. The step repeats until the remainder is zero; the last non-zero value is the GCD.

Example: GCD(48, 18)

Step	$a$	$b$	$a \bmod b$
1	48	18	12
2	18	12	6
3	12	6	0

The last non-zero remainder is 6, so GCD(48, 18) = 6.

The algorithm is efficient: the number of steps never exceeds five times the number of digits in the smaller number.

The GCD–LCM identity

Given the GCD, the LCM follows from a single formula:

$\text{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$

This identity is a theorem that follows from the unique prime factorization of integers. Writing each number as a product of prime powers, the GCD takes the minimum exponent for each prime and the LCM takes the maximum; multiplying the two always reconstructs the product $a \times b$.

Example: LCM(12, 8)

$\text{GCD}(12, 8) = 4, \quad \text{LCM}(12, 8) = \frac{12 \times 8}{4} = 24$

Check: $4 \times 24 = 96 = 12 \times 8$. ✓

Applications

Simplifying fractions

Reducing $\dfrac{a}{b}$ to lowest terms divides both numerator and denominator by $\gcd(a, b)$. For example, $\dfrac{12}{8}$ simplifies to $\dfrac{3}{2}$ because $\gcd(12, 8) = 4$.

Adding fractions

Adding $\dfrac{1}{12} + \dfrac{1}{8}$ requires the least common denominator, which is $\text{LCM}(12, 8) = 24$:

$\frac{1}{12} + \frac{1}{8} = \frac{2}{24} + \frac{3}{24} = \frac{5}{24}$

Scheduling and cycles

When two events repeat every $a$ days and $b$ days respectively, they next coincide in $\text{LCM}(a, b)$ days. LCM appears for this reason in gear-ratio design, tile-pattern period calculations, and calendar problems such as the realignment of two periodic cycles.

Cryptography

The Euclidean algorithm is a core primitive in RSA encryption, where the GCD is used to verify that a chosen key exponent is coprime with the totient of the modulus.

Edge cases

• GCD(a, 0) = a for any positive a. This is the base case of Euclid's algorithm and follows naturally from the definition: every integer divides zero.
• Coprime numbers have GCD = 1 and LCM = a × b. For instance, GCD(7, 13) = 1, LCM(7, 13) = 91.
• Equal numbers: GCD(n, n) = n and LCM(n, n) = n.

Quick reference

Property	Formula
GCD via Euclid	$\gcd(a, b) = \gcd(b,\ a \bmod b)$
LCM from GCD	$\text{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$
Identity	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$
Simplify fraction	divide numerator and denominator by $\gcd$
Common denominator	use $\text{lcm}$ of the two denominators

Frequently Asked Questions (FAQ)

What is the greatest common divisor?

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both without a remainder. For example, GCD(12, 8) = 4 because 4 is the largest number that divides both 12 and 8 evenly.

What is the least common multiple?

The least common multiple (LCM) of two integers is the smallest positive integer divisible by both. For example, LCM(12, 8) = 24 because 24 is the smallest number that is a multiple of both 12 and 8.

How are GCD and LCM related?

For any two positive integers a and b: GCD(a, b) × LCM(a, b) = a × b. This means you can find one from the other: LCM = a × b ÷ GCD. This relationship is why the two measures are often calculated together.