# How can I solve the following congruence $x^2 \equiv 9 \pmod {2^3 . 3 . 5^2}$?

How can I solve the following congruence $$x^2 \equiv 9 \pmod {2^3 . 3 . 5^2}$$?

The problem is that I do not know the number of solutions of $$x^2 \equiv 9 \pmod { 3}$$, it seems like either it is zero only or any multiple of 3 other than 0, could anyone explain for me why it is not any multiple of 3 other than 0?

• Any $x\equiv 0\pmod{3}$ satisfies $x^2\equiv 9 (\equiv 0) \pmod{3}$. That is, $x$ could be $0$, or $3$ or $6$, or $-3$, or,.... – vadim123 Jun 14 '19 at 3:39
• are you asking why the number of solutions is not any multiple of $3$, or why not any multiple of $3$ is a solution? – J. W. Tanner Jun 14 '19 at 3:40
• why not any multiple of 3 is a solution ? only the zero multiple is a solution? .... by the way how many solutions are there?@J.W.Tanner – Secretly Jun 14 '19 at 3:44
• $3^2\equiv9\pmod{2^3\cdot3\cdot5^2}$ but $6^2\equiv36\not\equiv9\pmod{2^3 \cdot3 \cdot5^2}$ – J. W. Tanner Jun 14 '19 at 3:45
• so we have only 0 and 3 for this congruence ..... correct ? @J.W.Tanner – Secretly Jun 14 '19 at 3:50

\begin{align} x^2\equiv 9\bmod 8&\iff x\equiv 1\bmod 2\\ x^2\equiv 9\bmod 3&\iff x\equiv 0\bmod 3\\ x^2\equiv 9\bmod 25&\iff x\equiv \pm 3\bmod 25 \end{align}
So, $$x^2\equiv 9\mod 600\iff x\equiv \pm3\bmod 150$$.
So, the solutions $$\pmod{600}$$ are going to be $$8$$, namely $$\pm 3\bmod{600}$$, $$150\pm 3\bmod{600}$$, $$300\pm3\bmod{600}$$, and $$450\pm 3\bmod{600}$$.
• @hopefully makes sense they give 8 solutions because the solutions actually should be given in the original modulus $\bmod(2^3\cdot 3\cdot 5^2)=\bmod(600)$. So, the actual 8 solutions will be $\pm 3,150\pm3,300\pm 3$ and $450\pm 3$ ($\bmod 600$) – Julian Mejia Jun 14 '19 at 4:15