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}, a

_{1}, ... ] where all values a

_{i}are integers and where we use the following equations:

(a) α

_{0}= α

(b) a

_{k}= floor(α

_{k})

(c) α

_{k+1}= 1 / (α

_{k}- a

_{k})

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

α = α

_{0}= floor(α

_{0}) + [α

_{0}- floor(α

_{0})] =

= a

_{0}+ 1/α

_{1}

(2) Assume it is true up to [a

_{0}, ..., α

_{k}]

(3) We see that:

α

_{k}= floor(α

_{k}) + [α

_{k}- floor(α

_{k}] =

= a

_{k}+ 1/α

_{k+1}=

[ a

_{0}, ..., a

_{k}, α

_{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

a

_{0}= floor(√6) = 2.

α

_{1}= 1 / (√6 - 2) =

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

= (√6 + 2)/2

a

_{1}= 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

a

_{2}= 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 a

_{1}]

p = 2 [Size of period. The representation repeats every two items]

Example 2: √23

a

_{0}= floor(√23) = 4.

α

_{1}= 1/(√23 - 4) =

= (√23 + 4)/(23 - 16) =

= (√23 + 4)/7

a

_{1}= 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

a

_{2}= 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

a

_{3}= 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

a

_{4}= 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 a

_{1}]

p = 4 [Size of period. The representation repeats every four items]