Recurrence Relation for a Pell Equation

Date: 11/09/1999 at 22:18:14
From: Steve Cash
Subject: Pell Equations

Can you help me with the following:

I need to find a recurrence relation for generating solutions to the 
Pell equation x^2 - 5y^2 = 1. I can't remember much about Pell 
equations or recurrence relations from previous math courses I have 
taken and I'm having trouble finding any information.

Thank you for your help.
Steve

Date: 11/10/1999 at 09:04:53
From: Doctor Floor
Subject: Re: Pell Equations

Hi, Steve,

Thanks for writing.

First see my answer to this question in our archives:

  Triangular Numbers That are Perfect Squares
  http://mathforum.org/dr.math/problems/manuel.9.07.99.html   

Now, the minimal solution of x^2 - 5y^2 = 1 is (9,4).

So the solutions (u,v) of x^2 - 5y^2 = 1 can be found by:

     u + v*sqrt(5) = (9 + 4*sqrt(5))^n

If you have a solution (u,v), then the next one is found in the 
following way:

       (u + v*sqrt(5))(9 + 4*sqrt(5))

     = 9u + 9v*sqrt(5) + 4u*sqrt(5) + 20v

     = 9u + 20v + (4u + 9v)*sqrt(5)

So the next solution is (9u+20v, 4u+9v).

This can be written in matrix multiplication:

     ( 9 20 )   ( u )
     ( 4 9  ) * ( v )

gives the next solution.

I hope this helped you out. If you have more questions, just write 
back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/