Math Is Fun Forum

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Pell’s equation

Today, I read about Pell’s equation in the chapter on continued fractions of A Course in Number Theory by H.E. Rose. This is a Diophantine equation of the form

[align=center]

[/align]

where

and

is a fixed positive integer which is not a perfect square.

Note that

are always solutions to any Pell’s equation (called the trivial solutions). It can be proved that Pell’s equation always has a nontrivial solution (i.e. for which

) for all positive nonsquare integers

.

Last edited by JaneFairfax (2009-07-21 10:13:27)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Pell’s equation

Is there an easy way of finding the non-trivial solutions?
Can continued fractions help somehow?

---

Why did the vector cross the road?
It wanted to be normal.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pell’s equation

Hi mathsyperson and Jane;

Continued fractions are used to calculate the smallest solution.
For instance to solve:

You start by computing the continued fraction of √14

The sequence is periodic with length 4 (1,2,1,6...) The nice part is that a theorem by
Lagrange assures us that every square root like this will always have a repeating
form.

Compute the convergents of the √14. These are done by 2 recurence formulae or matrix multiplication

You pick the 4th one in the sequence 15/4 and that is the smallest non trivial answer.

This example is simple enough to get using this theorem. For any positive integer d, if d+2 is a perfect square,
then d+1 is the first solution to Pell's Equation for x. I haven't seen a proof to this, just some web page.

For harold the saxon problem:

Compute the continued fraction of √61

The sequence is periodic with length 11 (1,4,3,1,2,2,1,3,4,1,14...)

Compute the convergents of the continued fraction:

So we pick the 11 term which is 29718/3805 but

which is incorrect. So we try the next 11th (22nd term) term which is

So this is the smallest solution that is not trivial.

Here is a page to solve these and many tougher types of diophantine equtions.
http://www.alpertron.com.ar/QUAD.HTM

Here are other methods: This one uses matrices, it like the continued fraction approach is excellent for computers.
http://fermatslasttheorem.blogspot.com/ … ution.html

The most famous pell equation is the cattle of the sun.

Last edited by bobbym (2009-07-25 05:24:11)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Pell’s equation

Here is an application of Pell’s equation in solving a number-theory problem:

http://www.artofproblemsolving.com/Foru … p?t=208906

itiselizabeth also shows how to calculate the first few convergents in the continued-fraction expansion of √47.

Last edited by JaneFairfax (2009-07-25 03:52:58)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pell’s equation

Hi Jane;

Here's how to use continued fractions to get the best rational approximations to the
roots of a quadratic.

one of the roots is phi ≈ 1.61803...

Now just replace the x in the fraction with the entire statement with 1).

Now again, replace x with 1).

Again.

You can truncate this at anytime to get the approximation.

And their is an algorithm for higher order polys too.

Last edited by bobbym (2009-07-26 20:08:34)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Pell’s equation

Thanks.

Rose (A Course in Number Theory) mentions various approximation techniques using continued fractions;
for example, one method shows that

is the first “best” appproximation to π. The next best approximation is

Last edited by JaneFairfax (2009-07-27 01:15:41)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pell’s equation

Hi Jane;

Great that you are posting what you are learning. Haven't done any CF's in 10 years. My favorite convergent to π is the one after 355/113, it gives 10 correct digits:

Last edited by bobbym (2009-07-27 08:22:22)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.