Given LCM of three natural numbers, find the possibilities.

LCM of three natural numbers =150. How many sets of three numbers are possible?

I know how to do this for two natural numbers.There is also a general formula for that. But for 3 numbers it is posing a problem. Is there a standard method for any n natural numbers?

• Are the numbers required to be different? Is order important? – paw88789 Mar 31 '15 at 10:53
• I got the answer as 156. – archangel89 Mar 31 '15 at 11:06

I will assume that the numbers are distinct, and that the order doesn't matter.

If we let D be the set of positive divisors of 150, let S be the set of 3-element subsets of D, and

let $A_i$ for $1\le i\le3$ be the set of 3-element subsets of D not containing a multiple of 2, 3, or 25, respectively,

then $|A_1^c\cap A_2^c\cap A_3^c|=|S|-|A_1|-|A_2|-|A_3|+|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|-|A_1\cap A_2\cap A_3|$

$\hspace{1.2 in}=\dbinom{12}{3}-\dbinom{6}{3}-\dbinom{6}{3}-\dbinom{8}{3}+\dbinom{3}{3}+\dbinom{4}{3}+\dbinom{4}{3}-0=133$.

• Hey, this answer actually has the correct result! :) – rogerl Mar 31 '15 at 20:14
• @rogerl Thanks for letting me know - I thought it was right, but wasn't absolutely positive. – user84413 Mar 31 '15 at 20:15
• I cheated. I used Mathematica to figure it out. – rogerl Mar 31 '15 at 20:16
• @rogerl I don't even know how to figure it out with Mathematica. – user84413 Mar 31 '15 at 21:41
• Count[Apply[LCM, Subsets[Divisors[150], {3}], {1}], 150] – rogerl Mar 31 '15 at 21:43

Hint

We are looking for the LCM of $3$ numbers, so consider the prime factorization of $150$:

$$150 = 50*3 = 5^2*2*3$$

Therefore, we have numbers of the form: $$5^x2^y3^z = 150$$

Where $x$, $y$, and $z$ are integers.

We also know that: $0 \le x \le 1$, $0 \le y \le 1$, $0 \le z \le 1$

• You meant $0 \leq x \leq 2$. – N. F. Taussig Mar 31 '15 at 11:04

$$150=2\cdot3\cdot5^2$$

The highest power of $2$ in at least one of the three number has to be $1$

This can be achieved in the following ways: $\{1,0,0\};\{1,1,0\};\{1,1,1\}$

The highest power of $5$ in at least one of the three number has to be $2$

This can be achieved in the following ways: $\{2,0,0\};\{2,1,0\};\{2,1,1\};\{2,2,0\};\{2,2,1\};\{2,2,2\}$

So, the number of possible distinct combinations $3\cdot3\cdot6$

• For the three number set, if the formula for the highest power is $n(\ge1),$ $$\sum_{r=0}^n (1\sum_{s=0}^r 1)=\dfrac{(n+1)(n+2)}2$$ – lab bhattacharjee Mar 31 '15 at 11:08
• Your matching doesn't work - the first component will always be divisible by $150$ if you take the factors in order - there are seven ways of having at least one number divisible by $2$, taking order into account, and $3+6+3+3+3+1=16$ ways of having at least one number divisible by $25$. That gives $7\times 7\times 16$ if order doesn't matter. But there are repetitions included, and it is not so easy using this method to de-duplicate. – Mark Bennet Mar 31 '15 at 11:11
• @MarkBennet, By the definition of set, I have assumed unique elements and order does not matter . – lab bhattacharjee Mar 31 '15 at 11:14
• But then you have to match the elements to get actual factors, and you have seven patterns from your three sets for $2$. – Mark Bennet Mar 31 '15 at 11:15
• @MarkBennet, Have you considered uniqueness? – lab bhattacharjee Mar 31 '15 at 11:16