Continued Fractions

As we are all aware, there are plenty of numbers besides just the integers. Now is the time to bring this fact to the forefront. In this section, we will begin to explore the idea of continued fractions. Continue fractions are useful in many advanced areas of number theory.

Introductory Section/Basic Concepts:

First, we will begin by providing a common definition of a rational number:

Definition:
Let $\alpha$ be a real number. Then, $\alpha$ is said to be a rational number if $\alpha = \dfrac{a}{b}$, where a,b are integers and b ≠ 0. If $\alpha$, is not a rational number, then $\alpha$ is said to be an irrational number.

A couple of examples include: $\.4 = \dfrac{2}{5}$ or $1.5 = \dfrac{3}{2}$

One of the most famous proofs ever conducted was to decide if a certain number is a rational or not, which brings us to our next proposition:

Proposition: √2 is a not a rational

We will not include this proof, as we are all familiar from previous math experience (located in our text, also!).

Rational numbers also follow many properties, which are common to us through our early days in math, including these basic propositions:

Proposition:
Let $\alpha$, $\beta$ be rationals. Then, $\alpha ± \beta$, $\alpha$ß are all rational, and if $\beta\neq0$ then $\dfrac{\alpha}{\beta}$ is rational.

Next, we are going to focus on a topic that is used throughout with continued fractions, the idea that a rational number is eventually repeating/periodic:

Definition:
Let $\alpha$ be a real number with 0≤ $\alpha$<1 and let the 0.a0a1….an-1anan+1…… be a decimal representation of $\alpha$. If there exists p and N such that aN = an+p for all n≥N, then $\alpha$ is eventually periodic; The minimal p with the sequence aN-1,aN,aN+1,…….aN+(p-1) is said to be the period of $\alpha$, and p is the length of the period. And if N=1, then $\alpha$ is periodic.

Notation with a bar over the repeating part of the decimal can be used to show repetition in the decimal expansion. This is something everyone has been using since elementary school!

Again, some examples include:

$\dfrac{1}{2}$ = .500000…. with the zeros repeating and $\dfrac{2}{3}$ = .6666 with the sixes repeating.

While being able to write a number in a long decimal form seems very exciting, the more important fact is that it brings us to another important proposition:

Proposition:
Let $\alpha$ be a rational and 0 ≤ $\alpha$ < 1. Then, $\alpha$ is rational if and only if $\alpha$ is eventually periodic

Numbers like $\pi$ and e are examples of numbers that look to be never periodic and thus cannot be written as fractions, while $\dfrac{1323}{122}$ is periodic at some point since it is a fraction.

After this brief introduction to fractions, now it is time for the big idea, Continued Fractions!

We will start with an example to demonstrate:

Example:

Running the Euclidean Algorithm in Chapter 1 led us to a set of equations to find the (803,154). Rearranging some these equations gives us some curious, yet important equations:

(1)
\begin{align} 803 = 154*5 + 33 \end{equation} \begin{equation} 154 = 33*4 + 22 \end{equation} \begin{equation} 33 = 22*1 + 11 \end{equation} \begin{equation} 22 = 11*2 + 0 \end{align}

Now, if we divide each factor in each equation by the smaller of the compared numbers in the division algorithm we get some new equations, basically to find what (803/154) is:

(2)
\begin{align} \dfrac{803}{154} = 5 + \dfrac{33}{154} \end{equation} \begin{equation} \dfrac{154}{33} = 4 + \dfrac{22}{33} \end{equation} \begin{equation} \dfrac{33}{22} = 1 + \dfrac{11}{22} \end{equation} \begin{equation} \dfrac{22}{11} = 2 + 0 \end{align}

Rearranging all of these equations into our original (803/154) equation, we get that:

(3)
\begin{align} \begin{equation} \dfrac{803}{154} = 5 + \dfrac{154}{233} \end{equation} \begin{equation} = 5 + \cfrac{1}{4+\cfrac{1}{33/22}}\end{equation} \begin{equation} = 5 + \cfrac{1}{4+\cfrac{1}{1+\cfrac{1}{22/11}}} \end{equation} \begin{equation} = 5 + \cfrac{1}{4+\cfrac{1}{1+\cfrac{1}{2}}}} \end{align}

In sum, manipulation of the steps in the Euclidean Algorithm used to obtain (803, 154) allows the expression of the rational number (803/154) as a somewhat different looking fraction called a continued fraction. This example will bring us to our next definition:

An expression of the form:

$a_0 + \cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\ddots+\cfrac{\ddots}{a_{n-1}+\cfrac{1}{a_n}}}}}}$
is a finite continued fraction. And if all ai are integers, then it is a simple finite continued fraction.

