# Modular arithmetic with Legendre symbol

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.

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

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

• Thank you! This is a very clear answer. – bitsbit Jun 21 at 13:12

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

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