Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 12 down vote accepted

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

share|cite|improve this answer
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.$$

share|cite|improve this answer

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.

share|cite|improve this answer

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$

share|cite|improve this answer

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


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

share|cite|improve this answer

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 \begin{equation} A_{n+3} = rA_{n+2} - sA_{n+1} + tA_n,\qquad n \ge 0. \end{equation}

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.