Continued Fractions and the Euclidean Algorithm

Lecture notes prepared for MATH 326, Spring 1997
Department of Mathematics and Statistics
University at Albany

William F. Hammond

Table of Contents

1  Introduction... *
2  The continued fraction expansion of a real number... *
3  First examples... *
4  The case of a rational number... *
5  The symbol t1,t2,,tr... *
6  Application to Continued Fractions... *
7  Bezout's Identity and the double recursion... *
8  The action of GL2Z on the projective line... *
9  Periodic continued fractions... *
References  ... *

1.  Introduction

Continued fractions offer a means of concrete representation for arbitrary real numbers. The continued fraction expansion of a real number is an alternative to the representation of such a number as a (possibly infinite) decimal.

The reasons for including this topic in the course on Classical Algebra are:

(i) The subject provides many applications of the method of recursion.
(ii) It is closely related to the Euclidean algorithm and, in particular, to “Bezout's Identity”.
(iii) It provides an opportunity to introduce the subject of group theory via the 2-dimensional unimodular group GL2Z.

2.  The continued fraction expansion of a real number

Every real number x is represented by a point on the real line and, as such, falls between two integers. For example, if n is an integer and nx<n+1, x falls between n and n+1, and there is one and only one such integer n for any given real x. In the case where x itself is an integer, one has n=x. The integer n is sometimes called the floor of x, and one often introduces a notation for the floor of x such as n=x.

Examples:

1. 2=1.5
2. 3=π

For any real x with n=x the number u=xn falls in the unit interval I consisting of all real numbers u for which 0u<1.

Thus, for given real x there is a unique decomposition x=n+u where n is an integer and u is in the unit interval. Moreover, u=0 if and only if x is an integer. This decomposition is sometimes called the mod one decomposition of a real number. It is the first step in the process of expanding x as a continued fraction.

The process of finding the continued fraction expansion of a real number is a recursive process that procedes one step at a time. Given x one begins with the mod one decomposition x=n1+u1, where n1 is an integer and 0u1<1.

If u1=0, which happens if and only if x is an integer, the recursive process terminates with this first step. The idea is to obtain a sequence of integers that give a precise determination of x.

If u1>0, then the reciprocal 1u1 of u1 satisfies 1u1>1 since u1 is in I and, therefore, u1<1. In this case the second step in the recursive determination of the continued fraction expansion of x is to apply the mod one decomposition to 1u1. One writes 1u1=n2+u2, where n2 is an integer and 0u2<1. Combining the equations that represent the first two steps, one may write x=n1+1n2+u2.

Either u2=0, in which case the process ends with the expansion x=n1+1n2, or u2>0. In the latter case one does to u2 what had just been done to u1 above under the assumption u1>0. One writes 1u2=n3+u3, where n3 is an integer and 0u3<1. Then combining the equations that represent the first three steps, one may write x=n1+1n2+1n3+u3.

After k steps, if the process has gone that far, one has integers n1,n2,,nk and real numbers u1,u2,,uk that are members of the unit interval I with u1,u2,,uk1 all positive. One may write x=n1+1n2+1n3+1+1nk+uk. Alternatively, one may write x=n1,n2,n3,,nk+uk. If uk=0, the process ends after k steps. Otherwise, the process continues at least one more step with 1uk=nk+1+uk+1.

In this way one associates with any real number x a sequence, which could be either finite or infinite, n1,n2, of integers. This sequence is called the continued fraction expansion of x.

Convention.   When n1,n2,... is called a continued fraction, it is understood that all of the numbers nj are integers and that nj1 for j2.

3.  First examples

 1511=1+411 =1+1114 =1+12+34 =1+12+143 =1+12+11+13 =1,2,1,3.

 10=3+11103 =3+110+3 =3+16+11103 =3+16+110+3 =3+16+16+1 =3,6,6,6,.

 2,3,5,2=2+13,5,2 =2+13+15,2 =2+13+15+12 =2+13+1112 =2+13+211 =2+13511 =2+1135 =8135.

Let x=1+12+13+12+13+12+. In this case one finds that x=1+1y, where y=2+13+12+13+12+. Further reflection shows that the continued fraction structure for y is self-similar: y=2+13+1y. This simplifies to y=7y+23y+1 and leads to the quadratic equation 3y26y2=0 with discriminant 60. Since y>2, one of the two roots of the quadratic equation cannot be y, and, therefore, y=3+153. Finally, x=1512.

