Lowest Common Multiple (LCM)

[Probability]

I have been practicing the LCM ideas from maths books, I can see their methods which are very similar to finding the HCF in their ideas, but I do get confused after factoring and looking at all the prime numbers, sometimes the examples don't stand out clear which numbers to use to find the LCM, by example;

Find the lowest common multiple of; 196, 210, 462, 910.

So I take it to mean that the LCM is the smallest number that all these numbers will go into, in this example that smallest number is very large at [420420]

Now working this out;

196 = [2 x 2] x [7 x 7]
210 = 2 x [5 x 3] x 7
462 = 2 x 3 x 7 x [11]
910 = 2 x 5 x 7 x [13]

Hence the lowest common multiple (LCM) is 2 x 2 x 3 x 5 x 7 x 7 x 11 x 13 = 420420

The prime numbers have five 2's, two 3's, two 5's, five 7's, one 11 and one 13

The difficult part is understanding without using trial and improvement all the time how to (know) select the correct prime numbers in each LCM examples to reach the correct solution, as the above example shows some type of formula to solve these LCM problems must be available?

Please advise

 

[Ishuda]

I have been practicing the LCM ideas from maths books, I can see their methods which are very similar to finding the HCF in their ideas, but I do get confused after factoring and looking at all the prime numbers, sometimes the examples don't stand out clear which numbers to use to find the LCM, by example;

Find the lowest common multiple of; 196, 210, 462, 910.

So I take it to mean that the LCM is the smallest number that all these numbers will go into, in this example that smallest number is very large at [420420]

Now working this out;

196 = [2 x 2] x [7 x 7]
210 = 2 x [5 x 3] x 7
462 = 2 x 3 x 7 x [11]
910 = 2 x 5 x 7 x [13]

Hence the lowest common multiple (LCM) is 2 x 2 x 3 x 5 x 7 x 7 x 11 x 13 = 420420

The prime numbers have five 2's, two 3's, two 5's, five 7's, one 11 and one 13

The difficult part is understanding without using trial and improvement all the time how to (know) select the correct prime numbers in each LCM examples to reach the correct solution, as the above example shows some type of formula to solve these LCM problems must be available?

Please advise

For the LCM you must have at least the number of prime numbers for each of the given numbers, i.e. for
196 = 2 x 2 x 7 x 7
you must have at least two 2's and two 7's. Now look at
210 = 2 x 3 x 5 x 7
Well you already have two 2's so you don't need any more of these, you don't have a 3 so you will need one 3, you don't have a 5 so you will need one 5, and you already have two 7's so you won't need any more of these. You can continue in this way to get what you need.

This turn's out to be the following: List all the primes, p₁, p₂, p₃, ..., p_m occurring in the numbers. Remembering that p⁰ = 1, we can write each of the i number's n_j; j=1, 2, 3, ...i as
n_j = p₁^k_j,1 * p₂^k_j,2 * p₃^k_j,3 * ... * p_m^k_j,m
now let
o₁ = max(k_j,1; j = 1,2, 3, ..., m)
o₂ = max(k_j,2; j = 1,2, 3, ..., m)
o₃ = max(k_j,3; j = 1,2, 3, ..., m)
...
o_i = max(k_j,i; j = 1,2, 3, ..., m)
The LCM is then
LCM = p₁^o_j,1 * p₂^o_j,2 * p₃^o_j,3 * ... * p_m^o_j,m

That looks more complicated than it is so let's use 5, 16, and 120 as an example: The primes we need are 2, 3, and 5.

[FONT=courier new]
  5 = 2[SUP]0[/SUP] * 3[SUP]0[/SUP] * 5[SUP]1[/SUP]
 16 = 2[SUP]4[/SUP] * 3[SUP]0[/SUP] * 5[SUP]0[/SUP]
120 = 2[SUP]3[/SUP] * 3[SUP]1[/SUP] * 5[SUP]1[/SUP][/FONT]

The maximum exponent for the prime 2 is 4. The maximum exponent for the prime 3 is 1. The maximum exponent for the prime 5 is 1. So the LCM is given by
LCM = 2⁴ * 3¹ * 5¹ = 16 * 3 * 5 = 240

EDIT: I just looked at this again and saw that it was under Arithmetic and realized that my answer might be a bit beyond that. Possibly
http://www.cimt.plymouth.ac.uk/projects/mepres/book8/bk8i2/bk8_2i4.htm
may explain it better.

 

[Probability]

For the LCM you must have at least the number of prime numbers for each of the given numbers, i.e. for
196 = 2 x 2 x 7 x 7
you must have at least two 2's and two 7's. Now look at
210 = 2 x 3 x 5 x 7
Well you already have two 2's so you don't need any more of these, you don't have a 3 so you will need one 3, you don't have a 5 so you will need one 5, and you already have two 7's so you won't need any more of these. You can continue in this way to get what you need.

