Jtdylktuy

Let $p$ be prime and $(frac{-3}p)=1$, where $(frac{-3}p)$ is Legendre symbol. Prove that $p$ is of the form $p=a^2+3b^2$.

My progress:

$(frac{-3}p)=1 Rightarrow$ $(frac{-3}p)=(frac{-1}p)(frac{3}p)=(-1)^{frac{p-1}2}(-1)^{lfloorfrac{p+1}6rfloor}=1 Rightarrow$ $frac{p-1}2+lfloorfrac{p+1}6rfloor=2k$
I'm stuck here. This is probably not the way to prove that.

Also tried this way:

$(frac{-3}p)=1$, thus $-3equiv x^2pmod{p} Rightarrow$ $p|x^2+3 Rightarrow$ $x^2+3=pcdot k$

stuck here too.

Any help would be appreciated.

First part:
$$left(frac{-3}{p}right)=1 text{ if and only if }; pequiv{1}!!!!pmod{3}.tag{1}$$
This can be achieved through the Gauss quadratic reciprocity theorem in the most general form, or through the following lines. If $p=3k+1$, by the Cauchy theorem for groups there is an order-3 element in $mathbb{F}_p^*$, say $omega$; from $omega^3=1$ follows $omega^2+omega+1equiv 0pmod{p}$, hence:
$$(2omega+1)^2 = 4omega^2+4omega+1 = 4(omega^2+omega+1)-3 = -3,$$
and $-3$ is a quadratic residue $pmod{p}$. On the other hand, if $-3$ is the square of something $pmod{p}$, say $-3equiv a^2pmod{p}$, then:
$$left(frac{a-1}{2}right)^3equivfrac{1}{8}(a^3-3a^2+3a-1)equivfrac{1}{8}cdot 8equiv{1},$$
and $frac{a-1}{2}$ is an order-3 element in $mathbb{F}_{p}^*$. From the Lagrange theorem for groups it follows that $3|(p-1)$.

Second part:
$$text{If }pequiv 1pmod{3},qquad p=a^2+3b^2.tag{2}$$
Since by the first part we know that $-3$ is a quadratic residue $pmod{p}$, there exists an integer number $cin[0,p/2]$ such that:
$$ c^2+3cdot 1^2 = kcdot p.tag{3}$$
The trick is now to set a "finite descent" in order to have $k=1$. Let $d$ the least positive integer such that $cequiv dpmod{k}$. Regarding $(3)$ mod $k$, we have:
$$ d^2+3cdot 1^2 = kcdot k_1.tag{4}$$
Since the generalized Lagrange identity states:
$$(A^2+3B^2)(C^2+3D^2)=(AC+3BD)^2 + 3(BC-AD)^2,tag{5}$$
by multiplying $(3)$ and $(4)$ we get:
$$ (cd+3)^2 + 3(c-d)^2 = k^2 pk_1.$$
Since $cd+3equiv c^2+3equiv 0pmod{k}$ and $cequiv dpmod{k}$, we can rewrite the last line in the following form:
$$ left(frac{cd+3}{k}right)^2+3left(frac{c-d}{k}right)^2 = k_1cdot p.tag{6}$$
Now a careful analysis of the steps involved in the algorithm reveals that $k_1<k$, so the descent is able to reach $k_i=1$, or:
$$ p = a^2 + 3b^2$$
as wanted.

$(frac{p}{3})=(frac{-3}{p})(frac{p}{3})=(frac{-1}{p})(frac{3}{p})(frac{p}{3})=(-1)^{frac{p-1}{2}}(frac{3}{p})(frac{p}{3})=(-1)^{frac{p-1}{2}}(-1)^{frac{p-1}{2}frac{3-1}{2}} = 1$

Hence,$(frac{-3}{p})=1$ iff, $pequiv1mod3$.

Since, there is $u in mathbb{Z}$ such that, $-3equiv u^2pmod{p}$

Consider the lattice defined by $L={(a,b)inmathbb{Z}^2, : ,aequiv ubpmod p}$ generated by $(u,1)$ and $(0,p)$. $L$ has index $p$ in $mathbb{Z}^2$, and area of its fundamental domain is $p$. Now, consider an ellipse $E_n$ defined by $x^2+3y^2=n$, then the area of $E_n=frac{pi n}{sqrt3}>1.8n$

Choose, $n=2.3 p$, then Area of $E_{n}>4p$ and $E_ncap L$ has a non zero point $(a,b)$.

Now, $a^2+3b^2equiv(ub)^2+3b^2equiv b^2(u^2+3)equiv0 pmod p$.

Since, $(a,b)in E_n implies a^2+3b^2<2.3p$ we have $a^2+3b^2=p,2p$.

But, $a^2+3b^2=2p implies a^2equiv 2p pmod 3 equiv 2 pmod 3$ contradiction !!

Therefore, $a^2+3b^2=p$.