Continued Fractions

CONTINUED FRACTIONS. An expression of the form Regular Continued Fractions.—The type of continued frac tion of most practical interest and importance is the simple or regular continued fraction, which is the fraction of the type -}- I I I • where ... are all positive integers. Any positive number less than unity can be represented in this form, and any number whatever, positive or negative, not an integer, can be represented in the form bo+ I b I2 -F • • • where ... , called the partial quotients, are positive integers and is either zero or an integer, positive or negative. For a positive number N, greater than unity, is the integral part of N; for a negative number —N, is —(b+I), where b is the integral part of N. The process of converting a positive number x/y into a regular continued fraction is effectively that of finding the greatest common measure of two numbers, so that the repre sentation is unique, with an exception to be presently mentioned, and the fraction terminates if the number is rational. If the number is irrational the fraction is infinite; and, conversely, a finite regular continued fraction is a rational number and an infinite continued fraction represents an irrational number.

The exception to the unique representation is the following. In converting a rational number into a finite continued fraction bo+ ? • • • b , we should naturally stop at a term b , where n n was greater than unity. We might however write term as I Ii • Thus we could write as I + 3 I -}- 4 I or 7 I I I I i + 3 + 3 + i , so that a rational number can be converted into a simple continued fraction having an odd or even number of partial quotients, whichever we please.