Another quick example which demonstrates a similar technique is shown on page 191, example 7 of the text. As we were crunched for time, we could not include this example, however, please check that one out!

To help give notation to this idea of a continued fraction, here is a way to define a continued fraction is a condensed way:

Notation:
The representation of a continued fraction is most easily expressed by:
[a0,a1,a2,…….,an-1,an] in the continued fraction definition.

From our example: Looking at the number before the continued fraction or before the + sign on each factor, we can denote (803/154) = [5,4,1,2] = [5,4,1,1,1] (with more expansion)

Now, having a finite simple fraction is very important in deciding if a number can be expressed as a rational number. It is almost a corollary from our example, but it brings us to our next proposition:

Proposition:
Let $\alpha \in \Re$. Then, $\alpha \in Q$ if and only if $\alpha$ is expressible as a finite simple continued fraction.

Now that we know how to write continued fractions in their own notation, it is important to note that we can also go backwards from the shorthand notation back into the large fraction.

Awesome Lemma:
[ a0, ……. , an] = [ a0, …….. , an-1 + $\cfrac{1}{a_n}$].

Note that if we kept taking this back further, we would eventually reach our continued fraction's original notation.
In order to discuss the infinite continued fractions mentioned earlier, we first need to understand convergents for finite continued fractions.

Definition:
Let $\alpha$ = [a0, a1, ……. , an] be a finite continued fraction. The finite continued fraction Ci = [a0, ….. , ai], 0 $\leqq$ i $\leqq$ n, is the ith convergent of $\alpha$.

Note that since we are currently looking at finite continued fractions, then the nth convergent (Cn) of $\alpha$ is equal to $\alpha$.

Example:

Let $\alpha$ = [4, 3, 5, 1], then
C0 = [4] = 4
C1 = [4, 3] = 4 + 1/3 = 13/3
$C_2 = [4, 3, 5] = 4 + \cfrac{1}{3+\cfrac{1}{5}} = 4 + \cfrac{1}{\cfrac{16}{5}} = 4 + 5/16 = 69/16$
$C_3 = [4, 3, 5, 1] = 4 + \cfrac{1}{3 + \cfrac{1}{5 + \cfrac{1}{1}}} = 4 + \cfrac{1}{3 + \cfrac{1}{6}} = 4 + \cfrac{1}{\cfrac{19}{6}} = 4 + (6/19) = 82/19 = \alpha$

Now let's look at a critical proposition that deals further with convergents.

Proposition 7.6 (in the book):
Let $\alpha$ = [a0, …. , an] be a finite continued fraction. Define the following:
p0 = a0
p1 = a0a1 + 1
pi = aipi-1 + pi-2, 2 $\leqq$ i $\leqq$ n, pi recursive.
q0 = 1
q1 = a1
qi = aiqi-1 + qi-2, 2 $\leqq$ i $\leqq$ n, qi recursive.
Then Ci = pi/qi, 0 $\leqq$ i $\leqq$ n.

Proof (by induction): We start with two special cases.
Case 1: Let i = 0. Then $C_0 = [a_0] = \cfrac{a_0}{1} = \cfrac{p_0}{q_0}.$ Yay, we're great!
Case 2: Let i = 1. Then $C_1 = [a_0, a_1] = a_0_ + \cfrac{1}{a_1} = \cfrac{a_0a_1 + 1}{a_1} = \cfrac{p_1}{p_2}.$ Yay, we did it again!
Base Case: Let i = 2. Then $C_2 = [a_0, a_1, a_2] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2}} = a_0 + \cfrac{1}{\cfrac{a_1a_2 + 1}{a_2}} = a_0 + \cfrac{a_2}{a_1a_2 + 1} = \cfrac{a_0(a_1a_2 + 1) + a_2}{a_1a_2 + 1} = \cfrac{a_2(a_1a_2 + 1) + a_0}{a_2a_1 + a_1} = \cfrac{a_2(p_1) + p_0}{a_2(q_1) + q_0} = \cfrac{p_2}{q_2}.$ We're awesome!
Induction Case: Assume that for $i = k \in N \geqq 2$(N is the set of natural numbers), $C_k = [a_0, ...... , a_k] = \cfrac{a_kp_{k-1} + p_{k-2}}{a_kq_{k-1} + q_{k-2}} = \cfrac{p_k}{q_k}$holds.
We want to show that for i = k + 1, Ck+1 = pk+1/qk+1 holds. We'll start off using the definition of convergents: $C_{k+1} = [a_0, ...... , a_k, a_{k+1}] = [a_0, .... , a_{k-1}, a_k + \cfrac{1}{a_{k+1}}]$ by our Awesome Lemma. We can the use our assumption to say that this is equal to $\cfrac{(a_k + \cfrac{1}{a_>{k+1}})p_{k-1} + p_{k-2}}{(a_k + \cfrac{1}{a_{k+1}})q_{k-1} + q_{k-2}}} = \cfrac{(a_ka_{k+1} + 1)p_{k-1} + a_>{k+1}p_{k-2}}{\cfrac{a_{k+1}}{\cfrac{(a_ka_{k+1}+ 1)q_{k-1} + a_{k+1}q_{k-2}}}{a_{k+1}}}} = \cfrac{a_ka_{k+1}p_{k-1} + p_{k-1} + a_{k+1}p_{k-2}}{a_ka_{k+1}q_{k-1} + q_{k-1} + a_{k+1}q_{k-2}} = \cfrac{a_{k+1}(a_kp_{k-1} + p_{k-2}) + p_{k-1}}{a_{k+1}(a_kq_{k-1} + q_{k-2}) + q_{k-1}},$
by definition of our recursive formulas, this is equal to $\cfrac{a_{k+1}p_k + p_{k-1}}{a_{k+1}q_k + q_{k-1}} = \cfrac{p_{k+1}}{q_{k+1}}$ by definition of our recursive formulas again. Thus, we have proved that $C_i = \cfrac{p_i}{q_i}, 0 \leqq i \leqq n.$ $\blacksquare$

