# All pair of $m,n$ satisfying $lcm(m,n)=600$

Find the number of pairs of positive integers $(m,n)$, with $m \le n$, such that the ‘least common multiple’ (LCM) of $m$ and $n$ equals $600$.

My tries:

It's very clear that $n\le600$, always.

Case when $n=600=2^3\cdot 3\cdot 5^2$, and let $m=2^{k_1}\cdot 3^{k_2}\cdot 5^{k_3}$, all possible values of $k_1=3+1=4,\ k_2=1+1=2,\ k_3=2+1=3$. So number of $m$ which satisfy above will be $4\cdot 2 \cdot 3=24$

Help me analyzing when $n<600$.

• Please give me final solution. – mnulb Feb 3 '17 at 12:46

Forget about the condition $m\leq n$ for the moment. Since $600=2^3\cdot 3^1\cdot 5^2$ we have $$m=2^{\alpha_2}3^{\alpha_3}5^{\alpha_5},\quad n=2^{\beta_2}3^{\beta_3}5^{\beta_5}$$ with $\alpha_i$, $\beta_i\geq0$ and $$\max\{\alpha_2,\beta_2\}=3,\quad \max\{\alpha_3,\beta_3\}=1,\quad \max\{\alpha_5,\beta_5\}=2\ .$$ It follows that \eqalign{(\alpha_2,\beta_2)&\in\{(0,3),(1,3),(2,3),(3,3),(3,2),(3,1),(3,0)\}\>,\cr (\alpha_3,\beta_3)&\in\{(0,1),(1,1),(1,0)\}\>,\cr (\alpha_5,\beta_5)&\in\{(0,2),(1,2),(2,2),(2,1),(2,0)\}\cr} are admissible, allowing for $7\cdot3\cdot5=105$ combinations. Exactly one of them has $m=n$, namely $m=n=600$, and in all other $104$ cases $m\ne n$. Since we want $m\leq n$ we have to throw out half of these cases, leaving $52+1=53$ different solutions of the problem.

• Thank you so much!!! I really need something like this. – mnulb Feb 3 '17 at 16:58

The least common multiple of two integers, $a$ and $b$, can be calculated by the following procedure:

• Decompose $a$ and $b$ into prime factors;

• For every prime factor that is in $a$ but is not in $b$, put it in the $lcm$ factorization with the exponent it has in $a$;

• For every prime factor that is in $b$ but is not in $a$, put it in the $lcm$ factorization with the exponent it has in $b$;

• For every prime factor that is both in $a$ and in $b$, put it in the $lcm$ but with the biggest exponent of the two.

Example:

$a = 2^2 \cdot 5 \cdot 101^3\\ b = 2^3 \cdot 7^4 \cdot 11$

$5$ and $101$ appear in $a$ but not in $b$, so we get $5 \cdot 101^3$.

$7$ and $11$ appear in $b$ but not in $a$, so we get $5 \cdot 101^3 \cdot 7^4 \cdot 11$.

Finally, we have $2$ in both factorizations. Since the greatest exponent is $3$, we get $5 \cdot 101^3 \cdot 7^4 \cdot 11 \cdot 2^3 = 2^3 \cdot 5 \cdot 7^4 \cdot 11 \cdot 101^3$.

Therefore, if we have $lcm(n, m) = 600$, then neither $n$ nor $m$ can have prime factors other than $2, 3$ or $5$. What is more, none of them can have $2$ to a greater power than $3$, $3$ to a greater power than $1$ and $5$ to a greater power than $2$.

We can see that we must have the following:

$n = 2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3}\\ m = 2^{b_1} \cdot 3^{b_2} \cdot 5^{b_3}$

But also, we must have the following:

$$\begin{cases}\max\{a_1, b_1\} = 3\\ \max\{a_2, b_2\} = 1\\ \max\{a_3, b_3\} = 2\\ 0 \leq a_1,b_1 \leq 3\\ 0 \leq a_2, b_2 \leq 1\\ 0 \leq a_3, b_3 \leq 2\end{cases}$$

Therefore it is a simple matter of counting. Also note that for every possible factorization of $n$, if $n$ has one of its prime factors to a power that is not the maximum needed, then $m$'s prime is determined. For example, if you are counting the possibilities for $m$ when $n = 2\cdot3\cdot5^2$, you know immediately that $m$ has $2^3$ in its factorization and thus $m = 2^3 \cdot 3^x \cdot 5^y$ with $x$ and $y$ varying.

EDIT: included final computation:

Note that if $n$ does not have any of $2^3, 3$ and $5^2$, then $m$ is automatically determined. For those such $n$, you can pick any of $2^0, 2^1, 2^2$, then you have to pick $3^0$ and you can pick $5^0$ or $5^1$. Thus there are $3\cdot1\cdot2 = 6$ such pairs where $m$ must be $600$.

The remaining cases are counted by fixing what powers $n$ already has complete:

• $n$ only has $2^3$. There are $2$ ways to finish it (because it does not have $3$ nor $5^2$. $m$ has $4$ possibilities for the exponent of $2$ and the others are already determined. Thus there are $2\cdot4 = 8$ pairs.

• $n$ only has $3$. There are $3\cdot2$ ways to finish it. $m$ can only have $3^0$ or $3^1$ thus there are $6\cdot2 = 12$ such pairs.

• $n$ only has $5^2$. There are $3\cdot1$ ways to finish it. $m$ can have either $5^0$ or $5^1$ or $5^2$ thus there are $3\cdot2\cdot2 = 12$ such pairs.

• $n$ has $2^3$ and $3$: gives $2 \cdot 4 \cdot 2 = 16$ pairs.

• $n$ has $2^3$ and $5^2$: gives $1 \cdot 4 \cdot 3 = 12$ pairs.

• $n$ has $3$ and $5^2$: gives $3 \cdot 2 \cdot 3 = 18$ pairs.

• $n$ has $2^3$, $3$ and $5^2$: gives $4 \cdot 2 \cdot 3 = 24$ pairs.

Summing up, we have $24 + 18 + 12 + 16 + 12 + 12 + 8 + 6 = 108$ pairs.

As you have very nicely written, you have the factorisation $$600=2^3\cdot 3\cdot 5^2.$$ Now recall that the lcm of two numbers, given their prime factorisation, is the product of their prime factors to the highest power. For example $$lcm(2\cdot 3\cdot 5^7,2^2\cdot 5^6)=2^2\cdot3\cdot5^7$$

So you have to find all the possible numbers of the form $2^p3^q5^r$, $p\leq 3,q\leq 1,r\leq 2\$ so that at least one of them contains $2^3$, $3^5$ and $5^2$ as factors.

• last line you wrote $3^5$, it should be $3$ (may be?). – mnulb Feb 3 '17 at 9:49
• Yes to the first comment, absolutely no to the second. – b00n heT Feb 3 '17 at 15:24