The greatest common divisor (GCD) and the least common multiple (LCM) answer two complementary questions about how two integers relate to each other. The GCD asks how far two quantities can be split into equal, waste-free units at once; the LCM asks how long two repeating cycles must run before they line up again. The same pair of questions reappears throughout mathematics and everyday life: reducing a fraction to lowest terms, adding fractions with different denominators, scheduling recurring events, and, as shown further below, the core machinery behind modular inverses and several cryptographic constructions.
Divisors and Multiples
As introduced in Modulo and Divisibility, an integer \(d\) divides an integer \(a\), written \(d\mid a\), if \(a=dk\) for some integer \(k\). Whenever \(d\mid a\), \(a\) is equally called a multiple of \(d\). The greatest common divisor and least common multiple are simply the extreme cases of this relation shared by two numbers at once: the largest \(d\) that divides both, and the smallest \(m\) that both divide.
The Greatest Common Divisor
Picture two rods of length \(18\) and \(24\), to be cut into equal-length pieces with nothing left over from either rod. A piece of length \(d\) fits both exactly when \(d\mid18\) and \(d\mid24\) at once, i.e.\ when \(d\) is a common divisor of the two lengths. The longest such piece uses the fewest cuts and wastes nothing, and is the greatest common divisor — a notion of "common measure" going back to Euclid's Elements.
For integers \(a,b\), not both zero, the greatest common divisor \(\gcd(a,b)\) is the unique positive integer \(d\) such that:
- \(d\mid a\) and \(d\mid b\),
- if \(c\mid a\) and \(c\mid b\), then \(c\mid d\).
Equivalently, \(\gcd(a,b)\) is the largest common divisor in absolute value.
Basic Examples
\[ \gcd(18,24)=6, \qquad \gcd(35,64)=1, \qquad \gcd(0,15)=15. \]
The rods above cut down to pieces of length \(6\): three pieces from the rod of length \(18\) and four from the rod of length \(24\), with nothing left over from either. If \(\gcd(a,b)=1\), the numbers are called coprime: they share no common measure larger than a single unit.
The Least Common Multiple
Now picture two lamps, one blinking every \(6\) seconds and the other every \(8\) seconds, both starting together. They flash together again exactly when the elapsed time is a common multiple of \(6\) and \(8\) — a multiple of both blinking periods at once. The first time this happens is the least common multiple.
For positive integers \(a,b\), the least common multiple \(\operatorname{lcm}(a,b)\) is the unique smallest positive integer \(m\) such that \(a\mid m\) and \(b\mid m\).
Basic Example
The positive multiples of \(6\) are \(6,12,18,24,30,\ldots\), and those of \(8\) are \(8,16,24,32,\ldots\). The smallest number appearing in both lists is \(24\), so
\[\operatorname{lcm}(6,8)=24,\]
matching the two lamps above: they first blink together again after \(24\) seconds.
Core Properties
For integers \(a,b,k\):
\[ \gcd(a,b)=\gcd(|a|,|b|), \qquad \gcd(a,b)=\gcd(b,a), \]
\[ \gcd(a,0)=|a|, \qquad \gcd(ka,kb)=|k|\,\gcd(a,b), \]
\[ \gcd(a,b)=\gcd(a,b-a)=\gcd(a,b+ta) \quad(t\in\mathbb{Z}). \]
The last identity is the algebraic basis of the Euclidean algorithm.
Computing via Prime Factorization
The Fundamental Theorem of Arithmetic writes every positive integer uniquely as a product of prime powers,
\[n=\prod_p p^{\nu_p(n)},\]
where \(p\) ranges over all primes and \(\nu_p(n)\) is the exponent of \(p\) in \(n\) (taken as \(0\) for primes not appearing in \(n\)). Given \(a=\prod_p p^{\alpha_p}\) and \(b=\prod_p p^{\beta_p}\), a common divisor can use at most \(\min(\alpha_p,\beta_p)\) copies of each prime \(p\) — any more of some \(p\) and it would fail to divide whichever of \(a,b\) has the smaller exponent. Taking the largest allowed power of every prime gives the greatest common divisor:
\[\gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}.\]
Symmetrically, a common multiple needs at least \(\max(\alpha_p,\beta_p)\) copies of each prime \(p\) to be reachable from both \(a\) and \(b\), and taking the smallest sufficient power of every prime gives the least common multiple:
\[\operatorname{lcm}(a,b)=\prod_p p^{\max(\alpha_p,\beta_p)}.\]
Worked Example
For \(a=60\) and \(b=84\),
\[60=2^2\cdot3\cdot5,\qquad84=2^2\cdot3\cdot7.\]
Taking the smaller exponent of each prime that appears, \(2^{\min(2,2)}\cdot3^{\min(1,1)}\cdot 5^{\min(1,0)}=2^2\cdot3=12\), gives \(\gcd(60,84)=12\). Taking the larger exponent instead, \(2^{\max(2,2)}\cdot3^{\max(1,1)}\cdot5^{\max(1,0)}\cdot7^{\max(0,1)}=2^2\cdot3\cdot5\cdot7=420\), gives \(\operatorname{lcm}(60,84)=420\).
The Product Formula
For any two exponents, the smaller and the larger together always add up to their sum, \(\min(\alpha_p,\beta_p)+\max(\alpha_p,\beta_p)=\alpha_p+\beta_p\). Multiplying the prime factorizations of \(\gcd(a,b)\) and \(\operatorname{lcm}(a,b)\) prime by prime therefore reconstructs exactly \(a\cdot b\), giving the identity
\[\boxed{\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|}\qquad\text{hence}\qquad \operatorname{lcm}(a,b)=\frac{|ab|}{\gcd(a,b)}.\]
For \(a=12,b=18\): \(\gcd(12,18)=6\), so \(\operatorname{lcm}(12,18)=12\cdot18/6=36\); indeed \(6\cdot36=216=12\cdot18\). For large integers, computing \(a\cdot b\) first risks overflow long before the division brings the result back down, so it is safer to divide before multiplying:
\[\operatorname{lcm}(a,b)=\left|\frac{a}{\gcd(a,b)}\cdot b\right|,\]
which is always an exact division, since \(\gcd(a,b)\) divides \(a\) by definition. By convention, \(\operatorname{lcm}(a,0)=0\) for every \(a\) (zero is the only multiple of zero), and \(\gcd(0,0)=0\); the product formula is only meaningful when \(a\) and \(b\) are not both zero.
The Euclidean Algorithm
Prime factorization computes \(\gcd\) and \(\operatorname{lcm}\) in one clean step, but factoring large numbers is itself expensive. The Euclidean algorithm computes the greatest common divisor directly, without ever factoring anything, using only division with remainder:
\[ a=bq+r, \qquad 0\le r<|b|. \]
Every common divisor of \(a\) and \(b\) also divides \(r=a-bq\), and conversely every common divisor of \(b\) and \(r\) also divides \(a=bq+r\); so the pairs \((a,b)\) and \((b,r)\) share exactly the same common divisors, and in particular the same greatest one:
\[ \gcd(a,b)=\gcd(b,r). \]
Repeating this remainder step strictly decreases the second argument, so the process terminates.
gcd(a, b)
a = abs(a)
b = abs(b)
while b != 0
r = a % b
a = b
b = r
return a Worked Example
The Euclidean algorithm always repeats the same state transition, \((a,b)\mapsto(b,a\bmod b)\). For \(\gcd(252,198)\), the sequence is:
- Start: \((a,b)=(252,198)\).
- Compute remainder: \(252\bmod198=54\), next pair \((198,54)\).
- Compute remainder: \(198\bmod54=36\), next pair \((54,36)\).
- Compute remainder: \(54\bmod36=18\), next pair \((36,18)\).
- Compute remainder: \(36\bmod18=0\), next pair \((18,0)\).
- Stop condition \(b=0\): result \(\gcd(252,198)=18\).
Since factoring \(252\) and \(198\) was never needed, the least common multiple is cheapest to recover from the product formula rather than from scratch:
\[\operatorname{lcm}(252,198)=\frac{252\cdot198}{18}=2772.\]
Relation to Modulo
Each Euclidean step uses a remainder:
\[ r=a\bmod b. \]
So the GCD algorithm is a direct application of modulo arithmetic. The remainder rules behind each step are the rules of modulo and divisibility.
GCD and LCM Calculator (with Steps)
The calculator below computes \(\gcd(a,b)\) and \(\operatorname{lcm}(a,b)\), prints the Euclidean steps, and returns one Bézout representation \(ax+by=\gcd(a,b)\).
Ready. Bézout Identity
There exist integers \(x,y\) such that
\[ ax+by=\gcd(a,b). \]
This is Bézout's identity. It implies in particular:
\[ \gcd(a,b)=1 \iff \exists x,y\in\mathbb{Z}:\ ax+by=1. \]
Extended Euclidean Algorithm
The extended algorithm computes both \(\gcd(a,b)\) and Bézout coefficients \((x,y)\).
For the previous example:
\[ 18=54-36, \qquad 36=198-54\cdot3, \qquad 54=252-198. \]
Substitute backwards:
\[ 18=4\cdot252-5\cdot198. \]
So one Bézout pair is \((x,y)=(4,-5)\).
Coprimality and Divisibility
Coprimality interacts with divisibility in a way that fails badly without it. The key fact, sometimes called Euclid's lemma, follows directly from Bézout's identity:
If \(a\mid bc\) and \(\gcd(a,b)=1\), then \(a\mid c\).
Indeed, Bézout's identity gives integers \(x,y\) with \(ax+by=1\). Multiplying by \(c\) yields
\[ acx+bcy=c. \]
The term \(acx\) is divisible by \(a\), and \(bcy\) is divisible by \(a\) because \(a\mid bc\) by assumption; hence \(a\) divides their sum \(c\).
A second consequence covers two divisors of the same number at once:
If \(a\mid c\), \(b\mid c\), and \(\gcd(a,b)=1\), then \(ab\mid c\).
Write \(c=ak\) since \(a\mid c\). Then \(b\mid ak\), and since \(\gcd(a,b)=1\), Euclid's lemma (with the roles of \(a\) and \(b\) swapped) gives \(b\mid k\), say \(k=bj\). Hence \(c=ak=abj\), i.e. \(ab\mid c\).
Both statements genuinely need the coprimality hypothesis, as the following counterexamples show:
- \(6\mid(4\cdot9)\), but \(6\nmid4\) and \(6\nmid9\) — here \(\gcd(6,4)=2\ne1\), so Euclid's lemma does not apply.
- \(4\mid12\) and \(6\mid12\), yet \(4\cdot6=24\nmid12\) — here \(\gcd(4,6)=2\ne1\) again.
GCD and LCM of Several Numbers
Both operations extend to more than two numbers by repeated application,
\[\gcd(a_1,\ldots,a_n)=\gcd\bigl(\gcd(a_1,\ldots,a_{n-1}),a_n\bigr),\]
and likewise for \(\operatorname{lcm}\); the associativity established below guarantees this does not depend on the order in which the numbers are combined. For \(\gcd(24,36,60)\): \(\gcd(24,36)=12\), then \(\gcd(12,60)=12\), so \(\gcd(24,36,60)=12\). The prime-factorization view extends just as directly: taking the smallest exponent of each prime across all the numbers gives their combined GCD, and the largest exponent gives their combined LCM. For \(6=2\cdot3\), \(9=3^2\), \(12=2^2\cdot3\), and \(15=3\cdot5\), the largest exponent of each prime appearing is \(2^2\), \(3^2\), and \(5^1\), so
\[\operatorname{lcm}(6,9,12,15)=2^2\cdot3^2\cdot5=180.\]
Algebraic Structure
Both operations are visibly commutative and associative, directly from their symmetric definitions, and idempotent, \(\gcd(a,a)=\operatorname{lcm}(a,a)=|a|\). Two further identities connect them to each other:
\[ \boxed{\operatorname{lcm}(a,\gcd(a,b))=a} \qquad\text{and}\qquad \boxed{\gcd(a,\operatorname{lcm}(a,b))=a.} \]
For the first: since \(\gcd(a,b)\mid a\), the number \(a\) is already a common multiple of \(a\) and \(\gcd(a,b)\), and no positive common multiple of \(a\) with anything can be smaller than \(a\) itself, so \(a\) is the least one. The second is the mirror argument: since \(a\mid\operatorname{lcm}(a,b)\), \(a\) is a common divisor of itself and \(\operatorname{lcm}(a,b)\), and no divisor of \(a\) can exceed \(a\), so \(a\) is the greatest one. The same reasoning gives a compact way to express plain divisibility:
\[ a\mid b \quad\Longleftrightarrow\quad \gcd(a,b)=a \quad\Longleftrightarrow\quad \operatorname{lcm}(a,b)=b. \]
For instance \(6\mid24\), and indeed \(\gcd(6,24)=6\) and \(\operatorname{lcm}(6,24)=24\). Finally, \(\gcd\) and \(\operatorname{lcm}\) distribute over each other exactly as \(\min\) and \(\max\) do over one another, prime exponent by prime exponent:
\[ \operatorname{lcm}\bigl(a,\gcd(b,c)\bigr)=\gcd\bigl(\operatorname{lcm}(a,b),\operatorname{lcm}(a,c)\bigr), \qquad \gcd\bigl(a,\operatorname{lcm}(b,c)\bigr)=\operatorname{lcm}\bigl(\gcd(a,b),\gcd(a,c)\bigr). \]
Applications
Fraction Reduction
Reduce \(\frac{a}{b}\) by dividing numerator and denominator by \(\gcd(a,b)\). Example:
\[ \frac{84}{126}=\frac{84/42}{126/42}=\frac{2}{3}. \]
Common Denominators
Adding fractions with different denominators requires rewriting them over a shared denominator, and the smallest one that works is the LCM of the two denominators. For \(\frac16+\frac1{15}\), \(\operatorname{lcm}(6,15)=30\), so
\[\frac16+\frac1{15}=\frac5{30}+\frac2{30}=\frac7{30}.\]
Recurring Events
Two gears with \(12\) and \(18\) teeth mesh together, with one tooth on each marked. The marked teeth meet again once the number of teeth that have passed the mesh point is a common multiple of \(12\) and \(18\); the first time is \(\operatorname{lcm}(12,18)=36\) teeth, after which the first gear has made \(36/12=3\) full turns and the second \(36/18=2\) turns. The same idea scales to any number of periodic processes at once: three signals with integer periods \(l,m,n\) that start in phase return to that same phase together after \(\operatorname{lcm}(l,m,n)\) time units.
Modular Inverse Existence
An integer \(a\) has a multiplicative inverse modulo \(m\) exactly when
\[ \gcd(a,m)=1. \]
Then Bézout gives \(ax+my=1\), so modulo \(m\):
\[ ax\equiv1\pmod m, \]
hence \(x\) is the inverse of \(a\) modulo \(m\).
Cancellation Rule
Coprimality with the modulus also justifies cancelling a common factor inside a congruence. If \(\gcd(c,m)=1\), then
\[ (ac)\bmod m=(bc)\bmod m \quad\Longrightarrow\quad a\bmod m=b\bmod m. \]
Indeed, \((ac)\bmod m=(bc)\bmod m\) means \(m\mid c(a-b)\). Since \(\gcd(c,m)=1\), Euclid's lemma gives \(m\mid(a-b)\), i.e. \(a\bmod m=b\bmod m\).
The hypothesis \(\gcd(c,m)=1\) cannot be dropped: for instance \(2\cdot3\equiv2\cdot8\pmod{10}\) (both are \(6\)), yet \(3\not\equiv8\pmod{10}\); here \(\gcd(2,10)=2\ne1\).
Complexity
The Euclidean algorithm runs in time logarithmic in the input size. It is one of the oldest and most efficient exact arithmetic algorithms.
Common Pitfalls
- Forgetting absolute values: by convention \(\gcd(a,b)\ge 0\).
- Using language-specific modulo with negative numbers without normalization.
- Assuming coprime means both numbers are prime; it only means their GCD is 1.
- Trying to compute \(\operatorname{lcm}(a,b)=ab/\gcd(a,b)\) without absolute value signs.
- Swapping \(\min\) and \(\max\) when reading off exponents from a prime factorization: the GCD always takes the smaller exponent, the LCM the larger one.