\documenttype{article}
\title{Continued Fractions and the Euclidean Algorithm}
\author{William F. Hammond}
\subtitle{Lecture notes prepared for MATH 326, Spring 1997\\
          Department of Mathematics and Statistics\\
          University at Albany}

\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beql}[1][]{\begin{equation}[#1][eqn]}
\newcommand{\Ref}[1][]{\anch[iref="#1"]{\ref{#1}}}

\newcommand{\begin{eqnarray}}{\begin{eqnarray}[:nonum="true"]}

\newcommand{\begin{thm}}[1][]{%
\begin{assertion}[#1][theorems]{Theorem}[\evalref{\popkey}]}
\newcommand{\end{thm}}{\end{assertion}}

\newcommand{\begin{defn}}[1][]{%
\begin{assertion}[:style="definition"][#1][definitions]{Definition%
}[\evalref{\popkey}]}
\newcommand{\end{defn}}{\end{assertion}}

\newcommand{\begin{cor}}[1][]{%
\begin{assertion}[#1][corollaries]{Corollary}[\evalref{\popkey}]}
\newcommand{\end{cor}}{\end{assertion}}

\newcommand{\begin{propn}}[1][]{%
\begin{assertion}[#1][propositions]{Proposition}[\evalref{\popkey}]}
\newcommand{\end{propn}}{\end{assertion}}

\newcommand{\begin{rem}}[1][]{%
\begin{assertion}[#1][remarks]{Remark}[\evalref{\popkey}]}
\newcommand{\end{rem}}{\end{assertion}}

\newcommand{\begin{exmp}}[1][]{%
\begin{assertion}[:style="definition"][#1][examples]{Example%
}[\evalref{\popkey}]}
\newcommand{\end{exmp}}{\end{assertion}}

\newcommand{\bibitem}[2][]{\bibentry\bibhead[#1]{#2}}

\mathsym{\Z}{\regch{\bold{Z}}}
\mathsym{\GL}{\mbox{GL}}
\newcommand{\proof}{\emph{Proof.}\ }

\newcommand{\mxtwo}[4]{%
\bal{\begin{array}{rr} #1 & #2 \\ %
 #3 & #4 \end{array}}}

\newcommand{\cvtwo}[2]{%
\bal{\begin{array}{r} #1 \\ %
 #2 \end{array}}}

\newcommand{\floor}[1]{[#1]}
\newcommand{\gln}[2][2]{\GL_{#1}(#2)}

\begin{document}
\tableofcontents
\section{Introduction}

Continued fractions offer a means of concrete representation for
arbitrary real numbers.   The continued fraction expansion of a real
number is an alternative to the representation of such a number as
a (possibly infinite) decimal.

The reasons for including this topic in the course on Classical Algebra
are:
\begin{menu}
\item[(i)] The subject provides many applications of the method of
recursion.
\item[(ii)] It is closely related to the Euclidean algorithm and, in
particular, to ``Bezout's Identity''.
\item[(iii)] It provides an opportunity to introduce the subject of
\emph{group theory} via the $2$-dimensional unimodular group
$\gln{2}{\Z}$\aos
\end{menu}

\section{The continued fraction expansion of a real number}

Every real number $x$ is represented by a point on the real line
and, as such, falls between two integers.   For example, if $n$ is
an integer and
\[ n \ \leq \ x \ < \ n + 1 \ , \]
$x$ falls between $n$ and $n+1$\aoc \ and there is one and only one
such integer $n$ for any given real $x$\aos   In the case where $x$
itself is an integer, one has \,$ n = x$\aos   The integer $n$ is
sometimes called the \emph{floor} of $x$\aoc \ and one often introduces
a notation for the floor of $x$ such as
\[ n \ = \ \floor{x} \eos\]

\bold{Examples:}
\begin{menu}
\item[1.]  \[ -2 \ = \ \floor{-1.5} \]
\item[2.]  \[  3 \ = \ \floor{\pi}  \]
\end{menu}

For any real $x$ with \( n = \floor{x} \) the number
\( u = x - n \) falls in the \emph{unit interval}
$I$ consisting of all real numbers $u$ for which \,$ 0 \leq u < 1$\aos

Thus, for given real $x$ there is a unique decomposition
\[ x \ = \ n + u \]
where $n$ is an integer and $u$ is in the unit interval.
\ Moreover, $u = 0$ if and only if $x$ is an integer.   This
decomposition is sometimes called the \emph{mod one decomposition}
of a real number.   It is the first step in the process
of expanding $x$ as a continued fraction.

The process of finding the continued fraction expansion of a real
number is a recursive process that procedes one step at a time.
\ Given $x$ one begins with the mod one decomposition
\[ x \ = \ n_1 + u_1 \ , \]
where $n_1$ is an integer and \,$0 \leq u_1 < 1$\aos

If \,$ u_1 = 0$\aoc \ which happens if and only if $x$ is an integer,
the recursive process terminates with this first step.  \ The idea
is to obtain a sequence of integers that give a precise determination
of $x$\aos

If \,$ u_1 > 0$\aoc \ then the reciprocal \(1/u_1\) of $u_1$ satisfies
\( 1/u_1 > 1 \) since $u_1$ is in $I$ and, therefore, \,$ u_1 < 1$\aos
In this case the second step in the recursive determination of the
continued fraction expansion of $x$ is to apply the mod one
decomposition to \,$ 1/u_1$\aos  One writes
\[ 1/u_1 \ = \ n_2 + u_2 \ , \]
where $n_2$ is an integer and \,$ 0 \leq u_2 < 1$\aos  Combining the
equations that represent the first two steps, one may write
\[ x = n_1 + \frac{1}{n_2 + u_2} \eos\]

Either \,$ u_2 = 0$\aoc \ in which case the process ends with the
expansion
\[ x = n_1 + \frac{1}{n_2} \ , \]
or \,$ u_2 > 0$\aos  In the latter case one does to $u_2$ what had just
been done to $u_1$ above under the assumption \,$ u_1 > 0$\aos
\ One writes
\[ 1/u_2 \ = \ n_3 + u_3 \ , \]
where $n_3$ is an integer and \,$ 0 \leq u_3 < 1$\aos  Then combining
the equations that represent the first three steps, one may write
\[ x = n_1 + \frac{1}{n_2 + \frac{1}{n_3 + u_3}} \eos\]

After $k$ steps, if the process has gone that far, one has integers
\(n_1, n_2, \ldots, n_k\) and real numbers
\(u_1, u_2, \ldots, u_k\) that are members of the unit interval
$I$ with \(u_1, u_2, \ldots, u_{k-1}\) all positive.
One may write
\[ x = n_1 + \frac{1}{n_2 + \frac{1}{n_3 +
    \frac{1}{\ldots + \frac{1}{n_k + u_k}}}} \eos\]
Alternatively, one may write
\[ x = [ n_1, n_2, n_3, \ldots, n_k + u_k ] \eos\]
If \,$u_k = 0$\aoc the process ends after $k$ steps.  Otherwise,
the process continues at least one more step with
\[ 1/u_k \ = \ n_{k+1} + u_{k+1} \eos\]

In this way one associates with any real number $x$ a sequence,
which could be either finite or infinite, \(n_1, n_2, \ldots\)
of integers.  This sequence is called the \emph{continued fraction
expansion of} $x$\aos

\begin{assertion}[][convention]{Convention}[\empty]
When \([n_1, n_2, ...]\) is called a
\bold{continued fraction}, it is understood that all of the numbers
$n_j$ are integers and that \(n_j \geq 1\) for \,$j \geq 2$\aos
\end{assertion}

\section{First examples}

\begin{eqnarray}
\    \frac{15}{11} & = & 1 + \frac{4}{11} \\
\      & = & 1 + \frac{1}{\frac{11}{4}} \\
\      & = & 1 + \frac{1}{2 + \frac{3}{4}} \\
\      & = & 1 + \frac{1}{2 + \frac{1}{\frac{4}{3}}} \\
\      & = & 1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{3}}} \\
\      & = & [1, 2, 1, 3] \ .
\end{eqnarray}

\begin{eqnarray}
\ \sqrt{10} & = & 3 + \frac{1}{\frac{1}{\sqrt{10}-3}} \\
\      & = & 3 + \frac{1}{\sqrt{10}+3} \\
\      & = & 3 + \frac{1}{6 + \frac{1}{\frac{1}{\sqrt{10}-3}}} \\
\      & = & 3 + \frac{1}{6 + \frac{1}{\sqrt{10}+3}} \\
\      & = & 3 + \frac{1}{6 + \frac{1}{6 + \frac{1}{\ldots}}} \\
\      & = & [3, 6, 6, 6, \ldots] \ .      
\end{eqnarray}

\begin{eqnarray}
\ [2, 3, 5, 2 ] & = & 2 + \frac{1}{[3, 5, 2]} \\
\      & = & 2 + \frac{1}{3 + \frac{1}{[5, 2]}} \\
\      & = & 2 + \frac{1}{3 + \frac{1}{5 + \frac{1}{2}}} \\
\      & = & 2 + \frac{1}{3 + \frac{1}{\frac{11}{2}}} \\
\      & = & 2 + \frac{1}{3 + \frac{2}{11}} \\
\      & = & 2 + \frac{1}{\frac{35}{11}} \\
\      & = & 2 + \frac{11}{35} \\
\      & = & \frac{81}{35} \ .
\end{eqnarray}

Let
\[ x = 1+\frac{1}{2+\frac{1}{3+\frac{1}{2+\frac{1}{3+\frac{1}{2+\ldots}}}}}
\eos\]
In this case one finds that
\[ x = 1 + \frac{1}{y} \ , \]
where
\[ y = 2+\frac{1}{3+\frac{1}{2+\frac{1}{3+\frac{1}{2+\ldots}}}} \eos\]
Further reflection shows that the continued fraction structure for
$y$ is self-similar:
\[ y = 2+\frac{1}{3+\frac{1}{y}} \eos\]
This simplifies to
\[ y = \frac{7y+2}{3y+1} \]
and leads to the quadratic equation
\[ 3y^2 - 6y - 2 = 0 \]
with discriminant $60$\aos \ Since \,$y > 2$\aoc \ one of the two
roots of the quadratic equation cannot be $y$\aoc \ and, therefore,
\[ y = \frac{3 + \sqrt{15}}{3} \eos\]
Finally,
\[ x = \frac{\sqrt{15}-1}{2} \eos\]

The idea of the calculation above leads to the conclusion that any
continued fraction \( [n_1, n_2, \ldots] \) that eventually repeats
is the solution of a quadratic equation with positive discriminant
and integer coefficients.    The converse of this statement is also
true, but a proof requires further consideration.

\section{The case of a rational number}

The process of finding the continued fraction expansion of a rational
number is essentially identical to the process of applying the
Euclidean algorithm to the pair of integers given by its numerator and
denominator.

Let \,$x = a/b, \ b > 0$\aoc \  be a representation of a rational number
$x$ as a quotient of integers $a$ and $b$\aos   The mod one decomposition
\[ \frac{a}{b} = n_1 + u_1 \, , \ \ u_1 = \frac{a - n_1 b}{b} \]
shows that \,$ u_1 = r_1/b$\aoc \ where $r_1$ is the remainder for
division of $a$ by $b$\aos   The case where \(u_1 = 0\) is the case
where $x$ is an integer.  Otherwise \,$u_1 > 0$\aoc \ and the mod one
decomposition of \(1/u_1\) gives
\[ \frac{b}{r_1} = n_2 + u_2 \, , \ \ u_2 = \frac{b - n_2 r_1}{r_1} \eos\]
This shows that \,$ u_2 = r_2/r_1$\aoc where $r_2$ is the remainder for
division of $b$ by $r_1$.   Thus, the successive quotients in Euclid's
algorithm are the integers \(n_1, n_2, \ldots\) occurring in the
continued fraction.  Euclid's algorithm terminates after a finite
number of steps with the appearance of a zero remainder.  Hence, the
continued fraction expansion of every rational number is finite.

\begin{thm}  The continued fraction expansion of a real number is
finite if and only if the real number is rational.
\end{thm}

\proof  It has just been shown that if $x$ is rational, then
the continued fraction expansion of $x$ is finite because its calculation
is given by application of the Euclidean algorithm to the numerator
and denominator of $x$\aos   The converse statement is the statement
that every finite continued fraction represents a rational number.
That statement will be demonstrated in the following section.

\section{The symbol \,$[t_1, \,t_2, \,\ldots, \,t_r]$}

For arbitrary real numbers \(t_1, t_2, \ldots, t_r\)
with each \(t_j \geq 1\) for \(j \geq 2\)
the symbol \( [ t_1, t_2, \ldots, t_r ] \) is defined recursively
by:
\[ [ t_1 ] \ = \ t_1 \]
\beql{t-rec}
[t_1,t_2,\ldots,t_r ]\ =\ t_1+\frac{1}{[t_2,\ldots,t_r ]}\ \eos\eeq
In order for this definition to make sense one needs to know that
the denominator in the right-hand side of (\Ref{t-rec}) is non-zero.
The condition \(t_j \geq 1\) for \(j \geq 2\) guarantees, in
fact, that \,$ [t_2,\ldots,t_r ] > 0$\aoc \ as one may prove using
induction.

It is an easy consequence of mathematical induction that the symbol
\([t_1, t_2, \ldots, t_r]\) is a rational number if each $t_j$ is
rational.   In particular, each finite continued fraction is a
rational number.   (Note that the symbol \([t_1, t_2, \ldots, t_r]\)
is to be called a continued fraction, according to the convention of
the first section, only when each $t_j$ is an integer.)

Observe that the recursive nature of the symbol \([t_1, \ldots, t_r]\)
suggests that the symbol should be computed in a particular case working
from right to left.   Consider again, for example, the computation above
showing that \,$[2, 3, 5, 2] = 81/35$\aos   Working from right to left one
has:
\begin{eqnarray}
\          [2] & = & 2\\
\       [5, 2] & = & 5+\frac{1}{[2]} = 5+\frac{1}{2} = \frac{11}{2}\\
\    [3, 5, 2] & = & 3+\frac{1}{[5, 2]} = 3+\frac{2}{11}
                                                 = \frac{35}{11}\\
\ [2, 3, 5, 2] & = & 2+\frac{1}{[3, 5, 2]} = 2+\frac{11}{35}
                                                 = \frac{81}{35}
\end{eqnarray}

There is, however, another approach to computing
\,$[t_1, t_2, \ldots, t_r]$\aos
Let, in fact, \(t_1, t_2, \ldots\) be any (finite or infinite)
sequence of real numbers.  One uses the double recursion
\beql{pdef}
p_j = t_j p_{j-1} + p_{j-2} \, , \ \ j \geq 1 \, ,
   \ \ p_0 = 1 \, , \ \ p_{-1} = 0 \eeq
to define the sequence \,$\{p_j\}\, , \ j \geq -1$\aos  The double
recursion, differently initialized,
\beql{qdef}
q_j = t_j q_{j-1} + q_{j-2} \, , \ \ j \geq 1 \, ,
   \ \ q_0 = 0 \, , \ \ q_{-1} = 1 \eeq
defines the sequence \,$\{q_j\}\, , \ j \geq -1$\aos
Note that \,$p_1 = t_1$\aoc \ \,$p_2 = t_1t_2 + 1$\aoc \ $\ldots$
\ and \,$q_1 = 1$\aoc \ \,$ q_2 = t_2$\aoc \ \,$q_3 = t_2t_3 + 1$\aoc
\ $\ldots\,$\aos

One now forms the matrix
\beql{Mr-def}
  M_j = \mxtwo{p_j}{q_j}{p_{j-1}}{q_{j-1}}\text{\ \ for\ \ } j\geq 0\ \eos\eeq
Thus, for example,
\[ M_0 = \mxtwo{1}{0}{0}{1}\, , \text{\ \ and\ \ }
   M_1 = \mxtwo{t_1}{1}{1}{0} \eos\]
It is easy to see that the matrices $M_j$ satisfy the double recursion
\beql{Mr-rec}
  M_j = \mxtwo{t_j}{1}{1}{0} \, M_{j-1} \, , \ j \geq 1 \eeq
as a consequence of the double recursion formulas for the $p_j$ and $q_j$\aos
Hence, a simple argument by mathematical induction shows that
\beql{Mrcomp}
M_r = \mxtwo{t_r}{1}{1}{0} \, \ldots \, \mxtwo{t_2}{1}{1}{0} \,
         \mxtwo{t_1}{1}{1}{0} \, , \ r \geq 1 \eos\eeq
This is summarized by:

\begin{propn}  For any sequence \(\{t_j\}, \, j \geq 1\) of
real numbers, if \(\{p_j\}\) and \(\{q_j\}\) are the sequences
defined by the double recursions (\Ref{pdef}) and (\Ref{qdef}), then one
has the matrix identity
\beql{prqr-row}
\mxtwo{p_r}{q_r}{p_{r-1}}{q_{r-1}} \ =
     \ \mxtwo{t_r}{1}{1}{0} \, \ldots \, \mxtwo{t_2}{1}{1}{0} \,
         \mxtwo{t_1}{1}{1}{0} \eeq
for each integer \,$r \geq 1$\aos
\end{propn}

\begin{cor}[pqiden]  One has the identity
\(p_r q_{r-1} - q_r p_{r-1} = (-1)^r\) for each
integer \,$r \geq 1$\aos
\end{cor}

\proof  The number \(p_r q_{r-1} - q_r p_{r-1}\) is the
determinant of the matrix \,$M_r$\aos   From the formula (\Ref{Mrcomp})
the matrix \(M_r\) is the product of $r$ matrix factors, each of
which has determinant $-1$\aos   Since the determinant of the product
of matrices is the product of the determinants of the factors, it is
clear that \,$ \mbox{det}(M_r) = (-1)^r$\aos

\begin{cor}[viden]  One has the vector identity
\beql{prqr-vec}
 \cvtwo{p_r}{q_r} \ =
     \ \mxtwo{t_1}{1}{1}{0} \, \mxtwo{t_2}{1}{1}{0} \,
          \ldots \, \mxtwo{t_r}{1}{1}{0} \, \cvtwo{1}{0} \eeq
for each integer \,$r \geq 1$\aos
\end{cor}

\proof  First recall \iseq{(i)} that the product of a matrix and a (column)
vector is defined by the relation
\[ \mxtwo{a}{b}{c}{d} \, \cvtwo{x}{y} \ = \ \cvtwo{ax + by}{cx + dy} \ , \]
\iseq{(ii)} that the \emph{transpose} of a matrix is the matrix whose rows
are the columns of the given matrix, and \iseq{(iii)} that the transpose
operation reverses matrix multiplication.  One tranposes both sides of
the relation (\Ref{prqr-row}) to obtain:
\beql{prqr-col}
\mxtwo{p_r}{p_{r-1}}{q_r}{q_{r-1}} \ =
     \ \mxtwo{t_1}{1}{1}{0} \, \mxtwo{t_2}{1}{1}{0} \,
         \ldots \, \mxtwo{t_r}{1}{1}{0} \eos\eeq
To this relation one applies the principle that the first column of
any $2 \times 2$ matrix is the product of that matrix with the
column
\[ \cvtwo{1}{0} \]
in order to obtain the column identity (\Ref{prqr-vec}).

\begin{thm}  For any sequence \(\{t_j\}, \, j \geq 1\) of
real numbers, if \(\{p_j\}\) and \(\{q_j\}\) are the sequences
defined by the double recursions (\Ref{pdef}) and (\Ref{qdef}), and
if \(t_j \geq 1\) for \,$j \geq 2$\aoc then the value of the symbol
\( [t_1, \ldots, t_r]\) is given by the formula
\beql{t-comp}
[t_1, \, t_2, \, \ldots, \, t_r] \ = \ \frac{p_r}{q_r}
   \text{\ \ for\ \ } r \geq 1 \ \eos\eeq
\end{thm}

\proof  What is slightly strange about this important
result is that while the \(\{p_r\}\) and the \(\{q_r\}\) are
defined by the \emph{front end} recursions, albeit double recursions,
(\Ref{pdef}) and (\Ref{qdef}), the symbol \( [t_1, \ldots, t_r]\)
is defined by the \emph{back end} recursion (\Ref{t-rec}).  The proof
begins with the comment that the right-hand side of (\Ref{t-comp})
does not make sense unless one can be sure that the denominator
\,$q_r \neq 0$\aos  One can show easily by induction on $r$ that
\(q_r \geq 1\) for \(r \geq 1\) under the hypothesis \(t_j \geq 1\)
for \,$j \geq 2$\aos

The proof proceeds by induction on $r$\aos   If \,$r = 1$\aoc \ the
assertion of the theorem is simply the statement \,$t_1 = p_1/q_1$\aoc
\ and, as noted above, \(p_1=t_1\) and \,$q_1=1$\aos   Assume now
that \,$r \geq 2$\aos   By induction we may assume the correctness of
the statement (\Ref{t-comp}) for symbols of length $r-1$\aoc \ and,
therefore, for the symbol \,$[t_2, \ldots, t_r]$\aos  That case of the
statement says that \([t_2, \ldots, t_r]\) must be equal to \,$a/c\,$\aoc
where by corollary \Ref{viden}
\[ \cvtwo{a}{c} = \mxtwo{a}{b}{c}{d} \, \cvtwo{1}{0} \]
with
\[ \mxtwo{a}{b}{c}{d} \ = \ \mxtwo{t_2}{1}{1}{0} \,
         \ldots \, \mxtwo{t_r}{1}{1}{0} \eos\]
Now by (\Ref{t-rec})
\[ [t_1, \, t_2, \, \ldots, \, t_r] \ = \ t_1 + \frac{1}{a/c} \ =
  \ t_1 + \frac{c}{a} \ = \ \frac{at_1 + c}{a} \eos\]
But by corollary \Ref{viden} again
\[ \cvtwo{p_r}{q_r} \ = \ \mxtwo{t_1}{1}{1}{0} \, \mxtwo{a}{b}{c}{d} \,
     \cvtwo{1}{0} \ = \ \mxtwo{at_1 + c}{bt_1 + d}{a}{b} \,
     \cvtwo{1}{0} \ =  \ \cvtwo{at_1 + c}{a} \eos\]
Hence,
\[ \frac{p_r}{q_r} \ = \ \frac{at_1 + c}{a} \ =
  \ [t_1, \, t_2, \, \ldots, \, t_r] \eos\]

\section{Application to Continued Fractions}

Recall that \( [n_1, n_2, \ldots ] \) is called a continued fraction
only when each $n_j$ is an integer and \(n_j \geq 1\) for \,$j \geq
2$\aos  \ The sequence \(n_1, n_2, \ldots\) may be finite or
infinite.   The symbol \( c_r \, = \,\, [n_1, n_2, \ldots, n_r] \)
formed with the first $r$ terms of the sequence, is called the
$r^{\mbox{\emph{th}}}$ \emph{convergent} of the continued fraction.
Associated with a given sequence \(n_1, n_2, \ldots \) are two sequences
\(p_1, p_2, \ldots \) and \(q_1, q_2, \ldots \) that are given,
according to the double recursions (\Ref{pdef}), (\Ref{qdef}) of the
previous section with \,$t_j = n_j$\aos   

\begin{propn}  If \( [n_1, n_2, \ldots] \) is a continued
fraction, then the integers $p_r$ and $q_r$ are coprime for each
\,$r \geq 1$\aos
\end{propn}

\proof  By Corollary \Ref{pqiden} of the previous section
\,$p_r q_{r-1} - q_r p_{r-1} = (-1)^r$\aos   Hence, any positive
divisor of both $p_r$ and $q_r$ must divide the left-hand side of
this relation, and, therefore, must also divide $(-1)^r$\aos

\begin{propn}  The difference between successive convergents
of the continued fraction \( [n_1, n_2, \ldots] \) is given by
the formula
\beql{convgtdiff}
 c_r - c_{r-1} \ = \ \frac{(-1)^r}{q_r q_{r-1}} \text{\ \ for\ \ }
      r \geq 2 \eos\eeq
\end{propn}

\proof  According to the theorem (formula \Ref{t-comp}) at the
end of the last section the convergent $c_r$ is given by
\[ c_r \ = \ \frac{p_r}{q_r} \eos\]
Hence,
\begin{eqnarray}
\ c_r - c_{r-1} & \ = \ & \frac{p_r}{q_r} \, -
                                   \, \frac{p_{r-1}}{q_{r-1}} \\
\               & \ = \ & \frac{p_r q_{r-1} - p_{r-1} q_r}{q_r q_{r-1}} \\
\               & \ = \ & \frac{(-1)^r}{q_r q_{r-1}} \ .
\end{eqnarray}
(The last step is by Corollary \Ref{pqiden} above.)

\begin{rem}  The formula (\Ref{convgtdiff}) remains true if
\( c_r = [t_1, \ldots, t_r] \) where the $t_j$ are real numbers
subject to the assumption \(t_j \geq 1\) for \,$j  \geq 1$\aos
\end{rem}

\begin{assertion}{Lemma}[\empty]  The sequence \(\{q_j\}\) is a strictly
increasing sequence for \,$j \geq 2$\aos
\end{assertion}

\proof  This is easily proved by induction from the recursive
definition (\Ref{qdef}) of the sequence.

\begin{thm}  If \( [n_1, n_2, \ldots] \) is an infinite
continued fraction, then the limit
\[ \func{lim}_{r \rightarrow \infty} \ \frac{p_r}{q_r} \]
always exists.
\end{thm}

\proof  As one plots the convergents $c_r$ on the line of real
numbers, one moves alternately right and left.   The formula
(\Ref{convgtdiff}) for the difference between successive convergents
elucidates not only the fact of alternate right and left movement but
also the fact that each successive movement is smaller than the one
preceding.   Therefore, one has
\[ c_1 < c_3 < c_5 < \ldots < c_6 < c_4 < c_2 \eos\]
Since any strictly increasing sequence of positive integers
must have infinite limit, the seqence \(q_j q_{j-1}\) has infinite
limit, and so the sequence of reciprocals \(1/q_j q_{j-1}\) must
converge to zero.  Hence, the sequences of odd- and even-indexed
convergents must have the same limit, which is the limit of the
sequence of all convergents.

\begin{defn}  The limit of the sequence of convergents of an
infinite continued fraction is called the \emph{value} of that
continued fraction.
\end{defn}

\begin{thm}  If \( [n_1, n_2, \ldots] \) is the continued
fraction expansion of an irrational number $x$\aoc  \ then
\[ x \ = \ \func{lim}_{r \rightarrow \infty} \ \frac{p_r}{q_r} \ ; \]
that is, the \emph{value} of the continued fraction expansion of a real
number is that real number.
\end{thm}

\proof  For each \(r \geq 1\) the continued fraction expansion
\( [n_1, n_2, \ldots] \) of $x$ is characterized by the identity
\beql{xconfrac}
x = [n_1, \, n_2, \, \ldots, \, n_r + u_r] \ , \eeq
where $u_r$ is a real number with \,$0 \leq u_r < 1$\aos
The sequences of $p$'s and $q$'s for the symbol
\( [n_1, n_2, \ldots, n_r + u_r] \) agree with those for the symbol
\( [n_1, n_2, \ldots, n_r] \) except for the $r^{\mbox{th}}$ terms.
One has by (\Ref{t-comp})
\[ [n_1, \, n_2, \, \ldots, \, n_r + u_r] \ = \frac{P_r}{Q_r} \ , \]
where by (\Ref{qdef})
\begin{eqnarray}
\  q_r & \ = \ &   n_r q_{r-1} \, + \, q_{r-2} \\
\  Q_r & \ = \ &  (n_r + u_r) q_{r-1} \, + \, q_{r-2}
\end{eqnarray}
Hence,
\[ Q_r \ = \ q_r \, + \, u_r q_{r-1} \eos\]
Therefore, the displacement from $c_{r-1}$ to $x$ is by (\Ref{convgtdiff})
\[ \frac{(-1)^r}{Q_r q_{r-1}} \ =
  \ \frac{(-1)^r}{(q_r q_{r-1} + u_r q_{r-1}^2)} \ , \]
which is in the same direction but of smaller magnitude than the
displacement from $c_{r-1}$ to $c_r$\aos  Therefore, $x$ must be larger
than every odd-indexed convergent and smaller than every even-indexed
convergent.  But since all convergents have the same limit, that limit
must be $x$\aos
 
\section{Bezout's Identity and the double recursion}

It has already been observed that the process of finding the continued
fraction expansion of a rational number \,$a/b$ ($b > 0$), \ involves
the same series of long divisions that are used in the application of
the Euclidean algorithm to the pair of integers $a$ and $b$\aos   Recall
that at each stage in the Euclidean algorithm the divisor for the current
stage is the remainder from the previous stage and the dividend for the
current stage is the divisor from the previous stage, or, equivalently,
the dividend for the current stage is the remainder from the second
previous stage.   The Euclidean algorithm may thus be viewed as a double
recursion that is used to construct the sequence of remainders.   One
starts the double recursion with
\[ r_{-1} = a  \text{\ \ and\ \ } r_0 = b \eos\]
At the $j^{\mbox{th}}$ stage one performs long division of $r_{j-2}$
by $r_{j-1}$ to obtain the integer quotient $n_j$ and the integer
remainder $r_j$ that satisfies \,$0 \leq r_j < r_{j-1}$\aos   Thus,
\beql{remrec}
r_j \ = \ r_{j-2} - n_j r_{j-1} \ .
\eeq
The Euclidean algorithm admits an additional stage if \,$r_j > 0$\aos
Since
\[ 0 \leq r_j < r_{j-1} < \ldots < r_2 < r_1 < r_0 = b \ , \]
there can be at most $b$ stages.

One may use the sequence of successive quotients $n_j$ ($j \geq 1$)
\ to form sequences \(\{p_j\}\) and \,$\{q_j\}$\aoc \, as in the 
previous section, according to the double recursions:
\beql{npdef}
p_j = n_j p_{j-1}+p_{j-2}\, ,\ j \geq 1 \, ;\ \ p_0 = 1\, ,\ \ p_{-1} = 0 \ .
\eeq
\beql{nqdef}
q_j = n_j q_{j-1}+q_{j-2}\, ,\ j \geq 1 \, ;\ \ q_0 = 0\, ,\ \ q_{-1} = 1 \ .
\eeq
It has already been observed that \(q_j \geq 1\) for \(j \geq 1\) and
\[ [n_1,\, n_2,\, \ldots,\, n_j]\ =\ \frac{p_j}{q_j}\, ,\ \ j \geq 1 \eos\]

Bezout's Identity says not only that the greatest common divisor of $a$
and $b$ is an integer linear combination of them but that the coefficents
in that integer linear combination may be taken, up to a sign, as $q$
and $p$\aos

\begin{thm}  If the application of the Euclidean algorithm to
$a$ and $b$ ($b > 0$) \ ends with the $m^{\mbox{th}}$ long division,
i.e., \,$r_m = 0$\aoc \ then
\beql{bezout}
r_j \ = \ (-1)^{j-1} \bal{q_j a - p_j b } \, , \ \ 1 \leq j \leq m \ .
\eeq
\end{thm}

\proof  One uses induction on $j$\aos \ For \(j = 1\) the statement
is \,$ r_1 = q_1 a - p_1 b$\aos   Since by (\Ref{npdef}, \Ref{nqdef})
\(q_1 = 1\) and \,$p_1 = n_1$\aoc \ this statement is simply the
case \(j = 1\) in (\Ref{remrec}).    Assume \,$j \geq 2$\aoc and that
the formula (\Ref{bezout}) has been established for indices smaller than
$j$\aos   By (\Ref{remrec}) one has
\[ r_j \ = \ r_{j-2} - n_j r_{j-1} \eos\]
In this equation one may use (\Ref{bezout}) to expand the terms
$r_{j-2}$ and $r_{j-1}$ to obtain:
\begin{eqnarray}
\ r_j & \ = \ & \balbr{(-1)^{j-3}(q_{j-2}a - p_{j-2}b) } \, - \,
             n_j \balbr{(-1)^{j-2}(q_{j-1}a - p_{j-1}b) }         \\
\       & \ = \ & \balbr{(-1)^{j-1}(q_{j-2}a - p_{j-2}b) } \, + \,
             n_j \balbr{(-1)^{j-1}(q_{j-1}a - p_{j-1}b) }         \\
\       & \ = \ & (-1)^{j-1}\balbr{(q_{j-2}a - p_{j-2}b) \, + \,
                                 n_j (q_{j-1}a - p_{j-1}b) }     \\
\       & \ = \ & (-1)^{j-1}\balbr{(q_{j-2} + n_j q_{j-1})a 
                               - (p_{j-2} + n_j p_{j-1})b }      \\
\       & \ = \ & (-1)^{j-1} \balbr{q_j a - p_j b } \ .
\end{eqnarray}

\begin{cor}  The greatest common divisor $d$ of $a$ and $b$
is given by the formula
\beql{gcdbezout}
d \ = \ (-1)^m (q_{m-1}a \, - \, p_{m-1} b) \, ,
\eeq
where $m$ is the number of divisions required to obtain zero
remainder in the Euclidean algorithm.
\end{cor}

\proof  One knows that $d$ is the last non-zero remainder
$r_{m-1}$ in the Euclidean algorithm.  This formula for $d$ is the
case \(j = m-1\) in (\Ref{bezout}).

\begin{cor}
\beql{checkbezout} p_m = \frac{a}{d} \, , \ \ q_m = \frac{b}{d} \eos\eeq
\end{cor}

\proof  The last remainder \,$r_m = 0$\aos  The case \(j = m\)
in (\Ref{bezout}) shows that \,$a/b = p_m/q_m$\aos   Since, by the first
proposition of the preceding section, $p_m$ and $q_m$ have no common
factor, this corollary is evident.

\section{The action of \(\gln{2}{\Z}\) on the projective line}

If $a$\aoc $b$\aoc $c$\aoc $d$ are real
numbers with \( ad - bc \neq 0\)\ and
\[ M = \mxtwo{a}{b}{c}{d} \]
is the matrix with entries $a$\aoc $b$\aoc $c$\aoc \ and $d$\aoc
then  \,$M \cdot z$\aoc \, for $z$ real, will denote the expression
\beql{glact} M \cdot z \ = \ \frac{a z \ + \ b}{c z \ + \ d} \eos\eeq
One calls \(M \cdot z\) the \emph{action} of $M$ on $z$\aos

\( M \cdot z \) is a perfectly good function of $z$ except for
the case \( z = - d/c \) where the denominator \(cz + d\) vanishes.
If it were also true that \(az + b = 0\) for the same $z$\aoc \, then
one would have \,$ - b/a = - d/c$\aoc \, in contradiction of the assumption
\,$ ad - bc \neq 0$\aos   Thus, when \,$ z = - d/c$\aoc \, the
value of $|M \cdot w|$ increases beyond all bounds as $w$ approaches $z$\aoc
and it is convenient to say that
\[ M \cdot \bal{- \frac{d}{c}} \ = \ \infty \]
where $\infty$ is regarded as large and signless.   If further it is agreed
to define
\[ M \cdot \infty \ = \ \frac{a}{c} \, , \]
which is the limiting value of \( M \cdot w \) as $|w|$ increases
without bound, then one may regard the expression \( M \cdot z \)
as being defined always for all real $z$ and for $\infty$.   The set
consisting of all real numbers and also the object (not a number)
$\infty$ is called the \emph{projective line}.   The projective line is
therefore the union of the (ordinary) affine line with a single point
$\infty$\aos

\begin{propn}  If \( [n_1, n_2, \ldots] \) is any continued
fraction, then
\beql{cfgl}
[n_1, n_2, \ldots, n_r, n_{r+1}, \ldots] \ = \ M \cdot [n_{r+1}, \ldots] \ .
\eeq
where
\[ M \ = \ \mxtwo{n_1}{1}{1}{0} \, \ldots \, \mxtwo{n_r}{1}{1}{0} \eos\]
\end{propn}

\proof  Let \,$ z = [n_{r+1}, \ldots]$\aos  Then
\[ [n_1, n_2, \ldots, n_r, n_{r+1}, \ldots ] \ =
  \ [n_1, n_2, \ldots, n_r, z ] \eos\]
The statement of the proposition now becomes
\[ [n_1, n_2, \ldots, n_r, z ] \ = \ M \cdot z \eos\]
This may be seen to follow by multiplying both sides in formula
(\Ref{prqr-col}), after replacing $t_j$ with $n_j$, by the column
\[ \cvtwo{z}{1} \eos\]

The matrix $M$ in the preceding proposition is an integer matrix with
determinant $\pm 1$\aos   The notation \(\gln{2}{\Z}\) denotes the set
of all such matrices.   (The $2$ indicates the size of the matrices,
and the $\Z$ indicates that the entries in such matrices are numbers
in the set $\Z$ of integers.) \ It is easy to check that the product of
two members of \(\gln{2}{\Z}\) is a member of \(\gln{2}{\Z}\) and
that the matrix inverse of a member of \(\gln{2}{\Z}\) is a member
of \,$\gln{2}{\Z}$\aos   Thus, \(\gln{2}{\Z}\) forms what is called
a \emph{group}.  The formula (\Ref{glact}) defines what is called the
\emph{action} of \(\gln{2}{\Z}\) on the projective line.

One says that two points $z$ and $w$ of the projective line are
\emph{rationally equivalent} if there is a matrix $M$ in \(\gln{2}{\Z}\)
for which \,$w = M \cdot z$\aos   Since (i) \(\gln{2}{\Z}\) is a group,
(ii) \,$M_1 \cdot (M_2 \cdot z) = (M_1 M_2) \cdot z$\aoc and (iii)
\(w = M \cdot z\) if and only \,$z = M^{-1} \cdot w$\aoc \, it is easy to
see that every point of the projective line belongs to one and only one
rational equivalence class and that two points rationally equivalent to
a third must be rationally equivalent to each other.

\begin{assertion}{Terminology}[\empty]  The rational equivalence of points
on the projective line is said to be the equivalence relation on the
projective line defined by the action of \,$\gln{2}{\Z}$\aos
\end{assertion}

\begin{exmp}  The set of real numbers rationally equivalent to
the point $\infty$ is precisely the set of rational numbers.
\end{exmp}

\begin{exmp}  The proposition above shows that any continued
fraction is rationally equivalent to each of its tails.  It follows that
all tails of a continued fraction are rationally equivalent to each
other.
\end{exmp}

\section{Periodic continued fractions}

In one of the first examples of a continued fraction expansion, it was
shown that \,$\sqrt{10} = [3,6,6,6,\ldots]$\aos   This is an example of
a \emph{periodic} continued fraction.   After a finite number of terms
the sequence of integers repeats cyclically.   If a cyclic pattern is
present from the very first term, then the continued fraction is called
\emph{purely periodic}.  Evidently, \([6,6,6,\ldots] = \sqrt{10}-3\)
is an example of a purely periodic continued fraction.

Note that a periodic continued fraction cannot represent a rational
number since the continued fraction expansion of a rational number is
finite.

\begin{thm}  Every periodic continued fraction is the continued
fraction expansion of a real quadratic irrational number.
\end{thm}

\proof  For clarity: it is being asserted that every periodic
continued fraction represent a number of the form
\[ \frac{a + b\sqrt{m}}{c} \]
where $a$\aoc $b$\aoc $c$\aoc and $m$ are all integers with \,$m > 0$\aoc
\,$c \neq 0$\aoc \, and $m$ not a perfect square.

Numbers of this form with fixed $m$ but varying integers $a$\aoc
$b$\aoc and \(c \neq 0\) may be added, subtracted, multiplied, and
divided without leaving the class of such numbers.  (The statement
here about division becomes clear if one remembers always to
\emph{rationalize} denominators.) \ Consequently, for $M$ in
\(\gln{2}{\Z}\) the number \(M \cdot z\) will be a number of this
form or $\infty$ if and only if $z$ is in the same class.

Since a periodic continued fraction is rationally equivalent to a
purely periodic continued fraction, the question of whether any
periodic continued fraction is a quadratic irrationality reduces to
the question of whether a purely periodic continued fraction is such.
Let
\[ x \ = \ [n_1, \ldots, n_r, n_1, \ldots, n_r, n_1, \ldots, n_r, \ldots] \]
be a purely periodic continued fraction.   By the proposition of the
preceding section, \(x = M \cdot x\) where $M$ is notationally
identical to the $M$ in (\Ref{cfgl}).   Ignoring the computation
(\Ref{prqr-col}) of $M$ in terms of convergents, let
\[ M \ = \ \mxtwo{a}{b}{c}{d} \eos\]
Then
\[ x \ = \frac{ax + b}{cx + d} \ , \]
or, otherwise said, $x$ is a solution of the quadratic equation
\[ cx^2 \, - (a-d) x  - b \ = \ 0 \eos\]

\begin{rem}
It is conversely true that the continued fraction expansion of every
real quadratic irrationality is periodic.
\end{rem}

This converse will not be proved here.


\begin{thebibliography}

\bibitem{}  G. Chrystal, \slnt{Algebra: An Elementary Textbook} (2 vols.),
            Chelsea.

\bibitem{}  G. Hardy \& E. Wright, \slnt{An Introduction to the Theory
            of Numbers}, Oxford Univ. Press.

\bibitem{}  S. Lang, \slnt{Introduction to Diophantine Approximations},
            Addison-Wesley.

\bibitem{}  O. Perron, \slnt{Die Lehre von den Kettenbr\umlau{u}chen}, 2nd ed.,
            Chelsea.
\end{thebibliography}

\end{document}