Solve $x^2+x+3=0$ mod $27$ I was preparing for my Number Theory class for next semester and one of the questions that I came upon is to solve $x^2+x+3=0$ mod $27$. I have seen modular arithmetic before but never one that involved using mod with an equation. I plugged it into WolframAlpha and it gave me $x=11,15$. My question is, how did wolfram alpha solve this? Is there some kind of procedure? My initial try was to use Brute Force and plug in every value possible until it is divisible by 27 but I would like to see how it is solved.
 A: There is no harm in completing the square. We have that $2^{-1}=-13$, so  $x^2+x+3=x^2-26x+3=0$ gives $(x-13)^2+3-13^2=0$, or $(x-13)^2=4=2^2$. This means that $(x-13)^2-2^2=0$ so that $(x-15)(x-11)=0$. Note you cannot really conclude $x-15=0$ or $x-11=0$ right away, since we're not working over an integral domain.
ADD  Let $p$ be an odd prime, $p\not\mid a$. Then $x^2=a\mod p^k$ has at most two (incongruent) solutions. 
P Suppose $x^2\equiv x_0^2\mod p^k$. Then $p^k\mid (x-x_0)(x+x_0)$. We cannot have $p$ dividing both $x-x_0,x+x_0$ for this means say $p\mid 2x_0$, which is impossible. Thus $x= \pm x_0\mod p^k$.
A: We can first solve the congruence modulo $3$, which means that $x\equiv 0 \mod 3$ or $x\equiv 2 \mod 3$. So many of the numbers $\{0,1,\ldots, 26 \}$ can be discarded already.
Continue with modulo $9$ and modulo $27$. Then you see without "brute force" that only $11$ and $15$ are left.
A: Your equation is equivalent to the following:
$$4x^2+4x+12\equiv0 \mod27$$ since $\gcd(4,27)=1$. Or $$(2x+1)^2+11\equiv0 \mod27$$ and even better $$(2x+1)^2-16\equiv0\mod27$$  which gives $27\mid (2x-3)(2x+5)$. But $\gcd(2x-3,2x+5)$ must be a divisor of $8$ which is relatively prime to $27$.  So, $27|2x-3$ or $27| 2x+5 $. The first case gives $x\equiv15$ and the second one gives $x\equiv11$ (mod27)
A: Hint $\ $ Complete the square, using ${\rm\, mod}\ 27\!:\ \color{#c00}1/2\equiv \color{#c00}{28}/2\equiv 14.\,$ As Pedro shows, this yields $\rm (x-15)\,(x-11)\equiv 0,\,$ i.e. $ \,27\mid (x-15)(x-11).\,$ Therefore either $27\mid x-15\,$ (so $x\equiv 15)$, or $27\mid x-11\,$ (so $x\equiv 11),\,$ or $\,3\mid x-15,\ 3\mid x-11.$ The latter case is impossible since it implies, modulo $3$, that $x\equiv 15\equiv 0$ and $x\equiv 11\equiv 2$. Thus there are no further roots besides $15$ and $11$.
Remark $\ $ That there are not more than $2$ roots does require proof, since generally modular quadratic equations can have more than $2$ roots, e.g. $\,x^2\equiv 1$ has the $4$ roots $\pm1, \pm3$ modulo $8$. 
The analysis above as to how the factors of $3$ must distribute into each factor depends upon the uniqueness of prime factorizations.
