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₀, a₁, ... ] where all values a_i are integers and where we use the following equations:
(a) α₀ = α
(b) a_k = floor(α_k)
(c) α_k+1 = 1 / (α_k - a_k)

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

α = α₀ = floor(α₀) + [α₀ - floor(α₀)] =
= a₀ + 1/α₁

(2) Assume it is true up to [a₀, ..., α_k]

(3) We see that:

α_k = floor(α_k) + [α_k - floor(α_k] =
= a_k + 1/α_k+1 =
[ a₀, ..., 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₀ = floor(√6) = 2.

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

a₁ = floor([√6 + 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₂ = floor(√6 + 2) = 4.

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

Since, this is the same as α₁ 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₁]
p = 2 [Size of period. The representation repeats every two items]

Example 2: √23

a₀ = floor(√23) = 4.

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

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

α₂ = 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₂ = floor([√23 +3]/2 ) = 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₃ = floor([√23 + 3]/7) = 1.

α₄ = 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₄ = floor(√23 + 4) = 8.

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

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

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

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