If $r,s,t$ are prime numbers and $p,q$ are the positive integers such that LCM of $p,q$ is $r^2s^4t^2$, then the number of ordered pairs $(p,q)$ is?
My attempt to the solution:
Let
$r^a s^b t^c$ be the LCM where $a=2,b=4,c=2$
Then the cases that arise are
I case
1) $p$ has $r^as^bt^c$ then there are a total of $(2+1)(4+1)(2+1)$ options
II case
1) $p$ has $r^as^b$ or $s^bt^c$,$r^at^c$ then there are total of $(2+1)(4+1)(2+1)(3)$ options.
The answers comes out to be $45*4$ but the answer is $45*5$. Which case am I missing?
Best Answer
Write $\nu_r(p)$ for the highest exponent $v$ such that $r^v$ divides $p$.
You have $\max \Big(\nu_r(p),\nu_r(q)\Big) = \nu_r\Big(\mathrm{lcm}(p,q)\Big) = 2,$ so this gives you possibilities $(\nu_r(p),\nu_r(q)) \in \{(0,2),(1,2),(2,2),(2,1),(2,0)\}.$
There are $5$ such possibilities.
The same logic works for $t$. There are $5$ ways to split up the powers of $t$ in $p$ and $q$.
For $s$, you will have the $9$ possibilities $$(\nu_s(p),\nu_s(q)) \in \{(0,4),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(4,0)\}.$$
Altogether, there are $5 \cdot 5 \cdot 9 = 45 \cdot 5$ ways to build $p$ and $q$ from their prime factors.