quadratic congruence using Newton-Raphson Method from calculus 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? 

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.
