<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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&amp;=&amp;[\overline{a_0;a_1,a_2\ldots,a_n}]\\
&amp;=&amp;[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&amp;=&amp;\frac{(p_n-q_{n-1})+\sqrt{(p_n-q_{n-1})^2+4q_np_{n-1}}}{2q_n}&gt;0\\
\overline{\alpha}&amp;=&amp;\frac{(p_n-q_{n-1})-\sqrt{(p_n-q_{n-1})^2+4q_np_{n-1}}}{2q_n}&lt;0
\end{eqnarray*}

Furthermore the LHS of the quadratic equation is $-p_{n-1}&lt;0$ for
$\alpha=0$ and $(q_n-q_{n-1})+(p_n-p_{n-1}&gt;0$ for $\alpha=-1$.
Thus $\alpha&gt;0$ and $-1&lt;\overline{\alpha}&lt;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&amp;=&amp;[b_0;b_1,\ldots b_k,\overline{a_0,a_1,\ldots a_n}]\\
\beta&amp;=&amp;\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$&amp;$-1$&amp;0&amp;1&amp;2&amp;3\\ $a_n$&amp;&amp;10&amp;1&amp;1&amp;1\\ $p_n$&amp;1&amp;10&amp;11&amp;21&amp;32\\
$q_n$&amp;0&amp;1&amp;1&amp;2&amp;3
\end{tabular}

So

\begin{eqnarray*}
\alpha&amp;=&amp;\frac{32\alpha+21}{3\alpha+2}\\
3\alpha^2+(2-32)\alpha-21&amp;=&amp;0\\ \alpha^2-10\alpha-7&amp;=&amp;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}&gt;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&amp;=&amp;a_{k-1}Q_{k-1}-P_{k-1}\\ Q_k&amp;=&amp;\frac{(D-P_k^2)}{Q_{k-1}}\\
a_k&amp;=&amp;[\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}&amp;=&amp;\frac{\overline{\alpha_{n+1}}p_n+p_{n-1}}{
\overline{\alpha_{n+1}}q_n+q_{n-1}}\\
\overline{\alpha_{n+1}}&amp;=&amp;\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}}&lt;0$ for all $n$ sufficiently large.

If $\overline{\alpha_k}&lt;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&lt;-a_k\leq-1$$

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

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

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

Also $\alpha&gt;1$ so $Q&lt;P+\sqrt{D}$

If $N=[\sqrt{D}]$ we have $0&lt;P\leq N$ and $0&lt;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 $&gt;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&gt;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$&amp;0&amp;1&amp;2&amp;3&amp;4&amp;5&amp;6\\ $P_k$&amp;$-80$&amp;16&amp;5&amp;5&amp;2&amp;2&amp;5\\
$Q_k$&amp;$-32$&amp;7&amp;1&amp;7&amp;4&amp;7&amp;1\\ $a_k$&amp;2&amp;3&amp;10&amp;1&amp;1&amp;1
\end{tabular}

\begin{eqnarray*}
P_k&amp;=&amp;a_{k-1}Q_{k-1}-P_{k-1}\\ Q_k=\frac{D-P_k^2}{Q_{k-1}}\\
a_k&amp;=&amp;\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&gt;1$ and
$-1&lt;\overline{\alpha_0}&lt;0$

Now $\alpha_0=a_o+\frac{1}{\alpha_1}$ and $\alpha_1&gt;1$

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

so $-1&lt;\overline{\alpha_1}&lt;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&lt;-\overline{\alpha_n}&lt;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&gt;1$, if $\overline{\alpha_0}&lt;-1,\ \alpha_0$ is not
reduced and so its contu=inued fraction is not purely periodic.
But $\overline{\alpha_0}&lt;0\Rightarrow\alpha_1$ reduced, so if
$\overline{\alpha_0}&lt;-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}&amp;=&amp;a_0+\frac{1}{\overline{\alpha_1}}\\
\overline{\alpha_k}&amp;=&amp;a_k+\frac{1}{\overline{\alpha_1}}
\end{eqnarray*}

So, since $-1&lt;\overline{a_k}&lt;0$, if $\overline{\alpha_0}&lt;-1,\
a_0&lt;a_k$ and if $\overline{\alpha_0}&gt;1\ a_0&gt;a_k$.

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


\end{document}
</pre></body></html>