0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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,.... $\endgroup$ – vadim123 Jun 14 '19 at 3:39
  • 1
    $\begingroup$ are you asking why the number of solutions is not any multiple of $3$, or why not any multiple of $3$ is a solution? $\endgroup$ – J. W. Tanner Jun 14 '19 at 3:40
  • $\begingroup$ 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 $\endgroup$ – Secretly Jun 14 '19 at 3:44
  • $\begingroup$ $3^2\equiv9\pmod{2^3\cdot3\cdot5^2}$ but $6^2\equiv36\not\equiv9\pmod{2^3 \cdot3 \cdot5^2}$ $\endgroup$ – J. W. Tanner Jun 14 '19 at 3:45
  • $\begingroup$ so we have only 0 and 3 for this congruence ..... correct ? @J.W.Tanner $\endgroup$ – Secretly Jun 14 '19 at 3:50
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ math.stackexchange.com/questions/3261661/… $\endgroup$ – Secretly Jun 14 '19 at 4:03
  • $\begingroup$ The solution at the back of the book contains 8 solutions? $\endgroup$ – Secretly Jun 14 '19 at 4:05
  • $\begingroup$ @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$) $\endgroup$ – Julian Mejia Jun 14 '19 at 4:15
  • $\begingroup$ from where you got the first equivalence? $\endgroup$ – Secretly Jun 14 '19 at 4:28
  • $\begingroup$ how do you remove the power from the prime in the mod ? $\endgroup$ – Secretly Jun 14 '19 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.