Rational Eisenstein primes that split In this Wikipedia article it is mentioned that primes of the form $p \bmod 3 = 1$ split in the ring of Eisenstein integers $\Bbb E$. By analogy to the Gaussian primes I tried to prove that for such primes there exists $a, b \in \Bbb Z$ such that $p = a^2-ab+b^2$. But I got stuck somewhere. Let's take following ingredients : $\omega, \omega^2$ the usual $3$thd degree roots of unity, $u$ a primitive root of $\Bbb Z_p$, $\mathfrak{p}$ the ideal $\Bbb Fp$. I am interested in the quotient ring $\Bbb F/\mathfrak{p}$. I chose $p^2$ elements of the form $a\omega+b\omega^2$ with $0 \leq a,b < p$ as representatives of the cosets and multiplication is executed as complex numbers and applying $\bmod p$ afterwards. It is not hard to see that $r = u^{\frac{p-1}{3}}$ is a root of $X^3-1 = (X-1)(X^2+X+1)$ in $\Bbb Z_p$. It is not a root of $X-1$ so $-r$ is a root of $X^2-X+1$. From this we can conclude that for $x = \omega +(p-r)\omega^2$ we must have that its norm $N(x) = 0 \bmod p$. Unluckily I don't see how this allows me to find an element with norm = $p$.


*

*Example 1: $p = 19$


We have $u = 2$  and $r = 2^6 \bmod 19 = 7$, $x = \omega + 12\cdot\omega^2$ but $N(x) = 7 \cdot 19$. I know that the ideal generated by $x$ in $\Bbb F/\mathfrak{p}$ is $x, 2x, 3x, \ldots, 18x$ and that (by luck?) $N(3x) = 19$ so that $19 = 3^2 - 3\cdot5 + 5^2$;


*

*Example 2: $p = 37$


We have $u = 2$  and $r = 2^{12} \bmod 37 = 26$, $x = \omega + 11\cdot\omega^2$ but $N(x) = 3 \cdot 37$. I know that the ideal generated by $x$ in $\Bbb F/\mathfrak{p}$ is $x, 2x, 3x, \ldots, 36x$ and that (by luck?) $N(4x) = 37$ so that $37 = 4^2 - 4\cdot7 + 7^2$;


*

*Conclusion


I am able to construct an ideal of elements all of which have norm that is a multiple of $p$, I strongly suspect that one of these has exactly norm $p$ but can't prove it.
 A: There seem to be some misunderstandigs in your current approach; see my comment to your question. Here's an alternative approach that for the most part generalizes to the context of rings of integers in number fields:
The ring of Eisenstein integers is isomorphic to the quotient $\Bbb{Z}[X]/(X^2+X+1)$. If $p\in\Bbb{Z}$ is a prime with $p\equiv1\pmod3$ then $(\Bbb{Z}/p\Bbb{Z})^{\times}$ is a group whose order is a multiple of $3$, so it has two distinct primitive third roots of unity, say $a$ and $b$. Then in $(\Bbb{Z}/p\Bbb{Z})[X]$ we have
$$X^2+X+1=(X-a)(X-b),$$
from which it follows that
\begin{align*}
\Bbb{E}/p\Bbb{E}
&\cong\Bbb{Z}[X]/(p,X^2+X+1)\\
&\cong(\Bbb{Z}/p\Bbb{Z})[X]/(X^2+X+1)\\
&\cong(\Bbb{Z}/p\Bbb{Z})[X]/(X-a)\times(\Bbb{Z}/p\Bbb{Z})[X]/(X-b).
\end{align*}
In particular this gives a bijection between the prime ideals of $\Bbb{E}$ containing $p$ and the prime ideals of $(\Bbb{Z}/p\Bbb{Z})[X]/(X-a)\times(\Bbb{Z}/p\Bbb{Z})[X]/(X-b)$, which is a product of two fields. So its prime ideals are
$$(\Bbb{Z}/p\Bbb{Z})[X]/(X-a)\times\{0\}\qquad\text{ and }\qquad\{0\}\times(\Bbb{Z}/p\Bbb{Z})[X]/(X-b).$$
The corresponding ideals in $\Bbb{E}$ are $(p,\omega-a)\Bbb{E}$ and $(p,\omega-b)\Bbb{E}$. Their product is $p\Bbb{E}$ which is an ideal of norm $p^2$, so both ideals are of norm $p$. Because $\Bbb{E}$ is a principal ideal domain, there exist $x,y\in\Bbb{E}$ such that 
$$x\Bbb{E}=(p,\omega-a)\Bbb{E}\qquad\text{ and }\qquad y\Bbb{E}=(p,\omega-b)\Bbb{E},$$
and so $x$ and $y$ both have norm $p$. Because $\Bbb{E}$ is even a Euclidean domain, both $x$ and $y$ can be computed by the Euclidean algorithm.

EDIT: Let's see what this means for the given examples. For $p=19$ we find
$$X^2+X+1\equiv(X-7)(X-11)\pmod{19},$$
so the prime ideals of $\Bbb{E}$ containing $p$ are $(19,\omega-7)\Bbb{E}$ and $(19,\omega-11)\Bbb{E}$. We apply the Euclidean algorithm to the generators $19$ and $\omega-7$ of the first ideal, where
$$N(19)=19^2\qquad\text{ and }\qquad N(\omega-7)=57=3\times19.$$
Now we want to find $q,r\in\Bbb{E}$ such that $19=q(\omega-7)+r$ with $N(r)<57$. We know that
$$57=N(\omega-7)=(\omega-7)(\omega^2-7)=(\omega-7)(-\omega-8),$$
so $\frac{1}{\omega-7}=\frac{-\omega-8}{57}$. Hence $q$ should be close to
$$\frac{19}{\omega-7}=19\times\frac{-\omega-8}{57}=-\frac{8}{3}-\frac{1}{3}\omega.$$
The nearest Eisenstein integer is $-2$, and we find that
$$19=(-2)\times(\omega-7)+(5+2\omega),$$
where $N(5+2\omega)=19$, so we're done. The other prime of norm $19$ is then
$$5+2\omega^2=3-2\omega,$$
and indeed if we apply the same algorithm to the ideal $(19,\omega-11)\Bbb{E}$ we find that $\frac{19}{\omega-11}=\frac{-12-\omega}{7}$, which is close to $-2$, and so
$$19=(-2)\times(\omega-11)+(-3+2\omega).$$
