|
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
- <math>{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42},<math>
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:
- <math>\operatorname{lcm}(a,b)=\frac{a\cdot b}{\operatorname{gcd}(a,b)}.<math>
Thus, the Euclidean algorithm for the gcd also gives us a fast algorithm for the lcm. To return to the example above,
- <math>\operatorname{lcm}(21,6)={21\cdot6\over\operatorname{gcd}(21,6)}={126\over3}=42.<math>
Efficient calculation
The formula
- <math>\operatorname{lcm}(a,b)=\frac{(a\cdot b)}{\operatorname{gcd}(a,b)}<math>
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:
- <math>\operatorname{lcm}(a,b)=\left({a\over\operatorname{gcd}(a,b)}\right)\cdot b<math>
or
- <math>\operatorname{lcm}(a,b)=a\cdot\left({b\over\operatorname{gcd}(a,b)}\right)\;.<math>
Done this way, the previous example becomes:
- <math>\operatorname{lcm}(21,6)={21\over\operatorname{gcd}(21,6)}\cdot6={21\over3}\cdot6=7\cdot6=42.<math>
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 consider analogously as the atomic elements which when combined together makes up a composite number.
For example:
- <math>90 = 2^1 \cdot 3^2 \cdot 5^1 = 2 \cdot 9 \cdot 5 \,\!<math>
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)
- <math>45\; \, = 2^0 \cdot 3^2 \cdot 5^1 \,\!<math>
- <math>120 = 2^3 \cdot 3^1 \cdot 5^1 \,\!<math>
- <math>75\; \,= 2^0 \cdot 3^1 \cdot 5^2. \,\!<math>
The lcm is the number which has the greatest multiple of each different type of atom. Thus
- <math>\operatorname{lcm}(45,120,75) = 2^3 \cdot 3^2 \cdot 5^2 = 8 \cdot 9 \cdot 25 = 1800. \,\!<math>
External links
- Online lcm calculator (http://wims.unice.fr/wims/wims.cgi?module=tool/popup.en&search=lcm)
- LCM Quiz (http://www.kwiznet.com/p/takeQuiz.php?ChapterID=1460&CurriculumID=5)
|
