Least Common Multiple

⚡ Key Takeaways

Least Common Multiple (LCM): the smallest positive integer that is a multiple of two or more given integers. For example, $\operatorname{lcm}(4,6)=12$ . It is central to adding fractions, scheduling problems, and modular arithmetic. Known since antiquity and formalized through Euclid's number theory (~300 BCE).

💡 The Core Insight

Every common multiple of $a$ and $b$ is itself a multiple of the least common multiple. The LCM is not just the smallest — it generates all the others. So once you know $\operatorname{lcm}(a,b)$ , the complete set of common multiples is exactly $\{0,\ \operatorname{lcm}(a,b),\ 2\operatorname{lcm}(a,b),\ 3\operatorname{lcm}(a,b),\dots\}$ .

DefinitionMultiple and Common Multiple

An integer $m$ is a multiple of an integer $a$ if $m = ka$ for some integer $k$ ; equivalently, $a \mid m$ (" $a$ divides $m$ "). A common multiple of $a$ and $b$ is an integer divisible by both. The least common multiple is the smallest positive common multiple.

DefinitionLeast Common Multiple

For nonzero integers $a$ and $b$ , the least common multiple is

1

\quad \operatorname{lcm}(a,b) = \min\{\, m \in \mathbb{Z}^{+} : a \mid m \text{ and } b \mid m \,\}

Derivation hint: The set of positive common multiples is nonempty (it contains $|ab|$ ), so by the well-ordering principle it has a least element. Here $\mathbb{Z}^{+}$ denotes the positive integers, and $a\mid m$ means " $a$ divides $m$ ." By convention $\operatorname{lcm}(a,0)=0$ .

TheoremGCD–LCM Product Identity

For any two positive integers $a$ and $b$ ,

2

\quad \operatorname{lcm}(a,b)\cdot\gcd(a,b) = a\,b

Derivation hint: Compare exponents of each prime $p$ on both sides; $\max(x,y)+\min(x,y)=x+y$ . where $\gcd(a,b)$ is the greatest common divisor. This gives a fast computational route:

3

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

Derivation hint: Divide both sides of equation [2] by $\gcd(a,b)$ , valid since the GCD is a positive divisor of $ab$ .

TheoremPrime Factorization Formula

If $a$ and $b$ have prime factorizations $a=\prod_p p^{\,\alpha_p}$ and $b=\prod_p p^{\,\beta_p}$ (over all primes $p$ , with finitely many nonzero exponents), then

4

\quad \operatorname{lcm}(a,b) = \prod_{p} p^{\max(\alpha_p,\ \beta_p)}, \qquad \gcd(a,b)=\prod_{p} p^{\min(\alpha_p,\ \beta_p)}

Derivation hint: A common multiple must contain each prime to at least the larger of the two exponents; the smallest such number takes exactly the maximum.

ProofThe Product Identity, equation 2

We prove $\operatorname{lcm}(a,b)\cdot\gcd(a,b)=ab$ via prime exponents. 1. Setup. Write $a=\prod_p p^{\alpha_p}$ and $b=\prod_p p^{\beta_p}$ using equation [4]'s notation. 2. Express both quantities. By the prime formulas,

\operatorname{lcm}(a,b)=\prod_p p^{\max(\alpha_p,\beta_p)},\qquad \gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}.

3. Multiply. Their product collects exponents prime-by-prime:

\operatorname{lcm}(a,b)\cdot\gcd(a,b)=\prod_p p^{\max(\alpha_p,\beta_p)+\min(\alpha_p,\beta_p)}.

4. Key arithmetic fact. For any two numbers, $\max(x,y)+\min(x,y)=x+y$ , because one of them is the max and the other is the min. Thus the exponent of each prime becomes $\alpha_p+\beta_p$ . 5. Conclude. Therefore

\operatorname{lcm}(a,b)\cdot\gcd(a,b)=\prod_p p^{\alpha_p+\beta_p}=\Big(\prod_p p^{\alpha_p}\Big)\Big(\prod_p p^{\beta_p}\Big)=ab. \qquad\blacksquare

