# Number of $1\leq n \leq 1000$ such that $\gcd(n,3000)=5$

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

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

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.$$