Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-07-21 08:29:07

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
. smile

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


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#2 2009-07-21 08:37: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.

Offline

#3 2009-07-21 10:10:18

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 82,620

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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#4 2009-07-25 03:41:58

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: big_smile

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

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

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


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#5 2009-07-26 19:43:37

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 82,620

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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#6 2009-07-27 01:15:10

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Pell’s equation

Thanks. smile


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)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

#7 2009-07-27 08:21:32

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 82,620

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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

Board footer

Powered by FluxBB