Least Common Multiple
The least common multiple (LCM) of two integers a and b is the smallest positive integer that is a multiple of both. It is denoted as $$ LCM(a, b) $$ or sometimes as $$ [a, b] $$.
In practical terms, the LCM of two numbers is found by multiplying all prime factors - both shared and distinct - each taken once, using the highest exponent that appears in either factorization.
Example. To compute the LCM of 30 and 40, we begin by factoring both numbers into primes: $$ 30 = 2 \cdot 3 \cdot 5 $$ $$ 40 = 2^3 \cdot 5 $$ We then take all prime factors that appear in either factorization, using the largest exponent found: $$ 2^3, \quad 3^1, \quad 5^1 $$ Thus, $$ LCM(30, 40) = 2^3 \cdot 3 \cdot 5 = 120 $$
Formally, the LCM of two integers a and b is the smallest positive integer m such that:
- Both a and b divide m: $$ a \mid m \quad \text{and} \quad b \mid m $$
- Any common multiple of a and b is also divisible by m: $$ \forall k \in \mathbb{Z}, \; a \mid k \land b \mid k \Rightarrow m \mid k $$
Note. Strictly speaking, we could refer to "a" least common multiple, since both m and −m satisfy the conditions. However, by convention, we refer exclusively to the positive solution. For example, both 30 and 40 divide −120, and −120 is a common multiple of any divisor of 30 and 40. But we define: $$ LCM(30, 40) = 120 $$ as the unique positive value.
How to Compute the Least Common Multiple
To find the LCM of two integers, factor each number into its prime components. Then, for every prime appearing in either number, take the highest power that occurs and multiply them together.
Note. This method is effective when the numbers are small or easily factored. For larger values, prime factorization may become impractical.
Example
Let’s take a = 40 and b = 30.
$$ a = 40 \quad b = 30 $$
Prime factorizations:
$$ \begin{array}{c|c} a & f \\ \hline 40 & 2 \\ 20 & 2 \\ 10 & 2 \\ 5 & 5 \\ 1 & \end{array} $$
$$ \begin{array}{c|c} b & f \\ \hline 30 & 2 \\ 15 & 3 \\ 5 & 5 \\ 1 & \end{array} $$
So:
$$ 40 = 2^3 \cdot 5 \qquad 30 = 2 \cdot 3 \cdot 5 $$
We now multiply all prime factors, each raised to its highest exponent:
$$ LCM(40, 30) = 2^3 \cdot 3 \cdot 5 = 120 $$
Alternative Methods for Calculating the LCM
There are other ways to compute the LCM, which are particularly useful when prime factorization is not straightforward.
A] Using the GCD
The least common multiple can be derived from the greatest common divisor (GCD) using the identity:
$$ LCM(a, b) = \frac{a \cdot b}{GCD(a, b)} $$
Example. We know that: $$ GCD(30, 40) = 10 $$ Then: $$ LCM(30, 40) = \frac{30 \cdot 40}{10} = \frac{1200}{10} = 120 $$
This approach still requires computing the GCD. To avoid using prime factorization, we can use the Euclidean Algorithm instead.
B] Using the Euclidean Algorithm
The Euclidean Algorithm is a fast and reliable method for finding the GCD of two integers.
Once the GCD is known, the LCM can be quickly found using the formula from method A - without factoring either number.
Example. To find GCD(30, 40): 1. Divide the larger number by the smaller: $$ 40 \div 30 = 1 \quad \text{remainder } 10 $$ 2. Divide the previous divisor by the remainder: $$ 30 \div 10 = 3 \quad \text{remainder } 0 $$ Since the remainder is now zero, the last nonzero remainder (10) is the GCD. Therefore: $$ LCM(30, 40) = \frac{30 \cdot 40}{10} = 120 $$
Relationship Between LCM and GCD
The least common multiple and the greatest common divisor of two integers a and b are linked by the identity: $$ LCM(a, b) = \frac{a \cdot b}{GCD(a, b)} $$
Example
Let a = 8 and b = 12.
We know: $$ LCM(8, 12) = 24 \qquad GCD(8, 12) = 4 $$
Let’s verify the identity:
$$ \frac{8 \cdot 12}{GCD(8, 12)} = \frac{96}{4} = 24 $$
The relationship holds true.
And so on.
