Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Aaron Mazel-Gee Dec 19 '12 at 6:05
    
@AaronMazel-Gee Who would have thought that coming up with examples could be difficult :/ –  trideceth12 Dec 19 '12 at 7:01
add comment

3 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.