# How to solve this quadratic congruence equation

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. ;)

-

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.

-
Note that the formula doesn't work quite as well if 2a is not invertible, e.g. $3x^2+3=0(mod 6)$ does have a solution, but you can't apply the quadratic formula to find it. –  tomasz Jun 19 '12 at 17:10
@Thanks for answer. –  Nancy Rutkowskie Jun 19 '12 at 17:11
Neat answer Prof. Magidin. –  Babak S. Jun 19 '12 at 17:53
@BabakSorouh: Honestly, I'm starting to feel stalked. –  Arturo Magidin Jun 19 '12 at 18:41

Here is an alternative solution. Suppose $x$ is a solution.

Let $a$ be a primitive root modulo 11, thus $x=a^k$ for some $1 \leq k \leq 10$.

$$x^2+x+1\equiv 0\pmod {11} \Rightarrow x^3 \equiv 1 \mod 11 \Rightarrow a^{3k} \equiv 1 \mod 11 \Rightarrow 10 | 3k$$ $$\Rightarrow 10|k \Rightarrow k =10 \Rightarrow x \equiv a^{10} \equiv 1 \mod 11 \,.$$

It is easy to see that $x \equiv 1 \mod 11$ is not a solution, and we proved that it is the only potential solution.

Thus, the equation has no solution.

-

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.

-
You say: "There are powerful methods to deal with such questions for large primes p." Please can you offer a reference for more information on this, more general, case? A web page or a textbook, perhaps? –  aSteve Jul 18 '13 at 6:17
There are special algorithms for certain classes of primes. For example, if $p=8k+5$, and $a$ is a QR of $p$, then $x\equiv a^{k+1}\pmod{p}$ or $x\equiv 2^{2k+1}a^{k+1}$ is a solution of $x^2\equiv a\pmod{p}$. These are cheap to compute using the binary method for exponentiation. For $8k+1$, one can use the Tonelli-Shanks algorithm. You can find lots of information on this online. –  André Nicolas Jul 18 '13 at 14:20
A search under modular square root algorithm or something similar will yield many hits. For general books on number-theoretic algorithms, there are several I like. The one by Henri Cohen is a classic. Not easy. There are a number of other good books. Search under computational number theory. –  André Nicolas Jul 18 '13 at 14:24

Hint $\rm\ mod\ p\ne 3\!:\ x^2\!+x+1 = 0 \iff x\ne 1,\ x^3 = 1\iff x\ne 1,\,\ x^{\,(3,\,p-1)}\! = 1$

Hence it has no roots when $\rm\:(3,p\!-\!1) = 1,\:$ e.g. any prime $\rm\:p = 6\,k\!-\!1,\:$ e.g. $\rm\:p = 11.$

-