Least common multiple
The least common multiple (LCM) of two or more whole numbers is the smallest whole number (except zero) that is divisible by both whole numbers.
The LCM is commonly used for adding and subtracting fractions. Using the least common denominator (LCM of all the denominators), ensures that the result of the addition or subtraction of the fractions is in simplest form.
How to find the LCM
There are several ways to find the least common multiple of two or more numbers including listing multiples, using prime factorization, a table, or Euclid's algorithm. Euclid's algorithm is the most efficient, but the other examples are a little more straightforward.
Listing multiples
Listing the multiples of each of the numbers is one way to find the LCM. It is fairly straightforward, but can be tedious.
Example
To find the LCM of 2, 6, and 9, list the nonzero multiples of each number until you find one that is common to all three numbers.
| 2: | 2, 4, 6, 8, 10, 12, 14, 16, 18, ... |
| 6: | 6, 12, 18, ... |
| 9: | 9, 18, ... |
Thus, the LCM of 2, 6, and 9 is 18. This is written as: LCM(2, 6, 9) = 18.
Using prime factorization
Prime factorization can also be used to find the LCM.
- Find the prime factorization of each number.
- Examine each of the prime factorizations and determine the highest power of each prime number.
- Find the product of the highest power of each prime number. The result is the LCM.
To find the LCM of 4 and 6, first write the prime factorization of each number.
| 4 = 2 × 2 |
| 6 = 2 × 3 |
The highest power of 2 comes from the prime factorization of 4, and is 22. The highest power of 3 comes from the prime factorization of 6, and is 31. Multiplying the highest powers yields:
22 × 31 = 4 × 3 = 12
Thus, LCM(4, 6) = 12.
This same method can be used even if we are trying to find the LCM of more than 2 numbers.
Using a table
To find the LCM using a table, use the following steps, and refer to the example below.
- List the numbers vertically in a table.
- Divide each number by 2 (the first prime number). If any of the numbers divides evenly, write the result in the following column of the table, and write the divisor (in this case 2) at the top of the table. If it does not divide evenly, rewrite the number in the following column.
- Divide each subsequent column by 2 until none of the numbers can be evenly divided by 2. Continue this process for the next largest prime number until the quotient of all the numbers is equal to 1 (the last column is all 1s).
- Multiply the numbers in the top row (the prime factors). The product is the LCM.
Example
Find LCM(7, 8, 14) using a table.
List the numbers vertically:
| 7 |
| 8 |
| 14 |
2 divides both 14 and 8 evenly. Divide them and write the result in the following column. Rewrite 7 in the column since it cannot be divided by 2:
| 2 | |
|---|---|
| 7 | 7 |
| 8 | 4 |
| 14 | 7 |
Continue the process, dividing by 2 until none of the numbers can be evenly divided:
| 2 | 2 | |
|---|---|---|
| 7 | 7 | 7 |
| 8 | 4 | 2 |
| 14 | 7 | 7 |
| 2 | 2 | 2 | |
|---|---|---|---|
| 7 | 7 | 7 | 7 |
| 8 | 4 | 2 | 1 |
| 14 | 7 | 7 | 7 |
The next two prime numbers are 3 and 5, which cannot divide 7 evenly. Divide by 7 to complete the division process:
| 2 | 2 | 2 | 7 | |
|---|---|---|---|---|
| 7 | 7 | 7 | 7 | 1 |
| 8 | 4 | 2 | 1 | 1 |
| 14 | 7 | 7 | 7 | 1 |
Now that the quotients are all 1, find the product of the numbers at the top of the table:
2 × 2 × 2 × 7 = 56
Therefore, LCM(7, 8, 14) = 56.
Euclid's algorithm
Euclid's algorithm can be used to quickly find the greatest common factor (GCF), also known as the greatest common divisor, between a set of numbers. Once the GCF is known, the following formula can be used to find the LCM:
In the formula above, a and b represent the numbers involved.
Example
Find LCM(114, 288) using the formula given that GCF(114, 288) = 6.
Finding the GCF
There are a number of ways to find the GCF. The Euclidean algorithm is one of the most efficient. To use the Euclidean algorithm to find the GCF:
- Divide the larger number by the smaller number. If the remainder is 0, the divisor is the GCF, if not continue to the next step.
- Divide the smaller number (the previous divisor) by the remainder. If the new remainder is 0, the divisor is the GCF.
- Continue the process of dividing the previous divisor by the remainder until there is no remainder. The divisor that results in a remainder of 0 is the GCF of the original two numbers.
Example
Find GCF(114, 288):
Note that the quotient doesn't really matter for this algorithm, and we're not completing the actual original long division problem.
After dividing 4 times, the remainder is 0, and the last divisor is 6. Therefore, based on the algorithm, GCF(114, 288) = 6. This can be tested by dividing both 114 and 288 by 6:
114 ÷ 6 = 19
288 ÷ 6 = 48
19 and 48 don't share any common factors, confirming that 6 is the GCF of 114 and 288.
This algorithm can also be used to find the GCF for more than 2 numbers by finding the GCF between the first two numbers then calculating the GCF of the result and the next number. This can be written as:
GCF(a, b, c) = GCF(GCF(a, b), c)