Greatest Common Divisor and Least Common Multiple

Two whole numbers can share a surprising amount of hidden structure. The greatest common divisor (GCD) captures the largest chunk two numbers have in common, while the least common multiple (LCM) captures the smallest number they can both grow into. These twin ideas quietly power everything from reducing fractions and syncing calendars to the internals of modern cryptography. Better still, one of them — the GCD — can be found by an algorithm so elegant and so old that it has been in continuous use for more than two thousand years.

This page teaches you not just the recipes but why they work, so you can compute GCDs and LCMs quickly, check your answers, and understand the deep relationship that ties the two together.

Learning Objectives

• Define the GCD and LCM precisely and recognise them in fraction, scheduling, and factoring problems.
• Compute both using prime factorization.
• Compute the GCD using the Euclidean algorithm and explain why it always terminates.
• Use the identity $\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b$ to get one from the other.
• Recognise coprime (relatively prime) numbers and their special properties.
• Apply GCD and LCM to real problems: reducing fractions, adding fractions, and scheduling.

Quick Answer

The GCD of two integers is the largest positive integer that divides both of them; the LCM is the smallest positive integer that both of them divide. You can find either by prime factorization: for the GCD take each shared prime to its lowest power, and for the LCM take each prime to its highest power. For the GCD there is a much faster route, the Euclidean algorithm: repeatedly replace the larger number by its remainder on division by the smaller, until the remainder is zero — the last nonzero remainder is the GCD. The two quantities are locked together by the beautiful identity $\gcd(a,b)\times\operatorname{lcm}(a,b) = a\times b$, so once you have one you get the other instantly.

Where It Came From

The need for the GCD is as old as the need to compare quantities. The ancient Greeks did not think in terms of numbers alone; they thought geometrically, in terms of lengths. A central question was whether two lengths were commensurable — that is, whether some common unit could measure both an exact whole number of times. Finding the greatest such common measure is exactly the problem of finding the GCD.

The method for doing this appears in Euclid's Elements (around 300 BCE), Book VII, Propositions 1 and 2, as the procedure of antanairesis — "repeated subtraction." To find the greatest common measure of two lengths, you repeatedly subtract the smaller from the larger; when the two become equal, that value is the greatest common measure. This is the Euclidean algorithm, and it is often cited as the oldest nontrivial algorithm still in everyday use. It almost certainly predates Euclid, who was compiling and systematising earlier knowledge rather than inventing it from scratch.

The genius of the method is what it avoids. There is no need to factor the numbers, which for large numbers is extremely hard. By trading the large problem for a smaller one at every step — replacing a pair by a strictly smaller pair — the algorithm grinds relentlessly down to the answer. Centuries later this same "reduce to a smaller instance" idea became a cornerstone of computer science, and the Euclidean algorithm is still taught as the archetype of a recursive procedure. It also generalises: the extended Euclidean algorithm, which tracks the arithmetic along the way, is the workhorse behind modular inverses in RSA encryption and countless other cryptographic systems.

Divisors, Multiples, and the Two Definitions

Before computing anything, get the two definitions crisp, because students constantly swap them.

A divisor (or factor) of $n$ is a number that divides $n$ with no remainder. A multiple of $n$ is a number you get by multiplying $n$ by an integer.

• The greatest common divisor $\gcd(a,b)$ is the largest number that is a divisor of both $a$ and $b$. Divisors are bounded above by the number itself, so a greatest one exists.
• The least common multiple $\operatorname{lcm}(a,b)$ is the smallest positive number that is a multiple of both $a$ and $b$. Multiples go up forever, so we want the least one.

Worked example. Take $12$ and $18$.

Divisors of $12$: $1, 2, 3, 4, 6, 12$. Divisors of $18$: $1, 2, 3, 6, 9, 18$. The common divisors are $1, 2, 3, 6$, and the greatest is $6$. So $\gcd(12,18) = 6$.

Multiples of $12$: $12, 24, 36, 48, \dots$ Multiples of $18$: $18, 36, 54, \dots$ The first value appearing in both lists is $36$. So $\operatorname{lcm}(12,18) = 36$.

Listing works for small numbers but collapses for large ones — hence the methods below.

Method 1: Prime Factorization

Every integer greater than $1$ factors uniquely into primes (the Fundamental Theorem of Arithmetic). That uniqueness is what makes this method reliable.

The rule:

• For the GCD, take every prime that appears in both factorizations, raised to the lowest power it has in either.
• For the LCM, take every prime that appears in either factorization, raised to the highest power it has in either.

Worked example. Find $\gcd(180, 168)$ and $\operatorname{lcm}(180,168)$.

Factor each:

$180 = 2^2 \times 3^2 \times 5$

$168 = 2^3 \times 3 \times 7$

Line up the primes $2, 3, 5, 7$:

