Chapter IV

In the second case, a ' can be approximated again by an integral number, and so on. This method leads to the representation of real numbers by continued fractions* with many interesting properties, which will be considered in 4.2 and 4.3. However, the underlying principle is more general; for the integral numbers as well as for the real numbers > 1, one may substitute other systems of mathematical objects. The interconnection between the system A of the real numbers > 1 and the domain of the integral numbers which has been used in the consideration above and which will be used in the general part of the theory is only the following:

1. The system A and the domain of the integral numbers are sub-sets of the same field (the field of real numbers.
2. In this field, the domain generates a partition into classes of residues, and the elements of A are distributed among these classes in such a way that, if any element a of A belongs to a particular class, then the same class contains an element b = a - s which is the inverse element of an element a ' of A, unless the class of residues is the class (0), i.e., the class formed by the domain itself.

* or simple continued fractions. Since this book does not use any other class of continued fractions, the term is here applied in this special sense.

Thus. the investigation of continued fractions will start here from a field K containing an integral domain.S and a sub-system A which are interconnected in the manner which has just been explained

4.1.1 Convergents of a continued fraction: Let K be a field, S an integral domain in K and A a subset of K with the property: If a class of residues ¹ (0) of S contains an element of A, this class contains also the inverse of an element of A. Hence, if

The representation of a₁ by (5) is said to be a continued fraction. The sequence of the formulae (4) can be continued indefinitely unless there is an element a_i which is an element of S. If there is m such that a_m= s_m, then it is a finite continued fraction, otherwise it is an infinite continued fraction. If acan be represented by a finite continued fraction, it belongs to the quotient field Q of S and every finite set of elements

Let a₁ be an arbitrary non-zero element of K, then a sequence of elements a₁, a₂, ··· , a_n+2is determined uniquely by

After multiplication of the first equation (12) by Q_k-1, the second equation by -P_k-1 and subsequent addition, (9) yields

Hence, if a continued fraction is finite, say a_n = s_nand therefore a_n+2 = 0, then

as may be applicable. Conversely, let a₁ = (s₁, ... , s_k-1|a_k) and a_k be given by (5'), then the expansion of a₁ into a continued fraction yields (5') or (6'), corresponding to the two cases of (5"). Set k = t; since a_t, a_t+1, ... are complete fractions obtained by expansion of a_t into a continued fraction, it follows from (1) that

Hence, application of (12), (13), (14) and (9) to the expansion of a_t into a continued fraction yields the system:

4.1.2 Finite continued fractions. Without loss of generality, it may be assumed that all the elements of the quotient field Q(S) of the domain S belong to the set A. As the terms P_n and Q_n of any element a_i of A belong to S, their quotients belong to Q(S). In particular, the expansions of P_n:P_n-1 and Q_n:Q_n-1 in the homogeneous form (4') of 4.1.1 can be derived directly from the expansion of a₁:

If S is the domain of the integral numbers, it is easy to show (as will be proved below) that an element can be expanded into a finite continued fraction if and only if it belongs to the field Q(S) which - in this particular case - is the field of the rational numbers. It is interesting to study the same question under more general conditions; a close connection between continued fractions and the factorization of S will then become apparent.

Let a₁ be represented by a finite continued fraction a₁ = (s₁ ··· , s_n). Then a_n:a_n+1=a_n= s_n, whence (12) and (14) of 4.1.1 yield

Every common factor of a₁ and a₂ is a factor of a_n+1, and a_n+1 is a common factor of a₁ and a₂. Hence a₁ and a₂ have an h.c.f. and it can be represented linearly by a₁ and a₂. Especially, a₁ = P_n : Q_n is a representation by two relatively prime elements of S, since

Now let every element of Q(S) be representable by a finite continued fraction and s', s" -~ 0 be two arbitrary elements of S, then s' : s" = a can be represented by two relatively prime-elements of S, so that 1 can be represented in a linear and homogeneous manner by those elements. Hence

Thus, s' = ps, s'q' + s"p' = s, and the arbitrary elements s',s" of S have an h.c.f. (s', s") = s which is represented in a linear and homogeneous manner by s' and s". Thus, S is a Euclidean domain (cf. 2.4.4).

Hence, if S is an integral domain other than a Euclidean one, not every element of Q(S) can be represented as a finite continued fraction, although all these fractions belong to Q(S). The system of all the finite continued fractions is a sub-set of Q(S) which contains S, whence it is not a field, unless S is a Euclidean domain.

Let there be defined a function N(s), which takes only positive integral values for every element s ¹ 0 of S, and exist for every pair of elements s, s' of S two other elements s₁ and s", so that

are all integral numbers, the sequence s', s", ··· must be finite, whence s:s' is a finite continued fraction and there follows the

Theorem: Let S be an integral domain and there be defined a positive integer N(s) satisfying Conditions (3) for every element s of S, then Q(S) will be formed by the finite continued fractions of S and the highest common factor of two elements a₁ and a₂ of S is given by a_n+1 in (2), where P_n-1, Q_n-1 have the same significance as in 4.1.1.

If S is the domain of the integral numbers, N(s) =|s| satisfies (3), whence every rational number can be expanded into a finite continued fraction with integral elements and, conversely, every finite continued fraction with integral elements represents a rational number. In general, the elements of S are not supposed to be factorizable; in particular, the condition N(ab) ³ N(a), stated in 2.4.2 may not hold. If it holds in addition to (3), then S is a Euclidean domain and therefore the factorization in S is unique (cf. 2.4.4).

4.1.3 Proper and improper equivalence: Equations (12), (13) and (14) of 4.1.1 show that the complete fractions a₁, a₂, ··· of a continued fraction are interconnected by linear equations. These can either be expressed in the homogeneous form

The coefficients of this substitution are elements of S and the determinant is equal to ± 1. These substitutions will now be studied more closely. Let A and B be the matrices of such substitutions, say

		transformed by	into	and
1.	a	E	a	"	det E = 1
2.	a '	A'	a	"	det A' = e
3.	a	BA	a"	"	det BA = ee ' = ± 1

An element of K is said to be equivalent to a if it is obtained by transformation by a linear fractional substitution with determinant ± 1. It follows from 1. and 3. above that this equivalence satisfies the conditions of reflexivity, symmetry and transitivity (cf. 2.1.2), whence this equivalence defines a partition of K into classes, so that two elements of K arc equivalent if and only if they belong to the same class.

transforms the element 1 into s, whence all elements of S are equivalent. By 4.1.1 (8) and (13), all complete fractions a₁, a₂, ··· of a continued fraction are equivalent, In particular, every finite continued fraction (s₁, ··· , s_n) is equivalent to a_n = s_n, whence it belongs to the class containing the elements of S.

An equivalence is said to be proper or improper according to whether detA=± 1 or detA = -1. As det A = det A', the notion of proper equivalence as well as that of improper equivalence is symmetric. Combination of two equivalences of the same kind yields a proper equivalence, of two different kinds an improper equivalence. Every element is properly equivalent to itself, because the matrix E has the determinant 1. If in a class of equivalent elements an element is also improperly equivalent to itself, i.e., if it is transformed into a by E' and det E' = - 1, then an arbitrary element b of the same class is transformed into a by B and by E'B. One of these matrices has the determinant 1, the other the determinant - 1, whence each element of the class is properly and improperly equivalent to a, so that every element is at the same time properly and improperly equivalent to every other element of the class. On the other hand, if a is transformed into b by A as well as by B, where det A = 1, det B = -1, then a is transformed into a by A'B, where det A'B = -1, whence a is improperly equivalent to itself, so that in this case every other element of the class (a) is properly and improperly equivalent to every other element of (a). If there are in (a) pairs of elements which are properly as well as improperly equivalent, then (a) must be divided into two classes without common elements; the elements of the first class are properly, those of the second class improperly equivalent to a. Elements of the same sub-class are properly equivalent, elements of different sub-classes are improperly equivalent, whence follows the

Theorem: In a class of equivalent elements, either every element is properly and improperly equivalent to every other element or there are two sub-classes without a common element such that elements of the same sub-class are properly and of different sub-classes improperly equivalent.

Since 1 is transformed into itself by

, every pair of elements is properly and improperly equivalent in the class containing the finite continued fractions.

These transformations transform every element ino itself. E and - E generate proper equivalences.

2. The polynomial (2) is reducible in a. This is only possible if a is an element of the quotient field Q of S.

3. The polynomial (3) is irreducible. In this case a is algebraic to Q and of order 2 over Q.

These considerations show that there are elements which are not improperly equivalent to themselves.

Let not all the complete fractions a₁, a₂, ··· of the continued fraction differ, say a_t = a_t+i , then

Hence a_t can be represented by an infinite, periodic continued fraction with the period s_t+1, ··· , s_t+i. It follows from 4.1.1 (17) that a_t is transformed into itself by the matrix

where det D = (-1)ⁱ, whence a_t is made equivalent to itself by that transformation. It follows from 4.1.1 (13) that

whence it belongs to the field Q(a_t). Hence [Q(a_t) : Q] £ 2, whence a satisfies a second degree equation with coefficients from Q, and as Q is the quotient field of S, one can arrange by multiplication by a common factor that the coefficients belong to S. The same applies to a₂, a₃, ···.

Now, let there be given a periodic sequence a₁, ··· , a_m, a₁, ··· , a_m, ··· of elements of S. Then one does not know whether there exists in any extension of the quotient field Q of S an element representable by the infinite periodic continued fraction

and if such an element exists, it may not be uniquely determined in the field. But if there is a field in which there exists one and only one element a, represented by the periodic continued fraction (3), then

and therefore a is a root of a quadratic polynomial an S[x]. The same applies to

as this number can be transformed into a by a linear transformation in Q.

Hence in the representation 4.1.1 (4) of any positive a as a continued fraction,

As has been shown in 4.1.2, rational numbers can be represented by finite continued fractions.

Let a₁ be a rational number ³ 1. If a₁ is an integral number, then there exist its two representations corresponding to the two cases (1)

If a₁ is not integral, a₂ is uniquely determined by a₁; if a₂ is not integral, a₃ is uniquely determined by a₂, etc. Changes in the sequence a₁, a₂, ··· are not possible as long as those elements are not integral; a₁ admits a representation by a finite continued fraction, the last complete fraction in it is necessarily integral. Let a_r+1 (if r > 0) be the first integral complete fraction which occurs; then a_r = s_r + 1: a_r+1 is not integral: 1 < a_r+1 = s' + 1, where s'>0. Thus, there are two possibilities for the continuation of the continued fraction:

If a₁ > 1 is irrational, then s₁ > 0, and a₂, a₃, ··· are uniquely determined, none of them being rational, whence there exists one and only one representation satisfying (2) and this continued fraction is infinite. If 0 < b < 1, then 1/b =a >1 and b = (0|a). The essence of these considerations is given by

Theorem 1: Every positive number can be represented as a continued fraction satisfying Condition (2). If the number is irrational, the representation is unique and the continued fraction is infinite. If the number is rational, there exist two representations, one by an even finite, another by an odd finite continued fraction.

It will be proved now that the converse theorem also applies, i.e., that every sequence, satisfying (2), determines one and only one real number.

These inequalities hold independently of whether there exists a number a=(s₁,s₂, ··· ,) or not. In particular, let there exist a₁, then P_k : Q_k are its convergents (for k = 1,2, ···); applying the homogeneous notations a_i=a_i:a_i+1, as in 4.1.1, one may select a₁ > 0 ; then every a_i is larger than zero. Therefore (cf. 4.1.1 (15))

Now, the finite continued fractions s₁, s₂, ··· , s_n= P_n : Q_n exist anyhow (even if s₁, s₂, ···does not exist) and (s₁,···, s_k ) is its k-th convergent, provided k < n. Applying (5) to a₁ = P_n/Q_n, one obtains for n > 2m

whence the quotients P_n/Q_n form two sequences, one increasing, the other decreasing, and every number of the first sequence is less than every number of the second sequence. The intervals

(cf. 4.1.1 (10), the length of which converges to 0. Hence there is, for every given sequence (2), one and only one real number a such that

If there exists a number a₁=(s₁,s₂,···), then a₁ must satisfy the inequalities (5); thus comparing (5) and (7), it follows from the uniqueness of the solution of (7) that a = a₁, provided that there exists a number which can be expanded into the infinite continued fraction (s₁, s₂, ···). For proving the existence of this number, one has the

Lemma: If t is a positive integral number, (s₁,···,s_n,s_n+1)=A, (s₁,···,s_n+t)=B, then

In a similar manner, one computes the difference (s₁,···, s_n - t) - (s₁,···, s_n). Denote the last convergent of the first term by P" : Q" and the other convergents as usually, then (Q_n - Q") : Q_n-1 = t, whence

when n is even and t > 0, whereas for an odd n and t > 0 hold the opposite inequalities. Again, let P_n : Q_n be the convergents of an infinite continued fraction (s₁,···, s_n) satisfying (2) and a₁ the real number which is uniquely determined by (7). This number admits an expansion into a continued fraction which will be shown to equal (s₁, s₂, ···). If this is not so, let a₁ be expanded into a different continued fraction - an infinite one. Then the expansion can be expressed by (s₁, ···, s_n-1, s , ···), where n > 0, s ¹ s_n. Let s - s_n=t > 0. If n is even, it follows from (5), (7) and (8) that

whereas the converse inequalities apply when n is odd. Hence s > s_n is impossible. If s < s_n, you set s_n - s = t and by interchanging the two expansions show in the same way as above that the assumption leads to a contradiction. Suppose now that the expansion of a₁ is finite; then it follows from (7) that this finite continued fraction cannot be a convergent of (s₁,s₂,···). Hence it can be expressed by (s₁, ···, s_n-1, s , ··· , t), where s ¹ s_n. For s >s_n, the same argument holds as in the case of an infinite continued fraction. Similarly, for s < s_n, provided the finite continued fraction has more than n elements. There remains to show that (s₁, ···, s_n - t) ¹ a₁, but this follows from (10) and (7), since for even n

whereas the converse inequality applies for odd n . Hence a₁ cannot be expanded into any continued fraction which differs from (s₁, s₂, ···), whence it is an irrational number; as every positive number can be expanded into a continued fraction, the expansion of a₁ must be (s₁, s₂, ···) and one has

Theorem 2: Let s₁, s₂, ··· be an infinite sequence satisfying (2), then there exists a uniquely determined number a₁ = (s₁, s₂, ···), which is irrational and does not admit any different expansion into a continued fraction with elements satisfying (3).

4.2.2 Distribution of a continued fraction along the real axis: By the two theorems of 4.2.1, it has been shown that there corresponds to every continued fraction, which satisfies (2), a non-negative real number; rational positive numbers can be expanded into exactly two different continued fractions which are both finite; irrational positive numbers admit one and only one expansion which is infinite, and 0 is expanded into the continued fraction with the only element s₁ = 0.

It is interesting to investigate the distribution of continued fractions along the real axis. The continued fractions with one element s₁ = 0, 1, 2, ··· represent these integral numbers and subdivide the positive half of the real axis into intervals of equal length 1. Continued fractions with two elements are distributed among these intervals as follows: As (s₁,m)=s₁+1/m for every positive integral value of m, (s₁,m) is situated in the interval, which is bounded by s₁ and s₁ + 1, and will be denoted by

. For m = 1, the number (s₁,m) is the right end point of the interval and it converges steadily with m tending to infinity to the left end. Thus, every interval

is subdivided into an infinity of abutting sub-intervals

bounded by (s₁, s₂ + 1) and (s₁, s₂) which covers

except its left end point. Since (s₁, s₂+m)=s₁+(s₂+1/m), each of these continued fractions lies in

and they converge steadily from the left end of

to its right end and subdivide it into an infinity of abutting intervals

. Consider now the interval

which is bounded by (s₁, ··· , s_n), and (s₁, ··· , s_n + 1). Application of the methods and formulae of 4.2.1 yields readily

The right hand side of (1) is a positive number which is equal to 1 if t = 1 and converges steadily to zero as t increases steadily. Hence the points (s₁,···, s_n,t) converge steadily from (s₁, ··· , s_n + 1) to (s₁, ··· , s_n) as t increases; they subdivide the interval

into an infinity of abutting intervals, which cover

with the only exception of (s₁, ··· , s_n). This point is the left or the right end point of

according to whether n is odd or even. There corresponds to every infinite sequence (s₁, s₂, ··· ) satisfying 4.2.1 (2) a sequence of intervals

which form a nest; the convergents of (s₁, s₂, ··· ) are alternatively the left and the right end points of these intervals, whence the nest converges to (s₁, s₂, ··· ). Thus, there exists a (1,1)-correspondence between positive irrational numbers and nests. The end points of the nest intervals are rational numbers and one arrives at a classification of the non-negative rational numbers in the following manner. The first class contains the numbers which can be expanded into continued fractions with only one element - integral numbers, the numbers of the second class can be expanded into continued fractions with two (not one) elements, etc., the m-th class is composed of the numbers which can be expanded into continued fractions with m (not m — 1) elements.

since the central part of this inequality is an integral positive number. Hence,

This theorem shows that the closest approximations of a real number with the aid of rational numbers with limited positive denominators are the approximations by the convergents P_m:Q_m.

Since a lies in the interval bounded by two consecutive convergents P_n:Q_n and P_n+1:Q_n+1, its distance from P_n:Q_n is less than the length of the interval. Hence

where |e | < Q_n:Q_n+1 < 1 and e is positive or negative according to whether n is odd or even. Thus

4.3 Periodic continued fractions with integral coefficients: The elements of the continued fractions, considered in this section and its sub-sections, are assumed to be integral numbers. The first element is positive or zero, the other elements are positive. A continued fraction with a period a_1m, ··· , a_m, say,

In the special case when there are no elements b_j, the continued fraction is said to be purely periodic. In any case, (1) determined uniquely an irrational number; hence it follows from the last paragraph of 4.1.3 that this number is a root of a quadratic polynomial, say f(x) of R[x], where R denotes the field of rational numbers. For the irrationality of the roots, f(x) is irreducible in R[x].

Theorem: Let [L : R] = 2, then every irrational number a belonging to L can be expanded into a periodic, continued fraction.

Expand a into a continued fraction a = (s₁, ··· , s_n, l) ; then (cf. 4.1.1 (5'))

As Q_n increases infinitely with n and b ¹ a, the root m. is negative for sufficiently high values of n, and as l is a complete fraction and therefore positive, lm = k : g < 0. Hence k g < 0 for all sufficiently high values of n. There corresponds to each of these values a partition of the positive number b²-ac = h² - kg (cf. (3)) into two non-negative summands h² and - kg; there correspond to the first term at most 2 values ± h and to the second term a finite number of integral factors k and g. Hence (3) admits only a finite number of solutions g, h, k for which k g < 0. Let now n run over 1, 2, ··· and consider the corresponding polynomials (2); there applies (3) to each of these polynomials h² - kg = b² - ac and the inequality k g < 0 holds for sufficiently high values of n. Hence not all of the polynomials gx² + 2hx + k can differ. There must at least occur one polynomial with k g < 0. This polynomial has exactly one positive root which is equal to the corresponding complete fraction. Hence not all the complete fractions differ, say

is represented by a purely periodic continued fraction and a is represented by a periodic continued fraction.

4.3.2 Purely periodic continued fractions: Let a₁, a₂, ··· be the complete fraction of

Since a_i = a_i+k for i > m, every property which holds for the complete fractions of sufficiently high index applies to every complete fraction of index > m. By 4.3.1, it is known that the root conjugate to a complete fraction of sufficiently high index is negative, whence this property belongs to every complete fraction of index > m, i.e., for every purely periodic continued fraction. In a purely periodic continued fraction s₁ = s_k+1 ¹ 0 (cf. 4.2 (2)), whence these continued fractions represent numbers > 1.

A root l of a quadratic equation is said to be reduced if l > 1, and the conjugate root m satisfies 0 > m >—1. It will be proved now that every purely periodic continued fraction represents a reduced quadratic number.

be two purely continued fractions, the elements s_i being the same in both the continued fractions. but ordered in an inverse manner.

are convergents of x, whence

~. Let b = -1/x, then 0>b>-1 and

, whence b is a root of

Since

a is also a root of f(x) and, since a > 1, the roots a and b differ. The essence of these considerations is the

Theorem: If a is represented by a purely periodic continued fraction (1), it is a reduced quadratic number; let b be the number conjugate to a and x = -1/b ^-1, then x is represented by (2).

Every continued fraction is equivalent to its complete fraction (cf. 4.1.3); in particular, every periodic continued fraction is equivalent to a purely periodic continued fraction, whence

Corollary: Every quadratic number is equivalent to a reduced quadratic number.

4.3.3 Scheme for computations: In order to discover the representation of any quadratic number a by a continued fraction, represent it by

Starting from these formulae, the simple numerical scheme given below furnishes the numbers a, b; a', b', ···, which define uniquely the complete fractions a, a', ··· and the numbers s, s', ···, which define the continued fraction. As this continued fraction is periodic, one pair a, b must be repeated after a finite number of steps. Then the first period is finished and the calculation can be terminated.

The last complete fraction is therefore equal to the preceding one, whence a=(0,1). This continued fraction is the simplest, but the least convenient one for practical computations, because the numbers P_k, Q_k are increasing more slowly than in any other case.

Hence a = 530451/104030 - e, where 0 < e < 10^-1, whence the last two figures are uncertain (cf. 4.2.2 (3)).

Thus Ö2 = (1,2). As P_k, Q_k are increasing very slowly, the method will be applied in a modified form.

Exercises: Prove that

compute Ö2501, Ö82, (Ö7+2)/3, Ö17, Ö3 directly and also using Ö300. Compute Ö(a+1).

Lemma: If a > 1 and b < 0 are conjugate quadratic numbers, a = (s₀,s₁,s₂,···), then all the complete fractions a₁ = (s₀,s₁,···), a₂ = (s₂,s₃,···) are reduced numbers.

Proof: a = s + 1/a₁, b = s + 1/b₁, a₁ and b₁are conjugate numbers a₁ > 1, -1/b₁ = s - b > s ³ = 1, whence a₁ is reduced, and it follows by repetition of this procedure that a₂, ··· are reduced.

Theorem: Every reduced quadratic number is represented by a purely periodic continued fraction.

Proof: Every quadratic number is represented by a periodic continued fraction

. Let this number be reduced and let the periodicity of the continued fraction begin with s₁ only (i.e., let s ¹ s_n), then it follows from the last lemma that (

) is also a reduced number.

We will prove that this is impossible. Using the same notation as in the lemma, we state

but as a and a_n are reduced, 0 < -b < 1 and 0 <-b_n<1; hence s < -1b₁ < s+ 1 and s_n < -1/b_n+1 < s_n+n+ 1. Hence it follows from b₁ = b_n+1 that s = s_n.

If, conversely, (1), (2) and (3) apply, then a is an irrational square root > 1.

Proof: As a > 1 and the number b = -a < 0 is conjugate to a, it follows from the lemma that the complete fractions a₁, a₂, ···of a are reduced, and therefore purely periodic, whence a satisfies (1). Since

This equation implies (2) and (3). Conversely, if a is defined by (1),(2) and (3), then (6) applies.

Let a₁and b₁ be defined by (4) and (5), and b = s +1:b₁, then, by (4) and (3), a₁ and b₁, and therefore a and b are conjugate, and, by (6), a+ b = 0. Hence aand b and are the roots of a rational polynomial tx² + 0x - r. It follows from 0 ¹ s_n = 2s that s ³ 1, and therefore a > 1, and as (1) is an infinite continued fraction, a must be irrational.

Corollary: Let a = Ö(r : t) and P₁ : Q₁, ··· be the convergents of a, then

s₁is a non-negative number and
	(4)
s₂, s₃, ··· are positive integral numbers