# Generating all solutions for a negative Pell equation

How to get all solutions for a negative Pell equation? For example, the equation $$x^2 - 2 y^2 = -1$$ has two solutions - $$(7, 5)$$ and $$(41, 29)$$, and the $$(7, 5)$$ is the fundamental one, right? How to get the $$(41, 29)$$ solution from the fundamental one?

The fundamental solution of the equation $x^2-2y^2=-1$ is $(1,1)$. We get all positive solutions by taking odd powers of $1+\sqrt{2}$. The positive solutions are $(x_n,y_n)$, where $x_n+y_n\sqrt{2}=(1+\sqrt{2})^{2n-1}$.
One can alternately obtain a recurrence for the solutions. If $(x_n,y_n)$ is a positive solution, then the "next" solution $(x_{n+1},y_{n+1})$ is given by $$x_{n+1}=3x_n+4y_n,\qquad y_{n+1}=2x_n+3y_n.$$
Note that your solution $(7,5)$ is the case $n=2$, and $(41,29)$ is the case $n=3$.
Similarly, the positive solutions of the equation $x^2-dy^2=-1$ (if they exist) are obtained by taking the odd powers of the fundamental solution.
• You are welcome. There is, as you can imagine, a lot of theory, though the characterization of the $d$ for which there is a solution is not completely satisfactory. The fundamental solution, when it exists, can be found by looking at the continued fraction expansion of $\sqrt{d}$. – André Nicolas Oct 19 '13 at 18:13