3
$\begingroup$

Let $n\in\mathbb{Z}_{>0}$ and let $p\neq3$ be a prime divisor of $n^2+n+1$. Show that $p\equiv1\mod3$.

I thought of trying to prove that $\left(\frac{p}{3}\right)=1$, since 1 is the only element of $\mathbb{F}_3$ that is a square modulo 3. I am supposed to use quadratic reciprocity, which leads to $\left(\frac{p}{3}\right)=\left(\frac{3}{p}\right)(-1)^{\frac{p-1}{2}}$. However, I don't know how to proceed from here.

$\endgroup$
  • 1
    $\begingroup$ I think you meant $1$ is the only element of $\Bbb F_3^\color{red}*$ that is a square $\endgroup$ – J. W. Tanner Jun 21 at 12:48
4
$\begingroup$

Since $4(n^2+n+1)=(2n+1)^2+3$ is divisible by $p$, we have $-3$ is a quadratic residue mod $p$. So \begin{align*} 1=\left(\frac{-3}{p}\right)&=\left(\frac{3}{p}\right)\left(\frac{-1}{p}\right)\\ &=\left(\frac{3}{p}\right)(-1)^{(p-1)/2}\\ &=\left(\frac{p}{3}\vphantom{\frac3p}\right)(-1)^{\frac{p-1}{2}\cdot\frac{3-1}{2}}(-1)^{\frac{p-1}{2}}&&\text{Quadratic Reciprocity}\\ &=\left(\frac{p}{3}\vphantom{\frac3p}\right) \end{align*} So $p\equiv 1\pmod{3}$.

$\endgroup$
  • $\begingroup$ Thank you! This is a very clear answer. $\endgroup$ – bitsbit Jun 21 at 13:12
2
$\begingroup$

First of all, we have to rule out prime divisor $2$ : $$n^2+n=n(n+1)$$ is always even hence $$n^2+n+1$$ is always odd.

Suppose $$p\mid n^2+n+1$$

Then $$p\mid 4n^2+4n+4=(2n+1)^2+3$$

hence $$(2n+1)^2\equiv -3\mod p$$

Now, if $$p\equiv 1\mod 4$$ we get $$(\frac{3}{p})=(\frac{-1}{p})\cdot (\frac{-3}{p})=1\cdot 1=1$$ It follows $$(\frac{p}{3})=1$$

And if $$p\equiv 3\mod 4$$ we get $$(\frac{3}{p})=(\frac{-1}{p})\cdot (\frac{-3}{p})=(-1)\cdot 1=-1$$ It follows again $$(\frac{p}{3})=1$$

$\endgroup$
  • 1
    $\begingroup$ Note the title "with Legendre symbol" and "I am supposed to use QR". $\endgroup$ – Bill Dubuque Jun 21 at 12:31

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.