 • ### What is a continued fraction?

To introduce this web site, the most appropriate place to start is with a definition of a continued fraction. A continued fraction refers to all expressions of the form where a1,a2,a3,.... and b1,b2,b3,... are either real or complex values. The number of terms can be either finite or infinite.

• ### What can I find at this site on continued fractions?

Let me answer this question by first explaining what you will not find at this site. You will not find any deep analysis of continued fractions. For those of you researching this area, I direct your attention to the resources.

Even though this site does not go into great analysis of continued fractions, it does cover some of the basic theorems of the field. For those of you who are "math-phobic," now would probably be a good time to leave.

When I created this site, my intention was to provide a brief introduction to this fascinating area of mathematics. I have aimed this presentation at those at my own level, that is, those at an undergraduate level with an interest in mathematics. For many, this may be a first introduction to continued fractions since this subject, if it is taught at all, is restricted to a single chapter in a number theory text. Hopefully this site will inspire others to study continued fractions in greater detail.

I have broken this site into four main pieces. In the first section, which is found below, I present some of the basic theorems about simple continued fractions. In the second, History, I have sketched out the past . In the third, Applications, I will allow the user to calculate continued fractions. I have created a number of interactive programs that convert rationals (or quadratic irrationals) into a simple continued fraction, as well as the converse. In the final section, resources, I have attempted to list some of the major works on continued fractions. I have also tried to find all the references to continued fraction on the World Wide Web.

• ### Some Basic Theory of Continued Fractions

In this section, I have provided some definitions that deal with continued fractions. After this, one will find a number of a theorems, complete with proofs, that deal with continued fractions.

For optimal viewing of this page, please use a browser that supports subscripts and superscripts, for example, Netscape 2.0 or larger, or Microsoft Explorer.

## Definitions

### Definition 1

An expression of the form is said to be a continued fraction. The values of a1, a2, a3,... and b1 , b2, b3,... can be either real or complex values. There can be either an infinite or a finite number of terms. A continued fraction can be created from any number alpha by using the following recursive algorithm.  where alpha1 = alpha. The sequence of ai's are the terms of the continued fraction.

### Definition 2

A simple continued fraction is a continued fraction in which the value of bn = 1 for all n. The value of an is a postive integer for all n > = 1. a1 can be any integer value, including 0. The above fraction is sometimes represented by
[a1; a2, a3,...]

### Definition 3

The terms of a simple continued fraction refer to the values of a1, a2, a3 ,.... For example, a4 is the fourth term. Also referred to as partial quotients.

### Definition 4 - 5

A finite simple continued fraction is a simple continued fraction with only a finite number of terms. An infinite simple continued fraction is a simple continued fraction with an infinite number of terms.

### Definition 6

The continued fraction [a1; a2, a3,...., ak] where k is a non-negative integer less than or equal to n is called the kth convergent of the continued fraction [a1; a2, a3,..., an]. The kth convergent is denoted by Ck. For example,

C1 = 1
C2 = 3/2
C3 = 10/7
are the three convergents of the continued fraction ### Definition 7

A quadratic irrational refers to all numbers of the form where A, B, and C, are integers. They are called quadratic irrationals since they are the roots of quadratic equations, specifically ### Definition 8

The Euclidean algorithm is a recursive function that enables one to find the greatest common denominator (gcd) of two integers a and b. Given integers a and b, we can find q1 and r1 such that
```b = a q1 + r1,   0 =< r1 < |a|
```

We can now do the same for the two numbers (a, r1) to get
```a = r1q2 + r2, 0 =< r2 < |r1|
```

We continue the sequence. Eventually, the remainder must converge to zero. The last two terms of the sequence are
```rn-2 = rn-1qn + rn

rn-1 = rnqn+1
```

The value rn can be shown to be the gcd of a and b.

### Definition 9

An indeterminate equation is an equation that cannot be directly solved from the given information. For example, the equations
a*x + b*y = c
x2 - P * y2 = 1

