LCM Calculator - Least Common Multiple
This Least Common Multiple (LCM) calculator can be used to find out the LCM of two or more positive integers that are smaller than 1 trillion. To use the calculator, provide some values, then click the "Calculate" button. To find the LCM of more than two numbers, select the "Find LCM of more than two numbers" checkbox and provide numbers separated by a comma or semicolon.
What is the LCM?
The least common multiple between a set of numbers is the smallest number that is a multiple of all the numbers, where a multiple is the product of some number and an integer. For example, the least common multiple of 2 and 4, denoted LCM(2, 4), is 4:
2 × 2 = 4
4 × 1 = 4
Other common multiples of 2 and 4 include 8, 12, 16, 20, and so on. 4 is the smallest number that is a multiple of both 2 and 4, so it is the LCM.
The LCM is commonly used when adding and subtracting fractions.
How to find the LCM?
There are various methods for finding the LCM of a set of numbers.
Listing multiples of each number in the set of numbers is a straightforward way to find the LCM of a set of numbers. It is as its name suggests, and involves writing a list of multiples of each of the numbers. For example, to find the LCM of 12 and 16, list their multiples:
Multiples of 12: 12, 24, 36, 48, 60
Multiples of 16: 16, 32, 48, 64, 80
48 is the first number that is a multiple of both 12 and 16, so LCM(12, 16) = 48. There is no exact number of multiples that should be listed when searching for the LCM. In this particular case, 5 multiples for 12 and 16 were listed, but this is an arbitrary number of multiples. The only thing to keep in mind is that the product of the numbers is a multiple of the two numbers, and this product is the largest number that could be the LCM. Thus, before listing the multiples, it can be useful to determine the product of the numbers being examined; in the above example, 12 × 16 = 192, so either this number is the LCM, or the LCM will be smaller than this number, as was the case in this example. It is therefore unnecessary to list any number larger than the product of the numbers being examined, since any larger number cannot possibly be the LCM.
Prime factorization is the process of decomposing a number into a product of its prime factors. For example, the prime factorization of 24 is:
24 = 2 × 2 × 2 × 3
Every number has a unique prime factorization, and it is this fact that allows us to use prime factorization to determine the LCM. The LCM of a set of numbers is the smallest number that can be formed that includes all of the prime factors of the set of numbers. For example, the prime factorizations of 12 and 16 are as follows:
|12 = 2 × 2 × 3 = 22 × 3|
|16 = 2 × 2 × 2 × 2 = 24|
The prime factorizations of 12 and 16 include the prime factors 2 and 3. The LCM is the product of the highest order prime factors between the two numbers. This is because we are looking for the smallest possible multiple, so we only need to count shared factors once, and therefore only include the highest order prime factor between the two when calculating the product. In this case, both 12 and 16 share the prime factor 2, but since the prime factorization of 16 includes four 2s and the prime factorization of 12 only includes two 2s, we use 24. Similarly, since 12 is the only number that has a 3 as part of its prime factorization, we use 31. The LCM is the product of these highest order prime factors, so:
LCM(12,16) = 24 × 31 = 48
Note that we could find a common multiple by multiplying all of the prime factors, but this would not be the LCM. For example:
22 × 24 × 3 = 192
This is the largest possible number that can be the LCM, but the reason that it is not the LCM is because of the shared 22 term. By removing the shared common factors (only counting them once), we arrive at the LCM.
Greatest Common Divisor (GCD) Method
The greatest common divisor method of finding the LCM is one of the most efficient ways to find the LCM. If the GCD is known, simply use the following formula to find the LCM:
Otherwise, it is necessary to find the GCD first. Like the LCM, there are a number of ways to find the GCD. One of the most efficient methods for finding the GCD is the Euclidean algorithm. The algorithm makes use of some properties of the GCD, as well as the modulo operator. The modulo operator indicates the process of division with remainder, and is denoted as "mod" or "%." Note that the % in this case has nothing to do with percentages. For example:
12 mod 8 = 4
8 divides 12 once, with a remainder of 4. The remainder of 4 is referred to as the modulus; this terminology is important for the algorithm, as are the following properties:
- GCD(a,0) = a
- GCD(0,b) = b
- GCD(a,b) = GCD(b,a mod b)
The third property is the most important of the three because it efficiently reduces the GCD to a simpler problem each time it is applied. Thus, to use the Euclidean algorithm to compute GCD(a, b), where a and b represent two integers, R is the remainder, and a > b, use the following steps:
- Reduce GCD(a, b) to GCD(b, a mod b) by finding a mod b.
- Treat GCD(b, a mod b) as the new GCD(a, b).
- Repeat steps 1 and 2 until b = 0
- Then, GCD(a, 0) = a
For example, to find GCD(16, 12):
|GCD(16,12) = GCD(12,16 mod 12)|
|GCD(12,4) = GCD(4,12 mod 4) = GCD(4,0)|
Then, using property 1 from above, GCD(4, 0) = 4. Plugging this into the LCM formula:
Depending on the numbers involved, this method may be less efficient than using the listing multiples or prime factorization methods. However, for larger numbers, this method will be far more efficient.