0
$\begingroup$

How can I determine the number of $1\leq n \leq 1000$ with $n \in \mathbb N$ such that $\gcd(n,3000)=5$?

'gcd' stands for greatest common divisor.

What would be a good way to solve this problem? I though about prime factorizations but perhaps there are better ways. Thanks

$\endgroup$
1
  • $\begingroup$ Prime factorization of 3000 is the key to solution. $\endgroup$
    – user
    Commented Apr 27, 2021 at 14:34

1 Answer 1

1
$\begingroup$

Note that $3000=2^3\cdot 3 \cdot 5^3$. Therefor, if $(n,3000)=5$, then $5$ divides $n$, $5^2$ does not divide $n$, $2$ does not divide $n$ and $3$ does not divide $n$. Write $n=5q$. We are looking for all the $q \leq 200$ such that $2,3,5$ do not divide $q$. We can use the inclusion-exclusion principle to calculate this. The number of such $q$ is

$$200-\left \lfloor{\frac{200}{2\cdot3\cdot5}}\right \rfloor +\left \lfloor{\frac{200}{2\cdot3}}\right \rfloor+\left \lfloor{\frac{200}{2\cdot5}}\right \rfloor+\left \lfloor{\frac{200}{3\cdot5}}\right \rfloor-\left \lfloor{\frac{200}{2}}\right \rfloor-\left \lfloor{\frac{200}{3}}\right \rfloor-\left \lfloor{\frac{200}{5}}\right \rfloor=54.$$

$\endgroup$

You must log in to answer this question.

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