Example:

Going back to our previous example where $\alpha$ = [4, 3, 5, 1], we now have that
p0 = 4
p1 = 4x3 + 1 = 13
q0 = 1
q1 = 3
Then:
$C_0 = \cfrac{p_0}{q_0} = \cfrac{4}{1} = 4$
$C_1 = \cfrac{p_1}{q_1} = \cfrac{13}{3}$
$C_2 = \cfrac{p_2}{q_2} = \cfrac{a_2p_1 + p_0}{a_2q_1 + q_0} = \cfrac{5\times13 + 4}{5\times3 + 1} = \cfrac{69}{16}$
$C_3 = \cfrac{p_3}{q_3} = \cfrac{a_3p_2 + p_1}{a_3q_2 + q_1} = \cfrac{1\times69 + 13}{1\times16 + 3} = \cfrac{82}{19}$
Which are the same solutions that we found using our earlier method.

Looking back at the examples, there are probably a couple of interesting results that you may notice. For instance, all the convergents come out in lowest terms, the convergents are rational numbers, and the convergents get closer and closer to our $\alpha$. We can now state some those results more formally in the following corollary/proposition.

Corollary 7.9/Proposition 7.10:
Let $\alpha$ = [a0, … , an] be a finite simple continued fraction and let notation be as in proposition 7.6. Then

1.) $C_i – C_{i-1} = \cfrac{(-1)^{i-1}}{q_iq_{i-1}} , 1 \leqq i \leqq n,$ and $C_i – C_{i-2} = \cfrac{(-1)^{i}(a_i)}{q_iq_{i-2}}, 2 \leqq i \leqq n.$
2.) C0 < C2 < C4 < …. < Cn < …. < C5 < C3 < C1.

While these two results may look intimidating, what they’re basically telling us is that the convergents keep bouncing back and forth around $\alpha$, getting closer and closer. Since we are considering finite continued fractions, the convergents will eventually reach Cn, but if we let n go to infinity, then we will just keep oscillating back and forth, getting closer, and closer, and closer….

Infinite Continued Fractions:

Proposition
Let a0,a1,a2,… $\in$$\mathcal{Z}$ with a1,a2,a3…>0 and let Ci=[a0,a1,a2,…,ai], i$\geq$0. Then:
limx$\rightarrow$$\infty$Ci
exists. The value of this limit is said to be the value of the infinite simple continued fraction [a0,a1,a2,…]; Ci is called the ith convergent of the infinite simple continued fraction.

Proof – Book page 203

Example
Analyze [1,1,1,…] and attempt to solve it
Write out:
$[1,1,1,…]=\alpha=1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{\ddots}}}}$
Notice
$\alpha=1+\frac{1}{\alpha}$
Solve this and you get
$\alpha^2-\alpha-1=0$
$\alpha=\frac{1\pm\sqrt{5}}{2}$, notice $\alpha>0$, this implies $\alpha=\frac{1+\sqrt{5}}{2}=\varphi$, which is the golden ratio

Proposition (existence and uniqueness)
Let $\alpha\in\mathcal{R}$. Then $\alpha\in\mathcal{R}-\mathcal{Q}$ if and only if $\alpha$ is uniquely expressible as an infinite simple continued fraction

Proof – Book Pages 204-207

