A nontrivial solution to the quadratic form $x^2 - xy + y^2$ over the finite field $_p$ with $p ≡ 1 \pmod3$ a prime I'm trying to prove that when $p ≡ 1 \pmod3$ is a prime, $p$ is reducible over the Eisenstein integers, and I've gotten to the point where, provided $p\,|\,u^2 - u + 1$ for some integer $u$, then $p$ is reducible, and in trying to prove the existence of such a $u$, I arrived at this problem. I may be going in the wrong direction, but assuming the end result (which I know to be true), there must exist some nontrivial solution. Unfortunately I'm a bit stuck at this point.
 A: Since $p\ne2$ we have
\begin{align}p\mid u^2-u+1\ \hbox{for some $u$}\quad
  &\hbox{iff}\quad p\mid4u^2-4u+4\ \hbox{for some $u$}\cr
  &\hbox{iff}\quad p\mid(2u-1)^2+3\ \hbox{for some $u$}\cr
  &\hbox{iff}\quad \hbox{$-3$ is a square modulo $p$}.
\end{align}
Using Legendre symbols and supposing $p\equiv1\pmod4$, we have
$$\Bigl(\frac{-3}p\Bigr)
  =\Bigl(\frac{-1}p\Bigr)\Bigl(\frac{3}p\Bigr)
  =\Bigl(\frac{3}p\Bigr)
  =\Bigl(\frac p3\Bigr)=1\ ,$$
the last equality being because $p\equiv1\pmod3$.  If on the other hand $p\equiv3\pmod4$ then
$$\Bigl(\frac{-3}p\Bigr)
  =\Bigl(\frac{-1}p\Bigr)\Bigl(\frac{3}p\Bigr)
  =-\Bigl(\frac{3}p\Bigr)
  =\Bigl(\frac p3\Bigr)=1\ ,$$
the same result.  So $-3$ is a square modulo $p$ and this completes the proof.
Alternative: use Gauss' lemma instead of quadratic reciprocity.  We have $p=6a+1$ and so $(p-1)/2=3a$.  Looking at the least positive residues of $(-3)k$ for $k=1,2,\ldots,3a$, the first $a$ of them are
$$p-3,\ p-6,\ldots,\ p-3a=3a+1$$
which are all greater than $p/2$; the next $a$ are
$$p-3(a+1)=3a-2,\ldots,p-3(2a)=1$$
which are all less than $p/2$; and the final $a$ of them are
$$2p-3(2a+1)=p-2,\ldots,2p-3(3a)=3a+2$$
which are all greater than $p/2$.  The number greater than $p/2$ is $2a$, which is even, so by Gauss' lemma, $-3$ is a square modulo $p$.
A: $u^2 - u + 1 = (u^3+1)/(u+1)$, so $p \mid u^2-u+1$ iff $u$ is a non-trivial cube root of $-1$ modulo $p$, in other words $-u$ is a primitive cube root of unity.  Let $g$ be any primitive root mod $p$, and then let $u = -g^{(p-1)/3}$.
A: Here’s another argument: If $p\equiv1\pmod3$, then $\Bbb F_p^\times$ is a cyclic group of order divisible by $3$, and so has three cube roots of unity, call them $1$, $a$, and $a^2$. Then $(X+1)(X^2-X+1)=X^3+1=(X+1)(X+a)(X+a^2)$, and so $X^2-X+1=(X+a)(X+a^2)$.
