Prove that there exists $x,y \in \mathbb{Z}$ such that $x^2 - 11y^2 = p$ if and only if $p = 1,3,4,5,9 \bmod 11$ with $p \equiv 1 \bmod 4$ prime

Here is a possible presentation for Fermat's descent method mentioned in lulu's comment.

First, we establish a lemma that will allow us to check easily by hand if a (small) positive integer is of the form $Q(x,y)=x^2-11y^2$ (i.e. is "representable") or not.

Lemma 1. Let $k\gt 0$ be an integer. If $k$ can be written as $k=Q(x,y)$ where $x,y$ are integers, then it has a representation $k=Q(x,y)$ with $\sqrt{\frac{11}{2}}k \gt x\gt y \gt 0$ (so there are only a finite number of candidates to check).

Proof of Lemma 1. Changing the sign of $x$ or $y$ if necessary, we can assume that $x,y$ are positive. Take such a representation with the smallest possible value for $x$. If we put $x'=10x-33y, y'=-3x+10y$, then we see that $k=Q(x',y')$ is another representation of $k$ (this comes from the fact that $u=10-3\sqrt{11}$ is a unit in ${\mathbb Z}[\sqrt{11}]$ and $x'+y'\sqrt{11}=u(x+y\sqrt{11})$). Now, $x' \geq 10\sqrt{11}y-33y \gt 0$, so by hypothesis we have $x' \geq x$ i.e. $x\geq \frac{11}{3}y$. It follows that $d=9x^2-121y^2$ is $\geq 0$, now $d=11(x^2-11y^2)-2x^2$, so that $11k\geq 2x^2$ as wished. This finishes the proof of Lemma 1.

Now, we can partition the primes into three categories : the set $I$ of "inert" primes, for which $11$ is not a square modulo $p$ ; the set $R$ of "regular" primes, for which $11$ is a square modulo $p$ and $p$ is representable ; and the set $S$ of "special" primes for which $11$ is a square modulo $p$ and $p$ is not representable.

The most easy cases of Fermat descent are for primes in $I$ or $R$.

Fact 2. (a : Descent for primes in $I$). Let $p\in I$. Then $p$ divides $Q(x,y)$ iff $p$ divides both $x$ and $y$. As a corollary, we have the descent rule that $pm$ is representable iff $p$ divides $m$ and $\frac{m}{p}$ is representable.

(b : Descent for primes in $R$). Let $p\in R$, so that $p=a^2-11b^2$ with $a,b\in{\mathbb Z}$. Then $p$ divides $Q(x,y)$ iff $\frac{x}{y} \equiv \frac{a}{b}$ modulo $p$. As a corollary, we have the descent rule that $pm$ is representable iff $m$ is (in fact, if $Q(x,y)$ is a representation of $pm$, then $Q(\frac{ax-11by}{p},\frac{-bx+ay}{p})$ is a representation of $m$).

Less obviously, we have :

Lemma 3. (a : Special descent rule for the prime $p=2$) We have that $4$ divides $Q(x,y)$ iff $2$ divides both $x$ and $y$. As a corollary, we have the descent rule that $4m$ is representable iff $m$ is (in fact, if $Q(x,y)$ is a representation of $4m$, then $Q(\frac{x}{2},\frac{y}{2})$ is a representation of $m$).

(b : Descent for primes in $S$). Let $p\in S$. Then $2p$ is representable, $2p=A^2-11B^2$ with $A,B\in{\mathbb Z}$. As a corollary, we have the descent rule that $pm$ is representable iff $2m$ is (in fact, if $Q(x,y)$ is a representation of $pm$, then $Q(\frac{Ax-11By}{p},\frac{-Bx+Ay}{p})$ is a representation of $2m$).

Proof of Lemma 3. (a) This is clear.

(b) We argue by induction on a prime $p\in S$. The base case is $p=2$ : we use Lemma 1 to show that $2$ is not representable, and $2\times 2=Q(2,0)$ is clearly representable. Now suppose that an odd $p$ is in $S$ and that the property holds for all primes $q\lt p$ in $S$.

The set ${\cal M}$ of all positive $m$'s such that $pm$ is representable, is not empty. Let $M$ be its smallest element. By definition of $S$, we must have $M\gt 1$. By definition of $S$ again, there is an integer $s$ such that $s^2 \equiv 11$ modulo $p$. We can take $|s|\leq \frac{p-1}{2}$, and then $M\leq \frac{s^2-11}{p} \lt p$. Thus all the primes divisors of $M$ are $\lt p$. If $M$ had a prime divisor $q$ in $I$ or $R$, we could use the descent rules in Fact 2 to deduce that $\frac{M}{q}\in {\cal M}$ contradicting the definition of $M$. So all the prime divisors of $M$ must be in $S$. By the induction hypothesis, the descent rule (b) above applies to all those prime divisors, so iterating it we have $2^{g}p$ is representable for some $g\geq 0$. Next, iterating the descent rule for $2$, we can assume $g=0$ or $1$. But $g=0$ is impossible by definition of $S$, so $g=1$ and $2p$ is representable as wished. This finishes the proof of Lemma 3.

We now have descent rules for every prime, and we easily deduce the following :

Theorem 4. Let $n$ be a positive integer, and let $\prod p^{e_p}$ be the prime factorization of $n$. Then $n$ is representable iff $e_p$ is even for every $p\in I$, and $\sum_{p\in S}e_p$ is even.

Now let $p$ be a prime. Suppose that $p\equiv 3$ modulo $4$. For any $y\in{\mathbb Z}$, $y^2$ is $0$ or $1$ modulo $4$, so that $p+11y^2$ is $2$ or $3$ modulo $4$, and therefore cannot be a perfect square. So $p$ is not representable.

Suppose that $p\equiv 1$ modulo $4$. For any $y\in{\mathbb Z}$, $y^2$ is $0,1$ or $4$ modulo $8$, so that $2p+11y^2$ is $2,5$ or $6$ modulo $8$, and therefore cannot be a perfect square. So $2p$ is not representable. By lemma 3 (b), it follows that $p$ is not in $S$. In other words, $p$ is representable iff $11$ is a square modulo $p$. By quadratic reciprocity, $11$ is a square modulo $p$ iff $p$ is a square modulo $11$. This finishes the proof.