A summer program and resource for middle school students showing high promise in mathematics


Continued Fractions

A number is usually written down using the place-value system. There are other systems. One such system is Continued Fractions. Let us look at how rational fractions and irrational numbers can be represented as continued fractions. For instance, the continued fraction representation of 153/53 is given on the bottom step in the left column below. Since it is cumbersome to obtain the needed numbers in the manner shown in the left column, we show a faster way [3] on the right column.

The continued fraction representation of 153/53 is written as [2,1,7,1,5]. This is a finite continued fraction. It is a consequence of the Euclidean Algorithm that the continued fraction representation of all rational fractions must terminate. The funny division process in the right column allows us to see this: In a division, the remainder is smaller than the divisor. But in the right column, the remainder in each division becomes the divisor in the next division. So the remainders become smaller and smaller, ultimately reaching zero where the funny division ends. This proves that every rational fraction can be represented as a finite continued fraction.

Notice that the numerators of the fractions in the alternate representation are 1's. Continued fractions where the numerators are positive integers - 1's in the above example - are called simple continued fractions. So rational fractions are finite simple continued fractions.

Let us find the continued fraction representation of √2.

We say the continued fraction expansion of √2 is [1,2,2,2,...]. It is an example of an infinite continued fraction which every irrational number is. √2 is an example of a quadratic irrational because it is the solution of the quadratic equation x2 - 2 = 0. In fact, any number of the form
where P,D,Q are integers and D is a positive integer that is not the square of an integer is called a quadratic irrational since it is the root of the quadratic equation
Q2x2 - 2PQx + (P2 - D) = 0.
Although it is clear that there are infinitely many quadratic irrationals, most irrationals are not quadratic - p is one such. Now notice that the continued fraction representation of √2 is [1,2,2,2,...]. In other words, after the second digit, there is a pattern. That is, the digit 2 repeats. A short way of indicating this is to write it as [1,(2)]. The string of digits inside the round parentheses repeats. The usual notation for this is not to use the round brackets, but place a line above the digit 2. We will use the round brackets here.

We will show later that √3 = [1,1,2,1,2,1,2,...] = [1,(1,2)]. The repeating string can be long in some instances: √31 = [5,(1,1,3,5,3,1,1,10)]. You will notice that if you do not consider the last number in the string, the remaining part of the string is symmetric about the centre of the string and that the last number in the string is double the number in the center of the symmetric part. This has been proved to be the case for all quadratic irrationals. Let us return to the strings that repeat in the continued fraction expansion. When this happens, we call the continued fraction "periodic." Joseph Louis Lagrange discovered in 1770 A.D. that the continued fraction expansion of any quadratic irrational is periodic after a while. The method we used to find the continued fraction representation of √2 will work [3] also for all integers of the form m2 + 1. There are general methods [2] for obtaining the continued fraction expansion of √Q, for any non-square integer Q.

Continued Fraction (CF) for √N
Let us find the CF for √3.

The procedure we used to find the CF representation of √3 can be used also to find the CF for √N, for any positive integer N that is not the square of another.

If we do not insist that the numerators of the fractions appearing in the CF are 1's, then there is a fast way to obtain the CF representation of √N:

You can get the CF for √2 by substituting a = 1 and b = 1.

NOTE: (You may omit this if you are not familiar yet with Differential Calculus)
The convergents in Continued Fractions can also be employed to find successively closer approximations of the roots - that is, values of x that satisfy f(x)=0) - of a function f of x, provided f has continuous derivatives of several orders[1]. Since polynomials have continuous derivatives of all orders, the solution of polynomial equations in one variable can be accomplished using the convergents. Thus we find that the approximation of √N was feasible using the convergents since square root of a number N is the solution of the polynomial equation x2-N = 0.

[1] J.S. Frame, The Solution of Equations by Continued Fractions, American Mathematical Monthly, Vol. 60, No. 5 (May, 1953) , pp. 293-305
[2] G.H. Hardy and E.M. Wright, Introduction to the theory of numbers, Oxford University Press
[3] C.D. Olds, Continued Fractions, New Mathematics Library, Mathematical Association of America, 1963
[4] B. P. Thurston, Private communication, 2012




Send suggestions to webmaster@mathpath.org
Copyright © 2001- MathPath
Last updated - January 24, 2005