The idea of the calculation above leads to the conclusion that any continued fraction n1,n2, that eventually repeats is the solution of a quadratic equation with positive discriminant and integer coefficients. The converse of this statement is also true, but a proof requires further consideration.

4.  The case of a rational number

The process of finding the continued fraction expansion of a rational number is essentially identical to the process of applying the Euclidean algorithm to the pair of integers given by its numerator and denominator.

Let x=ab,b>0, be a representation of a rational number x as a quotient of integers a and b. The mod one decomposition ab=n1+u1,u1=an1bb shows that u1=r1b, where r1 is the remainder for division of a by b. The case where u1=0 is the case where x is an integer. Otherwise u1>0, and the mod one decomposition of 1u1 gives br1=n2+u2,u2=bn2r1r1. This shows that u2=r2r1, where r2 is the remainder for division of b by r1. Thus, the successive quotients in Euclid's algorithm are the integers n1,n2, occurring in the continued fraction. Euclid's algorithm terminates after a finite number of steps with the appearance of a zero remainder. Hence, the continued fraction expansion of every rational number is finite.

Theorem 1.   The continued fraction expansion of a real number is finite if and only if the real number is rational.

Proof. It has just been shown that if x is rational, then the continued fraction expansion of x is finite because its calculation is given by application of the Euclidean algorithm to the numerator and denominator of x. The converse statement is the statement that every finite continued fraction represents a rational number. That statement will be demonstrated in the following section.

5.  The symbol t1,t2,,tr

For arbitrary real numbers t1,t2,,tr with each tj1 for j2 the symbol t1,t2,,tr is defined recursively by: t1=t1 (1)t1,t2,,tr=t1+1t2,,tr. In order for this definition to make sense one needs to know that the denominator in the right-hand side of (1) is non-zero. The condition tj1 for j2 guarantees, in fact, that t2,,tr>0, as one may prove using induction.

It is an easy consequence of mathematical induction that the symbol t1,t2,,tr is a rational number if each tj is rational. In particular, each finite continued fraction is a rational number. (Note that the symbol t1,t2,,tr is to be called a continued fraction, according to the convention of the first section, only when each tj is an integer.)

Observe that the recursive nature of the symbol t1,,tr suggests that the symbol should be computed in a particular case working from right to left. Consider again, for example, the computation above showing that 2,3,5,2=8135. Working from right to left one has:  2=2 5,2=5+12=5+12=112 3,5,2=3+15,2=3+211=3511 2,3,5,2=2+13,5,2=2+1135=8135

There is, however, another approach to computing t1,t2,,tr. Let, in fact, t1,t2, be any (finite or infinite) sequence of real numbers. One uses the double recursion (2)pj=tjpj1+pj2,j1,p0=1,p1=0 to define the sequence {pj},j1. The double recursion, differently initialized, (3)qj=tjqj1+qj2,j1,q0=0,q1=1 defines the sequence {qj},j1. Note that p1=t1, p2=t1t2+1, and q1=1, q2=t2, q3=t2t3+1, .

One now forms the matrix (4)Mj=pjqjpj1qj1  for  j0. Thus, for example, M0=1001,  and  M1=t1110. It is easy to see that the matrices Mj satisfy the double recursion (5)Mj=tj110Mj1,j1 as a consequence of the double recursion formulas for the pj and qj. Hence, a simple argument by mathematical induction shows that (6)Mr=tr110t2110t1110,r1. This is summarized by:

Proposition 1.   For any sequence {tj},j1 of real numbers, if {pj} and {qj} are the sequences defined by the double recursions (2) and (3), then one has the matrix identity (7)prqrpr1qr1=tr110t2110t1110 for each integer r1.

Corollary 1.   One has the identity prqr1qrpr1=1r for each integer r1.

Proof. The number prqr1qrpr1 is the determinant of the matrix Mr. From the formula (6) the matrix Mr is the product of r matrix factors, each of which has determinant 1. Since the determinant of the product of matrices is the product of the determinants of the factors, it is clear that detMr=1r.

