William F. HammondLecture notes prepared for MATH 326, Spring 1997 Department of Mathematics and Statistics University at AlbanyZGL1IntroductionSU-12The continued fraction expansion of a real numberSU-23First examplesSU-34The case of a rational numberSU-45The symbol t1,t2,,trSU-56Application to Continued FractionsSU-67Bezouts Identity and the double recursionSU-78The action of $GL{2}_{}Z$ on the projective lineSU-89Periodic continued fractionsSU-9ReferencesSU-TheBibLiog

1SU-1IntroductionContinued 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) decimalThe 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 Bezouts Identity(iii)It provides an opportunity to introduce the subject of group theory via the 2dimensional unimodular group GL2Z

2SU-2The continued fraction expansion of a real numberEvery 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 nxn1, x falls between n and n1 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 nx The integer n is sometimes called the floor of x and one often introduces a notation for the floor of x such as nxExamples: 1.21.52.3For any real x with $nx$ the number $uxn$ falls in the unit interval I consisting of all real numbers u for which 0u1Thus, for given real x there is a unique decomposition xnu where n is an integer and u is in the unit interval Moreover, u0 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 fractionThe 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 xn1u1, where n1 is an integer and 0u11If u10 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 xIf u10 then the reciprocal $1u{1}_{}$ of u1 satisfies $1u{1}_{}1$ since u1 is in I and, therefore, u11 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 1u1n2u2, where n2 is an integer and 0u21 Combining the equations that represent the first two steps, one may write xn11n2u2Either u20 in which case the process ends with the expansion xn11n2, or u20 In the latter case one does to u2 what had just been done to u1 above under the assumption u10 One writes 1u2n3u3, where n3 is an integer and 0u31 Then combining the equations that represent the first three steps, one may write xn11n21n3u3After k steps, if the process has gone that far, one has integers $n{1}_{},n{2}_{},,n{k}_{}$ and real numbers $u{1}_{},u{2}_{},,u{k}_{}$ that are members of the unit interval I with $u{1}_{},u{2}_{},,u{k}_{}$ all positive One may write xn11n21n311nkuk Alternatively, one may write xn1,n2,n3,,nkuk If uk0 the process ends after k steps Otherwise, the process continues at least one more step with 1uknk1uk1In this way one associates with any real number x a sequence, which could be either finite or infinite, $n{1}_{},n{2}_{},$ of integers This sequence is called the continued fraction expansion of x AssertLabel-1AssertLabel-1conventionConventionWhen $n{1}_{},n{2}_{},...$ is called a continued fraction, it is understood that all of the numbers nj are integers and that $n{j}_{}1$ for j2

3SU-3First examples15111411111141123411214311211131,2,1,310311103311033161110331611033161613,6,6,6,2,3,5,2213,5,221315,221315122131112213211213511211358135Let x11213121312 In this case one finds that x11y, where y213121312 Further reflection shows that the continued fraction structure for y is selfsimilar: y2131y This simplifies to y7y23y1 and leads to the quadratic equation 3y26y20 with discriminant 60 Since y2 one of the two roots of the quadratic equation cannot be y and, therefore, y3153 Finally, x1512The idea of the calculation above leads to the conclusion that any continued fraction $n{1}_{},n{2}_{},$ 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

4SU-4The case of a rational numberThe 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 denominatorLet xab,b0 be a representation of a rational number x as a quotient of integers a and b The mod one decomposition abn1u1,u1an1bb shows that u1r1b where r1 is the remainder for division of a by b The case where $u{1}_{}0$ is the case where x is an integer Otherwise u10 and the mod one decomposition of $1u{1}_{}$ gives br1n2u2,u2bn2r1r1 This shows that u2r2r1 where r2 is the remainder for division of b by r1 Thus, the successive quotients in Euclids algorithm are the integers $n{1}_{},n{2}_{},$ occurring in the continued fraction Euclids 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 AssertLabel-2AssertLabel-2theoremsTheorem1The continued fraction expansion of a real number is finite if and only if the real number is rationalProof. 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

