# Find all rational numbers $\frac p q$ such that $0 < p < q$ are relatively prime and $pq=25!$

Find all the rational numbers $\frac p q$ such that all the below three conditions are satisfied.

$$0<\frac{p}q<1,$$ $$p \hspace{4 mm} \text{and} \hspace{5 mm}q \hspace{5 mm}\text{are relatively prime, and}$$ $$pq=25!$$

My try

What i feel that answer should be $\sum_{r=1}^{9}\binom{9}{r}$ I have arranged the 9 primes between 1 to 25. but i guess not correct.

i still think that i am doing some silly mistake. Can you please provide me the answer ?

• Hint: Consider the prime factorization of $25!$, since $pq=25!$, this seriously limits the possibilities for $p$ and $q$, then you should ask yourself what it means for these number to be relatively prime. The first condition just says that $p<q$. Commented Jul 4, 2016 at 15:47

First we find the number of ordered pairs $(s,t)$ of positive integers such that $s$ and $t$ are relatively prime and $st=25!$. So we must decide which of the $2^9$ subsets of the $9$ primes less than $25$ to "give" to $s$. That completely determines $s$ and $t$.

Exactly half of these choices will give $s\lt t$, so the number of fractions of the desired type is $2^8$.

• Thanks brother... :) i need it . Commented Jul 4, 2016 at 16:03
• @Joffan: We are counting ordered pairs $(s,t)$ such that $s$ and $t$ are relatively prime, so $s=t$ is automatically excluded. Commented Jul 4, 2016 at 16:10
• Observation 1: $25! = 2^{22} \cdot 3^{10} \cdot 5^6 \cdot 7^3 \cdot 11^2 \cdot 13 \cdot 17 \cdot 19 \cdot 23$
• Observation 2: $m$ and $n$ are comprised of and only of these factors. Also, if a prime factor divides $m$, it cannot divide $n$. Hence, the factors must occur in clusters, in which all primes are together.

The problem thus reduces to partitioning the 9 clusters $2^{22}, 3^{10} , 5^6 , 7^3 , 11^2 , 13 , 17 , 19 , 23$ into $m$ and $n$.

For any cluster, there are two choices, it could either be in $m$ or in $n$. So, there are $2^9$ ways to split them.

How do we eliminate the cases where $m > n$? Well, for any pair $(m, n)$, if $m > n$, switching them obtains a pair $(n, m)$, where $n < m$. Hence there are half as many ways to split the numbers in the way we desire.

That'd be $\frac{2^9}{2} = \boxed{2^8}$ ways.

• Beautiful answer, thanks Commented Apr 11, 2022 at 14:40