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

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .