The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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.

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   

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 

Best regards,
- Doctor Floor, The Math Forum   
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.