# 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?

• @Moo How can I use a quadratic formula when $b^2 - 4ac$ is negative? Oct 30, 2016 at 1:13
• @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$ Oct 30, 2016 at 1:23

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

• Thank you so much. I have a question: when this method works? all the time? or only when we have $\equiv \bmod prime^{number}$? Oct 30, 2016 at 1:38
• 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!
– Moo
Oct 30, 2016 at 1:40
• I will read the notes now. Thanks again. Oct 30, 2016 at 1:40
• Notes link broken :'( Mar 3 at 8:47