How to find solutions of $x^2-3y^2=-2$?

$$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) \left( \begin{array}{c} -1 \\ 1 \end{array} \right) \; = \; \left( \begin{array}{c} 1 \\ 1 \end{array} \right), $$

$$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) \left( \begin{array}{c} 1 \\ 1 \end{array} \right) \; = \; \left( \begin{array}{c} 5 \\ 3 \end{array} \right), $$

$$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) \left( \begin{array}{c} 5 \\ 3 \end{array} \right) \; = \; \left( \begin{array}{c} 19 \\ 11 \end{array} \right), $$

$$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) \left( \begin{array}{c} 19 \\ 11 \end{array} \right) \; = \; \left( \begin{array}{c} 71 \\ 41 \end{array} \right), $$

$$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) \left( \begin{array}{c} 71 \\ 41 \end{array} \right) \; = \; \left( \begin{array}{c} 265 \\ 153 \end{array} \right), $$

$$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) \left( \begin{array}{c} 265 \\ 153 \end{array} \right) \; = \; \left( \begin{array}{c} 989 \\ 571 \end{array} \right), $$

$$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) \left( \begin{array}{c} 989 \\ 571 \end{array} \right) \; = \; \left( \begin{array}{c} 3691 \\ 2131 \end{array} \right), $$

EDIT, March 2016: From the stuff with the matrix above, we can use the Cayley-Hamilton theorem to give separate linear recurrences for $x$ and for $y.$ Just these: $$ x_{k+2} = 4 x_{k+1} - x_k, $$ $$ y_{k+2} = 4 y_{k+1} - y_k. $$ The $x$ sequence is $$ 1, 5, 19, 71, 265, 989, 3691, 13775, 51409, 191861, \ldots $$ while the $y$ sequence is $$ 1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, \ldots $$

Well. The theorem of Lagrange is that all values of the quadratic form (that are primitively represented) occur as output of the neighboring forms method, the same as doing continued fractions, if they are below $\frac{1}{2} \; \sqrt \Delta$ in absolute value, where in this case $\Delta = 12.$ So half the square root of that is $\sqrt 3,$ and $2$ is larger than this. This means that, while $-2$ is permitted to show up by the continued fraction method, it is possible that unexpected representations may occur. However, one may check with Conway's topograph method from The Sensual Quadratic Form and confirm that all appearances of $-2$ are along the "river" itself, meaning the simplest possible collection, as I illustrate with the matrix multiplications above. For your viewing pleasure, the topograph for $x^2 - 3 y^2,$ with a fair amount of detail:

=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=

Oh, well. The $-2$ at coordinates $(5,3)$ goes in the lower right open space, while the $-2$ at coordinates $(-5,3)$ goes in the lower left open space. If you think about it long enough, each edge in the infinite tree, including the little blue numbered arrow and the value on either side, is an indefinite quadratic form equivalent to $\langle 1,0,-3 \rangle,$ but is also an element in $PSL_2 \mathbb Z$ given by a little 2 by 2 matrix using the two column vectors in green.

Note that the automorph $$ \left( \begin{array}{cc} 2 & 3 \\ 1 & 2 \end{array} \right) $$ is visible as a pair of column vectors corresponding once again to $\langle 1,0,-3 \rangle,$ as, indeed, it must.

Suppose that we have found a particular solution of $x^2-3y^2=-2$, say $(x_0,y_0)$. We can then write $$(x_0+y_0\sqrt{3})(x_0-y_0\sqrt{3})=-2.$$ Note that $2^2-3(1^2)=1$. Write this as $$(2+\sqrt{3})(2-\sqrt{3})=1.$$ Combining the two results above, we see that $$(x_0+\sqrt{3}y_0)(2+\sqrt{3})(x_0-\sqrt{3}y_0)(2-\sqrt{3})=-2.$$ Expanding, we get $$[2x_0+3y_0+\sqrt{3}(x_0+2y_0)] [2x_0+3y_0-\sqrt{3}(x_0+2y_0)]=-2.$$ This just says that $$(2x_0+3y_0)^2-3(x_0+2y_0)^3=-2.$$ Put $x_1=2x_0+3y_0$, and $y_1=x_0+2y_0$. We have shown that $x_1^2-3y_1^2=-2$.

In general, once we have found a solution $(x_n,y_n)$ we can find another solution $(x_{n+1},y_{n+1})$ where $$x_{n+1}=2x_n+ 3y_n \qquad\text{and}\qquad y_{n+1}=x_n+2y_n.$$

Remark: The above idea is very old. You may be interested in looking up the Brahmagupta Identity.

If you're a bit familiar with algebraic number theory:

$x^2 - 3y^2$ is the norm of the element $x + y\sqrt{3}$ in $\mathbb{Q}(\sqrt{3})$. Given the obvious element $1 + \sqrt{3}$ with norm $-2$, every other possibility differs by multiplication with an element of norm $1$. Dirichlet's unit theorem characterizes them: all powers of $2 + \sqrt{3}$ (up to $\pm 1$).

So the solutions are given by $\pm x \pm y\sqrt{3} = (1 + \sqrt{3})(2 + \sqrt{3})^n$ for $n \in \mathbb{Z}$.

This is an issue that comes up over and over again. The quadratic form $m^2-3n^2$ happens to be the norm form for the quadratic field $\mathbb{Q}(\sqrt3)$. That is, when you write $z=m+n\sqrt3$ and $\bar z=m-n\sqrt3$, you see that $z\mapsto\bar z$ preserves both multiplication and addition. So $z\mapsto z\bar z$ is also multiplicative, taking integral things in the field to ordinary integers. And it takes the value $\pm1$ on the group of units of the corresponding integer ring $\mathbb{Z}[\sqrt3]$. We know, from the study of Pell’s Equation, or from continued fractions, or from much more advanced methods, that every unit is plus-or-minus a power of the primitive unit $2+\sqrt3$.

So what? If you can only find one of these quadratic integers, $z_0$, whose “norm” $z\bar z$ is equal to $-2$, you can get all the others by multiplying by units. But of course the norm of $1+\sqrt3$ is $-2$, you’ve got your recipe for finding all. So: $(1+\sqrt3)(2+\sqrt3)=5+3\sqrt3$; $(1+\sqrt3)(2+\sqrt3)^2=19+11\sqrt3$, etc.