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. ;)
 A: 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. 
A: 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.
A: 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.
A: 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.$ 