Corollary 2.   One has the vector identity (8)prqr=t1110t2110tr11010 for each integer r1.

Proof. First recall (i) that the product of a matrix and a (column) vector is defined by the relation abcdxy=ax+bycx+dy, (ii) that the transpose of a matrix is the matrix whose rows are the columns of the given matrix, and (iii) that the transpose operation reverses matrix multiplication. One tranposes both sides of the relation (7) to obtain: (9)prpr1qrqr1=t1110t2110tr110. To this relation one applies the principle that the first column of any 2×2 matrix is the product of that matrix with the column 10 in order to obtain the column identity (8).

Theorem 2.   For any sequence {tj},j1 of real numbers, if {pj} and {qj} are the sequences defined by the double recursions (2) and (3), and if tj1 for j2, then the value of the symbol t1,,tr is given by the formula (10)t1,t2,,tr=prqr  for  r1.

Proof. What is slightly strange about this important result is that while the {pr} and the {qr} are defined by the front end recursions, albeit double recursions, (2) and (3), the symbol t1,,tr is defined by the back end recursion (1). The proof begins with the comment that the right-hand side of (10) does not make sense unless one can be sure that the denominator qr0. One can show easily by induction on r that qr1 for r1 under the hypothesis tj1 for j2.

The proof proceeds by induction on r. If r=1, the assertion of the theorem is simply the statement t1=p1q1, and, as noted above, p1=t1 and q1=1. Assume now that r2. By induction we may assume the correctness of the statement (10) for symbols of length r1, and, therefore, for the symbol t2,,tr. That case of the statement says that t2,,tr must be equal to ac, where by corollary 2 ac=abcd10 with abcd=t2110tr110. Now by (1) t1,t2,,tr=t1+1ac=t1+ca=at1+ca. But by corollary 2 again prqr=t1110abcd10=at1+cbt1+dab10=at1+ca. Hence, prqr=at1+ca=t1,t2,,tr.

6.  Application to Continued Fractions

Recall that n1,n2, is called a continued fraction only when each nj is an integer and nj1 for j2. The sequence n1,n2, may be finite or infinite. The symbol cr=n1,n2,,nr formed with the first r terms of the sequence, is called the rth convergent of the continued fraction. Associated with a given sequence n1,n2, are two sequences p1,p2, and q1,q2, that are given, according to the double recursions (2), (3) of the previous section with tj=nj.

Proposition 2.   If n1,n2, is a continued fraction, then the integers pr and qr are coprime for each r1.

Proof. By Corollary 1 of the previous section prqr1qrpr1=1r. Hence, any positive divisor of both pr and qr must divide the left-hand side of this relation, and, therefore, must also divide 1r.

Proposition 3.   The difference between successive convergents of the continued fraction n1,n2, is given by the formula (11)crcr1=1rqrqr1  for  r2.

Proof. According to the theorem (formula 10) at the end of the last section the convergent cr is given by cr=prqr. Hence,  crcr1=prqrpr1qr1 =prqr1pr1qrqrqr1 =1rqrqr1. (The last step is by Corollary 1 above.)

Remark 1.   The formula (11) remains true if cr=t1,,tr where the tj are real numbers subject to the assumption tj1 for j1.

Lemma.   The sequence {qj} is a strictly increasing sequence for j2.

Proof. This is easily proved by induction from the recursive definition (3) of the sequence.

Theorem 3.   If n1,n2, is an infinite continued fraction, then the limit limrprqr always exists.

Proof. As one plots the convergents cr on the line of real numbers, one moves alternately right and left. The formula (11) for the difference between successive convergents elucidates not only the fact of alternate right and left movement but also the fact that each successive movement is smaller than the one preceding. Therefore, one has c1<c3<c5<<c6<c4<c2. Since any strictly increasing sequence of positive integers must have infinite limit, the seqence qjqj1 has infinite limit, and so the sequence of reciprocals 1qjqj1 must converge to zero. Hence, the sequences of odd- and even-indexed convergents must have the same limit, which is the limit of the sequence of all convergents.

Definition 1.   The limit of the sequence of convergents of an infinite continued fraction is called the value of that continued fraction.

