0
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – J. W. Tanner Sep 4 at 0:41
  • $\begingroup$ 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$)? $\endgroup$ – fabrizzio_gz Sep 4 at 17:58
  • $\begingroup$ You're welcome; I think you understand correctly $\endgroup$ – J. W. Tanner Sep 4 at 18:01
  • 1
    $\begingroup$ Thank you very much. You have been a great help. $\endgroup$ – fabrizzio_gz Sep 4 at 19:11
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Will Jagy Sep 4 at 13:29
1
$\begingroup$

$$ \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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.