Saturday, December 31, 2005

Continued Fractions: Method for determining [ a0, a1, ... ]

Today's blog continues the discussion on Pell's Equation. For those interested in the background of this problem, start here. For those interested in understanding how this relates to Fermat's Last Theorem, start here.

In a previous blog, I explained how continued fractions can be used to solve Pell's Equation. In today's blog, I will go into more detail about a method for determining the representation of a continued fraction. This method is assumed in the solution to Pell's Equation which is found here.

Today's blog is based on the Jody Esmonde and M. Ram Murty's Problems in Algebraic Number Theory.

Theorem: For any irrational number α, it is possible to represent it in the form
[ a
0, a1, ... ] where all values ai are integers and where we use the following equations:
(a) α0 = α
(b) ak = floor(αk)
(c) αk+1 = 1 / (αk - ak)

(1) First, I show this is true for the case k = 0.

α = α0 = floor(α0) + [α0 - floor(α0)] =
= a0 + 1/α1

(2) Assume it is true up to [a0, ..., αk]

(3) We see that:

αk = floor(αk) + [αk - floor(αk] =
= ak + 1/αk+1 =
[ a0, ..., ak, αk+1]

(4) By the Principle of Induction (see here), we are done.

QED

To show how this method can be used, let's apply it some examples:

Example 1: √6

a0 = floor(√6) = 2.

α1 = 1 / (√6 - 2) =
= (√6 + 2)/(6 - 4) =
= (√6 + 2)/2

a1 = floor([√6 + 2]/2) = 2

α2 = 1/[(√6 + 2)/2 - 2] =
= 1/[(√6 + 2 - 4)/2] =
= 1/[(√6 - 2)/2] =
= 2/(√6 - 2) =
= 2(√6 + 2)/(6 - 4) = 2(√6 + 2)/2 =
= 6 + 2

a2 = floor(√6 + 2) = 4.

α3 = 1/(√6 + 2 - 4) =
= 1/(√6 - 2) =
= (√6 + 2)/2

Since, this is the same as α1 so we have reached a repetition and we are done.

6 = [ 2, 2, 4 ]

We note that:
n = 1 [Position where repetition begins is a1]
p = 2 [Size of period. The representation repeats every two items]

Example 2: √23

a0 = floor(√23) = 4.

α1 = 1/(√23 - 4) =
= (√23 + 4)/(23 - 16) =
= (√23 + 4)/7

a1 = floor([√23 + 4]/7) = 1

α2 = 1/[ (√23 + 4)/7 - 1] =
= 1/[(√23 + 4 - 7)/7] = 1/[(√23 -3)/7] = 7/(√23 -3) =
= 7(√23 +3)/(23 - 9) = 7(√23 +3)/14 = (√23 +3)/2

a2 = floor([√23 +3]/2 ) = 3.

α3 = 1/[(√23 +3)/2 - 3] = 1/[(√23 +3 - 6)/2 ] = 1/[(√23 - 3)/2 ] =
= 2/(√23 - 3) = 2(√23 + 3)/(23 - 9) =
= (√23 + 3)/7

a3 = floor([√23 + 3]/7) = 1.

α4 = 1/[(√23 + 3)/7 - 1] = 1/[(√23 + 3 - 7)/7 ] =
= 1/[(√23 - 4)/7 ] = 7/(√23 - 4) = 7(√23 + 4)/(23-16) =
= 23 + 4

a4 = floor(√23 + 4) = 8.

α5 = 1/(√23 + 4 - 8) = 1/(√23 - 4)

This turns out to be the same value as α1 so we are done.

23 = [ 4, 1, 3, 1, 8 ]

We note that:
n = 1 [Position where repetition begins is a1]
p = 4 [Size of period. The representation repeats every four items]

5 comments:

JFlanigan said...

Am I correct in concluding that there are no irrational numbers? The concept of irrational numbers arose only because of a limitation in notation?

Larry Freeman said...

There are still irrational numbers. Continued fractions give us more tools for representing irrational numbers but they do not deny their existence.

Even without continued fractions, it is possible to represent an irrational number using a notation such as sqrt(2) but this doesn't change the fact that sqrt(2) can't be represented as a ratio of two integers.

Irrational numbers exist because of their definition. So long as there are values that cannot be represented as a ratio of two integers, there are irrational numbers.

-Larry

Scouse Rob said...

Typo in step (3) of the first theorem:

αk = floor(αk) + [αk - floor(αk]

should be:

αk = floor(αk) + [αk - floor(αk)]

Rob

Scouse Rob said...

Continued Fractions make my head hurt.

In the first theorem:

Is:

a0+1/α1=[a1,α1]?

And in step (3) of the first theorem is it not:

[a0, ..., αk]=[a0, ...,ak,αk+1]

Instead of αk=[a0, ...,ak,αk+1]?

Thanks in advance for your help.

Rob

Jiasheng said...

thanks alot for this
but it can be explained more precisely