1
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Grigory M May 5 '14 at 14:53
  • $\begingroup$ Related: Fermat's Christmas theorem on sums of two squares... $\endgroup$ – Grigory M May 5 '14 at 15:04
  • 1
    $\begingroup$ 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$ $\endgroup$ – mercio May 5 '14 at 15:09
0
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ the first equivalence is clearly not true. $\endgroup$ – mercio May 5 '14 at 14:41
  • $\begingroup$ See also : math.stackexchange.com/questions/84951/… or math.stackexchange.com/questions/398376/… $\endgroup$ – lab bhattacharjee May 5 '14 at 14:41
  • 1
    $\begingroup$ @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$$ $\endgroup$ – lab bhattacharjee May 5 '14 at 14:43
  • 2
    $\begingroup$ 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. $\endgroup$ – Grigory M May 5 '14 at 14:52
  • 2
    $\begingroup$ ...so as an answer this is substantially incomplete, and as a hint — almost misleading. $\endgroup$ – Grigory M May 5 '14 at 14:58

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