Generating all solutions for a negative Pell equation

Question

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?

Answer 1

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.