Proposition
Let $\alpha\in\mathcal{R}-\mathcal{Q}$ and let $C_i=\frac{p_i}{q_i}$, i=0,1,2,…, be the convergents of the infinite simple continued fraction expansion of $\alpha$. If $a,b\in\mathcal{Z}$ and 0<b<qi+1, then
|qi$\alpha$-pi|$\geq$|b$\alpha$-a|

Proof – Book page 209-210

Corollary
Let $\alpha\in\mathcal{R}-\mathcal{Q}$ and let $C_i=\frac{p_i}{q_i}$, i=0,1,2,…, be the convergents of the infinite simple continued fraction expansion of $\alpha$. If a,b$\in\mathcal{Z}$ and 1$\leq$b$\leq$qi, then
|$\alpha-\frac{p_i}{q_i}$|$\leq$|$\alpha-\frac{a}{b}$|

Proof – Assume, by way of contradiction, that |$\alpha-\frac{p_i}{q_i}$|>|$\alpha-\frac{a}{b}$|. Then
|qi$\alpha$-pi|=qi|$\alpha-\frac{p_i}{q_i}$|>b|$\alpha-\frac{a}{b}$|=|$\alpha$b-a|
which contradicts the above proposition.

This Corollary is very important because it says that the ith convergent of the infinite simple continued fraction is the best estimate of the fraction within all estimates with less than or equal to denominators.

Proposition
Let $a,b\in\mathcal{Z}$ with (a,b)=1 and b>0. If $\alpha$ is an irrational number and |$\alpha-\frac{a}{b}$|<$\frac{1}{2b^2}$, then $\frac{a}{b}$ is a convergent of the infinite simple continued fraction expansion of $\alpha$.

Proof – Book Page 211

Eventually Periodic Continued Fractions

Definition
Let $\alpha\in\mathcal{R}-\mathcal{Q}$. Then $\alpha$ is said to be a quadratic irrational number if $\alpha$ is a root of a (quadratic) polynomial $Ax^2+Bx+C$ with $A,B,C\in\mathcal{Z}$ and A$\neq$0.

Definition
Let $\alpha$ be an eventually periodic continued infinite fraction if $\alpha$ is expressible as [a0,a1,…,an,b0,b1,…,bm,b0,b1,…], where a0,a1,…,an,b0,b1,…,bm$\in\mathcal{Z}$ and a1,a2,…,an,b0,b1,…,bm>0, which is written as [a0,a1,…,an,$\overline{b_0,b_1,...,b_m}$]

Theorem
Let $\alpha\in\mathcal{R}-\mathcal{Q}$. Then the expression of $\alpha$ as an infinite simple continued fraction is eventually periodic if and only if $\alpha$ is a quadratic irrational number.

Proof – Book Pages 219-221

Example

Find the quadratic irrational number represented by the eventually periodic infinite simple continued fraction $[3,\overline{2,1}]$:
First find the quadratic irrational number represented by the periodic infinite simple continued fraction $\alpha=[\overline{2,1}]$. Note that we have
$\alpha=[2,1,\overline{2,1}]=[2,1,\alpha]$
so that
$\alpha=2+\cfrac{1}{1+\cfrac{1}{\alpha}}$
Simplifying the equation above, we obtain $\alpha^2-2\alpha-2=0$, from which, by the quadratic formula, we have $\alpha=[\overline{2,1}]=1+\sqrt{3}$. (The negative root $1-\sqrt{3}$ is rejected since $\alpha$>0.) So
$\alpha=[\overline{2,1}]=1+\sqrt{3}$
Now
$[3,\overline{2,1}]=[3,\alpha]$
=[3,1+$\sqrt{3}$]
=3+$\frac{1}{1+\sqrt{3}}$
=$\frac{4+\sqrt{3}}{1+\sqrt{3}}$
=$\frac{5+\sqrt{3}}{2}$
and hence $[3,\overline{2,1}]=\frac{5+\sqrt{3}}{2}$.

Example

Find the infinite simple continued fraction expansion of $\sqrt{2}$
$\alpha=\alpha_0=\sqrt{2}=1.41421…$
$a_0=\lfloor\alpha_0\rfloor=1$ $\alpha_1=\frac{1}{\alpha_0-a_0}=2.41421…$
$a_1=\lfloor\alpha_1\rfloor=2$ $\alpha_2=\frac{1}{\alpha_1-a_1}=2.41421…$
$a_2=\lfloor\alpha_2\rfloor=2$ $\alpha_3=\frac{1}{\alpha_2-a_2}=2.41421…$
$\vdots$

$\Rightarrow\sqrt{2}=[1,2,2,…]=[1,\overline{2,2}]$

Bibliography: Strayer, James K. Elementary Number Theory. Long Grove, IL: Waveland Press, Inc, 2002.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License