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?

  • $\begingroup$ 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. $\endgroup$ – Jimm Oct 28 '15 at 6:05
  • $\begingroup$ Sorry for the confusion I did not interpret the question correctly $\endgroup$ – cr001 Oct 28 '15 at 6:06
  • $\begingroup$ @cr001 in your case $p=3$ and $q=7$ but $(-3|p)=1$ AND $(-3|q)=1$ $\endgroup$ – ASKASK Oct 28 '15 at 6:07
  • $\begingroup$ 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$. $\endgroup$ – 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$.

  • $\begingroup$ You are welcome. Note that the information about $-3/q$ played no role. $\endgroup$ – André Nicolas Oct 28 '15 at 6:06
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Oct 28 '15 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.