If r is a real number, there are many sequences of rational numbers that approach r. One sequence is defined implicitly by the decimal expansion of r. For example, π is approached by the sequence {3, 3.1, 3.14, 3.141, 3.1415, …}, but other sequences will do just as well. Students of calculus might multiply the following series by 4 to get π.
1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + …
The continued fractions form a particular sequence of rational numbers that approach r. The terms of the sequence are constructed recursively; then one must prove that the sequence converges to r.
Continued fractions have some nice properties that prove useful in other areas of mathematics. For example, continued fractions can be used to describe the fundamental unit in a real quadratic number field. Perhaps we can explore some of these relationships, but first let's define the continued fractions for r.
A sequence of continued fractions contains the same information as a related sequence of positive integers. We will develop these two sequences in parallel. In the following, an is an integer, and cn (the corresponding continued fraction) is a rational number. Let's get started with a real number r.
Let a0 be the greatest integer ≤ r, and let c0 = a0. Let e0 = r-a0, the error in selecting a0. By the selection of a0, 0 ≤ e0 < 1, and the first inequality is strict if r is not itself an integer.
Once a1 is selected, c1 will equal a0 + 1/a1. Let a1 be as large as it can be, such that c1 is not less than r. In other words, c1 overestimates r, just as c0 underestimates r.
c0 + 1/a1 ≥ r
1/a1 ≥ r - c0
1/a1 ≥ e0
a1 ≤ 1/e0
As shown above, a1 = floor(1/e0). With e0 bounded below 1, a1 is at least 1. Let e1 be the remainder, the error, when selecting a1. In other words, e1 = 1/e0 - a1. This is another number in [0,1), and strictly greater than 0 unless r = c1.
Use a2 to "adjust" a1. Specifically, the reciprocal of a2 is added to a1, just as the reciprocal of a1 was added to a0. Thus c2 = a0 + 1/(a1 + 1/a2).
a1 + 1/a2 ≥ 1/e0
1/a2 ≥ 1/e0 - a1
1/a2 ≥ e1
a2 ≤ 1/e1
Set e2 = 1/e1 - a2. Find a3 = floor(1/e2), and so on. These definitions continue forever; with an = floor(1/en-1), and en = 1/en-1 - an. Then cn is the compound fraction built from the integers a0 through an.
Notice the alternation. To start, c0 ≤ r, then c1 ≥ r, then c2 ≤ r, and so on. Prove this by induction on the number of terms in the continued fraction. One term, e.g. c0, is shy of the real number it approximates. The rational number that begins with a1 approximates 1/e0, and by induction it is shy of 1/e0, or exceeds 1/e0, as the number of terms is odd or even respectively. This is in the denominator, hence it exceeds e0, or is shy of e0, as the number of terms is odd or even respectively. Add this to a0, one more term, and cn exceeds r, or is shy of r, as n is even or odd respectively.
Let's see what happens when r is a rational number p/q. (Note that p and q need not be prime; they're just integers representing numerator and denominator.) If r is negative let p be the negative integer.
To begin, a0 is the integer quotient p/q. Remember, you want the greatest integer in p/q, even if p is negative. Once a0 is set, e0 is the remainder (when p is divided by q), over q. At this point both numerator and denominator are positive.
To take the next step, take the reciprocal of the aforementioned fraction e0, let a1 be the quotient, and let e1 be the remainder, over the denominator. Continue this process and you are running the gcd algorithm. The sequence ai holds the quotients along the way. Recall that we used these quotients when writing the gcd as a linear combination of p and q. When en = 0 the process stops. You can consider the sequence of continued fractions as finite, or you can extend the sequence by repeating cn forever. It's a matter of taste. I will call the sequence finite.
But is cn really equal to r? It is if r is an integer. Proceed by induction on n. The continued fraction that begins with a1, running through an, is equal to the rational number that created it, namely 1/e0. Its reciprocal is e0. Add a0 to this to get cn, which is equal to r. The map from rationals to finite sequences, and back to rationals, is faithful. The same value of r appears.
Note that a finite sequence so produced has each ai positive, except perhaps for a0. Also, the last an, beyond a0, cannot be 1. This would make 1/en-1 equal to 1, whence en-1 = 1, and we should have incremented an-1.
Now we're ready for the converse. Start with any finite sequence of integers a0 through an, such that a1 through an are positive, and an (for n > 0) is not 1. Build the corresponding continued fraction cn and call it r. r creates a finite sequence of integers, but does it create this particular sequence? It does if n = 0. For larger n, the sequence beginning with a1 builds a real number greater than 1, that I will call 1/e0, which, by induction, yields the sequence starting with a1. Now cn = a0+e0. Since e0 < 1, unraveling cn yields a0, with remainder e0, and the rest of the sequence starting at a1 is produced from there. That completes the inductive step. Rational numbers and finite sequences of integers constrained as above correspond. Unravel r to obtain the sequence a0 through an, and build cn to get r back again.
Now for some irrational numbers. Let's look at r = π, just for grins.
Clearly c0 = a0 = 3, the greatest integer in π.
We can add 1/7 to this and still be greater than π, while 3.125 is smaller, hence a1 = 7, and c1 is the familiar 22/7.
Now it's time to tweak 7 by a reciprocal. Add 1/15 to 7, and we are still smaller than π. This is the best we can do, hence a2 = 15, and c2 = 333/106.
If you take the next step, a3 = 1, and c3 = 355/113. You can continue this as long as you like.
Here is a sequence that approaches the golden ratio φ. Consider the continued fraction where each integer element ai is set equal to 1, except for a0, which is set to 0. Verify that the first few continued fractions, starting with c0, are as follows:
0, 1, 1/2, 2/3, 3/5, 5/8, 8/13, 13/21, …
Look at the numerators and you may recognize the fibonacci sequence. The denominators run the same sequence shifted by 1. Therefore cn = fib(n)/fib(n+1). As described on the aforementioned page, the fibonacci sequence is exponential. Specifically, fib(n) approaches φn/sqrt(5), where φ is the golden ratio, approximately 1.618034. The quotient φn/φn+1 approaches 1/φ. We have built a continued fraction that approaches a real number, namely 1/φ, which is the same as φ-1, approximately 0.618034.
Change a0 to 1 in the above, so that each ai = 1, and cn approaches φ-1+1, or φ. This is a continued fraction that approaches the golden ratio. We will use this result to prove convergence in general.
Start with a finite sequence of positive integers from am to an. This builds a slice of the continued fraction. If m = n the sequence has length 1, and the contribution is 1/am. For longer sequences, am is modified by something positive, and the result will be something smaller than 1/am. Since am is at least 1, the resulting slice lies in the range (0,1].
Consider the difference between cm and cn. When am is increased, 1/am is decreased. The two quantities are inversely related. Similarly, am-1+1/am changes inversely with the change in am. Take the reciprocal and find an expression that changes directly with am. Add am-2 and find an expression that changes directly with am. Take the reciprocal and find an expression that changes inversely with am. By induction, the difference between cm and cn is maximized when am is changed as much as possible. As shown above, the change is at most 1. Thus it is enough to ask how cm changes as am advances by 1.
The greatest change in 1/am, and in cm, occurs when am moves from 1 to 2. Thus it is enough to ask how cm changes as am advances from 1 to 2. In other words, let am = 1.
As am moves from 1 to 2, the next compound fraction moves from 1/(am-1+1) to 1/(am-1+½). The greater this change, the greater the change in cm. This is maximized when am-1 = 1.
Continue the above all the way back to a1. In each case the difference is maximized when ai = 1. Therefore the difference between cm and cn is bounded by the difference, as am moves from 1 to 2, of a canonical continued fraction whose integer elements are all equal to 1. This continued fraction was described above. Set a0 = 0, for convenience, and cm = fib(m)/fib(m+1). Push am up to 2 and find fib(m+1)/fib(m+2). These quotients approach 1/φ for large m. Therefore, for any ε, there is some m, such that fib(m)/fib(m+1) and fib(m+1)/fib(m+2) are within ε of each other. This constrains the difference between cm and cn, for all n beyond m, and that is exactly the criteria we need to show the sequence of continued fractions is cauchy. It therefore converges to a real number r.
In summary, every sequence of continued fractions, built from a sequence of integers (positive beyond a0), approaches a real number. We have established a map from infinite sequences of integers into the reals. Conversely, each real number leads to a sequence of integers and a sequence of continued fractions, as described earlier. Are these maps faithful inverses of each other? They are, and we'll prove it, but first we need to get a handle on the denominators of cn.
Look at the denominators of cn. The fraction 1/an is in lowest terms. Add another integer, namely an-1, and the sum is an improper fraction in lowest terms with the same denominator an. Take the reciprocal and find a proper fraction in lowest terms. Add an-2 and find another improper fraction in lowest terms, using the same denominator. Continue this process until cn is written as an improper fraction in lowest terms.
Remember that each ai is positive, except perhaps a0. Increase any ai (for i > 0), and the fraction produced by bringing in ai becomes larger. Specifically, the numerator is larger. When flipped, the denominator is larger, which makes the next numerator larger, and so on. All the numerators and denominators are larger from that point on, and cn has a larger denominator. Therefore the smallest possible denominator for cn occurs when each ai, from a1 to an, equals 1.
We have already discussed this continued fraction. The denominator of cn is fib(n+1), which is (for all practical purposes) φn+1/sqrt(5). I'll call this 0.72 times φn. This result will come in handy later on.
Let cn be the continued fraction derived from r, and tie |r-cn| to these ever increasing denominators. If the denominator of cn is t, r will be within 1/t2 of cn. This will prove c converges back to r.
We will actually prove something stronger, the difference between cn and cn seeded by an+1 is bounded by 1/(t2+t). Remember that an was chosen so that an, and an+1, in this position, create rational numbers that bracket r. r fits within these two continued fractions, and 1/t2 > 1/(t2+t), so this ties r to cn, and as n approaches infinity t grows exponentially, hence cn converges to r.
Note that a0 never really enters into the picture. We could subtract a0 from r, and from the continued fractions of r - whence the difference between r and any cn, or the difference between cn and cnadjusted by an+1, does not change. Therefore it is sufficient to prove this theorem for r between 0 and 1. As a matter of convenience, let a0 = 0.
Start with c1. The two fractions that bracket r are 1/a1 and 1/(a1+1). The difference is 1 over a1×(a1+1), and since a1 stands in for t at this point, this is precisely the expression we are looking for.
The inductive assumption is that cn-1 is close to the same continued fraction when an-1 is incremented, according to the denominator of cn-1. This holds for every continued fraction out to length n-1. Fix an r between 0 and 1 and spin off the continued fractions out to cn. Let the continued fraction from a1 out to an equal s/t. With a0 = 0, cn = t/s. Adjust an by 1 and adjust s/t by at most 1/(t2+t). Get a common denominator and write this as (st+s±1)/(t2+t). Take the reciprocal and subtract t/s, giving t/(s×(st+s±1)).
Since a1 is nonzero, the numerator of the improper fraction seeded by a1 is strictly larger than the denominator. In other words, s > t. Replace s±1 with t, which can only make the denominator smaller and the fraction larger. The expression simplifies to 1/(s×(s+1)), and that completes the proof.
In summary, continued fractions that are "adjacent" are within 1/t2 of each other, and within 1/t2 of r. Since denominators increase quickly, the continued fractions of r approach r. For any real number, r spins off a sequence of continued fractions, that converges to r. The sequence is finite iff r is rational.
Now for the converse. Start with a sequence of positive integers ai, and build the continued fractions ci. This is cauchy and converges to some real number r. Does r spin off the same sequence ai? Suppose r creates another sequence of continued fractions d0 d1 d2 d3 etc, based on the integers b0 b1 b2 b3 etc, such that an ≠ bn and n is minimal. Since d is created from r, d converges to r. Thus c and d both converge to r. Assume r is irrational, hence d is also an infinite sequence.
Suppose n > 0, hence a0 = b0. Pull a0 down to 0. This subtracts a0 from r, leaving another irrational number. It also subtracts a0 from each ci and each di. Both series still converge to the new r. Take the reciprocal of r, and of each ci and di beyond i = 0. These are the continued fractions beginning with a1 and b1. Repeat the above process all the way down to n. Thus the problem has been reduced to two sequences that converge to r, yet a0 ≠ b0.
Assume a0 < b0 and subtract a0 across the board. Now r is strictly between 0 and 1. We know the inequalities are strict, since r is irrational. Each di begins with b0 plus something positive. Since b0 is also positive, each di is at least 1, and d cannot converge to r. This is a contradiction, hence ci converges to r, which recreates ai and ci.
We still need to consider an infinite sequence of continued fractions that might converge to a rational number. Start with r an integer. The reverse sequence has b0 = r, and stops there. Subtract b0 across the board, so that r = 0.
If a0 ≥ 1, each ci ≥ 1, and c cannot converge to 0.
For each ci, the contribution of 1/(a1+1/(a2+1/(a3+…))) is bounded by 1. If a0 ≤ -2, each ci ≤ -1, and c cannot converge to 0. Thus a0 is 0 or -1.
Suppose a0 = 0. Beyond i = 1, a1 is tweaked by something between 0 and 1. Take the reciprocal and the result is bounded by 1/a1 and 1/(a1+1). Since each ci is bounded above 0, c cannot converge to 0.
Suppose a0 = -1. We just showed that ci is trapped between -1+1/a1 and -1+1/(a1+1). This forces a1 = 1. Yet a1 is adjusted by something between 1/a2 and 1/(a2+1). This bounds a1 above 1+ε, which keeps the reciprocal below 1-ε, which keeps ci below -ε. Since c cannot converge to 0, we have a contradiction. An infinite sequence of continued fractions cannot approach an integer.
Suppose an infinite sequence of continued fractions converges to a rational number r. Remember that r is not an integer, and is not 0. Spin off the finite sequence bi and di as before. If a0 = b0, subtract this value across the board, then take reciprocals. This resets the sequences at a1 and b1. They both converge to the new value of r, which remains rational. If r is an integer we have a contradiction. So we can keep going. Since b is a finite sequence the process must stop. At this point a0 ≠ b0.
Subtract b0 across the board, so that r is a rational number whose derived sequence starts with 0. Remember that the representation of a rational number is faithful. The first coefficient that r creates is 0, and r is strictly between 0 and 1. If a0 is negative then each ci is bounded by 0, and c cannot approach r. If a0 ≥ 1 then each ci ≥ 1, and c cannot approach r. By assumption a0 is not 0, since it would then equal b0. We have reached a contradiction. Every infinite sequence of continued fractions converges to an irrational number, And this correspondence is one to one.
Given integers p and q, apply the gcd algorithm. A simple analysis says that the remainder is no worse than half of q at each step. The value of q is cut in half with each iteration, and the algorithm stops in n steps, where n is the number of bits in q. However, the algorithm actually runs faster than that.
Recall that the continued fractions of p/q run the gcd algorithm. They also converge to r according to the square of the denominator. As a lower bound, the denominators increase as φn. Put this all together and the gcd algorithm terminates in k steps, where φ2k attains the precision of q. Evaluate φ2 and get 2.618. Take the log base 2 and get 1.388, with reciprocal 0.72. Thus the number of steps is actually the number of bits times 0.72. This is two decimal digits every five steps, and this does not include any improvements you might realize by taking q - the remainder, if that proves to be smaller.
Let r = 1+sqrt(2). This is the fundamental unit for the number field Q adjoin sqrt(2). Its norm, 1+sqrt(2) times 1-sqrt(2), is 1-2, or -1, so indeed it is a unit. Spin off the continued fractions, starting with a0 = 2. The error term e0 is 0.4142135. Symbolically, this is sqrt(2)-1. Invert it to get 1/e0 = 1/(sqrt(2)-1) = (sqrt(2)+1)/{(sqrt(2)-1)×(sqrt(2)+1)} = sqrt(2)+1. This is the same as r. The largest integer less than or equal to this value is 2, giving the same error term sqrt(2)-1. This continues forever. The sequence that builds the continued fractions that approach r is constant at ai = 2.
What if we had chosen the inverse fundamental unit sqrt(2)-1? This is less than 1, hence a0 = 0. The unit becomes e0, and we invert it to reproduce the fundamental unit that is greater than 1. We may as well skip this step and start with the fundamental unit that is greater than 1.
The next number field, Q adjoin sqrt(3), has fundamental unit 2+sqrt(3). a0 = 3, and e0 = sqrt(3)-1. Invert this and get (sqrt(3)+1)/2. Set a1 = 1, and e1 = sqrt(3)-1)/2. Invert this and get sqrt(3)+1. Set a2 = 2, and e2 = sqrt(3)-1. This is the same as e0, hence the pattern repeats: {3, 1, 2, 1, 2, 1, 2, …}
The next field is Q adjoin sqrt(5), but since 5 is 1 mod 4, half integers are involved. The fundamental unit is (1+sqrt(5))/2. a0 = 1 and e0 = (sqrt(5)-1)/2. Flip and get (sqrt(5)+1)/2. This is the fundamental unit once again. The sequence is entirely ones, which we analyzed before. The fractions approach φ, which is our unit.
Let's try 7, with r = 8+3×sqrt(7). Subtract 15 and get 3×sqrt(7)-7. Flip and get (3×sqrt(7)+7)/14. Subtract 1 and get (3×sqrt(7)-7)/14. Flip and get 3×sqrt(7)+7. Sub tract 14 and get 3×sqrt(7)-7. This is where the pattern repeats: {15, 1, 14, 1, 14, 1, 14, …}
Fundamental units create periodic sequences, and sometimes continued fractions can be used to find the fundamental unit. Let's look at some periodic sequences.
Consider a constant sequence ai = d. Let this build the continued fraction for a real number d+u. If 1/u = d+u, then a1 = d, e1 = u, and the pattern goes on forever, building the constant sequence ai = d. Solve the quadratic equation u2 + du - 1 = 0. Set d = 1 and get u = φ-1, whence d+u = φ, as described earlier. Set d = 2 and get sqrt(2)+1, as described earlier. The general solution is u = (-d+sqrt(d2+4))/2. The square root of d2+4 is just a shade above d, and when you subtract d and divide by 2 the result is between 0 and 1, so there is no trouble. Add d back in to get (d+sqrt(d2+4))/2.
Some of the fundamental units described earlier had periods of length 2. Assume the integer sequence alternates between d and e, with leftovers of u and v. Thus a0 = d, leaving a fraction of u, and a1 = e, which is the largest integer in 1/u, leaving a fraction of v. From there, 1/v = d + u, and the pattern repeats.
1/u = e + v = e + 1/(d+u)
(d+u)/u = e×(d+u) + 1
d+u = eu×(d+u) + u
d = eu2 + eud
eu2 + edu - d = 0
u = (-de + sqrt((de)2 + 4de)) / 2e
Think of de as a single integer k, whence sqrt(k2+4k) is below k+2. Subtract k and divide by something that is at least 2, and u is less than 1. By symmetry of symbols, v = (-de+sqrt((de)2+4de))/2d, which is also less than 1.
As an example, set e = 1. Now u = (-d+sqrt(d2+4d))/2. Ad d back in, and the continued fractions approach (d+sqrt(d2+4d))/2. Set d = 2 and get 1+sqrt(3), which confirms the sequence produced earlier, approaching 2+sqrt(3). Granted, that sequence began with 3, but if you start with 1+sqrt(3) instead, the pattern starts with 2: {2, 1, 2, 1, 2, 1, …}
Set d = 14 to approach 7+3×sqrt(7), which is 1 less than the fundamental unit described in the previous section. Set d = 6 for 3+sqrt(15), which is 1 less than the fundamental unit 4+sqrt(15). Set d = 3 for (3+sqrt(21))/2, which is 1 less than the fundamental unit (5+sqrt(21))/2. (21 is 1 mod 4, so the half integers come rolling in.) In general, ((d+2) + sqrt(d2+4d))/2 times its conjugate equals 1, giving a unit in the number field, though not necessarily the fundamental unit. Set d = 1, giving (3+sqrt(5))/2. This is a unit with norm 1, but the fundamental unit, (1+sqrt(5))/2, has norm -1. Siting just one more example, let d = 18, giving 10+3×sqrt(11), which is indeed the fundamental unit.