Question: Find the number of rational numbers $\frac{m}{n}$ s.t. $\gcd(m,n)=1\;\land\; m,n\in\mathbb N\;\land m<n\;\land\;mn=25!
$
My approach:
Instead of taking $25$ in particular, let us take any $n\in\mathbb{N}$ and $n>1$. Let $a_i$ be the highest power of the $i^{th}$ prime $p_i$ s. t. $p_i^{a_i}|n!$.
Now consider the multiset $$S_n=\{\underbrace{2,2,2,\cdots,2}_{a_1},\underbrace{3,3,3,\cdots,3}_{a_2},\cdots,\underbrace{p_k,p_k,p_k,\cdots,p_k}_{a_k}\}$$ where $p_k$ is the greatest prime that divides $n$.
Let us choose any block of primes from $S_n$ or a combination of them and multiply all of them together (let us call this product to be $P$) and take the remaining block of primes in $S_n$ and multiply them together (let us call this product to be $p$). Now observe that $\forall P,p$, we have, $P\neq p$. $\implies P<p\;\underline{\lor}\;P>p$.
Also, we have $\gcd(P,p)=1$.
Now suppose WLOG that $P>p$, then setting $m=p$ and $n=P$, yields one of our required rational number $\frac{m}{n}=\frac{p}{P}$. And moving on like this we can find all of our required rational numbers.
Now let us move on to find the number of such rational numbers for our given $n$.
Now consider the set $$S_n^{'}=\{2,3,\ldots,p_k\}.$$
Observe that selecting any subset of $S_n^{'}$ corresponds to one of our required rational number. Therefore, counting the total number of subsets would yield the total number of our required rational numbers. But, while doing this, observe that we count each solution twice. Therefore, taking the half of the total number of subsets of $S_n^{'}$ would yield our answer.
Thus if the total number of primes that divides $n!$ is $p$ then the total number elements in $S_n^{'}$ is $p$, and hence the total number of subsets of $S_n^{'}$ is equal to $2^p$. Hence the total number of required solutions would be $2^{p-1}$.
Now let us consider the special case where $n=25$. Since, there $9$ primes less than or equal to $25$, implies $9$ primes divides $25$, which in turn $\implies p=9$. Therefore, the total number of required solutions=$2^{9-1}=2^8=256.$
Is my solution correct and rigorous enough and is there a shorter and better solution?
Best Answer
This approach looks good. You try to use combinatorics in sets of numbers. Your main combinatoric element was number of primes less than given point n. By definition using it for that sounds good. Really good problem. Try find other opinions.