∎

ProofEvery Common Multiple is a Multiple of the LCM

Let $L=\operatorname{lcm}(a,b)$ and let $m$ be any common multiple of $a$ and $b$ . 1. Apply division with remainder. Divide $m$ by $L$ : there exist integers $q$ and $r$ with $m = qL + r$ and $0 \le r < L$ . 2. Show $r$ is a common multiple. Since $a\mid m$ and $a\mid L$ (so $a\mid qL$ ), we get $a\mid(m-qL)=r$ . Identically $b\mid r$ . Hence $r$ is a common multiple of $a$ and $b$ . 3. Force $r=0$ . If $r>0$ , then $r$ would be a positive common multiple smaller than $L=\operatorname{lcm}(a,b)$ , contradicting minimality. So $r=0$ . 4. Conclude. Then $m=qL$ , i.e. $L\mid m$ . Every common multiple is a multiple of the LCM. $\qquad\blacksquare$

∎

mathematician · Euclid of Alexandria | c. 325 – c. 265 BCE

Although Euclid never wrote "LCM" as we do, Books VII–IX of his Elements contain the foundational machinery: the Euclidean algorithm for the GCD (Propositions VII.1–2) and results on common multiples (VII.34–36). Proposition VII.35 essentially states that any common multiple of two numbers is a multiple of the least common multiple — exactly the generating property proved above. Euclid worked geometrically, treating numbers as line segments, yet his logic of divisibility is identical to the modern integer arguments. His insistence on rigorous proof made number theory a deductive science rather than a collection of computational recipes.

🧠 Intuition

Imagine two gears (or two blinking lights, or two runners on a circular track). Gear $A$ returns to its starting position every $a$ seconds; gear $B$ every $b$ seconds. They are both back at the start exactly when an integer number of $A$ -cycles equals an integer number of $B$ -cycles — that is, at every common multiple of $a$ and $b$ . The first time they synchronize is $\operatorname{lcm}(a,b)$ . After that, synchronization repeats at every multiple of the LCM, which is why the pattern of "everyone back home together" is itself perfectly periodic. Sharing common factors lets the gears resync sooner; being coprime (no shared factors) forces the longest possible wait, $a\cdot b$ .

Figure

Two cycles of periods 4 and 6 synchronizing at their LCM = 12

ExampleAdding fractions via LCM of denominators

Given: Compute $\dfrac{5}{12}+\dfrac{7}{18}$ .

Step 1 — Factor the denominators. $12 = 2^2\cdot 3$ , and $18 = 2\cdot 3^2$ .

Step 2 — Apply the prime formula, equation [4]. Take the maximum exponent of each prime:

\operatorname{lcm}(12,18)=2^{\max(2,1)}\cdot 3^{\max(1,2)}=2^2\cdot 3^2 = 36.

Step 3 — Rewrite each fraction over 36.

\frac{5}{12}=\frac{15}{36},\qquad \frac{7}{18}=\frac{14}{36}.

Step 4 — Add.

\frac{15}{36}+\frac{14}{36}=\frac{29}{36}.

Since $\gcd(29,36)=1$ , this is already in lowest terms.

\boxed{\dfrac{5}{12}+\dfrac{7}{18}=\dfrac{29}{36}}

ExampleScheduling with the division method

Given: A train on Line 1 departs every $42$ minutes and a train on Line 2 every $56$ minutes. Both leave together at 8:00 AM. When do they next depart simultaneously?

Step 1 — Find the GCD by the Euclidean algorithm. $56 = 1\cdot 42 + 14$ , then $42 = 3\cdot 14 + 0$ , so $\gcd(42,56)=14$ .

Step 2 — Apply equation [3].

\operatorname{lcm}(42,56)=\frac{42\cdot 56}{14}=\frac{2352}{14}=168 \text{ minutes}.

Step 3 — Convert to clock time. $168$ minutes $= 2$ hours $48$ minutes after 8:00 AM.

\boxed{\text{Next simultaneous departure: } 10\!:\!48\text{ AM} \;(168 \text{ min})}

