= Least common multiple
{title2=$\operatorname{lcm}$}
{wiki}
= LCM
{c}
{synonym}
For <positive integers> $a,b$, their least common multiple is the \b[smallest positive <integer> that is an <integer multiple> of both]. Write it as $\operatorname{lcm}(a,b)$. A positive common <integer multiple> always exists, since $ab$ is one, but it can be larger than necessary.
For example, the positive <integer multiples> of $12$ begin $12,24,36,48,60,72$, while those of $18$ begin $18,36,54,72$. Their first positive coincidence is $36$, so $\operatorname{lcm}(12,18)=36$. Both also divide zero, but the word positive excludes zero from this minimum.
Suppose two events happen every twelve and eighteen days, and both happen at day $t=0$. Their next meeting is at day $36$, after three twelve-day intervals and two eighteen-day intervals. Through day $72$, their common event times are $0,36,72$.
\Image[/least-common-multiple-periods.png]
{title=Events every 12 and 18 days, starting together, meet again every 36 days}
{description=Each row marks the nonnegative <integer multiples> of its interval from zero through 72. The highlighted columns $0,36,72$ are shared; 36 is the first positive one and hence the <least common multiple>.}
The <prime factorization> explains why this coincidence occurs. For the <integers> $12$ and $18$,
$$
12=2^2\cdot3,\qquad18=2\cdot3^2,\qquad
\operatorname{lcm}(12,18)=2^{\max(2,1)}3^{\max(1,2)}=36.
$$
A common <integer multiple> must contain at least the <prime valuations> required by each input. Taking the larger <prime valuation> at each <prime number> meets both requirements with no extra factors. The <greatest common divisor> uses the smaller <prime valuations> instead. This is the same coordinate comparison developed under <prime factorization>, applied in opposite directions.
\Image[/gcd-lcm-prime-exponents.png]
{title=For 12 and 18, smaller <prime valuations> give <greatest common divisor> 6 and larger ones give <least common multiple> 36}
{description=Bars show the exponents of the <prime numbers> two and three in $12$, $18$, $6$ and $36$. The table makes the minimum and maximum in each column explicit.}
For any <positive integers> $a,b$, the <prime valuations> give
$$
\gcd(a,b)\operatorname{lcm}(a,b)=ab,\qquad
\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.
$$
The proof outline is one observation at each <prime number>: $\min(r,s)+\max(r,s)=r+s$. Hence the two sides have identical <prime factorizations>. Numerically, $6\cdot36=12\cdot18=216$. This also gives a calculation using the <Euclidean algorithm> for the <greatest common divisor>, without first finding the <prime factors> of both inputs.
Every positive common <integer multiple> is an <integer multiple> of the <least common multiple>, because its <prime valuations> must be at least the larger input <prime valuations>. Including negatives and zero, the common <integer multiples> of $12$ and $18$ are exactly $36k$ for <integers> $k$. For more than two <positive integers>, the same definition and rule of taking the largest <prime valuations> apply; one may also combine inputs successively. For example, $\operatorname{lcm}(12,18,20)=\operatorname{lcm}(36,20)=180$.
For nonzero signed <integers>, take <absolute values>: $\operatorname{lcm}(-12,18)=36$. We extend the definition to zero by the convention $\operatorname{lcm}(a,0)=0$, since zero is then the only common <integer multiple>; this is an extension, not a positive minimum. In particular $\operatorname{lcm}(0,0)=0$ must be handled separately from the displayed <quotient>, which would involve <division> by zero.
The <least common multiple> is useful for combining <fractions> with the smallest positive shared <denominator>. For example,
$$
\frac1{12}+\frac1{18}=\frac3{36}+\frac2{36}=\frac5{36}.
$$
Its scheduling interpretation requires care about starting times. If the events start at <integer> days $r$ and $s$, a common time must satisfy the <integer congruences> $t\equiv r\pmod{12}$ and $t\equiv s\pmod{18}$. The <Chinese remainder theorem for noncoprime moduli> says a solution exists exactly when $6\mid(r-s)$. If it exists, solutions form one <congruence class> modulo $36$, but the first meeting need not be day $36$. With starts $r=0,s=6$, the first meeting is day $24$ and subsequent meetings are $60,96,\ldots$; with $r=0,s=1$, they never meet. The beauty of the <least common multiple> is the exact shared spacing, while the <integer congruences> determine whether and where the spacing begins.
Book VII, Proposition 34 of <Euclid's Elements> constructs the <least common multiple> of two numbers, and Proposition 36 extends the construction to three by first combining two of them. In modern notation this is $\operatorname{lcm}(a,b,c)=\operatorname{lcm}(\operatorname{lcm}(a,b),c)$. These are specific ancient treatments of the construction, rather than a claim about its first discovery. https://geometor.github.io/euclid/heath/VII/34/index.html[Euclid, Elements VII.34, T. L. Heath translation: two numbers]{ref} https://geometor.github.io/euclid/heath/VII/36/index.html[Euclid, Elements VII.36, T. L. Heath translation: three numbers]{ref}
Back to article page
