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