Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ų ◊ Ĺ √ ∞ ≠ ≤ ≥ ≈ ⇒ Ī ∈ Δ θ ∴ ∑ ∫ ē π É -Ļ ≤ ≥ į

Login

Username

Password

Not registered yet?

#1 2009-07-22 06:29:07

JaneFairfax
Legendary Member

Offline

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



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-22 08:13:27)


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

A: Click here for answer.
 

#2 2009-07-22 06:37:27

mathsyperson
Moderator

Offline

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.
 

#3 2009-07-22 08:10:18

bobbym
Administrator

Offline

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-26 03: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.
 

#4 2009-07-26 01:41:58

JaneFairfax
Legendary Member

Offline

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-26 01:52:58)


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

A: Click here for answer.
 

#5 2009-07-27 17:43:37

bobbym
Administrator

Offline

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-27 18: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.
 

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

JaneFairfax
Legendary Member

Offline

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 23:15:41)


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

A: Click here for answer.
 

#7 2009-07-28 06:21:32

bobbym
Administrator

Offline

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-28 06: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.
 

Board footer

Powered by FluxBB