How many elements in $S$ satisfy $x^2=49 \pmod{5400}$?

Question

Let $S=\{0,1,2,...,5399\}$.

How many elements in $S$ satisfy $x^2=49 \pmod{5400}$?

So I'm thinking about using Chinese remainder Theorem, but since $5400$ has many factors, wouldn't cracking it down require too many steps of finding coprime numbers?

Answer 1

As $(7,5400)=1$ $$x^2\equiv49\pmod{5400}\iff(x/7)^2\equiv1\pmod{5400}$$

As $5400=100\cdot54=2^33^35^2$

$(x/7)^2\equiv1\pmod{5400}\implies$

$$(x/7)^2\equiv1\pmod{2^3}\iff x/7\equiv1\pmod2$$

$$(x/7)^2\equiv1\pmod{5^2}\iff x/7\equiv\pm1\pmod{5^2}$$

$$(x/7)^2\equiv1\pmod{3^3}\iff x/7\equiv\pm1\pmod{3^3}$$

So, we should have $1\cdot2\cdot2$ in-congruent solutions $\pmod{2\cdot5^2\cdot3^3}$

We can apply Chinese remainder theorem to find the actual residues