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.