Chemistry - 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 fractions, because it yields the lowest common denominator. Consider for instance

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

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:

$\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)}={126\over3}=42.$

Efficient calculation

The formula

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

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:

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

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

Done this way, the previous example becomes:

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

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:

$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.

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)

$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. \,\!$

External links

Categories: Elementary arithmetic