2 Confrac expansion of a real number

Definition 2.1   The confrac expansion of a real number is the integer sequence obtained by the recursion :

followed to infinity... or until for some , the later case only occurring when . From an obvious similarity with Euclidean algorithm, the are called (ordinary) quotients and the complete quotients. It is clear that while the other quotients are positive integers and, at any step, we have the continued fraction relation :

It is well known that a fractional-linear relation like (where is assumed) can be rewritten in the projective plane as . We therefore introduce matrices that represent transformation .

Notation 2.2   In order to avoid "towers of indices", we introduce two different notations for these matrices. Without special context, we will use:

In the context of the confrac expansion of a given , we will use:

The following two theorems are the founding stones of the continued fractions theory.

Theorem 2.3   For any number and all , the relation

holds, where the and are defined by the recursion:

Moreover, the fractions (the so-called convergents) are in lowest terms. When is rational, "all " must be understood as "all until the process stops".

Proof. When , relation 2.4 is nothing but the obvious . Using induction and the fact that composition of homographies multiplies the associated matrices, we obtain

By the way, we have obtained , and fraction is in lowest terms.

Example 2.4   Taking , we have

Leading to the matrices of FIG. 2.1.

FIG.  2.1: Elementary matrices appearing in the confrac expansion of .

For example, result in .

Remark 2.5   Thanks to the above mentioned irreducibility, the identification fractional-linear transform towards matrix is non-ambiguous (no proportionality factor can occur).

Theorem 2.6   Any matrix encountered in the confrac expansion of a given and written as verifies the following assertions:

Conversely, any matrix having these properties is an matrix, i.e. can be decomposed into a product of matrices :

Moreover, this decomposition is unique.

Proof. The direct part of this theorem is an immediate application of theorem 2.3, while the reciprocal part is equivalent to the correctness of algorithm 2.9.

Corollary 2.7   Therefore an irrational number is characterized by its confrac expansion, and can be written as

Lemma 2.8   Relation cannot be satisfied with , and .

Proof. Otherwise, one should have:

Algorithm 2.9   The factorization into elementary matrices must be carefully designed to take in account all cases where any of the numbers are 0 or . Otherwise, lemma 2.8 shows that is the sole and only left factor of the given matrix, being the common value of the Euclidean quotient of by and of by .