# Recurrence relation solution to negative Pell's equation

I'm trying to determine how to get the sequence of possible solutions for a negative Pell's equation: $$x^2 - 2y^2=-1$$ I know that the fundamental solution is $$x_1=1$$ and $$y_1=1$$, but I don't know how to get the recurrence relation to get all the solutions.

I have seen found here that the recurrence relation is: $$x_{n+1}=3x_n+4y_n,\qquad y_{n+1}=2x_n+3y_n.$$ Which is similar to the recurrence relation for positive Pell's equations found on Wikipedia:

$$x_{k+1} = x_1x_k+ny_1y_k,\qquad y_{k+1} = x_1y_k+y_1x_k$$ Using $$x_1=3$$ and $$y_1=2$$, but I don't understand why do we use those values instead of those of the fundamental solution.

How are the recurrence relations for negative Pell's equations obtained? (particularly for this case)

• Given $(1+\sqrt2)(1-\sqrt2)=-1$, $(1+\sqrt2)^2(1-\sqrt2)^2=(3+2\sqrt2)(3-2\sqrt2)=+1$, so if $(x+\sqrt2y)(x-\sqrt2y)=-1$ then $(x+\sqrt2y)(1+\sqrt2)(x-\sqrt2y)(1-\sqrt2)=1$, but $(x+\sqrt2y)(3+2\sqrt2)(x-\sqrt2y)(3-2\sqrt2)=-1$ – J. W. Tanner Sep 4 at 0:41
• Thank you very much. If I understand correctly, we can conclude from your last equation that we can get more solutions by multiplying the original equation ($x^2 - 2y^2=-1$) by $(3+2\sqrt2)(3-2\sqrt2)$ and then rearranging the terms to get new solutions ($x_{k+1}, y_{k+1}$) in terms of the initial solutions ($x_k,y_k$)? – fabrizzio_gz Sep 4 at 17:58
• You're welcome; I think you understand correctly – J. W. Tanner Sep 4 at 18:01
• Thank you very much. You have been a great help. – fabrizzio_gz Sep 4 at 19:11

Building on the comment from @J.W.Tanner, $$x_{n+1}+\sqrt2y_{n+1}=(x_n+\sqrt2y_n)(3+2\sqrt2)=(3x_n+4y_n)+(2x_n+3y_n)\sqrt2$$ is one way to get $$x_{n+1}=3x_n+4y_n$$, $$y_{n+1}=2x_n+3y_n$$.

• Gerry, I think it was Asaf and I who experimented with pings inside answers. The conclusion, which may be exactly what you intended, was that this visually helps call attention to that username, but does not product a ping (for Tanner, a little red sign of new notifications in the upper right) this way. – Will Jagy Sep 4 at 13:29

$$\left( \begin{array}{cc} 3&4 \\ 2&3 \\ \end{array} \right)$$

The matrix was traditionally called an "automorph."

$$\left( \begin{array}{cc} 3&2 \\ 4&3 \\ \end{array} \right) \left( \begin{array}{cc} 1 & 0\\ 0 & -2 \\ \end{array} \right) \left( \begin{array}{cc} 3&4 \\ 2&3 \\ \end{array} \right)= \left( \begin{array}{cc} 1 & 0\\ 0 & -2\\ \end{array} \right)$$

That is why....

Cayley-Hamilton is what tells us that

$$x_{n+2} = 6 x_{n+1} - x_n$$ $$y_{n+2} = 6 y_{n+1} - y_n$$

The $$x$$ values begin $$1, 7, 41, 239, 1393, 8119, 47321, 275807, 1607521,...$$ The $$y$$ values begin $$1, 5, 29, 169, 985, 5741, 33461, 195025, 1136689,...$$

This can also be proved by ordinary calculations.