I'm working through Reid's Undergraduate Commutative Algebra to prepare myself for Algebraic Geometry next semester, and one of the exercises (0.19) walks you through studying the ring $\mathbb Z[\sqrt5]$. Part of this analysis includes showing that if $5$ is a quadratic residue mod $p$ (i.e., by quadratic reciprocity, $p \equiv \pm1 \pmod 5$), then $p$ is reducible. Reid says this can be shown using a modification of the argument that any prime $p \equiv 1 \pmod 6$ is of the form $3 a^2 + b^2$ outlined in exercise 0.14:
pick any $a \in \mathbb Z$ with $a^2 \equiv -3 \mod p$ (this is possible by Ex. 0.13). Consider $x - a y$ as $(x, y)$ run independently through the integers in $[0, \sqrt p]$; there are > $p$ pairs $(x, y)$, hence they are not all distinct mod $p$. If $x_1 - a y_1 \equiv x_2 - a y_2$ then $$(x_1 - x_2)^2 + 3 (y_1 - y_2)^2 = N p \quad \text{with $N = 1, 2$ or $3$.}$$ Now $N = 2$ is impossible, and if $N = 3$ you can divide through.
Doing this, I was able to show that there are distinct pairs $(x_1, y_1), (x_2, y_2)$ such that $5(y_1 - y_2)^2 - (x_1 - x_2)^2 = N p$ with $N = 1$ or $N = 4$, but I've only been able to show you can divide through when $N = 4$ in the case both $x_1 - x_2, y_1 - y_2$ are even. Is there a way to complete this proof? Is there a better proof?
Expanding and simplifying my previous comment:
Using a variant of the Brahmagupta identity, we have
$$-4(5a^2 - b^2) = (1^2 - 5\cdot 1^2)(5a^2 - b^2) = 5(a+b)^2 - (b+5a)^2.$$
This gives you a new mechanism with which you can divide by $-4$: if $4p = 5x^2 - y^2$, then $-p = 5[(y-x)/4]^2 - [(5x-y)/4]^2$.
Now, it may be that $y-x$ is not divisible by $4$, but in the case that $x$ and $y$ are both odd, then you can just replace $x \mapsto -x$ to fix that. And you already know how to handle the case where $x$ and $y$ are both even. (We leave it to the reader to explain why we don't consider the case where exactly one of $x,y$ is odd.)
Once you have $-p$ represented by some $5r^2 - s^2$, it's easy to flip the sign using Brahmagupta again with $2^2 - 5\cdot 1^2 = -1$.