# If prime $p\not \equiv 1 \pmod 3$, then $p^2 = a^2 + ab + b^2$ has no solutions $a,\,b \in \mathbb{N} \}$

I would like to stress that this is a homework question that is worth a significant amount of my grade, so don't blurt out a solution if you find it.

I am trying to show that if $p^2 \in S := \{a^2 + ab + b^2 : a,\,b \in \mathbb{N} \}$ , then $p \in S$. I have worked out that $p \in S$ iff $p \not \equiv -1 \pmod 3$, so I can turn this into a contrapositive proof showing that if $p \equiv -1$ then $p^2 \notin S$.

However, I don't know what I can do with the fact that $p \equiv -1$ because either way, $p^2 \equiv 1$. I tried looking mod $p$, but I have no idea how to relate that back to mod 3. I've tried looking at the proof of the fact that $p = a^2 + b^2$ iff $p\equiv 1 \pmod 4$, but I don't see how to translate into something similar in this case.

I've used the formula $4p = 3(a+b)^2 + (a-b)^2$ to simplify a lot of my work so far. I have that $\gcd(a,b) = 1$. I know that for $p^2 = a^2 + ab + b^2$, $a,\,b \ne 1,\,2$ by essentially brute force. I have a bunch of calculations for particular a, b, but I think that is mostly irrelevant now that I know what $p$ is modulo $3$.

What approaches do you think I could take to solving the next step? I don't see where to go from here.

• Hint: look at what you can get from your equation $4p = 3(a+b)^2 + (a-b)^2$, using quadratic residues. – Old John Oct 17 '13 at 5:59
• why a significant amount of your grade? – Will Jagy Oct 17 '13 at 6:29
• and, what have they been teaching you so far? Hi @OldJohn – Will Jagy Oct 17 '13 at 6:33
• This is one of 5 questions on one of 6 problem sets that determine our entire grade. We have covered quadratic reciprocity, Wilson's theorem, Hensel's lemma, Euler's theorem, CRT, other things that don't have names so I don't know how to refer to them, other things that I can't recall. – fhyve Oct 17 '13 at 6:47
• This question appears to be off-topic because it is, in effect, a take-home exam. – Will Jagy Oct 17 '13 at 7:07

There are three possibilities of $p$:

$p \equiv 0 \pmod 3$.

$p \equiv 1 \pmod 3$.

$p \equiv 2 \pmod 3$.

Can you find the remainders of $p^2$ modulo 3 for each of the cases?

• Contrast $a\equiv b(\mod p)$ which is a\equiv b(\mod p) to $a\equiv b\pmod p$ which is a\equiv b\pmod p. – Pedro Tamaroff Oct 17 '13 at 6:47

HINT:

We have $4p^2=(2a+b)^2+3b^2\implies (2a+b)^2\equiv-3b^2\pmod p\implies \left(\frac{2a+b}b\right)^2\equiv-3\pmod p$

We can prove $\displaystyle\left(\frac{-3}p\right)=1$ if $p\equiv1\pmod 6$ (See here)

You can write $a^2+ab+b^2 = (a^3-b^3)/(a-b)$, whence fermat's little theorem states that if p has a three digit period in base $a/b$, then $3 \mid p-1$.

You can also use $(a+\frac b2)+\frac b2\sqrt{-3}$, which when multiplied by its conjucate $(a+\frac b2) - \frac b2\sqrt{-3}$, gives $a^2+ab+b^2$. So if $p^2$ can be expressed in this form, then $p \equiv (a+\frac b2) - \frac b2\sqrt{-3}$.