elementary number theory - Let $p$ be prime and $(frac{-3}p)=1$. Prove that $p$ is of the form $p=a^2+3b^2$

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)^{\lfloor\frac{p+1}6\rfloor}=1 \Rightarrow$ $\frac{p-1}2+\lfloor\frac{p+1}6\rfloor=2k$
I'm stuck here. This is probably not the way to prove that.

Also tried this way:
$(\frac{-3}p)=1$, thus $-3\equiv x^2\pmod{p} \Rightarrow$ $p|x^2+3 \Rightarrow$ $x^2+3=p\cdot k$
stuck here too.

Any help would be appreciated.

Answer

First part:
$$\left(\frac{-3}{p}\right)=1 \text{ if and only if }\; p\equiv{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+1\equiv 0\pmod{p}$, hence:
$$(2\omega+1)^2 = 4\omega^2+4\omega+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 $-3\equiv a^2\pmod{p}$, then:
$$\left(\frac{a-1}{2}\right)^3\equiv\frac{1}{8}(a^3-3a^2+3a-1)\equiv\frac{1}{8}\cdot 8\equiv{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 }p\equiv 1\pmod{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 $c\in[0,p/2]$ such that:
$$c^2+3\cdot 1^2 = k\cdot 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 $c\equiv d\pmod{k}$. Regarding $(3)$ mod $k$, we have:
$$d^2+3\cdot 1^2 = k\cdot 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+3\equiv c^2+3\equiv 0\pmod{k}$ and $c\equiv d\pmod{k}$, we can rewrite the last line in the following form:
$$\left(\frac{cd+3}{k}\right)^2+3\left(\frac{c-d}{k}\right)^2 = k_1\cdot p.\tag{6}$$
Now a careful analysis of the steps involved in the algorithm reveals that $k_1 $$p = a^2 + 3b^2$$
as wanted.