Least common multiple

From Wikipedia, the free encyclopedia

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.

For example, the least common multiple of the numbers 4 and 6 is 12.

When adding or subtracting vulgar fractions, it is useful to find the least common multiple of the denominators, often called the lowest common denominator. For instance,

${2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42},$

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

1 Calculating the least common multiple
2 Alternative method
3 The lcm in commutative rings
4 See also
5 External links

[edit] Calculating the least common multiple

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:

$\operatorname{lcm}(a,b)=\frac{a\cdot b}{\operatorname{gcd}(a,b)}.$

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

$\operatorname{lcm}(21,6) ={21\cdot6\over\operatorname{gcd}(21,6)} ={21\cdot 6\over 3}={126\over 3}=42.$

Because (ab)/c = a(b/c) = (a/c)b, one can calculate the lcm using the above formula more efficiently, by first exploiting the fact that b/c or a/c will be easier to calculate than the quotient of the product ab and c, because the fact that c is a factor of both a and b entails that in either fraction, a/c or b/c, one can completely cancel the 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:

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

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

Done this way, the previous example becomes:

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

Even if the numbers are large and not quickly factorable, the gcd can be calculated quickly with Euclid's algorithm.

[edit] 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, make up a composite number.

For example:

$90 = 2^1 \cdot 3^2 \cdot 5^1 = 2 \cdot 9 \cdot 5. \,\!$

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.

This knowledge can be used to find the lcm of a set of numbers.

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

$45\; \, = 2^0 \cdot 3^2 \cdot 5^1 \,\!$

$120 = 2^3 \cdot 3^1 \cdot 5^1 \,\!$

$75\; \,= 2^0 \cdot 3^1 \cdot 5^2. \,\!$

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

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

[edit] The lcm in commutative rings

The least common multiple can be defined generally over commutative rings as follows: Let a and b be elements of a commutative ring R. A common multiple of a and b is an element m of R such that both a and b divide m (i.e. there exist elements x and y of R such that ax = m and by = m). A least common multiple of a and b is a common multiple that is minimal in the sense that for any other common multiple n of a and b, m divides n.

In general, two elements in a commutative ring can have no least common multiple or more than one. However, any two least common multiples of the same pair of elements are associates. In a unique factorization domain, any two elements have a least common multiple. In a principal ideal domain, the least common multiple of a and b can be characterised as a generator of the intersection of the ideals generated by a and b (the intersection of a collection of ideals is always an ideal). In principal ideal domains, one can even talk about the least common multiple of arbitrary collections of elements: it is a generator of the intersection of the ideals generated by the elements of the collection.