5
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ No, tell us first how many natural numbers $x\leqslant\color{red}{20!}$ are there such that $\gcd(x,20!)=1$. $\endgroup$ – Ivan Neretin Jul 7 '16 at 8:45
  • 1
    $\begingroup$ 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$? $\endgroup$ – Gerry Myerson Jul 7 '16 at 9:10
  • $\begingroup$ @IvanNeretin $\varphi(20!)$? $\endgroup$ – Error 404 Jul 7 '16 at 9:16
  • 2
    $\begingroup$ 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... $\endgroup$ – Ivan Neretin Jul 7 '16 at 9:21
  • $\begingroup$ I will be happy to get a full answer from someone $\endgroup$ – Error 404 Jul 7 '16 at 10:17
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – joriki Jul 7 '16 at 10:58
  • $\begingroup$ May be I understood the question wrongly @joriki $\endgroup$ – Kushal Bhuyan Jul 7 '16 at 11:00
  • $\begingroup$ I don't understand what you mean. I think the question is clear. $\endgroup$ – Levent Jul 7 '16 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.