Primes congruent to 1 mod 6 I came across a claim that I found interesting, but can't seem to prove for some reason. I have the feeling it should be easy
a prime $p$ can be written in the form $p = a^2 -ab +b^2$ for some $a,b\in\mathbb{Z}$ if and only if $p\equiv 1\bmod{6}$
 A: Here is another, albeit non-elementary, solution for the "if" part due to Ireland and Rosen. If $p\equiv 1\pmod{3}$, there exists a multiplicative character $\chi$ of order $3$. Then, $\chi\in\{1,\omega,\omega^2\}$, where $\omega=e^{2\pi i/3}=\frac{1}{2}(-1+\sqrt{-3})$. Now, consider the Jacobi sum of two such characters: $$J(\chi, \chi)=\sum_{a+b=1}\chi(a)\chi(b)\in\mathbf{Z}[\omega].$$ Then, we can write $J(\chi, \chi)=a+b\omega$, for some $a,b\in\mathbf{Z}$. We have $$p=N(J(\chi, \chi))^2=N(a+b\omega)=a^2-ab+b^2,$$ as desired.
A: If $(a,b)=d,d^2\mid (a^2-ab+b^2)$
If $d>1,a^2-ab+b^2$ can not be prime $\implies d=1$
Now, if prime $p=a^2-ab+b^2\implies p\mid (a+b)(a^2-ab+b^2)\implies p\mid (a^3+b^3)$
So, $$a^3\equiv(-b)^3\pmod p\implies \left(-\frac ab\right)^3\equiv 1\pmod p\implies ord_p \left(-\frac ab\right)\mid 3$$
If $ord_p \left(-\frac ab\right)=1,p(=a^2-ab+b^2)\mid (a+b)$
If $(a^2-ab+b^2)\mid(a+b),(a^2-ab+b^2)\mid(a+b)^2$
$\implies (a^2-ab+b^2)\mid 3ab$
$\implies (a^2-ab+b^2)\mid 3$ as $(a^2-ab+b^2,a)=(b^2,a)=1$ as $(a,b)=1$
But, $a^2-ab+b^2>3,$  for $a,b>2$ 
$$\implies ord_p \left(-\frac ab\right)= 3\implies 3\mid \phi(p)\implies p\equiv1\pmod 3\equiv1,4\pmod 6$$
Hence, $p\equiv1\pmod 6$  as $p\equiv4\pmod 6$ is even and $p>2$
A: $a^2 - ab + b^2 = (-a)^2 + (-a)b + b^2$. So it suffices to deal with $a^2 + ab + b^2$.
Now, take a prime $p \equiv 1 \pmod{6}$. It is elementary to show their exists an integer $d$ such that $d^2 \equiv -3 \pmod{p}$, now take $z \equiv \frac{-1 + d}{2} \pmod{p}$ (so its a third root of unity modulo $p$).  Now define $\mathcal L = \{(a,b) \in \mathbb{Z}^2 | a \equiv zb \pmod{p}\}$. It is straightfoward to check $\mathcal L$ is a lattice whose fundamental parallelogram has area $p$. Now by Minkowski's theorem one has $\mathcal L$ contains a nontrivial lattice point inside the ellipse $a^2 + ab + b^2 < 2p$. Call this point $(a,b)$. But then $a^2 + ab + b^2 \equiv 0 \pmod{p}$ based on the definition of the lattice, thus it must be $a^2 + ab + b^2 = p$. The if part follows.
For the "only if" part, just check modulo $3$ and note that $a^2 + ab + b^2 \equiv 0,1 \pmod{3}$. Note that the problem statement fails for $p=3$ due to that.
A: Here is another solution for the "if" part, using algebraic number theory. Let $p$ be a prime satisfying $p \equiv 1 \pmod 3$ and consider the number field $K = \mathbb Q(\omega)$ where $\omega = (1\pm \sqrt{-3})/2$ is a primitive third root of unity. By quadratic reciprocity,
$$\left( \frac{-3}{p} \right) = \left(\frac{-1}{p} \right) \left( \frac{3}{p} \right) = (-1)^\frac{p-1}{2} (-1)^\frac{p-1}{2} \left(\frac{p}{3}\right) = \left(\frac{1}{3}\right) = 1,$$
so $\mathbb Z/p\mathbb Z$ contains a square root of $-3$. Since $-3$ is the discriminant of $X^2+X+1$ (the minimal polynomial of $\omega$), the polynomial splits in $\mathbb F_p[X]$, therefore $p$ splits in $K$:
$$(p) = \mathfrak p \overline{\mathfrak p}$$
for a prime $\mathfrak p$ of $K$. Since $K$ has class number one (the Minkowski bound is $<2$), $\mathfrak p$ is principal, say $\mathfrak p = (a+b\omega)$. So we have
$$(p) = \mathfrak p \overline{\mathfrak p} = (a+b\omega)(a+b\omega^2) = (a^2+ab+b^2).$$
Since $K$ is imaginary quadratic, the only units in $\mathcal O_K = \mathbb Z[\omega]$ are $\pm 1$, so 
$$p = \pm (a^2+ab+b^2).$$
Since $a^2+ab+b^2$ is positive, we must in fact have "+":
$$p = a^2+ab+b^2 = (-a)^2 - (-a)b + b^2.$$
A: $$(a,b)^2\mid(a^2-ab+b^2)\implies a^2-ab+b^2$$ can not be prime if $(a,b)>1$
Now, $a$ can be of the form $3m,3m+1$ or $ 3m-1$ where $m$ is an integer.
Similarly, $b$ can be $3n,3n+1$ or $3n-1$ where $n$ is an integer.
$(1)$ If $a=3m,a^2-ab+b^2\equiv b^2\pmod 3$
Now, $b^2\equiv0\pmod 3\iff 3\mid b\implies 3\mid(a,b)$ which is impossible as $(a,b)=1$
So, $b^2\equiv1\pmod 3\implies a^2-ab+b^2\equiv1\pmod 3$
$(2a)$ If $a=3m+1, b=3n-1, a^2-ab+b^2\equiv 1-1(-1)+1\equiv0\pmod 3\implies 3\mid p$
But $a^2-ab+b^2>3$ for $a,b>2$ hence in this case will be composite.
$(2b)$  If $a=3m+1, b=3n+1, a^2-ab+b^2\equiv 1-1(1)+1\equiv1\pmod 3$
Clearly,
$(2c),a=3m+1,b=3n\implies a^2-ab+b^2\equiv 1\pmod 3$
$(3a),a=3m-1,b=3n\implies a^2-ab+b^2\equiv 1\pmod 3$
$(3b),a=3m-1,b=3n+1\implies a^2-ab+b^2\equiv 0\pmod 3$
$(3c), a=3m-1,b=3n-1\implies a^2-ab+b^2\equiv1\pmod 3$
So, prime $p=a^2-ab+b^2\equiv1\pmod 3$ for $a,b>2$
Now, $p\equiv1\pmod3\implies p\equiv1,4\pmod 6$
Hence, $p\equiv1\pmod 6$  as $p\equiv4\pmod 6$ is even and $p>2$
A: Here is a relatively elementary solution. Handling $p=2,3$ as special cases, the statement for $p > 3$ is equivalent to $p = a^2 - ab + b^2$ for some integers $a,b$ iff $p \equiv 1 \mod 3$. The forwards part is easy - just consider numbers mod 3.
The key idea is that for any Eisenstein integer $a + b\omega$,  the norm is $N(a + b \omega) = (a + b\omega)(\overline{a + b\omega}) = a^2 - ab + b^2$. This is similar to the fact that the norm of any Gaussian integer $a + bi$ is $(a+bi)(a-bi) = a^2 + b^2$ and a very similar argument follows for Quick proof to showing that $p\equiv 1\pmod{4}$ implies $p$ is reducible in $\mathbb{Z}[i]$?, Fermat's Christmas theorem on sums of two squares with Gaussian integers.
From Does $x^2 + x + 1 \equiv 0 \mod p$ have a solution? there exists integer $x$ such that $p$ divides $x^2 + x + 1 = N(1-\omega) = (1-\omega)(\overline{1-\omega})$. If $p$ were prime in $\mathbb Z[\omega]$, $p \mid 1-\omega$ or $p \mid 1-\overline\omega$, both of which are impossible. So $p$ is not prime, so in the UFD $\mathbb Z[\omega]$, $p$ is not irreducible. Hence $p = (a+b\omega)(c+d\omega)$ for non-units $a+b\omega, c+d\omega$, and by an argument from norm being multiplicative, $N(p) = p^2 = N(a+b\omega)N(c+d\omega)$, and neither norm is $1$ for non-units, so it must be that $p = N(c+d\omega) = N(a+b\omega) = a^2 - ab + b^2$.
(By taking $-b$ instead of $b$, considering $a - b\omega$, we also get $p = a^2 + ab + b^2$.)
