|
|
|
The Least Common Multiple of two or more numbers is the smallest number that is a multiple of all the numbers.
I'll illustrate with some examples:
Find the LCM of the following numbers: 24, 180, 54. Their prime factorizations are:
24 = 23 × 31 × 50 180 = 22 × 32 × 51 54 = 21 × 33 × 50
Now add a row to this table that shows the maximum exponent of each base:
24 = 23 × 31 × 50 180 = 22 × 32 × 51 54 = 21 × 33 × 50 Maximum 23 × 33 × 51
The maximum exponent of each base gives 23 33 51 = 1080. Here is the table, completely filled out.
24 = 23 × 31 × 50 180 = 22 × 32 × 51 54 = 21 × 33 × 50 Maximum (LCM) 1080 = 23 × 33 × 51
Practice this method with a few different sets of numbers, and you will see how it works. If you have a question about this method, send me an email (click the link at the bottom of this page).
Take any two numbers, call them "x" and "y", and multiply them together. Save that product for future reference.
Now, find the GCD of x and y, and also find the LCM of x and y. Multiply the GCD and the LCM together -- what do you discover? That's right. The GCD times the LCM are equal to x times y.
Let's take a close look at what's happening here. I'll take 24 and 180 as my examples. The GCD has all the primes with the minimum exponent of that prime in either number; the LCM has all the primes with the maximum exponent of that prime in either number:
24 = 23 × 31 × 50 180 = 22 × 32 × 51 Minimum (GCD) 12 = 22 × 31 × 50 Maximum (LCM) 360 = 23 × 32 × 51
Now you may not know this yet, but I'll tell you now, you can find the product 23 and 22 by adding their exponents, so the product is 25, which is 32. So the product of 24 and 180 is given by this calculation:
24 = 23 × 31 × 50 180 = 22 × 32 × 51 24 × 180 = 25 × 33 × 51
I just added up the exponents. 24 × 180 happens to be 4320, and its prime factorization happens to be 25 × 33 × 51 -- you can check these facts for yourself. (And you should!) Now, let's find the product of the GCD and LCM the same way:
(GCD) 12 = 22 × 31 × 50 (LCM) 360 = 23 × 32 × 51 GCD × LCM = 25 × 33 × 51
Is it just a coincidence that the product of the GCD and LCM of 24 and 180 are exactly equal to the product of 24 and 180? Try some other numbers, and see if you can spot the pattern.
Once you spot the pattern, then how does this help you?
Well, it's quite a bit easier to spot the GCD than the LCM. For example, take 66 and 77 -- you can see they're both multiples of 11, so 11 is the GCD. But what is the LCM? Simple: LCM = 66 × 77 � 11, which is 66 × 7, or 462.
How to do Prime Factorization
The webmaster and author of this Math Help site is Graeme McRae.