# 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}$

-
The "only if" part is easy; the "if" part, not quite as easy. – Gerry Myerson Jan 17 '13 at 6:18
Oh, and there's one exception; $a=1$, $b=-1$, $p=3$. – Gerry Myerson Jan 17 '13 at 6:19
As Gerry points out, the only if part is easy since $a^2 - ab + b^2 \equiv 0,1 \pmod 3$. Hence, primes of the form $3k-1$ equivalently of the form $6k-1$ cannot be written as $a^2 - ab + b^2 \equiv 0,1 \pmod 3$. And all primes, except $2$ and $3$ are $\pm 1 \pmod 6$. – user17762 Jan 17 '13 at 6:26
So what is the trick for the "if" direction? Is it a long proof and is there a reference I can check? – Math2012pc Jan 17 '13 at 6:51
@Math2012pc, one possible answer is from the arithmetic of Eisenstein integers. There is probably an answer in the book "Primes of the form $x^2+ny^2$", but it would be better if you say a few words about your background, i.e. do you know what PID is? Do you know anything about splitting of primes? Quadratic reciprocity? – user27126 Jan 17 '13 at 7:22

$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.

-
Nice, but too much use of disturbing words like "elementary", "straightforward", "just"... – DonAntonio Jan 17 '13 at 12:17
Well the proofs for them are quite easy and well-known so there wasn't much reason to put them. – dinoboy Jan 17 '13 at 15:50
Indeed $4 > \pi \cdot \tfrac{2}{\sqrt{3}} \approx 3.63$ – cactus314 May 12 '14 at 18:00

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.$$

-

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.

-

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,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$

-

To prove the [more difficult] "if" portion in a totally elementary (and fairly simple) way, you can use Bini's recurrence:

Let $x$, $y$, $z$ be any numbers, and set \begin{align} r &:= x+y+z, & s &:= xy+xz+yz, & t &:= xyz. \end{align} Define $A_0 = 3$, and for every $n\ge 1$ define \begin{align*} A_n := x^n+ y^n+ z^n. \end{align*} Then $$A_{n+3} = rA_{n+2} - sA_{n+1} + tA_n,\qquad n \ge 0.$$

-
You seem to have posted this on the wrong thread... – Andrés Caicedo Oct 4 '13 at 0:55
Sorry, my mistake. – Kieren MacMillan Oct 4 '13 at 1:19