5SU-5The symbol t1,t2,,trFor arbitrary real numbers $t{1}_{},t{2}_{},,t{r}_{}$ with each $t{j}_{}1$ for $j2$ the symbol $t{1}_{},t{2}_{},,t{r}_{}$ is defined recursively by: t1t1 t-rect-receqnt1,t2,,trt11t2,,tr In order for this definition to make sense one needs to know that the denominator in the righthand side of (iref="t-rec"t-rec) is nonzero The condition $t{j}_{}1$ for $j2$ guarantees, in fact, that t2,,tr0 as one may prove using inductionIt is an easy consequence of mathematical induction that the symbol $t{1}_{},t{2}_{},,t{r}_{}$ is a rational number if each tj is rational In particular, each finite continued fraction is a rational number (Note that the symbol $t{1}_{},t{2}_{},,t{r}_{}$ 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 $t{1}_{},,t{r}_{}$ 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,28135 Working from right to left one has: 225,25125121123,5,2315,2321135112,3,5,2213,5,2211358135There is, however, another approach to computing t1,t2,,tr Let, in fact, $t{1}_{},t{2}_{},$ be any (finite or infinite) sequence of real numbers One uses the double recursion pdefpdefeqnpjtjpj1pj2,j1,p01,p10 to define the sequence pj,j1 The double recursion, differently initialized, qdefqdefeqnqjtjqj1qj2,j1,q00,q11 defines the sequence qj,j1 Note that p1t1 p2t1t21 and q11 q2t2 q3t2t31 One now forms the matrix Mr-defMr-defeqnMjrrpjqjpj1qj1forj0 Thus, for example, M0rr1001,andM1rrt1110 It is easy to see that the matrices Mj satisfy the double recursion Mr-recMr-receqnMjrrtj110Mj1,j1 as a consequence of the double recursion formulas for the pj and qj Hence, a simple argument by mathematical induction shows that MrcompMrcompeqnMrrrtr110rrt2110rrt1110,r1 This is summarized by: AssertLabel-3AssertLabel-3propositionsProposition1For any sequence $t{j}_{},j1$ of real numbers, if $p{j}_{}$ and $q{j}_{}$ are the sequences defined by the double recursions (iref="pdef"pdef) and (iref="qdef"qdef), then one has the matrix identity prqr-rowprqr-roweqnrrprqrpr1qr1rrtr110rrt2110rrt1110 for each integer r1 pqidenpqidencorollariesCorollary1One has the identity $p{r}_{}q{r}_{}q{r}_{}p{r}_{}1r$ for each integer r1Proof. The number $p{r}_{}q{r}_{}q{r}_{}p{r}_{}$ is the determinant of the matrix Mr From the formula (iref="Mrcomp"Mrcomp) the matrix $M{r}_{}$ 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 detMr1r videnvidencorollariesCorollary2One has the vector identity prqr-vecprqr-veceqnrprqrrrt1110rrt2110rrtr110r10 for each integer r1Proof. First recall (i) that the product of a matrix and a (column) vector is defined by the relation rrabcdrxyraxbycxdy, (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 (iref="prqr-row"prqr-row) to obtain: prqr-colprqr-coleqnrrprpr1qrqr1rrt1110rrt2110rrtr110 To this relation one applies the principle that the first column of any 22 matrix is the product of that matrix with the column r10 in order to obtain the column identity (iref="prqr-vec"prqr-vec) AssertLabel-6AssertLabel-6theoremsTheorem2For any sequence $t{j}_{},j1$ of real numbers, if $p{j}_{}$ and $q{j}_{}$ are the sequences defined by the double recursions (iref="pdef"pdef) and (iref="qdef"qdef), and if $t{j}_{}1$ for j2 then the value of the symbol $t{1}_{},,t{r}_{}$ is given by the formula t-compt-compeqnt1,t2,,trprqrforr1Proof. What is slightly strange about this important result is that while the $p{r}_{}$ and the $q{r}_{}$ are defined by the front end recursions, albeit double recursions, (iref="pdef"pdef) and (iref="qdef"qdef), the symbol $t{1}_{},,t{r}_{}$ is defined by the back end recursion (iref="t-rec"t-rec) The proof begins with the comment that the righthand side of (iref="t-comp"t-comp) does not make sense unless one can be sure that the denominator qr0 One can show easily by induction on r that $q{r}_{}1$ for $r1$ under the hypothesis $t{j}_{}1$ for j2The proof proceeds by induction on r If r1 the assertion of the theorem is simply the statement t1p1q1 and, as noted above, $p{1}_{}t{1}_{}$ and q11 Assume now that r2 By induction we may assume the correctness of the statement (iref="t-comp"t-comp) for symbols of length r1 and, therefore, for the symbol t2,,tr That case of the statement says that $t{2}_{},,t{r}_{}$ must be equal to ac where by corollary iref="viden"viden racrrabcdr10 with rrabcdrrt2110rrtr110 Now by (iref="t-rec"t-rec) t1,t2,,trt11act1caat1ca But by corollary iref="viden"viden again rprqrrrt1110rrabcdr10rrat1cbt1dabr10rat1ca Hence, prqrat1cat1,t2,,tr

6SU-6Application to Continued FractionsRecall that $n{1}_{},n{2}_{},$ is called a continued fraction only when each nj is an integer and $n{j}_{}1$ for j2 The sequence $n{1}_{},n{2}_{},$ may be finite or infinite The symbol $c{r}_{}n{1}_{},n{2}_{},,n{r}_{}$ formed with the first r terms of the sequence, is called the rth convergent of the continued fraction Associated with a given sequence $n{1}_{},n{2}_{},$ are two sequences $p{1}_{},p{2}_{},$ and $q{1}_{},q{2}_{},$ that are given, according to the double recursions (iref="pdef"pdef), (iref="qdef"qdef) of the previous section with tjnj AssertLabel-7AssertLabel-7propositionsProposition2If $n{1}_{},n{2}_{},$ is a continued fraction, then the integers pr and qr are coprime for each r1Proof. By Corollary iref="pqiden"pqiden of the previous section prqr1qrpr11r Hence, any positive divisor of both pr and qr must divide the lefthand side of this relation, and, therefore, must also divide 1r AssertLabel-8AssertLabel-8propositionsProposition3The difference between successive convergents of the continued fraction $n{1}_{},n{2}_{},$ is given by the formula convgtdiffconvgtdiffeqncrcr11rqrqr1forr2Proof. According to the theorem (formula iref="t-comp"t-comp) at the end of the last section the convergent cr is given by crprqr Hence, crcr1prqrpr1qr1prqr1pr1qrqrqr11rqrqr1 (The last step is by Corollary iref="pqiden"pqiden above.) AssertLabel-9AssertLabel-9remarksRemark1The formula (iref="convgtdiff"convgtdiff) remains true if $c{r}_{}t{1}_{},,t{r}_{}$ where the tj are real numbers subject to the assumption $t{j}_{}1$ for j1 AssertLabel-10AssertLabel-10AssertDefaultLemmaThe sequence $q{j}_{}$ is a strictly increasing sequence for j2Proof. This is easily proved by induction from the recursive definition (iref="qdef"qdef) of the sequence AssertLabel-11AssertLabel-11theoremsTheorem3If $n{1}_{},n{2}_{},$ is an infinite continued fraction, then the limit limrprqr always existsProof. As one plots the convergents cr on the line of real numbers, one moves alternately right and left The formula (iref="convgtdiff"convgtdiff) 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 c1c3c5c6c4c2 Since any strictly increasing sequence of positive integers must have infinite limit, the seqence $q{j}_{}q{j}_{}$ has infinite limit, and so the sequence of reciprocals $1q{j}_{}q{j}_{}$ must converge to zero Hence, the sequences of odd and evenindexed convergents must have the same limit, which is the limit of the sequence of all convergents AssertLabel-12AssertLabel-12definitionsDefinition1The limit of the sequence of convergents of an infinite continued fraction is called the value of that continued fraction AssertLabel-13AssertLabel-13theoremsTheorem4If $n{1}_{},n{2}_{},$ is the continued fraction expansion of an irrational number x then xlimrprqr; that is, the value of the continued fraction expansion of a real number is that real numberProof. For each $r1$ the continued fraction expansion $n{1}_{},n{2}_{},$ of x is characterized by the identity xconfracxconfraceqnxn1,n2,,nrur, where ur is a real number with 0ur1 The sequences of ps and qs for the symbol $n{1}_{},n{2}_{},,n{r}_{}u{r}_{}$ agree with those for the symbol $n{1}_{},n{2}_{},,n{r}_{}$ except for the rth terms One has by (iref="t-comp"t-comp) n1,n2,,nrurPrQr, where by (iref="qdef"qdef) qrnrqr1qr2Qrnrurqr1qr2 Hence, Qrqrurqr1 Therefore, the displacement from cr1 to x is by (iref="convgtdiff"convgtdiff) 1rQrqr11rqrqr1urqr12, which is in the same direction but of smaller magnitude than the displacement from cr1 to cr Therefore, x must be larger than every oddindexed convergent and smaller than every evenindexed convergent But since all convergents have the same limit, that limit must be x

7SU-7Bezouts Identity and the double recursionIt has already been observed that the process of finding the continued fraction expansion of a rational number ab (b0), 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 r1aandr0b 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 0rjrj1 Thus, remrecremreceqnrjrj2njrj1 The Euclidean algorithm admits an additional stage if rj0 Since 0rjrj1r2r1r0b, there can be at most b stagesOne may use the sequence of successive quotients nj (j1) to form sequences $p{j}_{}$ and qj as in the previous section, according to the double recursions: npdefnpdefeqnpjnjpj1pj2,j1;p01,p10 nqdefnqdefeqnqjnjqj1qj2,j1;q00,q11 It has already been observed that $q{j}_{}1$ for $j1$ and n1,n2,,njpjqj,j1Bezouts 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 AssertLabel-14AssertLabel-14theoremsTheorem5If the application of the Euclidean algorithm to a and b (b0) ends with the mth long division, i.e., rm0 then bezoutbezouteqnrj1j1qjapjb,1jmProof. One uses induction on j For $j1$ the statement is r1q1ap1b Since by (iref="npdef"npdef, iref="nqdef"nqdef) $q{1}_{}1$ and p1n1 this statement is simply the case $j1$ in (iref="remrec"remrec) Assume j2 and that the formula (iref="bezout"bezout) has been established for indices smaller than j By (iref="remrec"remrec) one has rjrj2njrj1 In this equation one may use (iref="bezout"bezout) to expand the terms rj2 and rj1 to obtain: rj1j3qj2apj2bnj1j2qj1apj1b1j1qj2apj2bnj1j1qj1apj1b1j1qj2apj2bnjqj1apj1b1j1qj2njqj1apj2njpj1b1j1qjapjb AssertLabel-15AssertLabel-15corollariesCorollary3The greatest common divisor d of a and b is given by the formula gcdbezoutgcdbezouteqnd1mqm1apm1b, where m is the number of divisions required to obtain zero remainder in the Euclidean algorithmProof. One knows that d is the last nonzero remainder rm1