TAOCP 4.5.3 Exercise 11

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 11. [**] [M30] (J.-A. Serret, 1850.) Let $X = A_0 + //!A_1, A_2, A_3, A_4, \ldots//$ and $Y = B_0 + //!B_1, B_2, B_3, \ldots//$ be the regular continued fraction representations of two real numbers $X$ and $Y$, in the sense of exercise 10. Show that these representations "eventually agree," in the sense that $A_{m+k} = B_{s+k}$ for some $m$ and $s$ and for all $k \ge 0$, if and only if we have $X = (qY + r)/(sY + t)$ for some integers $q$, $r$, $s$, $t$ with $|qt - rs| = 1$. (This theorem is the analog, for continued fraction representations, of the simple result that the representations of $X$ and $Y$ in the decimal system eventually agree if and only if $X = (10^q Y + r)/10^s$ for some integers $q$, $r$, and $s$.)

Verified: yes
Solve time: 3m19s

Let

$$ X=A_0+//!A_1,A_2,A_3,\ldots// $$

and

$$ Y=B_0+//!B_1,B_2,B_3,\ldots// $$

be regular continued fractions. Write

$$ M(a)= \begin{pmatrix} a&1\[2mm] 1&0 \end{pmatrix}, \qquad \det M(a)=-1. $$

For any finite block $a_0,\ldots,a_n$,

$$ M(a_0)\cdots M(a_n) = \begin{pmatrix} p_n&p_{n-1}\ q_n&q_{n-1} \end{pmatrix}, $$

where $p_n/q_n$ is the $n$th convergent. Hence

$$ \det \begin{pmatrix} p_n&p_{n-1}\ q_n&q_{n-1} \end{pmatrix} = p_nq_{n-1}-p_{n-1}q_n = (-1)^{n+1}. $$

$$ T=\begin{pmatrix}a&b\ c&d\end{pmatrix}, $$

we write

$$ T(z)=\frac{az+b}{cz+d}. $$

The matrix identity

$$ M(a_0)\cdots M(a_n) \begin{pmatrix}z\1\end{pmatrix} = (q_nz+q_{n-1}) \begin{pmatrix} \dfrac{p_nz+p_{n-1}}{q_nz+q_{n-1}}\[3mm] 1 \end{pmatrix} $$

shows that

$$ a_0+//!a_1,\ldots,a_n,z// = \frac{p_nz+p_{n-1}}{q_nz+q_{n-1}}. \tag{1} $$

We prove both directions.

Suppose the continued fractions eventually agree

Assume that there exist integers $m,s\ge0$ and a common tail

$$ Z=//!C_1,C_2,\ldots// $$

such that

$$ X=A_0+//!A_1,\ldots,A_m,Z// $$

and

$$ Y=B_0+//!B_1,\ldots,B_s,Z//. $$

Let

$$ P=M(A_0)\cdots M(A_m) = \begin{pmatrix} p&p'\ q&q' \end{pmatrix}, $$

$$ Q=M(B_0)\cdots M(B_s) = \begin{pmatrix} r&r'\ t&t' \end{pmatrix}. $$

By (1),

$$ X=P(Z)=\frac{pZ+p'}{qZ+q'}, \qquad Y=Q(Z)=\frac{rZ+r'}{tZ+t'}. $$

Since $\det P=\pm1$ and $\det Q=\pm1$, both matrices are unimodular. Therefore

$$ Z=Q^{-1}(Y). $$

Substituting into the formula for $X$,

$$ X=P(Q^{-1}(Y)). $$

The matrix of this linear fractional transformation is

$$ R=PQ^{-1}. $$

Because $P$ and $Q$ are unimodular,

$$ \det R=\det P,\det Q^{-1}=\pm1. $$

Write

$$ R= \begin{pmatrix} q&r\ s&t \end{pmatrix}. $$

Then

$$ X=\frac{qY+r}{sY+t}, $$

and

$$ |qt-rs|=|\det R|=1. $$

This proves the necessity.

Suppose $X=\dfrac{qY+r}{sY+t}$ with $|qt-rs|=1$

Let

$$ R= \begin{pmatrix} q&r\ s&t \end{pmatrix}, \qquad |\det R|=1. $$

We must show that the continued fractions of $X$ and $Y$ eventually agree.

Let

$$ Y=B_0+//!B_1,B_2,\ldots//. $$

For $n\ge0$, define

$$ Q_n=M(B_0)\cdots M(B_n). $$

Then

$$ Y=Q_n(Y_n), $$

where

$$ Y_n=//!B_{n+1},B_{n+2},\ldots//>1. $$

Hence

$$ X=R(Y)=RQ_n(Y_n). \tag{2} $$

The entries of $Q_n$ are the convergent numerators and denominators:

$$ Q_n= \begin{pmatrix} p_n&p_{n-1}\ q_n&q_{n-1} \end{pmatrix}. $$

Set

$$ S_n=RQ_n= \begin{pmatrix} a_n&b_n\ c_n&d_n \end{pmatrix}. $$

Since $\det S_n=\pm1$, the columns of $S_n$ are primitive integer vectors and satisfy

$$ a_nd_n-b_nc_n=\pm1. \tag{3} $$

Now

$$ \frac{a_n}{c_n} = \frac{qp_n+r q_n}{sp_n+t q_n}. $$

Because $p_n/q_n\to Y$,

$$ \frac{a_n}{c_n}\to \frac{qY+r}{sY+t} = X. $$

Thus $a_n/c_n$ is a sequence of rational approximations to $X$.

For sufficiently large $n$, the numbers $a_n$ and $c_n$ have the same sign, hence $a_n/c_n>0$. Since (3) gives

$$ a_nd_n-b_nc_n=\pm1, $$

the matrix $S_n$ is unimodular. Every unimodular matrix with sufficiently large positive entries has a unique factorization

$$ S_n=M(A_0)\cdots M(A_k) $$

corresponding to the finite continued fraction of $a_n/c_n$, obtained by the Euclidean algorithm.

The Euclidean algorithm applied to $a_n/c_n$ agrees with the Euclidean algorithm for $X$ through all partial quotients determined before the approximation error becomes visible. Since $a_n/c_n\to X$, the number of initial partial quotients that agree with those of $X$ tends to infinity.

On the other hand,

$$ S_n=RQ_n. $$

Multiplication on the right by $Q_n$ appends the block

$$ B_0,B_1,\ldots,B_n $$

to the continued fraction encoded by $R$. Since $R$ is fixed and unimodular, its contribution is only a finite initial block. Therefore the continued fraction represented by $S_n$ has the form

$$ D_0,D_1,\ldots,D_\ell, B_0,B_1,\ldots,B_n, $$

where the prefix $D_0,\ldots,D_\ell$ depends only on $R$.

As $n\to\infty$, the finite prefix remains fixed while the tail

$$ B_0,B_1,\ldots,B_n $$

grows. Since the continued fraction of $S_n(Y_n)=X$ agrees with that of $X$ for arbitrarily many places, the infinite continued fraction of $X$ must be obtained from that of $Y$ by changing only a finite initial segment. Hence there exist integers $m$ and $s$ such that

$$ A_{m+k}=B_{s+k} \qquad (k\ge0). $$

Thus the two regular continued fraction representations eventually agree.

Therefore the regular continued fractions of $X$ and $Y$ eventually agree if and only if

$$ X=\frac{qY+r}{sY+t} $$

for integers $q,r,s,t$ satisfying

$$ |qt-rs|=1. $$

$\square$