4.4 Applications to the theory of numbers

Let it be required to solve

by integral x and y.

Obviously, Equation (1) cannot be solved, if there is a common factor of a and b other than ± 1, whence assume that a and b are relatively prime. Since a : b can be represented by an even continued fraction (cf. 4.2.1 Theorem 1).

Hence one obtains the integral solutions

Solve by integral x and y Pell's Equation*

* Solved by Rahmagupta (born 598 A.D.) and independently by Fermat (1857). The name has no historical justification, but is commonly used. (L.E. Dickson, History of the theory of Numbers, Vol. II; B.B. Datta and A.N. Singh, History of Hindu Mathematics, Part II.

It follows from 4.3.5 that ); on applying the corollary, it is found that

Hence, if n is even (x, y) = (P_kn, Q_kn) and if odd, (x,y) = (P_2kn,Q_2kn) are solutions for every positive integral k.

Example:

This method yields the solutions

4.5* Continued fractions with elements f(x)

*This section may be omitted during a first reading.

The general method of continued fractions, the elements of which have been given in 4.1, can be applied to different fields K. In 4.2, 4.3, 4.4, the field of real numbers has been chosen for K and the expansion of a positive real number into a. continued fraction with integral elements studied. Thus, the positive real numbers formed the system A and the Integral numbers the domain S, referred to in the general theory. The expansion of positive numbers into continued fractions has yielded the opportunity for an approximation of real numbers by rational numbers. There arises now the question, whether in a similar manner power series in terms of an indeterminate x^-1 can be expanded into continued fractions with polynomials in x as their elements and whether by this method the power series can be approximated by quotients of polynomials. Approximation always means that for a certain entity, which is to be approximated, an infinite sequence of approximating entities can be constructed such that the differences between the approximated and the approximating entities can be made arbitrarily small. Thus, an approximation implies that these differences are measurable and a sequence approximating an entity may be made non-approximating when a different method of measurement of the differences is adopted. In the theory to be given here, the power series are measured by their degrees - integral numbers; the measurement does not imply that attention has been given to convergence. The theory is therefore so general that nothing must be assumed regarding the field of the coefficients of the power series. On the other hand, this generality makes it necessary to define afresh sums, products, etc., of power series. This definition must be done in such a manner that it agrees with the definitions for the corresponding operations on polynomials for the case when only a finite number of coefficients differ from zero.

4.5.1 The field B: Let F be an arbitrary field and x an indeterminate not included in F. The elements of F will be denoted by a, b, c, d with or without subscripts, the elements of the ring F[x] by

The integral domain F[x] will be chosen as S. In order to get a new system A, create the new elements denoted by Greek letters

in the following manner:

This purely formal definition means that there corresponds to every sequence of coefficients from F with fixed decreasing integral subscripts

;

one of the new elements and this element will not be changed if one places before a_n a finite set of null coefficients. The addition and multiplication of Elements (2) will now be defined in such a manner that the elements (2) for which a_k = 0, form for k < 0 a sub-ring isomorphic to F[x].

Definition: Let

where

then

where

This definition is obviously independent of null coefficients which have been placed ahead, the commutative, associative and distributive laws apply, and subtraction is defined by

Hence, for the null elements, every coefficient is 0. If for the coefficients of y(x) one has the conditions b_k = 0 for k ¹ 0, then in "]

The elements (2) form a ring B and those elements, for which a_k>0 = 0, form a sub-ring for which addition and multiplication have been defined in the same manner as for polynomials. Hence, there is an isormorphism I by which this sub-ring becomes isomorphic to F[x]. Let f(x) ¹ 0, then f(x) has at least one coefficient ¹ 0 ; let n be the highest index of the non-vanishing coefficients, then

and n is said to be the degree of f(x). From (4) follows directly:

The degree of a product is equal to the sum of the degrees of the factors.
The degree of a sum of elements of different degrees is equal to the maximum degree of the summands.

This remark shows that a product of two elements ¹ 0 cannot be equal to 0. Hence the ring B is an integral domain. Now, identify the elements of F[x] with the corresponding elements (2). For polynomials ¹ 0 of F[x], the degree tallies with that of B, but the zero element, which is a polynomial of degree -1 in F[x], has no degree when considered as an element of B.

The elements

for k ¹ 0 are identified with b₀ and

Let

then

Every field with B contains the quotient field Q of F[x]. The elements of B, which are quotients of elements of F[x], form a ring which is isomorphic to a sub-ring of Q. The elements of this ring will therefore be identified with the corresponding elements of Q. Thus, y_k(x) is identified with x^-k and the finite sum with the symbolic sum where a_k = 0 for k < -m.

Using this notation, one can extend the algorithm of division of polynomials to the elements of B.

Let f(x) and y(x) be of degree n and m, respectively, where n ³ m, and a_n and and b_m their highest coefficients,

Repetition of this procedure yields

and eventually one obtains an enumerable set of elements c_k of F for k £ n - m, so that

