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

share|improve this question

4 Answers 4

up vote 16 down vote accepted

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.

share|improve this answer
2  
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.

share|improve this answer

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.

share|improve this answer
    
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.$

share|improve this answer

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.