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

$\endgroup$
2
  • 2
    $\begingroup$ I like that you changed the question so as not to accidentally solve your homework. But note that 2 is a unit mod 23, so in fact you can legally divide both sides by 2, so this problem is essentially identical to the original one. $\endgroup$ Dec 19, 2012 at 6:05
  • $\begingroup$ @AaronMazel-Gee Who would have thought that coming up with examples could be difficult :/ $\endgroup$
    – jsj
    Dec 19, 2012 at 7:01

3 Answers 3

13
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ What is the general theory that for large $p$, helps us determine whether a congruency $y^2\equiv a \pmod{p}$ has a solution and computes it? $\endgroup$
    – mauna
    Oct 17, 2014 at 3:50
  • 1
    $\begingroup$ For existence, quadratic reciprocity. For construction, details depend on the type of prime, but there are fair to good algorithms. $\endgroup$ Oct 17, 2014 at 5:15
  • $\begingroup$ What would one do differently if the given equation had odd terms? For instance, you can't divide by two the equation $2x^{2}-14x+19\equiv0\pmod p$ . $\endgroup$
    – Ido
    Dec 11, 2020 at 15:48
  • $\begingroup$ @Ido I think we need to move away from the idea of "dividing" by 2, and instead multiply by the inverse of 2. This will be congruent to (p + 1) / 2 for any odd p. So if p was 23 then its a matter of multiplying by 12 to effectively "divide" by 2. $\endgroup$ Mar 16, 2021 at 3:06
  • $\begingroup$ I am late, but if the base is even, for instance 12, then there is no way to convert that odd coefficient to even, or is it? $\endgroup$ Aug 14, 2021 at 2:39
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .