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]