1
$\begingroup$

Question:

Find two solutions of $x^2 + 2x + 2 \equiv 0 \bmod 5^3$

My attempt:

  • rewrite the equation or simplify (optional step): $x^2 + 2x + 2 = (x+1)^2 + 1 \equiv 0 \bmod 5^3$

  • $x = 1$ then: $f(1) = 5$ and $5 \equiv 0 \bmod 5$

  • $f'(x) = 2(x+1)$ then: $f'(1) = 4$
  • solution $= 1 - \frac{5}{4}$
  • using extended euclidean algorithm: $4^{-1} \equiv 1 \bmod 125 \to 4x+125y = 1 \to x=-31$ (test: $125 * (1) + 4 * (-31) = 1$)
  • $1-\frac{5}{4} = 1-5*\frac{1}{4} \equiv 1-5*(-31) \bmod 125 \equiv 1+155 \bmod 125 \equiv 156 \bmod 125 = 31$
  • But $f(31) = 1025$ and $1025 \bmod 125 = 25 \neq 0$

$31$ is not a correct answer. What am I missing?

$\endgroup$
2
  • $\begingroup$ @Moo How can I use a quadratic formula when $b^2 - 4ac$ is negative? $\endgroup$
    – Node.JS
    Oct 30, 2016 at 1:13
  • $\begingroup$ @Moo I have spent hours on this question. Please clarify. $delta = b^2-4ac = 2^2 - 4*1*2 = -4 \equiv 121 \bmod 125$. Thus, $x = \frac{-b + \sqrt{ delta}}{ 2a}$ and $x = \frac{-b - \sqrt{delta}}{2a} \to \frac{-2 +11}{2} = 3.5$ and $\frac{-2 - 11}{ 2} = -7.5$ $\endgroup$
    – Node.JS
    Oct 30, 2016 at 1:23

1 Answer 1

Reset to default
2
$\begingroup$

Use the quadratic formula.

$x_{1,2} = \dfrac{-b \pm \sqrt{b^2-4ac}}{2a} = \dfrac{-2 \pm \sqrt{4-8}}{2} \pmod{125} = \dfrac{-2 \pm \sqrt{121}}{2} \pmod{125} = \dfrac{-2 \pm 11}{2} \pmod{125} = 2^{-1} \times (9, -13) \pmod{125} = 2^{-1} \times (9, 112) \pmod{125} = 63 \times (9, 112) \pmod{125}= (67, 56)$.

Note that the division is a modular inverse!

You can easily test these values, $x = 67$ and $x = 56$ in the original equivalence and make sure the LHS equals the RHS.

You can refer to these handy notes and more notes.

$\endgroup$
5
  • $\begingroup$ Thank you so much. I have a question: when this method works? all the time? or only when we have $\equiv \bmod prime^{number}$? $\endgroup$
    – Node.JS
    Oct 30, 2016 at 1:38
  • 1
    $\begingroup$ I think you should review those nice notes - they have an algorithmic approach that is quite handy. That is a very good question as we are working in modular arithmetic - so it is not as straightforward as working in the reals. For example, you can get more than two results! $\endgroup$
    – Moo
    Oct 30, 2016 at 1:40
  • $\begingroup$ I will read the notes now. Thanks again. $\endgroup$
    – Node.JS
    Oct 30, 2016 at 1:40
  • $\begingroup$ Notes link broken :'( $\endgroup$
    – Daniel Donnelly
    Mar 3 at 8:47
  • 1
    $\begingroup$ @DLeftAdjointtoU: Added a new link of notes. Regards. $\endgroup$
    – Moo
    Mar 3 at 11:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .