Elementary Number Theory – How to Solve a Quadratic Congruence Equation

elementary-number-theory

How to solve $x^2+x+1\equiv 0\pmod {11}$ ?

I know that in some equations like $ax\equiv b\pmod d$ if $(a,d)=1$ then the equation has one and only one solution $x\equiv ba^{\phi(d)-1}\pmod d$. Any help will be appreciated. 😉

Best Answer

You use the quadratic formula!

No, really. But you need to interpret the terms correctly: rather than "dividing" by $2a$ (here, $2$) you need to multiply by a number $r$ such that $2r\equiv 1\pmod{11}$ (namely, $r=6$). And rather than trying to find a square root, here $\sqrt{b^2-4ac} = \sqrt{1-4} = \sqrt{-3}$, you want to find integers $y$ such that $y^2\equiv -3\pmod{11}$. It may be impossible to do so, but if you can find them, then plugging them into the quadratic formula will give you a solution; and if you cannot find them, then there are no solutions.

Now, as it happens, $-3$ is not a square modulo $11$; so there are no solutions to $x^2+x+1\equiv 0\pmod{11}$. (You can find out if $-3$ is a square by using quadratic reciprocity: we have that $-1$ is not a square modulo $11$, since $11\equiv 3\pmod{4}$. And since both $3$ and $11$ are congruent to $3$ modulo $4$, we have $$\left(\frac{-3}{11}\right) = \left(\frac{-1}{11}\right)\left(\frac{3}{11}\right) = -\left(-\left(\frac{11}{3}\right)\right) = \left(\frac{11}{3}\right) = \left(\frac{2}{3}\right) = -1,$$ so $-3$ is not a square modulo $11$).

(You can also verify that this is the case by plugging in $x=1,2,\ldots,10$ and seeing that none of them satisfy the equation).

On the other hand, if your polynomial were, say $x^2+x-1$, then the quadratic formula would say that the roots are $$\frac{-1+\sqrt{1+4}}{2}\qquad\text{and}\qquad \frac{-1-\sqrt{1+4}}{2}.$$ Now, $5$ is a square modulo $11$: $4^2 = 16\equiv 5\pmod{11}$. So we can take $4$ as one of the square roots, and taking "multiplication by $6$" as being the same as "dividing by $2$" (since $2\times 6\equiv 1\pmod{11}$), we would get that the two roots are $$\begin{align*} \frac{-1+\sqrt{5}}{2} &= \left(-1+4\right)(6) = 18\equiv 7\pmod{11}\\ \frac{-1-\sqrt{5}}{2} &= \left(-1-4\right)(6) = -30\equiv 3\pmod{11} \end{align*}$$ and indeed, $(7)^2 + 7 - 1 = 55\equiv 0\pmod{11}$ and $3^2+3-1 = 11\equiv 0\pmod{11}$.


We can definitely use this method when $2a$ is relatively prime to the modulus; if the modulus is not a prime, though, nor an odd prime power, then there may be more than $2$ square roots for any given number (or none). But for odd prime moduli, it works like a charm.