For a regular continued fraction we have pnqn_i—pn—iqn=(—I)n, so that every convergent is a fraction in its lowest terms. Every odd convergent is greater than the succeeding even con vergent. The odd convergents steadily decrease and the even convergents steadily increase. Each odd convergent is greater than the succeeding even convergent and the value of the frac tion lies between that of any two consecutive convergents. The values of ['n and each increase steadily without limit unless the fraction terminates. It follows that every infinite continued fraction of this type determines a definite irrational number ly ing in value between any odd convergent and the succeeding or preceding even convergent. Every convergent is a better approximation to f, the value of the fraction, than any preceding convergent and also than any rational fraction whose denomi nator is less than The difference between and f is less than I/qnqn+i which is less than s/qn. If the difference between f and a fraction P/Q is less than 1/2 then P/Q must be a con vergent to the continued fraction into which f can be converted. This is also true if the difference between and is less than f. Of two consecutive convergents to a regular continued frac tion, f, at least one, p/q, differs from f by less than 1/2 and of three consecutive convergents at least one, p/q, differs from f by less than I/ The very difficult problem of determining whether it is possible or not to find approximations to an irra tional number x of the form p/q, where p and q are integers, such that the difference between p/q and x is less than where k is an assigned number, depends upon continued frac tions. It has been shown that, if k <3, there are an infinite num ber of such approximations unless x is a quadratic surd of a certain type. Some recent work on this subject is given by J. H. Grace (London Math. Soc. Proc., vol. 17) and P. J. Hea wood (ibid., vol. 2o) . A result of some interest that is estab lished by means of continued fractions far more easily is that, if x and y are any two numbers whose ratio is irrational, and a is any assigned number, then an infinite succession of pairs of positive integers m and n can be found such that mx—ny differs from a by less than any arbitrarily assigned small positive number E.

Since any convergent p/q to the regular continued fraction into which a number x may be converted differs from x by less than and is a better approximation than any fraction whose denominator is not greater than q, we can in this way find rational numbers which are approximations to any given number of any degree of accuracy that we require, but it may happen that the actual convergent found has an inconveniently large denomi nator. The problem of finding the best approximation to a number x in the form of a rational fraction whose denominator does not exceed a given number D can be solved as follows. Let and be two consecutive convergents to the fraction representing x and let Then the fractions of the sequence pn-2 pn-2+pn-1 qn-2 qn-2+qn-1 • qn-2+ are increasing or decreasing according as n is odd or even. They are called intermediate or auxiliary convergents. If we take the partial quotients of odd order with their intermediate convergents, wherever the partial coefficients differ from unity, and form the sequence • • p3 , Pn-2 • •• • and also the partial I qi q3 qn-2 qn quotients of even order with their intermediates, and form the quence I.. • . 122 _ .. • . • • then the members of the • o q2 q4 qn-1 first sequence are steadily increasing and the members of the sec ond sequence are steadily decreasing, both sequences tending to x as a limit, x lying between every two consecutive members of either sequence; also no rational number with a denominator less than that of the second member of the pair can be inserted between them. If then we take that member of either sequence whose denominator is not greater than D and nearest to it, we have the best approximation of the kind required.

A simple application of continued fractions is to find solutions in integers of the indeterminate equation ax± by = c, where a and b are integers prime to each other and c is an integer. If we con vert alb into a continued fraction with an even number of terms and p/q is its penultimate convergent, aq — bp = I; so that solu tions of the equation are furnished by x = cq -1- bt, y = c p -f- at, where t is any integer. Other interesting applications of con tinued fractions are to prove that any divisor of a number of any of the forms where a and b are mutually prime integers, is of the same form, and also not merely to prove that any prime number of the form 4n+ I can be represented as the sum of two squares in at least one way, but to obtain these representations explicitly.

Regular Recurring Fractions.

A very important type of the infinite regular continued fraction is the recurring continued fraction. In this type the partial quotients recur in a cycle, if not at once, at least after some fixed term. If a quadratic surd of the form (P+ IR)/Q, where P, Q and R are integers and R is not a perfect square, is converted into a continued fraction, the fraction will be of this type. Here R is essentially positive, P and Q may be positive or negative. A quadratic surd of the form (P-1.IR)/Q is the reciprocal of Q(P-FAIR) and there fore can be converted into a continued fraction of the same form. If however (P—AIR)/Q is negative, we must first write it in the form A + (P'-1,IR)/Q, where A is a negative integer and (P'-1IR)/Q is positive, which is always possible, and con vert (P'—iIR)/Q into a continued fraction.

A recurring continued fraction is said to be pure when all the quotients recur, mixed when there is a non-recurring part. The value of a pure recurring fraction is always of the form (P -+ AIR)/Q, being the positive solution of the equation -}- where and are the last and penultimate convergents of the terminated fraction formed by the cycle of recurring quotients. It follows imme diately that the value of a mixed recurring fraction is of the form (P + AIR)/Q. Two conjugate surds have the same cyclic part in their development. The continued fraction corresponding to surd of the form SIR/Q, where has a particular form. It is of the form b -+ I • • • i i • • • , the recurring -+ 62+ + 2b+ quotients being ... 2b and possessing the property b2 =. = etc. The convergents possess the property that where is one of a recurring cycle of integers. If p/q is the convergent correspond ing to the last partial quotient of a cycle, and p'/q' the preceding convergent, then = + the upper or lower sign being taken according as p/q is an even or odd convergent. These properties of the recurring continued fraction lead to the solu tions, when they exist, of the Diophantine equation — = +a, where x, y, N, a are integers and N is not a perfect square. (The particular case of this equation, r, is commonly known as Pell's equation, though Pell's connection with it is simply that he published the solutions given by Brouncker and Wallis. The equation itself was proposed by Fermat as a chal lenge to the English mathematicians. The complete theory of these equations was given by Lagrange.) The case of a> ,IN can be made to depend on that of a < -IN, and in this case x/y must be a convergent to the continued fraction which is the development of AIN. Since for every such convergent pn2 — = (— r) n1M1 where is one of a fixed cycle of numbers, the equation is either not soluble at all or admits of an infinite number of solutions. In particular the equation i is always soluble, x/y being a penultimate convergent to the suc cessive or alternate periods of the fraction corresponding to -IN. The equation — I has no solution if the number of quotients in the period of the fraction is even. If the number of quotients is odd, the solutions are given by the penultimate convergents in the alternate periods of the fraction. If x', y' is a particular solution of then another solution is X, Y where X+ YIN = (x' -F y'A!N) r, r being any integer. If p, q is a particular solution of so is px'±Nqy', py'±Nqx', and it may be shown that all possible solutions of both equations are of these forms. That the equation — — I cannot always be soluble is clear from the fact that N, being a factor of r, must be the sum of the squares. It is not true however that the equation is necessarily soluble if N is the sum of two squares. The equation — r is not soluble. In fact with N = 8, the only soluble equations are — = I, = — 4. Applications to Irrational Numbers.—Some other applica tions to irrational numbers may be mentioned. If two irrationals x and y are connected by a relation of the form x= (ay+b)/(cy+d), where a, b, c, d are integers, such that ad — be = ± r, then in the developments of x and y as regular continued fractions the partial quotients, after some fixed term, of one must coincide with the partial quotients, after some fixed term, of the other. In particular, if n, an index v can be found such that > pv/qv being the convergent corresponding to bp, then the irrational number x is transcendental; that is, it cannot be the root of an algebraic equation with rational coefficients.

General Continued Fractions.

The general continued frac tion differs in many respects from the regular continued fraction. In particular, the representation of a number as such a fraction is not unique, the value of an infinite continued fraction is not necessarily irrational, nor do its convergents necessarily tend to a finite limit. For example, it is easily verified that the nth con I I ...and I I I ••• - - 2— 2— 2 COS 2 COS 2 COS are n/(n •+ I) and sin nO/sin (n + I)6 respectively. The con vergents of the first fraction tend to the rational limit unity, the convergents of the second tend to no definite limit. The functions and the numerators and denominators of the nth convergent to the fraction + • • • , are algebraicintegral functions of ... ... They are called cumulants or continuants and can be studied as integral algebraic functions. It is also possible to exhibit and as determinants and their properties can be derived from the properties of determinants. The determination of pn and de pends on the solution of the difference equation u„= which may sometimes be solved by the methods of the Cal culus of Differences (q.v.) . In particular, if b==b and a„= a always, is of the form Aan+-BO", where a and /3 are the roots of the quadratic = ax+- b and A and B are constants deter mined by the values of and If the fraction is recurring, al a2 an al a2 an alsay + b2+ +bn + b, + b2+ + bn + bl+ ... , then, if a, v,. denotes the rth convergent, we have = bl+ + b n r leading to a relation of the form =o, where A, B, C, D are constants, a standard type of soluble differ ence equation. By the use of this solution we could determine any convergent of a recurring fraction with non-recurring ele ments at the beginning. As an instance of a fraction that can be I evaluated, consider Brouncker's fraction, i + 2 + 21-21- ... .

We have

= (2n - I) if = or This relation may be written as (2n- 2n- I whence (2n+I)pn-1= . . . -(2n-I)(2n-3) ... 3.1 (2n+ I)qn-1= (2n- I) (2n -- 3) ... 3 (q2 - 3q1) =0, from which we easily find that the nth convergent is the sum of the first n terms of the series I - I +• I - I + • • • , Gregory's 3 5 7 series for Hence the value of the fraction is ter.

The question of the convergence of the general continued

fraction is a matter of great difficulty, except in the case in which all the elements are positive.

The fraction

? al + • can be converted I I I b°4- + d2 + dB+ • •where ' = d2= = etc. If all the elements are positive the necessary and sufficient condition that the fraction should be convergent is that the series ... should be divergent.

There are no general conditions, both necessary and sufficient,

for the convergence of continued fractions whose terms may be negative or complex, and sufficient conditions are not of a simple kind. One case may be mentioned. The continued fraction continued fraction b - • • • converges to an irrational num 1 ber if is never less than and is infinitely often less than an+ I. These conditions, though sufficient, are not necessary.

A type of fraction which has some analogies with the regular

fraction is the semi-regular fraction. A fraction is said to be semi-regular when I, is a positive integer, bn+an+1 is not less than I, the last denominator exceeds I if the fraction terminates, and bn+an+l is not less than 2 infinitely often if the fraction is infinite. A real number x can be expressed in one way only as a semi-regular fraction, in which the ± determination of the ambiguities of the successive a's is specified. The fraction terminates if x is rational and is infinite if x is irrational. A pe riodic semi-regular fraction is a quadratic surd. A semi-regular fraction can always be converted into a regular fraction.

Conversion of Series into Continued Fractions.

A con tinued fraction can be found, whose convergents are the elements of any assigned sequence of numbers. In particular, if we take the sequence ... ... and take ... qn= I, we have = (I + un/un-1) Pn-1 —" pn-2un/un_i •, qn = (I + un/un-1) qn-1 — qn-2un/un-1 , so that, if we form the fraction, whose nth partial quotient is - and adjust the first term to give p, = P2 = I, = I, this fraction will be such a fraction. It can be simplified into the form ul U2 U1U2 un—lun I — ul+U2 — — Un--l+un a result given first by Euler.

A problem of a different character is the representation of an

infinite series of the form ... as a continued ao a,x fraction of the form — • • • , where ... are I - I - I independent of x. The formal expressions for ... in terms of ... by means of determinants have been given by T. Muir (Edinburgh Trans., vol. 2 7) . There remains always, of course, the question of convergence to be considered. Some particular cases were known in the i8th century; for example, if F(n, x) = I+•x/(I ! ! 7+n 7+n+I)+ ... then x x x •••.

+ 7+1 +

7+2 + + 7+n + In particular we can deduce that 2 tan x= - x • • x2 x x • • • and tan hx = I - - 2n+I - I + From these we can show that 7, and any rational power of e are irrational, results given in the i8th century by the German mathematician Lambert. An extension of these results to the ratio of two hypergeometric series has been given by Gauss.

Applications of this type of continued fraction have been made

to definite integrals. For example x x x x 2X 2X a result obtained 0 by Euler. Under certain conditions, definite integrals of the form I called Steiltje's integrals, can be represented by z+x convergent continued fractions of the form + b2- + b3z Any further discussion is beyond the scope of this article but a good idea of the principle can be found in a paper by L. J. Rogers in vol. 4 of the London Mathematical Society's Proceedings.

BIBLIOGRAPHY.

O. Perron, Die Lehre von dem Ketten-briickenBibliography.—O. Perron, Die Lehre von dem Ketten-briicken (1913) is complete on both the arithmetic and the function-theory sides. The arithmetic side is dealt with in most treatises on algebra, very thoroughly in G. Chrystal, Algebra and in great detail in J. A.

Serret, Cours d'Algebra. Full details of the history and development can be found in the Encyclopaedie der mathematische Wissenschiiften (Leipzig in progress) or in the French edition of the same work (Tome I., vol. I., pp. 282-317). (A. E. j.)