This turn's out to be the following: List all the primes, p₁, p₂, p₃, ..., p_m occurring in the numbers. Remembering that p⁰ = 1, we can write each of the i number's n_j; j=1, 2, 3, ...i as
n_j = p₁^k_j,1 * p₂^k_j,2 * p₃^k_j,3 * ... * p_m^k_j,m
now let
o₁ = max(k_j,1; j = 1,2, 3, ..., m)
o₂ = max(k_j,2; j = 1,2, 3, ..., m)
o₃ = max(k_j,3; j = 1,2, 3, ..., m)
...
o_i = max(k_j,i; j = 1,2, 3, ..., m)
The LCM is then
LCM = p₁^o_j,1 * p₂^o_j,2 * p₃^o_j,3 * ... * p_m^o_j,m

That looks more complicated than it is so let's use 5, 16, and 120 as an example: The primes we need are 2, 3, and 5.

[FONT=courier new]
  5 = 2[SUP]0[/SUP] * 3[SUP]0[/SUP] * 5[SUP]1[/SUP]
 16 = 2[SUP]4[/SUP] * 3[SUP]0[/SUP] * 5[SUP]0[/SUP]
120 = 2[SUP]3[/SUP] * 3[SUP]1[/SUP] * 5[SUP]1[/SUP][/FONT]

The maximum exponent for the prime 2 is 4. The maximum exponent for the prime 3 is 1. The maximum exponent for the prime 5 is 1. So the LCM is given by
LCM = 2⁴ * 3¹ * 5¹ = 16 * 3 * 5 = 240

EDIT: I just looked at this again and saw that it was under Arithmetic and realized that my answer might be a bit beyond that. Possibly
http://www.cimt.plymouth.ac.uk/projects/mepres/book8/bk8i2/bk8_2i4.htm
may explain it better.

Thank you for your very much appreciated efforts, yes your right it is a bit advanced for a beginner. I found a much easier method;

196/2 = 98. Write it out like this;

196 = 1 x ... 196
196 = 1 x 2... 98
196 = 1 x 2 x 4... 49

so I end up writing;

196 = 1 x 2 x 4....... 49, 98, 196

As the number meet in the middle at some point, GCD will be found, then;

196 x 210 = 41160, now divide this by the GCD calculated, let's just say 14, we end up with a LCM of 2940 for those two numbers, so now I follow the same line of reasoning and find the remaining GCD and finish off the question.

Thank you for your advice.

 

[Deleted member 4993]

I have been practicing the LCM ideas from maths books, I can see their methods which are very similar to finding the HCF in their ideas, but I do get confused after factoring and looking at all the prime numbers, sometimes the examples don't stand out clear which numbers to use to find the LCM, by example;

Find the lowest common multiple of; 196, 210, 462, 910.

So I take it to mean that the LCM is the smallest number that all these numbers will go into, in this example that smallest number is very large at [420420]

Now working this out;

196 = [2 x 2] x [7 x 7]
210 = 2 x [5 x 3] x 7
462 = 2 x 3 x 7 x [11]
910 = 2 x 5 x 7 x [13]

Hence the lowest common multiple (LCM) is 2 x 2 x 3 x 5 x 7 x 7 x 11 x 13 = 420420

The prime numbers have five 2's, two 3's, two 5's, five 7's, one 11 and one 13

The difficult part is understanding without using trial and improvement all the time how to (know) select the correct prime numbers in each LCM examples to reach the correct solution, as the above example shows some type of formula to solve these LCM problems must be available?

Please advise

I was taught the following way:

Find a common "prime" divisor of at least two numbers

LCM of (196, 210,462,910) = 2*(98, 105, 231, 455) → 2* 3* (98, 35, 77, 455) → 2*3*5*(98, 7, 77, 91) → 2*3*5*7*(14 , 1, 11, 13)

(14 , 1, 11, 13) are all relatively prime.

So LCM of (196, 210,462,910) = 2*3*5*7*(14 * 1* 11* 13) = 420420

This algorithm works for me!!

 

[Ishuda]

Thank you for your very much appreciated efforts, yes your right it is a bit advanced for a beginner. I found a much easier method;

196/2 = 98. Write it out like this;

196 = 1 x ... 196
196 = 1 x 2... 98
196 = 1 x 2 x 4... 49

so I end up writing;

196 = 1 x 2 x 4....... 49, 98, 196

As the number meet in the middle at some point, GCD will be found, then;

196 x 210 = 41160, now divide this by the GCD calculated, let's just say 14, we end up with a LCM of 2940 for those two numbers, so now I follow the same line of reasoning and find the remaining GCD and finish off the question.

Thank you for your advice.

The method given in the link can be extended to

[FONT=courier new]
196 = 2 * 2 *         7 * 7
210 = 2 *     3 * 5 * 7
462 = 2 *     3 *     7 *     11
910 = 2 *         5 * 7 *          13
--------------------------------------
LCM = 2 * 2 * 3 * 5 * 7 * 7 * 11 * 13 = [FONT=courier new]420420
HCF = 2 *             7               = 14[/FONT][/FONT]

where you line up the primes in the prime factorization of the numbers. Then on the bottom you put the prime everywhere there is a prime above the line for a number (where there is a prime in any list of the prime factorizations) for the LCM and the prime everywhere the is a prime above the line for all numbers (where there is a prime in all lists of the prime factorizations) for the highest common factor (HCF)

 

[Probability]

Thanks again for your input, your experiences are very much appreciated.