I'm trying to solve the following
$x^2 + 3x + 7 \equiv 0 \pmod {37}$
What I've tried -
I've tried making the left side as a square and then I know how to solve
but couldn't make it as a square root..
We also learned in class that you can multiply the left side and the modulo by $4a$
(that is $4\cdot 1 = 1$) and continue somehow - which I can't figure out how.
any help will be appreciated.
$\endgroup$ 12 Answers
$\begingroup$In the real numbers, a method of finding a solution to a quadratic equation is to complete the square. This would involve adding and subtracting $(b/2)^2$. $b=3$ in your case, and remember that $1/2 = 19 \mod 37$.
Specifically notice: $$(x+3 \cdot 19)^2 \equiv x^2 + 2\cdot 3 \cdot 19 x + (3 \cdot 19)^2$$ $$\equiv x^2 + 3x + (20)^2 \mod 37$$
Note that $3 \cdot 19 \equiv 20 \mod 37$. Also $20^2 = 400 \equiv 30 \mod 37$.
Thus the method of completing the square is as follows $$x^2 + 3x + 7 \equiv x^2 + 3x + 20^2 - 20^2 + 7 \equiv (x+20)^2 - 23 \mod 37$$
Finally this means you need to solve $$(x+20)^2 \equiv 23 \mod 37$$
$\endgroup$ 3 $\begingroup$$$x^2+3x+7\equiv x^2+40x+400+(-393)\equiv 0$$
$$\iff (x+20)^2\equiv 393\equiv 23\pmod{\! 37}$$
Use Quadratic Reciprocity: $$\left(\frac{23}{37}\right)=\left(\frac{37}{23}\right)=\left(\frac{14}{23}\right)=\left(\frac{7}{23}\right)\left(\frac{2}{23}\right)$$
$$=-\left(\frac{23}{7}\right)=-\left(\frac{2}{7}\right)=-1$$
In general, you can always complete the square after multiplying both sides by $4a$:
$$x^2+3x+7\equiv 0\stackrel{\cdot 4}\iff (2x+3)^2\equiv 18\pmod{\! 37}$$
$$\left(\frac{18}{37}\right)=\left(\frac{3^2}{37}\right)\left(\frac{2}{37}\right)=-1$$
$$ax^2+bx+c\equiv 0\stackrel{\cdot 4a}\iff (2ax+b)^2\equiv b^2-4ac\pmod{\! p}$$
Using this you can prove the quadratic formula that can be applied to quadratic congruences too (see this answer).
$\endgroup$