Theorem 4.   If n1,n2, is the continued fraction expansion of an irrational number x, then x=limrprqr; that is, the value of the continued fraction expansion of a real number is that real number.

Proof. For each r1 the continued fraction expansion n1,n2, of x is characterized by the identity (12)x=n1,n2,,nr+ur, where ur is a real number with 0ur<1. The sequences of p's and q's for the symbol n1,n2,,nr+ur agree with those for the symbol n1,n2,,nr except for the rth terms. One has by (10) n1,n2,,nr+ur=PrQr, where by (3)  qr=nrqr1+qr2 Qr=nr+urqr1+qr2 Hence, Qr=qr+urqr1. Therefore, the displacement from cr1 to x is by (11) 1rQrqr1=1rqrqr1+urqr12, which is in the same direction but of smaller magnitude than the displacement from cr1 to cr. Therefore, x must be larger than every odd-indexed convergent and smaller than every even-indexed convergent. But since all convergents have the same limit, that limit must be x.

7.  Bezout's Identity and the double recursion

It has already been observed that the process of finding the continued fraction expansion of a rational number ab (b>0), involves the same series of long divisions that are used in the application of the Euclidean algorithm to the pair of integers a and b. Recall that at each stage in the Euclidean algorithm the divisor for the current stage is the remainder from the previous stage and the dividend for the current stage is the divisor from the previous stage, or, equivalently, the dividend for the current stage is the remainder from the second previous stage. The Euclidean algorithm may thus be viewed as a double recursion that is used to construct the sequence of remainders. One starts the double recursion with r1=a  and  r0=b. At the jth stage one performs long division of rj2 by rj1 to obtain the integer quotient nj and the integer remainder rj that satisfies 0rj<rj1. Thus, (13)rj=rj2njrj1. The Euclidean algorithm admits an additional stage if rj>0. Since 0rj<rj1<<r2<r1<r0=b, there can be at most b stages.

One may use the sequence of successive quotients nj (j1) to form sequences {pj} and {qj}, as in the previous section, according to the double recursions: (14)pj=njpj1+pj2,j1;p0=1,p1=0. (15)qj=njqj1+qj2,j1;q0=0,q1=1. It has already been observed that qj1 for j1 and n1,n2,,nj=pjqj,j1.

Bezout's Identity says not only that the greatest common divisor of a and b is an integer linear combination of them but that the coefficents in that integer linear combination may be taken, up to a sign, as q and p.

Theorem 5.   If the application of the Euclidean algorithm to a and b (b>0) ends with the mth long division, i.e., rm=0, then (16)rj=1j1qjapjb,1jm.

Proof. One uses induction on j. For j=1 the statement is r1=q1ap1b. Since by (14, 15) q1=1 and p1=n1, this statement is simply the case j=1 in (13). Assume j2, and that the formula (16) has been established for indices smaller than j. By (13) one has rj=rj2njrj1. In this equation one may use (16) to expand the terms rj2 and rj1 to obtain:  rj=1j3qj2apj2bnj1j2qj1apj1b =1j1qj2apj2b+nj1j1qj1apj1b =1j1qj2apj2b+njqj1apj1b =1j1qj2+njqj1apj2+njpj1b =1j1qjapjb.

Corollary 3.   The greatest common divisor d of a and b is given by the formula (17)d=1mqm1apm1b, where m is the number of divisions required to obtain zero remainder in the Euclidean algorithm.

Proof. One knows that d is the last non-zero remainder rm1 in the Euclidean algorithm. This formula for d is the case j=m1 in (16).

Corollary 4.   (18)pm=ad,qm=bd.

Proof. The last remainder rm=0. The case j=m in (16) shows that ab=pmqm. Since, by the first proposition of the preceding section, pm and qm have no common factor, this corollary is evident.

8.  The action of GL2Z on the projective line

If a, b, c, d are real numbers with adbc0 and M=abcd is the matrix with entries a, b, c, and d, then M·z, for z real, will denote the expression (19)M·z=az+bcz+d. One calls M·z the action of M on z.