⚠️ Common mistake

The LCM is not the product unless the numbers are coprime. Beginners often "multiply the two numbers" — but $\operatorname{lcm}(4,6)=12$ , not $24$ . The product overcounts shared factors. The product equals the LCM only when $\gcd(a,b)=1$ . Equation [3], $\operatorname{lcm}=ab/\gcd$ , makes this precise: dividing by the GCD removes the double-counted common part. A second pitfall: the LCM is always at least as large as the larger input ( $\operatorname{lcm}(a,b)\ge\max(a,b)$ ), whereas the GCD is at most the smaller input. Confusing which is "bigger" leads to wrong setups when adding fractions.

Counterexample

One might guess that $\operatorname{lcm}(a,b)$ scales linearly — e.g. that doubling both inputs doubles the LCM. Indeed $\operatorname{lcm}(2a,2b)=2\operatorname{lcm}(a,b)$ is true. But changing only one input is unpredictable: $\operatorname{lcm}(6,4)=12$ , yet $\operatorname{lcm}(6,8)=24$ and $\operatorname{lcm}(6,9)=18$ . Increasing $4\to8\to9$ moves the LCM up, then down, because what matters is the prime-factor overlap, not the raw magnitude. The LCM is sensitive to structure, not size.

connection

The LCM is inseparable from the Greatest Common Divisor via the product identity [2]; computing one instantly gives the other. Both rest on the Fundamental Theorem of Arithmetic, which guarantees the unique prime factorizations used in equation [4]. The LCM appears whenever one solves systems of congruences in Modular Arithmetic — the Chinese Remainder Theorem uses LCMs of the moduli to describe the periodicity of solutions. It is also the cornerstone of Operations with Fractions, where the least common denominator is precisely the LCM of the denominators. More abstractly, in lattice theory the LCM is the "join" and the GCD the "meet" of the divisibility partial order on the positive integers.

🔬 Where this appears

⏳ History

- c. 1800 BCE — Babylonian scribes manipulate sexagesimal fractions, implicitly requiring common multiples to combine units; their base-60 system was chosen partly for its many divisors.

- c. 300 BCE — Euclid's Elements, Book VII, gives the GCD algorithm and Proposition VII.35 on least common multiples and their generating property.

- c. 100 CE — Nicomachus of Gerasa, in Introduction to Arithmetic, classifies number relationships and discusses multiples systematically.

- c. 250 CE — Diophantus solves problems requiring common multiples of denominators in his Arithmetica.

- 7th century — Indian mathematician Brahmagupta develops rules for fractions and integers that presuppose finding common multiples.

- 1202 CE — Fibonacci's Liber Abaci spreads Hindu–Arabic arithmetic, including systematic fraction addition via common denominators, throughout Europe.

- 1801 — Gauss's Disquisitiones Arithmeticae places the GCD, LCM, and congruences on a rigorous modern footing, founding analytic and algebraic number theory.

- 1910 — R. D. Carmichael introduces the function

\lambda(n)

, defined through LCMs of orders, refining Euler's totient in the study of cyclic groups.

- 20th century — The LCM/GCD pair is generalized to the abstract notions of least common multiple and greatest common divisor in arbitrary integral domains and lattices, central to modern algebra.

open-problem

The LCM is elementary, yet its growth hides deep questions. Define $\Psi(n)=\operatorname{lcm}(1,2,\dots,n)$ . A remarkable theorem connects it to the Prime Number Theorem: $\log\Psi(n)$ is asymptotically equal to $n$ , i.e. $\Psi(n)=e^{(1+o(1))n}$ — proving good explicit bounds on $\Psi(n)$ is essentially equivalent to estimating the distribution of primes, a topic that touches the (still unproven) Riemann Hypothesis. More elementary but genuinely open: precise understanding of the distribution of $\operatorname{lcm}(a,b)$ as $a,b$ range over intervals, and behavior of LCMs of random subsets, remain active research areas. So a concept introduced in grade school sits at the doorstep of the deepest unsolved problems in number theory.

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also