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: 86,260

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#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: 86,260

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#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: 86,260

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

Board footer

Powered by FluxBB