M·z is a perfectly good function of z except for the case z=dc where the denominator cz+d vanishes. If it were also true that az+b=0 for the same z, then one would have ba=dc, in contradiction of the assumption adbc0. Thus, when z=dc, the value of |M·w| increases beyond all bounds as w approaches z, and it is convenient to say that M·dc= where is regarded as large and signless. If further it is agreed to define M·=ac, which is the limiting value of M·w as |w| increases without bound, then one may regard the expression M·z as being defined always for all real z and for . The set consisting of all real numbers and also the object (not a number) is called the projective line. The projective line is therefore the union of the (ordinary) affine line with a single point .

Proposition 4.   If n1,n2, is any continued fraction, then (20)n1,n2,,nr,nr+1,=M·nr+1,. where M=n1110nr110.

Proof. Let z=nr+1,. Then n1,n2,,nr,nr+1,=n1,n2,,nr,z. The statement of the proposition now becomes n1,n2,,nr,z=M·z. This may be seen to follow by multiplying both sides in formula (9), after replacing tj with nj, by the column z1.

The matrix M in the preceding proposition is an integer matrix with determinant ±1. The notation GL2Z denotes the set of all such matrices. (The 2 indicates the size of the matrices, and the Z indicates that the entries in such matrices are numbers in the set Z of integers.) It is easy to check that the product of two members of GL2Z is a member of GL2Z and that the matrix inverse of a member of GL2Z is a member of GL2Z. Thus, GL2Z forms what is called a group. The formula (19) defines what is called the action of GL2Z on the projective line.

One says that two points z and w of the projective line are rationally equivalent if there is a matrix M in GL2Z for which w=M·z. Since (i) GL2Z is a group, (ii) M1·M2·z=M1M2·z, and (iii) w=M·z if and only z=M1·w, it is easy to see that every point of the projective line belongs to one and only one rational equivalence class and that two points rationally equivalent to a third must be rationally equivalent to each other.

Terminology.   The rational equivalence of points on the projective line is said to be the equivalence relation on the projective line defined by the action of GL2Z.

Example 1.   The set of real numbers rationally equivalent to the point is precisely the set of rational numbers.

Example 2.   The proposition above shows that any continued fraction is rationally equivalent to each of its tails. It follows that all tails of a continued fraction are rationally equivalent to each other.

9.  Periodic continued fractions

In one of the first examples of a continued fraction expansion, it was shown that 10=3,6,6,6,. This is an example of a periodic continued fraction. After a finite number of terms the sequence of integers repeats cyclically. If a cyclic pattern is present from the very first term, then the continued fraction is called purely periodic. Evidently, 6,6,6,=103 is an example of a purely periodic continued fraction.

Note that a periodic continued fraction cannot represent a rational number since the continued fraction expansion of a rational number is finite.

Theorem 6.   Every periodic continued fraction is the continued fraction expansion of a real quadratic irrational number.

Proof. For clarity: it is being asserted that every periodic continued fraction represent a number of the form a+bmc where a, b, c, and m are all integers with m>0, c0, and m not a perfect square.

Numbers of this form with fixed m but varying integers a, b, and c0 may be added, subtracted, multiplied, and divided without leaving the class of such numbers. (The statement here about division becomes clear if one remembers always to rationalize denominators.) Consequently, for M in GL2Z the number M·z will be a number of this form or if and only if z is in the same class.

Since a periodic continued fraction is rationally equivalent to a purely periodic continued fraction, the question of whether any periodic continued fraction is a quadratic irrationality reduces to the question of whether a purely periodic continued fraction is such. Let x=n1,,nr,n1,,nr,n1,,nr, be a purely periodic continued fraction. By the proposition of the preceding section, x=M·x where M is notationally identical to the M in (20). Ignoring the computation (9) of M in terms of convergents, let M=abcd. Then x=ax+bcx+d, or, otherwise said, x is a solution of the quadratic equation cx2adxb=0.

Remark 2.   It is conversely true that the continued fraction expansion of every real quadratic irrationality is periodic.

This converse will not be proved here.


REFERENCES

[1]   G. Chrystal, Algebra: An Elementary Textbook (2 vols.), Chelsea.
[2]   G. Hardy & E. Wright, An Introduction to the Theory of Numbers, Oxford Univ. Press.
[3]   S. Lang, Introduction to Diophantine Approximations, Addison-Wesley.
[4]   O. Perron, Die Lehre von den Kettenbrüchen, 2nd ed., Chelsea.