Solve the following equation for x and y: $x^2 = y^2 + xy + 5$, where $x$ and $y$ are natural numbers.
Here is what I have so far:


*

*$x \neq y$ (from the equation).

*$x$ is always odd (using the equation and assuming $2$ cases - $y$ is odd or $y$ is even).

*Solving for the equation as a quadratic in $y$, $5x^2 - 20 \geq 0$ and a perfect square.
I feel I am missing a crucial point which will guide me towards a solution.
Hint please!
 A: Multiply by $4$. 
$$4x^2=4y^2+4xy+20$$
$$5x^2=(2y+x)^2+20$$
So, try to solve $$5x^2=z^2+20$$
$z$ must be multiple of $5$. So put $z=5a$ to get $$x^2-5a^2=4$$
This is a Pell's equation with a solution $x=3, a=1$. From this and a minimal solution of $$A^2-5B^2=1,$$
say $A=9, B=4$, you can generate all solutions, and return to the original variables to get the solutions for the original equation.
A: I like Conway's graphical method for these, the quadratic form is $f(x,y) = x^2 - xy- y^2,$ and we are looking for the value $5.$ As you can see, these happen when $y,x$ are consecutive Lucas numbers, $x$ is the larger one. I will need to look this up, there is something about odd/even indices as well. Alright, looked it up, the solutions with natural numbers are
$$  x = L_{2n}, \; \; y = L_{2n-1}; \; \; \; \; \; \;  n \geq 1 $$
See chapter 1 in http://www.maths.ed.ac.uk/~aar/papers/conwaysens.pdf 
Let's see, Conway likes the letter $h$ for the little blue numbers labelling edges, the arrow points in the direction of increasing form value. He likes $a,b$ for the values, and two values $a,b$ on either side of an edge $h$ denote the quadratic form $a x^2 + h x y + b y^2$ or  $a x^2 - h x y + b y^2$  which is "equivalent" to the original. Our original is $x^2 - xy - y^2$ as that arrow points left, we see that $x^2 + xy - y^2,$ $x^2 + 3xy + y^2,$ and $x^2 + 5 xy + 5 y^2$ are equivalent to that. So is $5 x^2 + 5 xy + x^2.$
Conway does not generally draw in the $x,y$ coordinates of a point, i did that in green. Conway prefers to write those as vectors $e_1$ or $e_2.$ My way  is done in another book, by Stillwell. Finally, neither author forces the diagram to show the automorphism group, but, for MSE, that seems an important aspect. 

What is traditionally called the automorphism group of the quadratic forms tells us that if we have a solution $x^2 - x y - y^2 = 5,$ then we get another one from
$$ (2x+y, x+y).  $$ This is the matrix product
$$
\left(
\begin{array}{cc}
2 & 1 \\
1 & 1
\end{array}
\right)
\left(
\begin{array}{c}
x \\
y
\end{array}
\right) = 
\left(
\begin{array}{c}
2x+y \\
x+y
\end{array}
\right)
$$
The matrix 
$$
A =
\left(
\begin{array}{cc}
2 & 1 \\
1 & 1
\end{array}
\right)
$$
has determinant $1,$ and trace $3.$ So, Cayley-Hamiltion says
$$ A^2 - 3 A + I = 0,  $$ or
$$ A^2 = 3 A - I .  $$
This tells us that, if we put the solutions $(x_n, y_n),$ we have
$$ x_{n+2} = 3 x_{n+1} - x_n, $$
$$ y_{n+2} = 3 y_{n+1} - y_n $$
as identities in the separate variables. these lead quickly to confirmation of the Lucas property. 
