Finding coprime $p,q$ such that $pq=10! $ and $ p<q$

123 Views Asked by At

Find the number of fractions p/q such that $\gcd(p,q)=1$ and $p<q$, where $pq=10!$.
My approach: The obvious first step is to factor $10!$, and this comes out to be $$10!= 2^8\times 3^4\times 5^2\times 7$$ This further tells us that there are a total of $270$ divisors. Now, i don't believe the factors are symmetric in such a sense that, in $\frac 12$ of the cases,$p>q$, and for the remaining half $q>p$ , so the answer cannot be $135$.

Since p,q are coprime, they share no common factors, but then the additional constraint,$p<q$ makes the calculations quite cumbersome.

This was part of an 11th grade problem book under "permutations and combinations".

2

There are 2 best solutions below

0
On BEST ANSWER

The number $10!$ has $4$ distinct prime factors, namely $2$, $3$, $5$, and $7$. Hence, it has $2^4=16$ unitary divisors. Of those $16$ unitary divisors, half of them, or $8$, are under $\sqrt{10!}$.

0
On

After insight(s) by Lulu and TonyK,I believe I can answer this now. Say the number N has $r$ distinct prime factors. Then the number of pairs $(p,q)$ such that $pq=N$ and $gcd(p,q)=1$, can simply be obtained by dividing the r prime factors into 2 groups. For which there are ${r\choose 0}+{r\choose 1}.....{r\choose r}=2^r$ cases. Which, as TonyK pointed out , is always even except for r=0. Now , for exactly $1/2$ of these cases, p is less than q.