Associated Topics || Dr. Math Home || Search Dr. Math

### Proof Using Pell's Equation

```
Date: 09/18/1999 at 04:49:02
From: Tran Nam Dung
Subject: Continued fractions

Solving the Pell equation x^2 - Dy^2 = 1 for different D, finding the
minimal solution (x0,y0) by using continued fractions, I determined
that if

1
Sqrt(D)= a1 + -----------------------
1
a2 + ------------------
a3 + ...
k
an + ---------
sqrt(D)+t

and

p/q = [a1;a2;...;an]

then

p^2 - D.q^2 = (-1)^n.k

instructions or some hints. Thanks a lot.

Namdung (Viet Nam)
```

```
Date: 09/18/1999 at 11:01:19
From: Doctor Anthony
Subject: Re: Continued fractions

I'll be using the notation x^2 - d.y^2 = 1  for Pell's equation.

We must show that if p/q is a convergent of the continued fraction
expansion of sqrt(d) then x = p, y = q is a solution of one of the
equations

x^2 - d.y^2 = k

where  |k| < 1 + 2.sqrt(d)

If p/q is a convergent of sqrt(d) then we have:

|sqrt(d) - p/q| < 1/q^2     (a property of convergents)

and multiplying through by q:

|p - q.sqrt(d)| < 1/q   .................................(1)

but

|p + q.sqrt(q)| =  |(p - q.sqrt(q)) + 2q.sqrt(d)|

<= |p - q.sqrt(d)| + |2q.sqrt(d)|

<  1/q + 2q.sqrt(d)
<  (1 + 2.sqrt(d))q

So
|p + q.sqrt(d)| <  (1 + 2.sqrt(d)).q  ...................(2)

Combining the inequalities (1) and (2) we get:

|p^2 - d.q^2| = |p - q.sqrt(d)|.|p + q.sqrt(d)|

< (1/q)(1 + 2.sqrt(d)).q = 1 + 2.sqrt(d)

In general not all the convergents p(n)/q(n) of sqrt(d) give solutions
to x^2 - d.y^2 = 1, but the above reasoning gives us information about
the size of the values taken on by the sequence p^2 - d.q^2.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Basic Algebra
High School Sequences, Series

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