Prime	Power in 180	Power in 168	Min (GCD)	Max (LCM)
2	2	3	2	3
3	2	1	1	2
5	1	0	0	1
7	0	1	0	1

GCD $= 2^2 \times 3^1 = 4 \times 3 = 12$.

LCM $= 2^3 \times 3^2 \times 5 \times 7 = 8 \times 9 \times 5 \times 7 = 2520$.

Check with the product identity: $\gcd \times \operatorname{lcm} = 12 \times 2520 = 30240$, and $180 \times 168 = 30240$. They match.

Why does taking the minimum give the GCD? A number divides both $180$ and $168$ exactly when its prime powers do not exceed either number's prime powers — so each prime is capped at the smaller exponent. The largest such number uses those caps exactly. The maximum rule for the LCM is the mirror image.

Method 2: The Euclidean Algorithm

Factoring large numbers is slow. The Euclidean algorithm sidesteps it entirely, using only division with remainder.

The key fact: $\gcd(a,b) = \gcd(b, r)$, where $r$ is the remainder when $a$ is divided by $b$. Intuitively, any number dividing both $a$ and $b$ must also divide $a - b$ (and hence the remainder $r$), so the pair $(a,b)$ and the pair $(b,r)$ share exactly the same common divisors — and therefore the same greatest one.

The procedure. Divide, take the remainder, repeat with the divisor and remainder, until the remainder is $0$. The last nonzero remainder is the GCD.

Worked example. Find $\gcd(1071, 462)$.

$1071 = 2 \times 462 + 147$ $462 = 3 \times 147 + 21$ $147 = 7 \times 21 + 0$

The last nonzero remainder is $21$, so $\gcd(1071, 462) = 21$.

Notice how fast this is — three divisions, no factoring. If you tried to factor $1071 = 3 \times 3 \times 7 \times 17$ and $462 = 2 \times 3 \times 7 \times 11$ by hand, the algorithm would still beat you, and the gap only widens for genuinely large numbers.

Why it always stops: each remainder is strictly smaller than the previous divisor and can never go below $0$. A strictly decreasing sequence of non-negative integers cannot go on forever, so a remainder of $0$ is guaranteed.

The Relationship Between GCD and LCM

The single most useful fact linking the two is:

$\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b$

This lets you compute the LCM the smart way: find the GCD (fast, via Euclid), then divide.

$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$

Worked example. Find $\operatorname{lcm}(1071, 462)$. We already found $\gcd = 21$.

$\operatorname{lcm}(1071, 462) = \frac{1071 \times 462}{21} = \frac{494802}{21} = 23562$

To avoid huge intermediate numbers, divide first: $462 / 21 = 22$, then $1071 \times 22 = 23562$. Same answer, easier arithmetic.

Why does the identity hold? For each prime, $\min(x,y) + \max(x,y) = x + y$ — the smaller and larger exponents always add up to the sum of the two exponents. Summing this over all primes says the exponents in $\gcd \times \operatorname{lcm}$ match the exponents in $a \times b$ prime by prime, so the two products are equal.

When $\gcd(a,b) = 1$ the numbers are called coprime (or relatively prime), and the identity collapses to $\operatorname{lcm}(a,b) = a \times b$. For example, $8$ and $15$ are coprime, so $\operatorname{lcm}(8,15) = 120$.

Real-World Applications

• Reducing fractions. To write $\tfrac{180}{168}$ in lowest terms, divide top and bottom by $\gcd = 12$: $\tfrac{15}{14}$. One GCD does the whole job.
• Adding fractions. The least common denominator is the LCM of the denominators. For $\tfrac{1}{6} + \tfrac{1}{4}$, $\operatorname{lcm}(6,4) = 12$, giving $\tfrac{2}{12} + \tfrac{3}{12} = \tfrac{5}{12}$.
• Scheduling and cycles. Two buses leave a depot every $12$ and $18$ minutes. They next leave together after $\operatorname{lcm}(12,18) = 36$ minutes. Gears, traffic lights, and planetary alignments follow the same LCM logic.
• Cryptography. The extended Euclidean algorithm computes modular inverses, a core step in RSA key generation. The plain Euclidean algorithm's speed is exactly why it scales to the huge numbers used in encryption.
• Tiling and packing. The largest square tile that exactly fills a $180 \times 168$ cm floor has side $\gcd(180,168) = 12$ cm.

Common Mistakes

Mistake 1: Swapping min and max. Students take the highest powers for the GCD. This gives the LCM instead. Why it's wrong: a common divisor cannot have more of a prime than the poorer of the two numbers has. Correction: GCD uses the minimum exponent (the "greatest common divisor" is at most as big as either number); LCM uses the maximum.

Mistake 2: Forgetting primes that appear in only one number when computing the LCM. For $\operatorname{lcm}(180,168)$, dropping the $5$ or the $7$ gives a number that isn't actually a multiple of both. Why it's wrong: the LCM must be divisible by each original number in full. Correction: include every prime from either factorization for the LCM. (For the GCD, by contrast, a prime in only one number contributes nothing.)

