Difference between revisions of "Least common multiple"
I like pie (talk | contribs) |
|||
| Line 1: | Line 1: | ||
| − | The '''least common multiple''' (LCM) of two or more [[positive integer]]s is the smallest [[integer]] which is a [[multiple]] of all of them. Any [[finite]] [[set]] of integers has an [[infinite]] number of common multiples, but only one LCM. The LCM of a set of numbers <math>\{a_1,a_2,\cdots,a_n\}</math> is conventionally represented as <math>[a_1,a_2,\ | + | The '''least common multiple''' ('''LCM''') of two or more [[positive integer]]s is the smallest [[integer]] which is a [[multiple]] of all of them. Any [[finite]] [[set]] of integers has an [[infinite]] number of common multiples, but only one LCM. The LCM of a set of numbers <math>\{a_1,a_2,\cdots,a_n\}</math> is conventionally represented as <math>[a_1,a_2,\ldots,a_n]</math>. |
== How to find == | == How to find == | ||
| − | ===Brute force=== | + | === Brute force === |
The most primitive way to find the LCM of a set of numbers is to list out the multiples of each until you find a multiple that is common to all of them. This is a tedious method, so it is usually only used when the numbers are small. For example, suppose we wanted to find the LCM of two numbers, 4 and 6. We would begin by listing the multiples of 4 and 6 until we find the smallest number in both lists, as shown below. | The most primitive way to find the LCM of a set of numbers is to list out the multiples of each until you find a multiple that is common to all of them. This is a tedious method, so it is usually only used when the numbers are small. For example, suppose we wanted to find the LCM of two numbers, 4 and 6. We would begin by listing the multiples of 4 and 6 until we find the smallest number in both lists, as shown below. | ||
| Line 10: | Line 10: | ||
12 is the LCM of 4 and 6. | 12 is the LCM of 4 and 6. | ||
| − | ===Using prime factorization=== | + | === Using prime factorization === |
The LCM of two or more numbers can also be found using [[prime factorization]]. In order to do this, factor all of the numbers involved. For each [[prime number]] which divides any of them, take the largest [[exponentiation | power]] with which it appears, and multiply the results together. For example, to find the LCM of 8, 12 and 15, write: | The LCM of two or more numbers can also be found using [[prime factorization]]. In order to do this, factor all of the numbers involved. For each [[prime number]] which divides any of them, take the largest [[exponentiation | power]] with which it appears, and multiply the results together. For example, to find the LCM of 8, 12 and 15, write: | ||
| Line 21: | Line 21: | ||
Three primes appear in these factorizations, 2, 3 and 5. The largest power of 2 that appears is <math>2^3</math>; the largest power of 3 that appears is <math>3^1</math>; and the largest power of 5 that appears is <math>5^1</math>. Therefore the LCM, <math>LCM(8, 12, 15) = 2^3\cdot 3^1\cdot 5^1 = 120</math>. | Three primes appear in these factorizations, 2, 3 and 5. The largest power of 2 that appears is <math>2^3</math>; the largest power of 3 that appears is <math>3^1</math>; and the largest power of 5 that appears is <math>5^1</math>. Therefore the LCM, <math>LCM(8, 12, 15) = 2^3\cdot 3^1\cdot 5^1 = 120</math>. | ||
| − | ===Using the GCD=== | + | === Using the GCD === |
The LCM of two numbers can be found more easily by first finding their [[greatest common divisor]] (GCD). Once the GCD is known, the LCM is calculated by the following equation, <math> LCM(a, b) = \frac{a \cdot b}{GCD(a, b)} </math>. | The LCM of two numbers can be found more easily by first finding their [[greatest common divisor]] (GCD). Once the GCD is known, the LCM is calculated by the following equation, <math> LCM(a, b) = \frac{a \cdot b}{GCD(a, b)} </math>. | ||
Let's use our first example. The GCD of 4 and 6 is 2. Using the above equation, we find <math> LCM(4, 6) = \frac{4 \cdot 6}{2} = \frac{24}{2} = 12 </math>, just like we expected. | Let's use our first example. The GCD of 4 and 6 is 2. Using the above equation, we find <math> LCM(4, 6) = \frac{4 \cdot 6}{2} = \frac{24}{2} = 12 </math>, just like we expected. | ||
| + | |||
| + | == See also == | ||
| + | * [[Common multiple]] | ||
| + | * [[Greatest common divisor]] | ||
| + | |||
| + | [[Category:Definition]] | ||
Revision as of 10:14, 19 April 2008
The least common multiple (LCM) of two or more positive integers is the smallest integer which is a multiple of all of them. Any finite set of integers has an infinite number of common multiples, but only one LCM. The LCM of a set of numbers 
is conventionally represented as ![$[a_1,a_2,\ldots,a_n]$](http://latex.artofproblemsolving.com/a/7/f/a7f0fdfa5bc98445f5cbfa029f5f9d6613d47dbf.png)
.
How to find
Brute force
The most primitive way to find the LCM of a set of numbers is to list out the multiples of each until you find a multiple that is common to all of them. This is a tedious method, so it is usually only used when the numbers are small. For example, suppose we wanted to find the LCM of two numbers, 4 and 6. We would begin by listing the multiples of 4 and 6 until we find the smallest number in both lists, as shown below.
4 8 12
6 12
12 is the LCM of 4 and 6.
Using prime factorization
The LCM of two or more numbers can also be found using prime factorization. In order to do this, factor all of the numbers involved. For each prime number which divides any of them, take the largest power with which it appears, and multiply the results together. For example, to find the LCM of 8, 12 and 15, write:
Three primes appear in these factorizations, 2, 3 and 5. The largest power of 2 that appears is 
; the largest power of 3 that appears is 
; and the largest power of 5 that appears is 
. Therefore the LCM, 
.
Using the GCD
The LCM of two numbers can be found more easily by first finding their greatest common divisor (GCD). Once the GCD is known, the LCM is calculated by the following equation, 
.
Let's use our first example. The GCD of 4 and 6 is 2. Using the above equation, we find 
, just like we expected.
