4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Please give me final solution. $\endgroup$ – mnulb Feb 3 '17 at 12:46
2
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.