# How many natural numbers $x\leqslant 21 !$ there are such that $\gcd(x,20!)=1$

How many natural numbers $x\leqslant 21 !$ there are such that $\gcd(x,20!)=1$

Attempt:

I used this methode and I have found that:

$21!$$=2^{18}\times3^{9}\times5^{4}\times7^{3}\times11\times13\times17\times19 20!$$=2^{18}\times3^{\color{red}8}\times5^{4}\times7^{\color{red}2}\times11\times13\times17\times19$

It's easy to see that the prime factorization contains the same prime numbers, but how can I know how many numbers $x\leqslant 21 !$ there are such that $\gcd(x,20!)=1$

If I look at $3$ and $3^2$, so there are $4$ numbers between $3$ and $9$ such that $\gcd(3,x)=1$ $3,\color{blue}4,\color{blue}5,6,\color{blue}7,\color{blue}8,9$

• No, tell us first how many natural numbers $x\leqslant\color{red}{20!}$ are there such that $\gcd(x,20!)=1$. – Ivan Neretin Jul 7 '16 at 8:45
• Let $n$ be the product of the primes up to 20. Can you work out how many numbers up to $n$ are relatively prime to $n$? – Gerry Myerson Jul 7 '16 at 9:10
• @IvanNeretin $\varphi(20!)$? – Error 404 Jul 7 '16 at 9:16
• That's right. Now add $20!$ to all these numbers. That would not change the gcd. Therefore the interval $(20!,2\cdot20!)$ contains exactly as much numbers that we want. Ditto for $(2\cdot20!,3\cdot20!)$, and so on... – Ivan Neretin Jul 7 '16 at 9:21
• I will be happy to get a full answer from someone – Error 404 Jul 7 '16 at 10:17

You can easily notice that for a natural number $n$, gcd$(n,20!)=1$ if and only if gcd$(n,21!)=1$. Thus you can ask the question as follows :
How many natural numbers $x\leq 21!$ such that gcd($x,21!)=1$. Then the answer is $\varphi(21!)$ which is easy to calculate.
• @KushalBhuyan: You're comparing the wrong numbers. You should be comparing the number of numbers coprime to $3!$ up to $4!$ and the number of numbers coprime to $4!$ up to $4!$, and these are both eight. – joriki Jul 7 '16 at 10:58