# Prove that there are no solutions to $x^2 + x + 1 \equiv 0$ (mod $n$) in $\mathbb{Z}/_{n}\mathbb{Z}$

Let's say I want to prove that there are no solutions to $x^2 + x + 1 \equiv 0$ (mod $n$) in $\mathbb{Z}/_{n}\mathbb{Z}$ where $n=pq$ and $p$ and $q$ are chosen prime numbers greater than $2$, given that the Legendre symbols

($\frac{-3}{p}$) $=$ $-1$ and ($\frac{-3}{q}$) $=1$.

I know that this means that the Jacobi symbol $(\frac{-3}{n}) = -1$, so this means that $-3$ is a nonresidue modulo $n$.

How can I apply the Chinese Remainder Theorem to show this means there are no solutions to the congruence equation?

• Yes I just meant that I already know the prime numbers $p$ and $q$, not that this is true for every $p$ and $q$ by any means. – Jimm Oct 28 '15 at 6:05
• Sorry for the confusion I did not interpret the question correctly – cr001 Oct 28 '15 at 6:06
• @cr001 in your case $p=3$ and $q=7$ but $(-3|p)=1$ AND $(-3|q)=1$ – ASKASK Oct 28 '15 at 6:07
• For contradiction, let $x^2+x+1\equiv 0\pmod{n}$. But then $x^2+x+1\equiv 0\pmod{p}$, so $4x^2+4x+4\equiv 0\pmod{p}$, i.e. $(2x+1)^2\equiv -3\pmod{p}$, contradiction, because we're given $\left(\frac{-3}{p}\right)=-1$. – user236182 Oct 28 '15 at 6:25

Suppose that $x^2+x+1\equiv 0\pmod{pq}$ has a solution. Then $x^2+x+1\equiv 0\pmod{p}$ has a solution. From the answer to an earlier question of yours, $x^2+x+1\equiv 0\pmod{p}$ has a solution if and only if the Legendre symbol $(-3/p)$ is equal to $1$. But we have been told it is equal to $-1$.
• You are welcome. Note that the information about $-3/q$ played no role. – André Nicolas Oct 28 '15 at 6:06
• We could instead have completed the square as in the previous answer, and then used your observation about the Jacobi symbol. But the path taken in the answer is a bit quicker, and also works if $(-3/p)=(-3/q)=-1$. – André Nicolas Oct 28 '15 at 6:11