Take the 2-minute tour ×
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.

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|improve this question
    
The "only if" part is easy; the "if" part, not quite as easy. –  Gerry Myerson Jan 17 '13 at 6:18
2  
Oh, and there's one exception; $a=1$, $b=-1$, $p=3$. –  Gerry Myerson Jan 17 '13 at 6:19
1  
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
1  
@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
show 1 more comment

6 Answers

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|improve this answer
2  
Nice, but too much use of disturbing words like "elementary", "straightforward", "just"... –  DonAntonio Jan 17 '13 at 12:17
1  
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$ –  john mangual May 12 at 18:00
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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

share|improve this answer
add comment

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|improve this answer
1  
You seem to have posted this on the wrong thread... –  Andres Caicedo Oct 4 '13 at 0:55
    
Sorry, my mistake. –  Kieren MacMillan Oct 4 '13 at 1:19
add comment

Your Answer

 
discard

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.