and

is of degree n_p+1 < n_p.

Let

then w_p(x) is of degree n_p+1 - m, whence y(x)w_p(x) is of degree n_p+1,

of degree < n for every n, whence this difference is 0. Hence f(x)=y(x)c(x). As y(x) was assumed to be an arbitrary element ¹ 0 of B, one has the

Theorem: The set B of the elements (2) is a field containing the quotient field Q of F[x].

4.5.2 Expansion of the elements of B into continued fractions: The general theory of continued fractions which has been explained in 4.1 can be applied to the expansion of elements of the type f (x), if the field B is taken for K, the domain F[x] for S and the system of the elements with non-negative degree taken for the system A. It is readily proved that those elements satisfy the conditions required for elements of a system A (cf. 4.1.1). Naturally, an element has a positive degree if and only if its inverse has a negative degree.

Now,

Hence either

where degree (y(x) > 0.

The. representation (1) of f (x) is uniquely determined, whence there exists an expansion of f (x) into a continued fraction. The first element s₁ = f(x) may have any degree ³ 0 or it may be the zero element, whereas the second element s₂ (if any) can be assumed to have a positive degree; the same applies to s₂,s₃,···. If this is assumed regarding the degrees, the expansion is uniquely determined , whence follows the

Theorem: The elements 4.5.1 (2) can be represented in one and only one manner by a continued fraction (s₁, s₂, ···), where s_i is a polynomial in x, the degree of which is > 0 for i > 1.

The degree of a polynomial s has just the properties of the function N(s) in 4.1.2. From that section and the preceding theorem follows the

Corollary: Finite continued fractions represent the elements of Q and every element of Q is represented by a finite continued fraction.

4.5.3 Approximation by rational functions: The elements of B can be approximated by finite continued fractions, the elements of which are polynomials. The following theory of approximation has great analogy with the approximation of real numbers by finite continued fractions with integral elements explained in 4.2; the same formulae of the general theory (cf. 4.1) will be applied. Whereas the real numbers have been approximated in such a way that the absolute value of the error was made smaller than any positive number, the elements of B will he approximated with an error the degree of which diverges to -¥. If the field F of the coefficients consists of numbers, the functions of x, which are the elements of B, are numerically approximated by the continued fractions for absolute values of x which are sufficiently high. Thus, the method can be used for numerical approximation of the asymptotic behaviour of those functions.

Let an element a₁ of B be expanded into a continued fraction (s₁, s₂, ···), which satisfies the conditions of the preceding theorem, and

Hence d₁, d₂, ··· are positive integers. Apply the notation of 4.1; then, since a_i=s_i+1,

degree a_i = d_i . (2)

Moreover, since a_i =a₁:a _i+1, it follows that

whence

By the general formulae

whence, for i = 2, 3, ···, Q_i has a positive degree. By mathematical induction, it follows that these degrees increase steadily with i so that

Now,

whence this formula with (3) and (4) yields

The right hand side of (5) can also be expressed by - degree (Q_k,Q_k-1), whence it is equal to degree This show that, when a₁ is approximated by its k-th convergent, the degree of the error is the same as the degree of the difference between the k-th and the (k + 1)-th convergent. It is now easy to prove a theorem analogous to that for the approximation of real numbers in 4.2.2

Theorem:

Proof: Set

As b is the sum of two elements of B, where the-first term has a higher degree than the second term, its degree is the same as the degree of the first term, whence follows from (5)

On the other hand, bg(x) Q_k is a polynomial in x and differs from zero, whence

substituting the value of the degree b from (6), one obtains

Exercise:

Represent this function by a continued fraction and approximate it by rational functions.

4.5.4 Continued fractions with polynomial elements: In order to develop a theory of expansion of the elements of B in continued fractions analogous to the corresponding theory for real numbers, it must be shown that every infinite continued fraction of the type considered here is indeed the expansion of an element of B. This objective is assisted by the

Lemma: Let a = (s₁ ···), a ' = (s'₁ ···) be finite or infinite continued fractions, let m be the lowest subscript for which s_m ¹ s'_m or for which s_m, but not s'_m exists and (s₁, ··· , s_m) = A, (s'₁, ··· , s'_m) = A', then

Proof: Wthout loss of generality, assume that degree s_m = r ³ degree s'_m=r'. The ordinary notation will be used for the convergents of a, while those of a ' will be distinguished by an apostrophe. Then

Now,

Two different cases must be considered:

1. Let r = r'; as degree (s'_m - s_m) ³ 0,

2. Let r > r'; then degree (s'_m - s_m) = r, and therefore

Hence, in each case,

Now, by (1),

and

Hence,

