Let $S$ be the set of all ordered pairs $(x,y)$ of positive integers, with HCF $(x,y) = 16$ and LCM $(x,y) = 48000$. The
number of elements in $S$ is
My Attempt : $48000= 2^7. 3 . 5^3$ As the L.c.m contains $2^7$ as a factor and G.c.d contains $2^4$ as a factor , we can assure that one element contains $2^7$ and the other one contains $2^4$. And $3$ and $5^3$ will be divided between two numbers in a manner so that the L.C.M and G.C.D remain as given.
So the possible pairs are $(2^7 .3 . 5^3 , 2^4)$ , $(2^7 .3 , 5^3.2^4)$ , $(2^7 , 3.5^3.2^4)$ , $(2^7.5^3 , 3.2^4)$.
So I think the number of elements in the set $S$ is $4$. Have I gone wrong anywhere? Can anyone please help me ?
Best Answer
Let $m$ and $n$ be positive integers such that $m\mid n$. Then the number of solutions $(x,y)$ of positive integers $x,y$ such that $$\gcd(x,y)=m$$ and $$\operatorname{lcm}(x,y)=n$$ is $$2^{\omega(n/m)},$$ where $\omega$ is the prime $\omega$-function, namely, $\omega(d)$ is the number of distinct prime divisors of $d$ (e.g., $\omega(1)=0$, $\omega(9)=1$, $\omega(12)=2$). For a proof, each prime $p$ dividing $n/m$ has two choices, namely,
Here, $p^k \parallel d$ if $p^k\mid d$ but $p^{k+1}\nmid d$, and $s_p$ and $t_p$ are such that $p^{s_p}\parallel m$ and $p^{t_p}\parallel n$.
In particular, for $m=16$ and $n=48000$, we have $$\frac{n}{m}=3000=2^3\cdot 3\cdot 5^3$$ so that $\omega(n/m)=3$. Hence, the answer is $2^3=8$.
If the number of unordered pairs $\{x,y\}$ is to be calculated or if you require that $x\leq y$, then the answer is $$\left\lceil 2^{\omega\left(\frac{n}{m}\right)-1}\right\rceil\,.$$ (Normally, you wouldn't need the ceiling function. It is needed only in the special case where $m=n$.) In particular, for $m=16$ and $n=48000$, the number of solutions with $x\leq y$ is $\frac{2^3}{2}=4$.