TAOCP 4.5.3 Exercise 11
Let X=A_0+//\!
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}. $$
If
$$ 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$