$p = x^2 + xy + y^2$ if and only if $p \equiv 1 \text{ mod }3$? For a prime number $p \neq 3$, do we have that$$p = x^2 + xy + y^2$$for some $x$, $y \in \mathbb{Z}$ if and only if$$p \equiv 1 \text{ mod }3?$$I suspect this is true from looking at the example$$7 = 2^2  + 2 \times 1 + 1^2.$$Here is a thought I have so far that might be helpful towards solving this: I know that $$\mathbb{Z}[(1 + \sqrt{-3})/2]$$is a PID. But I am not sure what do from here. Could anybody help?
 A: $p=x^2+xy+y^2=(x-y)^2+3xy$, so this is about the behaviour of perfect squares.
If $z$ is an integer not divisible by $3$, then $z^2\equiv 1\mod 3.$
Since $p\ne 3$ is prime, it is not divisible by $3$.
Hence $x-y$ is not divisible by $3$, and it follows that $p\equiv 1\mod 3.$
A: Here is an answer, maybe not the most illuminating for you and probably not that different from Mathmo123's answer, but involving Jacobi sums.
Let $p\equiv 1 ($mod $3$), $\lambda$ a generator of the group of characters over $\mathbb{F}_p^{\times}$ and set $\chi=\lambda^{\frac{p-1}{3}}$. So the character $\chi$ takes it values in $V=\{0,1,\alpha,\alpha^2\}$ where $\alpha=\frac{-1+\sqrt(-3)}{2}$. Given that the set $V$ is stable under multiplication, the Jacobi sum associated to $\chi$, $J(\chi,\chi)=\sum_{a+b=1} \chi(a)\chi(b)$ is in $\mathbb{Z}+\alpha\mathbb{Z}+\alpha^2\mathbb{Z}=\mathbb{Z}+\alpha\mathbb{Z}$.
So we can write $J(\chi,\chi)=x+y\alpha$ with $x$ and $y$ in $\mathbb{Z}$. But we know $p=|J(\chi,\chi)|^2$; so $p=x^2-xy+y^2$.
Of course the same strategy works for $p\equiv 1$ mod $4$ $\Longleftrightarrow p=x^2+y^2$.
A: Since a lot of the answers are only answering the "only if" part, I'll add a generalization of that part.
If $p> 3$ is prime, $x,y\in\mathbb Z$, $\gcd(p,y)=1$ and $p\mid x^2+xy+y^2$, then $p\equiv 1\pmod{3}$.
Proof: $$p\mid x^2+xy+y^2\implies p\mid 4\left(x^2+xy+y^2\right)=(2x+y)^2+3y^2$$
$$\implies \left((2x+y)y^{-1}\right)^2\equiv -3\pmod{p}\implies p\equiv 1\pmod{3}$$
The last step used Quadratic Reciprocity.
A: In Mathmo's answer, I think we could use a local-global argument to characterize the complete splitting of p>5 in the ring $O_K$. By completion at the primes P of $O_K$ above p, it is straightforward that p splits iff the p-adic field $Q_p$ coincides with the completed fields $K_P$, iff $Q_p$ contains a primitive cubic root of $1$. Since p is not 3, this is equivalent to say that the polynomial $X^3$ - $1$ splits (has 3 distinct roots) in $Q_p$. The roots being actually p-adic integers, we can reduce modulo p and deduce that 3 must divide p-$1$. For the converse, use Hensel's lemma.
A: Partial answer :
We have the following implications (every congruence is mod 3) :
$$x\equiv 0\ ,\ y\equiv 0\implies x^2+xy+y^2\equiv 0$$
$$x\equiv 0\ ,\ y\ne 0\implies x^2+xy+y^2\equiv y^2\ne 2$$
The case $y\equiv 0\ ,\ x\ne 0$ works analogue.
Finally , $$x\ne 0\ ,\ y\ne 0\implies x^2+xy+y^2=1+1+xy=2+xy\ne 2$$
So, we never have $x^2+xy+y^2\equiv 2$. This shows one of the directions.
A: If $p \equiv 1 \pmod 3,$ then the Legendre symbol $(-3|p) = 1.$ We can solve $\beta^2 \equiv -3 \pmod p.$ By choosing either $\beta$ or $p - \beta,$ because this time we need $\beta$ odd, we can solve $\beta^2 \equiv -3 \pmod {4p}.$ That is, $\beta^2 = -3 + 4pt$ for some integer $t.$
So far, we have the binary quadratic form $\langle p, \beta, t \rangle,$ or
$$ f(x,y) = px^2 + \beta xy + t y^2,  $$
of discriminant $-3.$
We apply Gauss reduction to get a reduced form; inequalies show that the only reduced form of discriminant $-3$ is $\langle 1, 1, 1 \rangle.$ The 2 by 2 integer matrix $P$ of determinant $1$ that took us from $\langle p, \beta, t \rangle$ to $\langle 1, 1, 1 \rangle$ has an inverse of integers, $P^{-1}.$ The left hand column of $P^{-1}$ shows how to represent $p$ as $x^2 + xy + y^2.$
Let's see; we find $P$ one step at a time. In the end, though, we have
$$ P^T G P = H,  $$
where
$$ G =
\left(
\begin{array}{rr}
p & \frac{\beta}{2} \\
\frac{\beta}{2} & t
\end{array}
\right)
$$
and
$$ H =
\left(
\begin{array}{rr}
1 & \frac{1}{2} \\
\frac{1}{2} & 1
\end{array}
\right)
$$
If we name $Q = P^{-1},$ we have
$$ Q^T H Q = P. $$ Which, you see, is a good thing.
A: Regarding only if:
$x =y (mod 3)$ is not possible since that would imply that $p=0+0+0=0 (mod 3)$  or $1+1+1 =0 (mod 3) $
For the other alternatives we have:
For $x=0$ and $y=1$ or $2$ gives the result $p=1 (mod 3) $.
Otherwise assume $x=1  (mod 3)$ and $y=2 (mod 3)$. This also gives us $p=1+2+1=1 (mod 3) $
A: Let $K = \mathbb Q(\sqrt{-3})$. Consider the integer ring $\mathcal O_K = \mathbb Z[\alpha]$, where $\alpha = \frac{1+\sqrt{-3}}{2}$. Recall that the field norm of an element $x+y\alpha\in\mathcal O_K$ is 
$$N_{K/\mathbb Q}(x+y\alpha) =(x+y\alpha)(x+y\overline\alpha) = x^2+xy+y^2.$$
You've correctly remarked that $\mathcal O_K$ is a PID. It follows that

