TITLE: Prove that there are no solutions to $x^2 + x + 1 \equiv 0$ (mod $n$) in $\mathbb{Z}/_{n}\mathbb{Z}$
QUESTION [1 upvotes]: 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?

REPLY [2 votes]: 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$.
{"set_name": "stack_exchange", "score": 1, "question_id": 1501352}