Mistake 3: Stopping the Euclidean algorithm too early or reading the wrong number. Some take the last quotient or the final remainder $0$ as the answer. Why it's wrong: the quotients are irrelevant to the GCD, and $0$ is never the answer. Correction: the GCD is the last nonzero remainder — the divisor in the step that produced remainder $0$.

Comparison and Connections

Feature	GCD	LCM
What it finds	Largest shared divisor	Smallest shared multiple
Prime-power rule	Minimum exponent	Maximum exponent
Size relative to inputs	$\le$ both numbers	$\ge$ both numbers
Fast algorithm	Euclidean algorithm	Via GCD, then divide
When numbers are coprime	Equals $1$	Equals $a \times b$

The GCD and LCM are dual notions — one reaches down to what two numbers share, the other reaches up to what contains them both. Both rest on the Fundamental Theorem of Arithmetic (unique prime factorization), which is why the prime-power rules are trustworthy. The Euclidean algorithm connects forward to modular arithmetic and its extended form to Bézout's identity, $\gcd(a,b) = ax + by$ for some integers $x, y$.

Practice Questions

Recall

State the definition of the GCD and of the LCM in one sentence each.

Answer: The GCD of two integers is the largest positive integer that divides both; the LCM is the smallest positive integer that is a multiple of both.

Understanding

Using prime factorization, find $\gcd(24, 36)$ and $\operatorname{lcm}(24, 36)$.

Answer: $24 = 2^3 \times 3$, $36 = 2^2 \times 3^2$. GCD $= 2^2 \times 3 = 12$. LCM $= 2^3 \times 3^2 = 72$. Check: $12 \times 72 = 864 = 24 \times 36$. Correct.

Application

Use the Euclidean algorithm to find $\gcd(252, 105)$, then find $\operatorname{lcm}(252,105)$.

Answer: $252 = 2 \times 105 + 42$; $105 = 2 \times 42 + 21$; $42 = 2 \times 21 + 0$. So $\gcd = 21$. Then $\operatorname{lcm} = \tfrac{252 \times 105}{21} = 252 \times 5 = 1260$.

Analysis

Explain why $\gcd(a,b)\times\operatorname{lcm}(a,b) = a\times b$ must hold, referring to prime exponents. Then show why it can fail if extended naively to three numbers.

Answer: For each prime, $\min(x,y)+\max(x,y)=x+y$, so multiplying GCD and LCM recovers exactly the exponents of $a\times b$. For three numbers the identity $\gcd(a,b,c)\times\operatorname{lcm}(a,b,c) = abc$ fails because $\min$ and $\max$ of three exponents need not sum to the total; e.g. for $a=b=c=2$, $\gcd = \operatorname{lcm} = 2$ but $2\times 2 = 4 \ne 8$.

FAQ

Is the GCD ever bigger than the numbers involved? No. A divisor of $n$ can be at most $n$, so $\gcd(a,b)$ is at most the smaller of $a$ and $b$. The LCM, conversely, is at least the larger of the two.

What is $\gcd(a, 0)$? It is $a$ (for $a \ne 0$), because every integer divides $0$, so the largest divisor of both $a$ and $0$ is just the largest divisor of $a$, namely $a$. This is exactly the terminating case of the Euclidean algorithm.

Do GCD and LCM work for more than two numbers? Yes. Extend the prime-power rules to all the numbers (min across all for GCD, max across all for LCM), or apply the Euclidean algorithm pairwise: $\gcd(a,b,c) = \gcd(\gcd(a,b), c)$.

Why is it called "Euclidean" if Euclid may not have invented it? Because its first surviving written statement is in Euclid's Elements. The naming honours the source we can point to, a common convention in the history of mathematics.

What does "coprime" mean and why does it matter? Two numbers are coprime when $\gcd = 1$ — they share no prime factors. It matters because their LCM is simply their product, and coprimality is the condition that makes fractions already reduced and makes modular inverses exist.

Quick Revision

• GCD = largest common divisor; LCM = smallest common multiple.
• Factorization: GCD takes the minimum prime exponents; LCM takes the maximum.
• Euclidean algorithm: replace $(a,b)$ with $(b,\ a \bmod b)$ until remainder $0$; GCD is the last nonzero remainder.
• Master identity: $\gcd(a,b)\times\operatorname{lcm}(a,b) = a\times b$, so $\operatorname{lcm} = \dfrac{a\times b}{\gcd}$.
• Coprime means $\gcd = 1$, and then $\operatorname{lcm} = a\times b$.
• GCD $\le$ smaller number; LCM $\ge$ larger number.

Related Topics

Prerequisites

• Divisibility and Primes
• Number Theory overview

Related Topics

• Fundamental Theorem of Arithmetic
• Modular Arithmetic

Next Topics

• Mathematics subject index