Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2015-04-03 14:12:23

tush9211
Member
Registered: 2015-04-03
Posts: 1

Finding numbers if LCM is given.

Suppose we are given a number N.
Can we find all the combinations of numbers whose LCM is N?

Offline

#2 2015-04-03 19:46:17

Bob
Administrator
Registered: 2010-06-20
Posts: 10,058

Re: Finding numbers if LCM is given.

hi tush9211

Welcome to the forum.

Yes, this can be done.

Reduce the number to its prime factors.  Hence list all the factors. Then find all the combinations of those factors to produce two numbers.  The list could be quite large.

example.  I'll choose N = 15 to keep the list short.

15 = 3 x 5 so the factors are {1,3,5,15}

So here's all the possible pairs:

1,15
3,15
5,15
3,5

I think that's a full list.

Just adding one more factor, greatly increases the list:

example 2.  N = 30

30 = 2 x 3 x 5 so the factors are {1,2,3,5,6,10,15,30}

1,30
2,30
3,30
5,30
6,30
10,30
15,30
2,15
6,15
10,15
3,10
6,10
5,6


Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#3 2015-04-04 03:08:40

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Finding numbers if LCM is given.

What about 15,15 or 30,30?

Last edited by Olinguito (2015-04-04 03:09:22)


Bassaricyon neblina

Offline

#4 2015-04-04 03:17:57

Bob
Administrator
Registered: 2010-06-20
Posts: 10,058

Re: Finding numbers if LCM is given.

Olinguito wrote:

What about 15,15 or 30,30?

Yes, those too.  Whoops.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#5 2015-04-04 09:28:49

math9maniac
Member
From: Tema
Registered: 2015-03-30
Posts: 443

Re: Finding numbers if LCM is given.

Uhm, hi Bob, it seems your explanation is for GCF or HCF instead and not LCM.


Only a friend tells you your face is dirty.

Offline

#6 2015-04-04 20:06:05

Bob
Administrator
Registered: 2010-06-20
Posts: 10,058

Re: Finding numbers if LCM is given.

hi math9maniac

Why do you say that? 

If you take for example my 5,6 pair.

The multiples of 5 are {5,10,15,20,25,30,35,40,........}

The multiples of 6 are {6,12,18,24,30,36,42,........}

The lowest number in both lists is 30.  So LCM{5,6} = 30.

The equivalent problem with HCF would have an infinite list.

eg.  Find all the combinations of pairs of numbers that have an HCF of 15.

15,30
15,45
15,60
15.......................

30,45
30,75

and so on

One way of solving both HCF and LCM problems involves reducing both numbers to products of primes.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#7 2015-04-13 04:39:48

ishwar
Member
Registered: 2015-04-12
Posts: 2

Re: Finding numbers if LCM is given.

ok say N is 15. The factors are 1 3 5 and 15. One way to do it is say,what two groups of numbers can have together,the factors 1,3,5 and 15.
one way is start with each second number and work out the possible first numbers.
so here I go with,

1,15
3,15
5,15
15,15
Now set the second no. to 5 but avoid 15 cos we already included that but it should be multiple of 3.
3,5.

we cant do it with 3 or 1.

So here we go! the answer is

1,15
3,5
3,15
5,15
15,15.

Lets do another much harder example.
N is 60.
The prime factorization is 2 squared*3*5
And all the factors are:
1,2,3,4,5,6,10,12,15,20,30,60.

the 60s we have all the factors with a 60:

1,60
2,60
3,60
4,60
5,60
6,60
10,60
12,60
15,60
20,60
30,60
60,60.

Now the 30s.
60/30=2 and 30 is divisible by 2.So the divisiblility no.has to have another 2 in it,so the other ones are factors divisible by 4 but not 60 since we already included 60.

4,30
12,30
20,30

Now the 20s.
60/20=3 but 20 is not divisible by 3.The first number has to be divisible by 3.60 and 30 are not there since they had 20 in them.

3,20
6,20
12,20
15,20
Now the 15s.
60/15 is 4.15 isn't divisible by 4 so... you get the idea.20 and 60 are excluded

4,15
12,15

and so on...

the 12s:

10,12.

the 10s:
wait a second.30 is also excluded in addition to 12 and 60 since it is a multiple of 10.

6,10

1,2,3,4,5 and 6 have no solutions since they are less than square root of 60.

So FINALLY we have our answer.





1

Last edited by ishwar (2015-04-13 18:14:28)

Offline

Board footer

Powered by FluxBB