A prime $p$ can be expressed as $p=x^2+xy+y^2$ if and only if $p$ is the norm of some element of $\mathcal O_K$. 

If $p\ne 3$ (so that $p$ does not ramify in $\mathcal O_K$) and $p = N_{K/\mathbb Q}(x+y\alpha)$, then the ideal $(x+y\alpha)$ is a prime ideal of $\mathcal O_K$ lying above $p$ with norm $p$. So $p$ splits completely in $\mathcal O_K$.
Conversely, if $p = \mathfrak{p_1p_2}$, then since $\mathcal O_K$ is a PID, $\mathfrak p_1$ is generated by an element of $\mathcal O_K$, which must have norm $p$. Hence,

A prime $p\ne 3$ can be expressed as $p=x^2+xy+y^2$ if and only if $p$ splits completely in $\mathcal O_K$.

To examine when this can happen, we can use the following version of the Kummer-Dedekind Theorem:

Theorem: Let $p$ be a prime, and let  $\beta\in \mathcal O_K$ be such that $K=\mathbb Q(\beta)$ and $p\nmid (\mathcal O_K:\mathbb Z[\beta])$. Let $f(X)$ be the minimal polynomial of $\beta$ over $\mathbb Q$. Suppose that 
  $$f(X) \equiv f_1(X)^{e_1}\cdots f_m(X)^{e_m}\pmod p. $$ 
  Then $p$ splits as $p\mathcal O_K = \mathfrak{p_1^{e_1}\cdots p_m^{e_m}}$ in $\mathcal O_K$.

In particular, taking $K$ as above and $\beta = \sqrt{-3}$, since $(\mathcal O_K, \mathbb Z[\sqrt{-3}]) = 2$, the above theorem applies to all primes $p>2$. The case $p=2$ can be checked manually.
So for $p\ge 5$
$$
\begin{align}
p \text{ splits completely in }\mathcal O_K&\iff X^2+3\text{ splits into distinct linear factors mod }  p\\&\iff X^2+3\text{ is reducible mod }  p\\
&\iff\left(\frac{-3}p\right)=1\\
&\iff(-1)^{(p-1)/2}\left(\frac{3}p\right)=1\\
&\iff(-1)^{\frac{p-1}2}(-1)^{\frac{p-1}2\frac{3-1}2}\left(\frac p3\right) = 1\text{ by quadratic reciprocity}\\
&\iff \left(\frac p3\right) = 1\\&\iff p\equiv 1 \pmod 3.
\end{align}
$$
The result follows.
A: This maybe or maybe doesn't help, but for the "if" part, the only prime numbers which could satisfy the condition $p \equiv 1 \ mod\  3$ are those of the form $(2n)*3+1$, since if it was one more than an odd multiple of three it would be even, hence not prime.
As in your example, 7=(2*1)*3+1, n=1.
I.e. a necessary condition for p is that it equals 1 $\equiv$ mod 6.
