# Find the number of rational numbers $m/n$, where $m,n$ are relatively prime positive integers satisfying $m<n$ and $mn=25!$.

Question: Find the number of rational numbers $$\frac{m}{n}$$ s.t. $$\gcd(m,n)=1\;\land\; m,n\in\mathbb N\;\land m

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

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?

• I'm fine with it Mar 29, 2020 at 13:48