# How many positive integers $x \le 3600$ are there such that $\gcd(3600, x)=9$?

I'm trying to answer this question which has a hint: think about $$\mathbb Z_{3600}$$.

I tried to set up a linear equation,$$\mod{3600},$$ without any success. Not even the factorization of $$3600$$ gives me any ideas on how to set the problem.

Any help?

Note that$$\gcd(3600,x)=9\Longrightarrow x=9y\quad,\quad y\in \Bbb Z_{400}\to \gcd(400,y)=1$$therefore the number of solutions of $$\gcd(3600,x)=9$$ on $$\Bbb Z_{3600}$$ is equal to number of solution of $$\gcd(400,y)=1$$ on $$\Bbb Z_{400}$$ which is $$\phi(400)$$.
$$\gcd(3600,x) = 9 \iff \gcd(400,x/9) = 1.$$
• Not true. You mean $\gcd(400,x/9)=1$ (and $x$ has to be a multiple of $9$). Jan 18 '19 at 16:17
Hint: Such a number must be of the form $$9k$$, where $$k\le 400$$ and $$\gcd(400,k)=1$$.