# Least common multiple

In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. If there is no such positive integer, e.g., if a = 0 or b = 0, then lcm(a, b) is defined to be zero.

The least common multiple is useful when adding or subtracting vulgar fractions, because it yields the lowest common denominator. Consider for instance

[itex]{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42},[itex]

where the denominator 42 was used because lcm(21, 6) = 42.

If a and b are not both zero, the least common multiple can be computed by using the greatest common divisor (gcd) of a and b:

[itex]\operatorname{lcm}(a,b)=\frac{a\cdot b}{\operatorname{gcd}(a,b)}.[itex]

Thus, the Euclidean algorithm for the gcd also gives us a fast algorithm for the lcm. To return to the example above,

[itex]\operatorname{lcm}(21,6)={21\cdot6\over\operatorname{gcd}(21,6)}={126\over3}=42.[itex]

## Efficient calculation

The formula

[itex]\operatorname{lcm}(a,b)=\frac{(a\cdot b)}{\operatorname{gcd}(a,b)}[itex]

is adequate to calculate the lcm for small numbers using the formula as written.

Because that (ab)/c = a(b/c) = (a/c)b, one can calculate the lcm using the above formula more efficiently, by firstly exploiting the fact that b/c or a/c may be easier to calculate than the quotient of the product ab and c. This can be true whether the calculations are performed by a human, or a computer, which may have storage requirements on the variables a, b, c, where the limits may be 4 byte storage - calculating ab may cause an overflow, if storage space is not allocated properly.

Using this, we can then calculate the lcm by either using:

[itex]\operatorname{lcm}(a,b)=\left({a\over\operatorname{gcd}(a,b)}\right)\cdot b[itex]

or

[itex]\operatorname{lcm}(a,b)=a\cdot\left({b\over\operatorname{gcd}(a,b)}\right).\,[itex]

Done this way, the previous example becomes:

[itex]\operatorname{lcm}(21,6)={21\over\operatorname{gcd}(21,6)}\cdot6={21\over3}\cdot6=7\cdot6=42.[itex]

## Alternative method

The unique factorization theorem says that every positive integer number greater than 1 can be written in only one way as a product of prime numbers. The prime numbers can be considered as the atomic elements which when combined together makes up a composite number.

For example:

[itex]90 = 2^1 \cdot 3^2 \cdot 5^1 = 2 \cdot 9 \cdot 5 \,\![itex]

Here we have the composite number 90 made up of one atom of the prime number 2, two atoms of the prime number 3 and one atom of the prime number 5.

We can use this knowledge to easily find the lcm of a group of numbers.

For example: Find the value of lcm(45, 120, 75)

[itex]45\; \, = 2^0 \cdot 3^2 \cdot 5^1 \,\![itex]
[itex]120 = 2^3 \cdot 3^1 \cdot 5^1 \,\![itex]
[itex]75\; \,= 2^0 \cdot 3^1 \cdot 5^2. \,\![itex]

The lcm is the number which has the greatest multiple of each different type of atom. Thus

[itex]\operatorname{lcm}(45,120,75) = 2^3 \cdot 3^2 \cdot 5^2 = 8 \cdot 9 \cdot 25 = 1800. \,\![itex]

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy