How to solve this quadratic congruence equation

Solution 1:

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.

Solution 2:

You can use the technique of Completing the Square.

Suppose that we want to solve the congruence $ax^2+bx+c\equiv 0 \pmod p$, where $a\not\equiv 0\pmod{p}$, and $p$ is an odd prime. The congruence is equivalent to $$4a^2x^2+4abx+4ac\equiv 0\pmod{p}.\tag{$1$}$$ Completing the square, we see that the congruence is equivalent to $$(2ax+b)^2-b^2+4ac\equiv 0\pmod{p},$$ or equivalently to $$(2ax+b)^2\equiv b^2-4ac\pmod{p}.\tag{$2$}$$

To solve this last congruence we (i) Try to solve the congruence $y^2 \equiv b^2-4ac\pmod{p}$. There may be no solution, in which case the original congruence has no solution. There may be a single solution, if $b^2-4ac\equiv 0\pmod{p}$. In all other cases there will be two solutions. (ii) After having found such $y$, we solve the linear congruences $2ax+b\equiv y\pmod{p}$.

Now we turn to $x^2+x+1\equiv 0\pmod{p}$, and use the basic technique, although inspection would work faster.

Rewrite as $4x^2+4x+4\equiv 0\pmod{11}$, then as $(2x+1)^2-1+4\equiv 0\pmod{11}$, then as $(2x+1)^2\equiv -3\equiv 8\pmod{11}$.

So we first try to solve the congruence $y^2\equiv -3\equiv 8\pmod{11}$. It turns out there are no solutions. There are powerful methods to deal with such questions for large primes $p$. For $11$, just calculate $1^2$, $2^2$, $3^3=2$, $4^2$, and $5^2$ modulo $11$. None of them work. The rest cannot work, for they are essentially the negatives of the numbers we have already checked, so their squares are, modulo $11$, the same as the squares of the numbers $1$ to $5$. For example, $6\equiv -5\pmod{11}$, so $6^2\equiv (-5)^2\equiv 5^2\pmod{11}$, and similarly $7^2\equiv 4^2$, and so on.

Remarks: $1.$ The congruence $(2)$ has a solution if and only if the congruence $y^2\equiv b^2-4ac\pmod{p}$ has a solution, that is, iff $b^2-4ac$ is a square modulo $p$. This $b^2-4ac$ is the familiar discriminant of elementary algebra.

$2.$ The general idea can be used even when we are solving a quadratic congruence modulo $m$, where $m$ is not prime. But significant modifications need to be made. The congruence $ax^2+bx+c\equiv 0\pmod{m}$ is equivalent to $4a^2x^2+4abx+4ac\equiv 0 \pmod{4am}$, so we end up looking at $$(2ax+b)^2\equiv b^2-4ac\pmod{4am}.$$ The study of the congruence $y^2\equiv b^2-4ac\pmod{4am}$ is more complicated than when the modulus is $p$, and there may be many solutions. But after that we are solving linear congruences $2ax+b\equiv y\pmod{4am}$, and we can use the Extended Euclidean Algorithm.