# $p$ is an odd prime number where $p=3k+1\Longleftrightarrow\exists a,b\in\Bbb Z^+$ such that $p=a^2+ab+b^2$ [duplicate]

Let $p$ be odd prime number,show that:

$$p=3k+1\Longleftrightarrow \exists a,b\in\Bbb Z^+ \textrm{ such that } p=a^2+ab+b^2$$

I guess this is true because I find

when: $p=7,k=2$,and $$7=2^2+2\cdot 1+1^2$$

(2) when $p=13,k=4$,and $$13=1^2+1\cdot 3+3^2$$ and so on.

How do I prove this ?

• If you know e.g. a proof that $p=a^2+b^2$ iff $p=4k+1$ you can try to do smth analogous. If not — perhaps you should try to use some number theory text book (e.g. Ireland–Rosen). – Grigory M May 5 '14 at 14:53
• – Grigory M May 5 '14 at 15:04
• this is a minor nitpick, but $3 = 1 + 1 + 1$ and $3$ is an (odd) prime number but $3$ is not of the form $3k+1$ – mercio May 5 '14 at 15:09

HINT:

For odd prime $p$,

$$a^2+ab+b^2=p\implies(2a+b)^2\equiv-3b^2\mod p$$ $$\iff\left(\frac{2a+b}b\right)^2=-3\mod p$$

Check when $-3$ is a Quadratic Residue $\pmod p$

Now, use this

Alternatively, $$\left(\frac{-3}p\right)=\left(\frac{-1}p\right)\cdot\left(\frac3p\right)$$

$-1$ is a quadratic residue modulo $p$ if and only if $p\equiv 1\pmod{4}$

Using Quadratic Reciprocity Theorem $$\left(\frac3p\right)\left(\frac p3\right)=(-1)^{\frac{(p-1)(3-1)}4}=(-1)^{\frac{p-1}2}$$

$$a\equiv\pm1\pmod 3\implies a^2\equiv1\pmod3$$

Can you take it home from here?

• the first equivalence is clearly not true. – mercio May 5 '14 at 14:41
• – lab bhattacharjee May 5 '14 at 14:41
• @mercio, $$p=a^2+ab+b^2\implies 4p=4a^2+4ab+4b^2=(2a+b)^2+3b^2\implies (2a+b)^2\equiv-3b^2\pmod p$$ – lab bhattacharjee May 5 '14 at 14:43
• The direction '$-3$ is a residue => $p$ is representable' is quite non-trivial and requires either factorization in Eisenstein integers or some clever descent argument. – Grigory M May 5 '14 at 14:52
• ...so as an answer this is substantially incomplete, and as a hint — almost misleading. – Grigory M May 5 '14 at 14:58