<s>[INST] 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.
 [/INST] 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}$.
</s>