# 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.

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.

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)

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$.

• See my answer for how to complete the proof, i.e. that there are no further roots. – Bill Dubuque Dec 18 '13 at 21:06

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.

• You can proceed as panoramix did, since their GCD is a divisor of $4$, coprime to $27$, no worries here :) – chubakueno Dec 18 '13 at 21:13
• @chubakueno When I wrote this, Pedro's answer did not prove that there are at most $2$ roots, nor did any answer stress that some modular quadratics can have more than $2$ roots. This deserves explicit emphasis, since many students are not aware that this can occur. – Bill Dubuque Dec 18 '13 at 21:35
• @BillDubuque Agreed. – Pedro Tamaroff Dec 19 '13 at 14:01