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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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

Today, I read about Pells 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 Pells equation (called the trivial solutions). It can be proved that Pells 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)*

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,389

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.****No great discovery was ever made without a bold guess. **

Offline

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

Here is an application of Pells 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)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,389

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.****No great discovery was ever made without a bold guess. **

Offline

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

Thanks.

Rose (

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)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,389

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.****No great discovery was ever made without a bold guess. **

Offline

Pages: **1**