\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

\begin{center}

CONTINUED FRACTIONS

PERIODIC CONTINUED FRACTIONS

\end{center}

%page 36

Consider first a purely periodic continued fraction

\begin{eqnarray*}
\alpha&=&[\overline{a_0;a_1,a_2\ldots,a_n}]\\
&=&[a_0;a_1,\ldots,a_n,\alpha]
\end{eqnarray*}

So $\alpha=\frac{\alpha p_n+p_{n-1}}{\alpha q_n+q_{n-1}}$

so $\alpha^2q_n+\alpha(q_{n-1}-p_n)-p_{n-1}=0$

This has two roots

\begin{eqnarray*}
\alpha&=&\frac{(p_n-q_{n-1})+\sqrt{(p_n-q_{n-1})^2+4q_np_{n-1}}}{2q_n}>0\\
\overline{\alpha}&=&\frac{(p_n-q_{n-1})-\sqrt{(p_n-q_{n-1})^2+4q_np_{n-1}}}{2q_n}<0
\end{eqnarray*}

Furthermore the LHS of the quadratic equation is $-p_{n-1}<0$ for
$\alpha=0$ and $(q_n-q_{n-1})+(p_n-p_{n-1}>0$ for $\alpha=-1$.
Thus $\alpha>0$ and $-1<\overline{\alpha}<0$.

Quadratic irrationals with this property are termed reduced.

This is related to reduced quadratic forms as Gauss defined them.

Now if we have a periodic continued function where the period
starts at stage $k+1$

\begin{eqnarray*}
\beta&=&[b_0;b_1,\ldots b_k,\overline{a_0,a_1,\ldots a_n}]\\
\beta&=&\frac{\alpha p_k+p_{k-1}}{\alpha q_k+q_{k-1}}
\end{eqnarray*}

%page 37

Since $\alpha$ is a quadratic irrational, so is $\beta$.

Thus any periodic continued fraction represents a quadratic
irrational.

Example

$\beta=[2,3,\overline{10,1,1,1}]\ \alpha=[\overline{10,1,1,}]$

$2+\frac{1}{3}=\frac{7}{3}$ so $\beta=\frac{7\alpha+2}{3\alpha+1}$

To evaluate $\alpha$

\begin{tabular}{cccccc}
$n$&$-1$&0&1&2&3\\ $a_n$&&10&1&1&1\\ $p_n$&1&10&11&21&32\\
$q_n$&0&1&1&2&3
\end{tabular}

So

\begin{eqnarray*}
\alpha&=&\frac{32\alpha+21}{3\alpha+2}\\
3\alpha^2+(2-32)\alpha-21&=&0\\ \alpha^2-10\alpha-7&=&0
\end{eqnarray*}

The positive root is $\alpha=5+\sqrt{32}=5+4\sqrt{2}$.

So
$\beta=\frac{35+28\sqrt{2}+2}{15+12\sqrt{2}+1}=\frac{20-\sqrt{2}}{8}$

We now prove the convers.

Theorem

A continued fraction which represents a quadratic irrational is
periodic (Lagrange)

Proof

Let $\alpha=\frac{P+\sqrt{D}}{Q}>0$ be a positive quadratic
irrational.

Now $\alpha=\frac{Pm+\sqrt{Dm^2}}{Qm}=\frac{P'+\sqrt{D'}}{Q'}$

$\frac{D'-P'^2}{Q'}=m.\frac{D-P^2}{Q}\in Z$ for suitable $m$.

%page 38

So suppose w.l.o.g. $\alpha_0=\frac{P_0+\sqrt{D}}{Q_0}$ and
$Q_0|D-P_0^2\ D_0,q_0\in Z$

$\alpha_0=a_0+\frac{1}{\alpha_1}$ so
$\frac{1}{\alpha_1}=\frac{\sqrt{D}+P_0-a_0Q_0}{Q_0}$ and
$$\alpha_1=\frac{Q_0}{\sqrt{D}+P_0-a_0Q_0}=\frac{\sqrt{D}-
a_0Q_0-P_0}{\frac{1}{Q_0}[D-(a_0Q_0-P_0)^2]}=\frac{\sqrt{D}
+P_1}{Q_1}$$

(note that $Q_0|[]$) where $P_1=a_0Q_0-P_0$

$$Q_1=\frac{D-(a_0Q_0-P_0)^2}{Q_0}=\frac{D-P_1^2}{Q_0}$$

So $Q_0=\frac{D-P_1^2}{Q_1}$ i.e. $Q_1|D-P_1^2$

so this divisibility property is preserved through the continued
fraction algorithm.

At the $k$th stage we therefore have
$\alpha_k=\frac{\sqrt{D}+P_k}{Q_k}$ where

\begin{eqnarray*}
P_k&=&a_{k-1}Q_{k-1}-P_{k-1}\\ Q_k&=&\frac{(D-P_k^2)}{Q_{k-1}}\\
a_k&=&[\alpha_k]
\end{eqnarray*}

We now show that the process eventually produces reduced quadratic
irrationals.

$$\alpha_0=[a_0,a_1,\ldots
a_n\alpha_{n+1}]=\frac{\alpha_{n+1}p_m+p_{n-1}}{\alpha_{n+1}q_n+
q_{n-1}}$$

If we denote $\overline{\alpha}$ the quadratic conjugate of
$\alpha$ then we have

%page 39

\begin{eqnarray*}
\overline{\alpha_0}&=&\frac{\overline{\alpha_{n+1}}p_n+p_{n-1}}{
\overline{\alpha_{n+1}}q_n+q_{n-1}}\\
\overline{\alpha_{n+1}}&=&\frac{-\overline{\alpha_0}q_{n-1}+p_{
n-1}}{\overline{\alpha_0}q_n-p_n}=-\frac{q_{n-1}}{q_n}\left(\frac{
\overline{\alpha_0}-\frac{p_{n-1}}{q_{n-1}}}{\overline{\alpha_0}-
\frac{p_n}{q_n}}\right)
\end{eqnarray*}

Now as $n\to\infty$

$$\frac{\overline{\alpha_0}-\frac{p_{n-1}}{q_{n-1}}}{\overline{\alpha_0}-\frac{p_n}{q_n}}\to\frac{\overline{\alpha_0}-\alpha_0}{\overline{\alpha_0}-\alpha_0}=1$$

so for all $n$ sufficiently large

$$\overline{\alpha_{n+1}}=-\frac{q_{n-1}}{q_n}(1+\varepsilon_n)\
|\varepsilon|\textrm{ small}$$

so $\overline{\alpha_{n+1}}<0$ for all $n$ sufficiently large.

If $\overline{\alpha_k}<0$ then from
$\alpha_k=a_k+\frac{1}{\alpha_{k+1}}$ we conclude

$$\frac{1}{\overline{\alpha_{k+1}}}=\overline{\alpha_k}-a_k<-a_k\leq-1$$

So we conclude that for all $n$ sufficiently large
$-1<\overline{\alpha_n}<0$, and since $\alpha_n>1,\ \alpha_n$ is a
reduced quadratic irrational.

Now if $\alpha=\frac{P+\sqrt{D}}{Q}$ is reduced then
$\alpha-\overline{\alpha}>0$ and $\alpha+\overline{\alpha}>0$, so
$\frac{2\sqrt{D}}{Q}>0$ and $\frac{2\sqrt{P}}{Q}>0$ so $Q>0$ and
so $P>0$

Also $\overline{\alpha}<0$ so $P-\sqrt{D}<0$ i.e. $P<\sqrt{d}$.

Also $\alpha>1$ so $Q<P+\sqrt{D}$

If $N=[\sqrt{D}]$ we have $0<P\leq N$ and $0<Q\leq2N$

%page 40

so there is only a finite set of reduced quadratic irrationals
associated with a given $\sqrt{D}$. So at some stage in the
process we eventually have

$$\alpha_h=\alpha_k$$

i.e.

$$[a_h;a_{h+1},a_{h+2},\ldots]=[a_k;a_{k+1},a_{k+1},\ldots]$$

and by uniqueness the $a$'s are equal, so we have periodicity,
where the shortest period is $\leq|k-h|$

Note. If $N=[\sqrt{D}]$ there are at most $2N^2$ RQI so the period
is $\leq2N^2\sim2D$

\begin{description}

\item[(i)]

$$\alpha=\frac{\sqrt{2}-20}{-8}=[2,3,\overline{10,1,1,1}]$$

$N=1$ but the period is $>2N$?

This is because $\alpha$ is not in a form which satisfies the
divisibility condition. We need to write

$$\alpha=\frac{\sqrt{2m^2}-20m}{-8m}\ (m>0)$$

and we need $8m|2m^2-(20m)^2$ i.e. $8|2m-400m$

$m=4$ is the first solution. So we must write
$\alpha=\frac{\sqrt{32}-80}{-32}$

we then use the recursive scheme for the $p$'s and $Q$'s to obtain
the complete quotients.

\begin{tabular}{ccc|cccc|c}
$k$&0&1&2&3&4&5&6\\ $P_k$&$-80$&16&5&5&2&2&5\\
$Q_k$&$-32$&7&1&7&4&7&1\\ $a_k$&2&3&10&1&1&1
\end{tabular}

\begin{eqnarray*}
P_k&=&a_{k-1}Q_{k-1}-P_{k-1}\\ Q_k=\frac{D-P_k^2}{Q_{k-1}}\\
a_k&=&\left[\frac{P_k+\sqrt{D}}{Q_k}\right]=\left[\frac{P_k+[\sqrt{D}]}{Q_k}\right]
\end{eqnarray*}

%page 41

\item[(ii)]
The number of RQI is about $\leq$ about $2D$ astablished above.
This can be improved. In 1971 KEH showed that this number is
$O(\sqrt{D}\log D)$

\end{description}

We now want to see where the period starts. We have seen that a
purely periodic continued fraction represents a RQI.

Theorem

A RQI has a purely periodic continued fraction (Galois)

Proof

Let $\alpha_0$ be reduced, so $\alpha_0>1$ and
$-1<\overline{\alpha_0}<0$

Now $\alpha_0=a_o+\frac{1}{\alpha_1}$ and $\alpha_1>1$

Also $\overline{\alpha_0}=a_0+\frac{1}{\overline{\alpha_1}}$ and
$\overline{\alpha_0}<0$ so
$\frac{1}{\overline{\alpha_1}}=-a_0+\overline{\alpha_0}<-a_0\leq-1$

so $-1<\overline{\alpha_1}<0$ and so $\alpha_1$ is reduced.
Continuing gives

$\alpha_n=a_n+\frac{1}{\alpha_{n+1}}$ and
$-\frac{1}{\overline{\alpha_{n+1}}}=a_n-\overline{\alpha_n}$ and
$0<-\overline{\alpha_n}<1$

Thus
$$a_n=[\alpha_n]=\left[-\frac{1}{\overline{\alpha_{n+1}}}\right]$$

Suppose that the period for the continued fraction begins with
$a_m\ m\geq1$. Then

$$\alpha_0=[a_0,a_1\ldots a_{m-1}\overline{a_ma_{m+1}\ldots
a_{m+k-1}}]$$

period $k$ and $a_{m-1}\neq a_{m+k-1}$

Because of periodicity however, $|alpha_m=\alpha_{m+k}$ and so
$-\frac{1}{\overline{\alpha_m}}=-\frac{1}{\overline{\alpha_{m+k}}}$

Taking the integer part gives $a_{m-1}=a_{m+k-1}$

So the period must start at $a_0$.

%page 41a

Given $\alpha_0>1$, if $\overline{\alpha_0}<-1,\ \alpha_0$ is not
reduced and so its contu=inued fraction is not purely periodic.
But $\overline{\alpha_0}<0\Rightarrow\alpha_1$ reduced, so if
$\overline{\alpha_0}<-1$ then the continued fraction has just one
term before the period begins.

Suppose that $\alpha_0$ has just one term before the period begins

$$\alpha_0=[a_0;\overline{a_1,\ldots,a_k}]$$

$\alpha_0$ is not reduced. Now $\alpha_1=\alpha_{k+1}$ and
$a_0=a_0+\frac{1}{\alpha_1}\
\alpha_k=a_k+\frac{1}{\alpha_{k+1}}=a_k+\frac{1}{\alpha_1}$

so

\begin{eqnarray*}
\overline{\alpha_0}&=&a_0+\frac{1}{\overline{\alpha_1}}\\
\overline{\alpha_k}&=&a_k+\frac{1}{\overline{\alpha_1}}
\end{eqnarray*}

So, since $-1<\overline{a_k}<0$, if $\overline{\alpha_0}<-1,\
a_0<a_k$ and if $\overline{\alpha_0}>1\ a_0>a_k$.

Naturally if $\overline{\alpha_0}>1$ the continued fraction for
$\alpha_0$ may have more then one entry in its a cyclic part.


\end{document}