Existence of integers $a$ and $b$ such that $p = a^2 +ab+b^2$ for $p = 3 $ or $p\equiv 1 \mod 3$ **Eisenstein primes, existence of integers **
I am working in subring $$R = \{a + b\zeta : a,b \in \mathbb{Z}\}$$ of $\mathbb{C}$ where $\zeta = \frac{1 + \sqrt{-3}}{2} \in \mathbb{C}$. I want to show that there exist integers $a$ and $b$ with $p = a^2 + ab+ b^2$ where $a,b \in \mathbb{Z}$ and that $p =3$ or $p \cong 1 \mod 3$. In this problem, we have a norm defined by $$N(a+ b\zeta) = a^2 +ab +b^2.
$$ I have been stuck in this problem for a while now. I was wondering if anyone could give me a hint on how to find the existence of such integers. I have been thinking of using the norm somehow, like considering some $x \in R$ such that $N(x) = p$ and from there try to show something about $a$ and $b$, but I haven't really made any progress. Any help with this will be ggreatly appreciated!
 A: If $p=3$ then $a=b=1$.
If $p\equiv 1\pmod 3$ then
$$(-3/p)=(3/p)(-1)^{(p-1)/2}=(p/3)(-1)^{(p-1)/2}(-1)^{(p-1)/2}=(1/3)=1$$
(Here, $(a/b)$ means the Legendre symbol).
Then, $-3$ is a square mod $p$. Assume that $m^2\equiv -3\pmod p$. Let $x=(m-1)(p+1)/2$. We see that
$$x^2+x+1\equiv 0\pmod p$$
or
$$(x-\zeta)(x+\zeta)=kp$$
Note that $\Bbb Z[\zeta]$ is an UFD. If $p$ were prime in $\Bbb Z[\zeta]$ then $p$ would divide $x+\zeta$ or $x-\zeta$. This is clearly impossible, so $p$ is not prime in $\Bbb Z[\zeta]$.
Then
$$p=(a+b\zeta)(c+d\zeta)$$
Taking norms
$$p^2=(a^2+ab+b^2)(c^2+cd+d^2)$$
and both factors in RHS must be $p$.
Example: Take $p=97$. We see that $26^2+3=679=97\cdot 7$. And $25/2\equiv 61\pmod {97}$ so $61^2+61+1=97\cdot 39$. Then $97$ divide $(61+\zeta)(61-\zeta)$. Since 
$$\frac{61\pm\zeta}{97}\notin\Bbb Z[\zeta]$$
then $97$ can be factored in $\Bbb Z[\zeta]$. This method does not give the factorization, but we can try by brute force. 
$$97=8^2+3\cdot 8+3^2$$
A: The method in this answer is very similar to that of ajotatxe, but it avoids the use of Legendre symbols and quadratic reciprocity. (But I will use more abstract algebra.)
The case $p=3$ can be worked out explicitly.
By the same argument as given by ajotatxe, it is enough to show that for integer primes $p\neq 3$, $p$ is a prime element of $\Bbb Z[\zeta]$ iff $p \equiv 2 \pmod{3}$.
Now we have $p$ is prime in $\Bbb{Z}[\zeta]$ $\Leftrightarrow$ $\Bbb{Z}[\zeta]/(p)$ is an integral domain.
But $\Bbb{Z}[\zeta]/(x) \cong (\Bbb{Z}[x]/(x^2+x+1))/(p) \cong \Bbb Z[x]/(x^2+x+1,p)$ $\cong (\Bbb{Z}[x]/(p)) /(x^2+x+1) \cong \Bbb F_p[x]/(x^2+x+1)$
Now $\Bbb F _p[x]/(x^2+x+1)$ is an integral domain iff $(x^2+x+1)$ is irreducible, but as the degree of this polynomial is $2$, $(x^2+x+1)$ is irreducible over $\Bbb F_p$ iff $x^2+x+1$ has not roots in $\Bbb F_p$.
As $x^2+x+1 = \frac{x^3-1}{x-1}$ a root of $x^2+x+1$ is just an elment of the multiplicative group $\Bbb F_p^\times$ of order $3$. By Lagrange's theorem and the cyclicity of $\Bbb F_p^\times$, such an element exists iff $3$ divides the order of $\Bbb F_p^\times$, that is iff $p \equiv 1 \pmod{3}$
A: Consider $p = a^2 +ab+b^2$.
If $p$ divides $a$, then $p$ divides $b$, and so $p^2$ divides the RHS but not the LHS.
So, $p$ does not divide either $a$ or $b$.
Then, $p$ divides $a^3-b^3=(a-b)(a^2 +ab+b^2)$, that is $a^3 \equiv b^3 \bmod p$.
If $bc \equiv 1 \bmod p$, then $(ac)^3 \equiv 1 \bmod p$.
If $ac \equiv 1 \bmod p$, then $a \equiv b \bmod p$ and so $3a^2 \equiv 0 \bmod p$. This implies $3 \equiv 0 \bmod p$ and $p=3$.
If $ac \not\equiv 1 \bmod p$, then $ac$ is an element of order $3$ in $U(p)$ and so $3$ divides $p-1$, by Lagrange's theorem of group theory.
All this shows that the conditions in the problem are necessary. But they also point the way to the existence of a solution.
Indeed, for $p=3$ we can take $a=b=1$.
For $p \equiv 1 \bmod 3$, take $g$ a primitive root mod $p$ and let $a=g^{\frac{p-1}{3}}$ and $b=1$.
A: $a^2 + ab+ b^2 \equiv \{0_{a\equiv 0}|1_{a\equiv\pm 1}\} + \{-1_{\text{if }a\equiv -b\equiv \pm 1}|0_{a\equiv 0\lor b\equiv 0}|1_{b\equiv \pm 1}\} + \{0_{b\equiv 0}|1_{b\equiv\pm 1}\} \mod 3$.
If one of $a$ or $b$ is equiv to $0$ and the other isnt then the result is $0+0 + 1$ (or $1+0+1$)$\equiv 1 \mod 3$.
If $a \equiv b$ then the result is $\{0|1\} + \{0|1\} + \{0|1\}\equiv \{0|3\}\equiv 0 \mod 3$.
And if $a \equiv -b \equiv \pm 1$ the result is $1 -1 +1\equiv 1 \mod 3$.
So the result follows precisely when $a\not \equiv b \mod 3$.
What am I missing about the question?
If $p = 3$.  possibilities are $(\pm 1,\pm 1),(\pm 2, \mp 1)$.  
