3
$\begingroup$

How can I solve quadratic equations using modular arithmetic? E.g.

$2x^2 + 8x + 2 = 0 \pmod{23}$

N.b. I have changed the figures from those in my homework question because I don't want a solution I want to understand the process. Consequently the example I gave might not have solutions. For the example I am working from divide the LHS by 2.

  • 0
    @AaronMazel-Gee Who would have thought that coming up with examples could be difficult :/2012-12-19

3 Answers 3

6

We have $2x^2+8x+2\equiv 0\pmod{23}$ if and only if $x^2+4x+1\equiv 0\pmod{23}$.

Now complete the square. We have $x^2+4x+1=(x+2)^2-3$. So we want to solve the congruence $(x+2)^2\equiv 3\pmod{23}$.

Let $y=x+2$. We want to solve the congruence $y^2\equiv 3\pmod{23}$.

There is general theory that, for large $p$, helps us determine whether a congruence $y^2\equiv a \pmod{p}$ has a solution, and even to compute a solution. But at this stage you are probably expected to solve such things by inspection.

Note that $y\equiv 7\pmod{23}$ works, and therefore $y\equiv -7\equiv 16\pmod{23}$ also works. We have found two solutions, and by general theory if $p\gt 2$ there are either $2$ solutions or none, so we have found all the solutions.

From $y\equiv 7\pmod{3}$ we conclude that $x+2\equiv 7\pmod{23}$, and therefore $x\equiv 5\pmod{23}$.

From $y\equiv 16\pmod{23}$ we conclude that $x\equiv 14\pmod{23}$.

Remarks: If our congruence had been (for example) $x^2+7x-8\equiv 0\pmod{23}$, there would be a bit of unpleasantness in completing the square, since $7$ is odd. But we could replace $7$ by, say, $30$, and complete the square to get $(x+15)^2-225-8$. So our congruence would become $(x+15)^2\equiv 233\pmod {23}$, or equivalently $(x+15)^2\equiv 3\pmod {23}$.

In general, if we have $ax^2+bx+c\equiv 0\pmod{p}$, it is useful to multiply through by the inverse of $a$ modulo $p$ to make the lead coefficient equal to $1$. There are a number of other helpful "tricks."

  • 1
    For existence, quadratic reciprocity. For construction, details depend on the type of pri$m$e, but the$r$e are fair to goo$d$ algorith$m$s.2014-10-17
2

Since $(2,23) = 1$, you pull $2$ out and 'cancel' it. Now complete the square.

At this point you will need to take the square root of $3$.

In the mod $23$ world, by Fermat's little theorem, you know that $3^{22} \equiv 1 \bmod 23$, So $3^{12}$ is most likely $3$. Try it:

$ 3^{12} \equiv (3^3)^4 \equiv 4^4 \equiv (-7)^2 \equiv 49 \equiv 3 \bmod 23$

Thus $\pm3^6 \bmod 23$ must be the square roots of $3$. That is $16$ and $7$ are square roots of $3$.

Now your equation looks like $x+2 \equiv \pm7 \bmod 23$. So the solutions are $14$ and $5$.

0

The proof of the quadratic formula proceeds by completing the square and then taking a square root. Completing the square works as long as we can divide by 2. So as long as we can divide by 2 and take square roots, the quadratic formula gives the roots of the equation.

If the modulus is odd (as in your case), we can always divide by 2.

Whether taking a (modular) square root is possible will depend on the precise equation.