where a, b, c, and P are given integers (P is square free, that is, it is not 1, 4, 9, 16, and so on), are indeterminate equations. In general, we are interested in finding integer solutions to these equations. Equations of the first form are called Diophantine equations. Those of the second form are named Pell's equations.

### Definition 10

The infinite simple continued fraction [a1; a2, a3,....] is said to be periodic if there are postive integers N and k such that for all n >= N, an = an+k. We represent this continued fraction by the more effecient notation ## Theorems

### Theorem 1

A number is rational if and only if it can expressed as a simple finite continued fraction

PROOF: Let n be a rational number. Then p/q for some integers p and q. Suppose also that p and q are in lowest terms. To prove the statement, we make use of Euclid's Algorithm. By applying this algorithm, we can write

p = a1q + r1, 0 <= r1 < q,

q = a2r1 + r2, 0 <= r2 < r1,

r1 = a3r2 + r3, 0 <= r3 < r2,

:
:
rn-3 = an-1rn-2 + rn-1, 0 <= rn-1 < rn-2,

rn-2 = anrn-1.

The sequence r1, r2, r3,..., rn-1 forms a strictly decseasing sequence of non-negative integers that must converge to zero in a finite number of steps. So, there are at most n ai's.

The next step involves rearranging the algorithm in the following manner. Now, sustituting each equation into the previous, we find that which is a finite simple continued fraction, as desired.

To show the converse, we prove by induction that if a simple continued fraction has n terms, it is rational. Let X represent the value of the continued fraction. We first check the base case n = 1. Then

X = a1
But then X is clearly a rational, since a1 is an integer.

We now prove the inductive case. Assume the theorem is true for all i <= n. We now show that the theorem also holds for n+1. Let X be a continued fraction that is represented by n+1 terms. We wish to show that X is rational. So, we have Note, however, that we can rewrite this expression as where B is the continued fraction But B is a continued fraction with n terms, and by our induction hypothesis, it can be written as a rational p/q. This implies that By applying some simple algebra, we arrive at the following equality Since a1, as well as p and q, is an integer, X must be a rational. Thus, the theorem is true for n+1, and by induction, it must hold for all integers.

### Theorem 2

Given a continued fraction with the terms, [a1; a2, a3,..., an-1, an], the numerator pi and denominator qi of the ith convergent are definied for all i >= 0 by the recursive definition

pi = aipi-1 + pi-2

qi = aiqi-1 + qi-2

where p-1 = 0, p0 = 1, q-1 = 1, and q0 = 1.

PROOF: We will prove this statement by using induction. Let the continued fraction [a1; a2, a3, .... an] be given. We need to first check the two base cases. Both cases agree with the definition. We now assume that the statement is true for all i <= k. We wish to show that the statement is true for k+1. By definition, We can rewrite this fraction in the following manner The continued fraction now has k terms, and by hypothesis The last step made use of the induction hypothesis for the subtitution. The theorem is thus true for k+1, and by induction, must hold for all integers.

### Theorem 3

If pk and qk are defined as in the above theorem, then

pkqk-1 - pk-1qk = (-1)k

for all i >= 0.

To prove this, we will once again do a proof by induction We first check the two base cases, that is, for i=1 and i=2. Now we show that the above theorem holds for all k. Assume it holds for all i <= k, We want to show that the statement is true for k+1. Since the statement is true for k+1, by induction, the theorem holds for all integers k.

### THEOREM 4

If X is an irrational number, then its simple continued fraction expansion is infinite.

PROOF: Let X be an irrational number, and suppose that its simple continued fraction is finite. Then the simple continued fraction has n terms where n is a postive integer. But by Theorem 1, the value of any continued fraction with a finite number of terms must be rational. Hence the continued fraction is equivalent to a rational, and thus, it cannot be equivalent to X. This provides us with the neccesary contradiction

|Main |Introduction |History |Applications |Resources |Credits