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