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.

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search