Prime representable as $ x^2 + 3y^2 $ 
I'm to prove that if $ p = 3k+1 $ is a prime greater than $ 3 $ then there exist $ x,y \in \mathbb{Z} $ such that
  $$ p=x^2 + 3y^2.$$

I just don't know how to begin. All I have is Thue lemma and it doesn't seem to be helpful right now
 A: For $\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}\let\leq\leqslant$the sake of an answer I'll give a sketch of the beautiful 'finite descent' proof in the related question Let $p$ be prime and $(\frac{-3}p)=1$. Prove that $p$ is of the form $p=a^2+3b^2$. It goes as follows.
First of all, note that $-3$ is a quadratic residue modulo $p$. This follows from some properties of the Legendre symbol and quadratic reciprocity:
$$\leg{-3}p=\leg{-1}p\leg3p=\leg{-1}p(-1)^{\frac{p-1}2}\leg p3=\leg{-1}p^2\cdot1=1.$$
From here the attack is completely similar to the one in the linked question, but I'll only give a sketch of the technique:


*

*Because $-3$ is a QR modulo $p$, there exist $k,x\in\mathbb N$ s.t. $kp=x^2+3=x^2+3\cdot1^2$. (This follows by definition of a QR.)

*The descent step: Suppose we have $k,x,y\in\mathbb N$ with $x^2+3y^2=kp$. If $k>1$, we can find $x',y'$ s.t. $x'^2+3y'^2=k'p$ for some $0<k'<k$.

*Repeating this step will at some point give $k=1$, as desired.


A crucial fact in this 'finite descent' is the Brahmagupta(-Fibonacci) identity
$$\begin{align*}(a^2+nb^2)(c^2+nd^2)&=(ac-nbd)^2+n(ad+bc)^2\\&=(ac+nbd)^2+n(ad-bc)^2.\end{align*}$$
