3.4 Least common multiple

The least common multiple (LCM) is the smallest positive integer that's divisible by two or more given integers. It shows up constantly in fraction arithmetic, scheduling problems, and modular arithmetic, and it ties together ideas like prime factorization and GCD that run throughout number theory and abstract algebra.

Definition and concept

Meaning of LCM

The LCM of two or more integers is the smallest positive integer that each of them divides into evenly. For example, $LCM(4, 6) = 12$ because 12 is the first number that appears in both the list of multiples of 4 (4, 8, 12, 16, ...) and the list of multiples of 6 (6, 12, 18, ...).

You can calculate it directly using:

$LCM(a,b) = \frac{|a \times b|}{GCD(a,b)}$

This formula is efficient because it leverages the GCD, which is fast to compute. The LCM is especially useful for finding common denominators when adding or subtracting fractions.

Relationship to factors

The LCM of a set of numbers incorporates all of their prime factors, taken at the highest power that appears in any of the numbers. For instance, $12 = 2^2 \times 3$ and $18 = 2 \times 3^2$, so $LCM(12, 18) = 2^2 \times 3^2 = 36$.

This connects to a fundamental identity:

$LCM(a,b) \times GCD(a,b) = |a \times b|$

This relationship isn't just a formula to memorize. It tells you that the LCM and GCD together account for all the prime factor "information" in both numbers, with no overlap.

LCM vs GCD

LCM and GCD go in opposite directions. The GCD finds the largest factor shared by the numbers, while the LCM finds the smallest multiple they share. As numbers get larger, their LCM tends to grow (or stay the same), while their GCD tends to shrink (or stay the same).

A useful way to think about it: GCD strips away everything that isn't shared, while LCM combines everything from both numbers. If two numbers are coprime ($GCD = 1$), their LCM is simply their product.

Finding LCM

Three standard methods exist for computing LCM. Which one you reach for depends on the size of the numbers and the context.

Prime factorization method

1. Decompose each number into its prime factorization.
2. For each prime that appears in any factorization, take the highest power.
3. Multiply those highest powers together.

Example: Find $LCM(60, 90)$.

• $60 = 2^2 \times 3 \times 5$
• $90 = 2 \times 3^2 \times 5$
• Take the highest powers: $2^2, 3^2, 5^1$
• $LCM = 4 \times 9 \times 5 = 180$

This method is clean and reliable, but it requires you to factor the numbers first, which can be slow for large integers.

Division method (ladder method)

1. Write the numbers side by side.
2. Find the smallest prime that divides at least one of the numbers. Divide whichever numbers it divides, and bring down the rest unchanged.
3. Repeat until every number has been reduced to 1.
4. Multiply all the primes you divided by.

Example: Find $LCM(12, 18)$.

$LCM = 2 \times 2 \times 3 \times 3 = 36$

This is particularly handy when working with three or more numbers at once.

Listing multiples method

Write out the multiples of each number until you spot the first one they share.

• Multiples of 4: 4, 8, 12, 16, 20, ...
• Multiples of 6: 6, 12, 18, 24, ...
• First common multiple: 12

This is the most intuitive approach and works well for small numbers or mental math, but it becomes impractical as numbers grow.

Properties of LCM

These properties aren't just trivia. They're what let you manipulate LCM expressions in proofs and extend LCM calculations to more than two numbers.

Commutative property

The order doesn't matter:

$LCM(a,b) = LCM(b,a)$

This extends to any number of inputs: $LCM(a,b,c) = LCM(c,a,b)$, etc.

Associative property

Grouping doesn't matter:

$LCM(a, LCM(b,c)) = LCM(LCM(a,b), c)$

This is what lets you compute the LCM of a long list of numbers by processing them two at a time, in any order.

Distributive property

LCM distributes over GCD:

$LCM(a, GCD(b,c)) = GCD(LCM(a,b), LCM(a,c))$

This property mirrors how multiplication distributes over addition, and it reveals a deep structural connection between LCM and GCD. Together, they form a lattice on the positive integers, which becomes important in abstract algebra.

Applications in mathematics

Fraction arithmetic

The most common everyday use of LCM is finding a common denominator. To add $\frac{1}{4} + \frac{1}{6}$, you need $LCM(4,6) = 12$:

$\frac{1}{4} + \frac{1}{6} = \frac{3}{12} + \frac{2}{12} = \frac{5}{12}$

Using the LCM (rather than just any common multiple) keeps the numbers as small as possible, which reduces the chance of arithmetic errors and minimizes simplification at the end.

Problem-solving scenarios

LCM naturally models situations where multiple cycles need to sync up:

• Scheduling: Two bus routes with cycles of 15 and 20 minutes both depart at 8:00 AM. They'll next depart together in $LCM(15, 20) = 60$ minutes, at 9:00 AM.
• Gear teeth / rotating systems: If two gears have 12 and 18 teeth, they return to their starting alignment after $LCM(12, 18) = 36$ teeth have passed.
• Packaging: You need to buy hot dogs (packs of 8) and buns (packs of 6) with none left over. You need $LCM(8, 6) = 24$ of each.