degree (A')a - a') = degree [(A - A') - (A - a) + (A' - a')] = degree (A - A'),

since the degree of the first one of the three summands is larger than the degrees of the other two.

Theorem: Let s₁, s₂, ··· be an infinite set of polynomials of F[x] and for i > 1, degree s > 0, then there exists a continued fraction (s₁, s₂, ···).

Proof: The set s₁, s₂, ··· determines uniquely the values P₁, ··· , Q₁, ··· and P_N:Q_N = (s₁, ··· , s_N). Let 1< n < N ; by the preceding lemma,

degree (P_N:Q_N-P_n:Q_n)=degree(1/P_n+1:Q_n+1-P_n:Q_n)=degree (1/Q_nQ_n-1)=-k_n,

where k_n increases to infinity with n.

The coefficients b_k are independent of N. As k_n increases with the subscript n, one gets an infinite set b_m, ··· , , ···, which determines

Finally, it has to be proved that f(x) = (s₁, s₂, ···). Let f(x) = (s'₁, s'₂, ···) and m be the smallest subscript for which s_m ¹ s'_m, then, by the lemma, for every n>m

since both sides are equal to the degree ( (s'₁, ··· ,s'_m) - (s₁, ··· ,s_m)). However,

is of degree - k_n which decreases infinitely with n. Thus, there is no subscript like m, whence follows the theorem.

4.6 Continued fractions with rational elements: Let S be the field of rational numbers, then every finite continued fraction

represents a rational number, but an infinite continued fraction determines a number by approximation, if and only if

converges. I the sum is convergent,

determines a real number equal to (2). Hence a necessary condition for the convergence of (3) is

If each of the numbers Q_n are either > or < 0, or have alternating signs, the sum (2) is an alternating sum; hence, in these cases, the continued fraction converges if |Q_n Q_n-1| increases steadily to infinity.

4.6.1 Convergence of continued fractions:

For the continued fractions considered above, certain criteria of convergence will now be established. In these investigations, every sequence (series, continued fractions) which does not converge to a real number will be said to be divergent.

Theorem 1: If S|s_n| is convergent, 4.6 (3) diverges.

Proof:. At first, it will be shown by mathematical induction that

Since Q₁ = 1, Q₂ = s₂, the formula holds for n < 3. If (1) is true for n < m, it follows from

that

If Ss_j converges, the infinite product P(1 +|s_j|) converges to a positive number Q, and |Q_n| < Q holds for every value of n, whence 4.6 (4) above does apply and the continued fraction diverges.

Let s_j > 0 for j > 1. By mathematical induction, it follows from Q₁ = 1, Q₂ = s₂ > 0, Q_n = s_nQ_n-1 + Q_n-2 that each number Q_i > 0.

4.6 (2) is therefore an alternating series the absolute values of the elements of which decrease steadily. This series converges therefore if and only if 4.6 (4) is satisfied. These considerations lead to

Theorem 2: Let s_i > 0 for i > 1, then the continued fraction 4.6 (3) converges if and only if Ss_i diverges.

Proof: If converges, the continued fraction diverges, as has been proved by the preceding theorem.

Let Ss_i diverge, then Ss_i ® ¥. Since Q_i > 0, Q₁ = 1, Q_2n+1=s_2n+1Q_2n+Q_2n+1, one finds by mathematical induction that Q_2n+1³1. Hence

Q_2n=s_2nQ_2n-1+Q_2n-2³s_2n+1+Q_2n-2

and, since Q₂ = s_2n, it follows by mathematical induction that

If the sum (2) diverges with steadily increasing n,

whence 4.6 (4) is satisfied. However, if (2) converges, then Ss_i+1 diverges, whence Q_2n+1 ³ s₂(s₂ + ··· + s_2n+1) diverges with increasing n. Thus 4.6 (4) applies in every case and this condition implies the convergence of the continued fraction in the case under consideration, whence follows the theorem.

4.6.2 Test of irrationality: The preceding investigations can be used to prove the irrationality of certain numbers.

Let s₁ = 0, s ³ 1. As Ss_i ® ¥, the continued fraction converges by the preceding theorem. The limit lies between the convergents with odd and even subscripts, i.e., between P₁ : Q₁ = 0 and P₂ : Q₂ = 1: s₂. It will now be shown that this value is irrational

Let a₁ = ( s₁, s₂, ··· ) be rational, say a₁ = a₂/a₁, where a₁, a₂ are integral, then a₁ > a₂ and a₂/a₁ = - 1/(s₂ + a₂), whence a₂ = a₁/a₂ - s₂ = a₂/a₁, where a₃ = a₁ - s₂a₂ is integral. Since a₂ = (0, s₂, ···), one has 0 < a₂ < 1, whence a₂> a₃ > 0. In the same manner, one finds

This procedure must end after a finite number of steps, as a sequence a₁>a₂>a₃>a₄> ··· of integral positive numbers cannot be continued indefinitely. Since the continued fraction has been assumed to be infinite, the assumption of a₁ to be rational leads to a contradiction. Hence a₁ is irrational.

Example: If

then

and by the identities

by mathematical induction,

whence

and the continued fraction is irrational. Its value is

i.e., the number e is irrational.

last next