Algebraic manipulations

LCM extends to algebraic expressions. To add $\frac{1}{x^2} + \frac{1}{x^3}$, you find $LCM(x^2, x^3) = x^3$ and rewrite:

$\frac{x}{x^3} + \frac{1}{x^3} = \frac{x+1}{x^3}$

The same principle applies when solving equations with fractional coefficients: multiply through by the LCM of the denominators to clear all fractions at once.

LCM and number theory

Connection to prime numbers

The prime factorization method for LCM works because of the Fundamental Theorem of Arithmetic: every integer greater than 1 has a unique prime factorization. Without unique factorization, the "take the highest power of each prime" recipe wouldn't be well-defined.

The behavior of LCM across ranges of integers also connects to deeper questions about prime distribution. For example, $LCM(1, 2, 3, \ldots, n)$ grows roughly like $e^n$ as $n$ gets large, a fact tied to the Prime Number Theorem.

Role in modular arithmetic

LCM determines when periodic patterns re-sync. If one event repeats every $a$ steps and another every $b$ steps, they coincide every $LCM(a,b)$ steps.

This idea is central to the Chinese Remainder Theorem (CRT): a system of congruences $x \equiv r_1 \pmod{m_1}$ and $x \equiv r_2 \pmod{m_2}$ has a solution modulo $LCM(m_1, m_2)$ (provided the congruences are compatible). When the moduli are coprime, $LCM(m_1, m_2) = m_1 \cdot m_2$, and a unique solution is guaranteed.

LCM in Diophantine equations

For a linear Diophantine equation like $ax + by = c$, integer solutions exist if and only if $GCD(a,b)$ divides $c$. The LCM enters when you look at the spacing between solutions: consecutive solutions for $x$ differ by $\frac{b}{GCD(a,b)}$, and the overall structure of the solution set ties back to the LCM-GCD identity.

Computational aspects

Algorithms for LCM calculation

The standard approach computes LCM via GCD:

$LCM(a,b) = \frac{|a \times b|}{GCD(a,b)}$

So the efficiency of LCM computation reduces to the efficiency of GCD computation. The main algorithms:

• Euclidean algorithm: Repeatedly replace the larger number with the remainder of dividing the two. Fast and simple.
• Binary GCD (Stein's algorithm): Replaces division with bitwise shifts and subtraction, which can be faster on hardware that handles binary operations efficiently.

Both run in $O(\log(\min(a,b)))$ steps for the basic Euclidean algorithm, making LCM computation very efficient even for large numbers.

Efficiency considerations

One practical concern: computing $a \times b$ before dividing by the GCD can cause overflow for large integers. A safer approach is to divide first: $LCM(a,b) = \frac{a}{GCD(a,b)} \times b$. Since $GCD(a,b)$ divides $a$, the intermediate result stays smaller.

For computing the LCM of many numbers, apply the associative property and process them pairwise: $LCM(a,b,c) = LCM(LCM(a,b), c)$.

LCM in programming languages

Most modern languages provide LCM either directly or through their GCD function:

• Python 3.9+: math.lcm(a, b) (also accepts multiple arguments)
• Python (any version): abs(a * b) // math.gcd(a, b)
• C++17: std::lcm(a, b) in <numeric>

These built-in functions handle edge cases like zero inputs ($LCM(0, n) = 0$ by convention) and negative numbers.

Advanced topics

LCM of polynomials

The LCM concept extends naturally to polynomials. Just as with integers, you factor each polynomial, then take the highest power of each irreducible factor.

Example: For $p(x) = (x-1)^2(x+2)$ and $q(x) = (x-1)(x+2)^3$:

$LCM(p, q) = (x-1)^2(x+2)^3$

This is essential when adding rational expressions (algebraic fractions) with polynomial denominators.

LCM in abstract algebra

In a ring, the LCM of two elements $a$ and $b$ is an element $m$ such that $a \mid m$ and $b \mid m$, and $m$ divides every other common multiple. This doesn't always exist in arbitrary rings, but it does in unique factorization domains (UFDs) and principal ideal domains (PIDs).

In the language of ideals, $LCM(a,b)$ corresponds to the intersection of ideals: $(a) \cap (b) = (LCM(a,b))$ in a PID. Compare this with GCD, which corresponds to the sum of ideals: $(a) + (b) = (GCD(a,b))$.

Generalizations to other structures

The pattern of LCM and GCD generalizes to any lattice: a partially ordered set where every pair of elements has a least upper bound (join, analogous to LCM) and a greatest lower bound (meet, analogous to GCD). The positive integers ordered by divisibility form one such lattice, but the same framework applies to sets ordered by inclusion, subgroups ordered by containment, and many other structures across mathematics.