\documentclass[12pt]{report}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[dvips]{graphicx}
\usepackage[dvips]{graphics}
\usepackage{uuhonors}
\author{Michael Lowell Hofmann}
\title{The Length of the Continued Fraction of $p\sqrt{3}$}
\date{May 2004}
\degree{Honors Degree of Bachelor of Arts}
\department{Mathematics}
\advisor{Fletcher Gross}
\chair{Graeme Milton}
\supervisor{Gordan Savin}
\director{Martha S. Bradley}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{note}{Note}
\newtheorem{remark}{Remark}
\newtheorem{case}{CASE}
\newtheorem{case2}{CASE}
\newtheorem{algorithm}{Algorithm}
\bibliographystyle{plain}
%\pagestyle{plain}
\AtBeginDocument{\renewcommand\listfigurename{\center{LIST OF FIGURES}}}
\begin{document}
\maketitle
\begin{abstract}
An investigation into the length $\ell$, of the period of simple continued fractions for numbers of the form $p\sqrt{3}$. We investigate some relationships of continued fractions to other areas of mathematics like Pell's equation, indefinite binary quadratic forms and the class number, and use these results to show
$$
\frac{(p \pm 1)\log(\eta)}{h(12p^2) \log(4p)} \leq \ell(p\sqrt{3})
\leq \frac{(p \pm 1)\log(\eta)}{h(12p^2) \log(\alpha)},
$$
where $h(12p^2)$ is the class number of the order $\mathbb{Z} + \mathbb{Z}p\sqrt{3}$, $\eta = 2 + \sqrt{3}$ is the fundamental unit in $\mathbb{Z} + \mathbb{Z}\sqrt{3}$ and $\alpha = \frac{1+\sqrt{5}}{2}$.
We also used Matlab to calculate the actual value of the length for all positive integers up 10,000 and primes up 100,000 and showed the accuracy of our estimates as well as the amazing underlying structure that becomes apparent.
\end{abstract}
\begin{dedication}
I would like to thank my advisor Gordan Savin for his help, suggestions and ideas. Without him none of this would have been possible.
This work has been partially supported by an NSF VIGRE grant.
\end{dedication}
\pagestyle{plain}
%\null %\vskip 0.05in
\tableofcontents
\addcontentsline{toc}{chapter}{\protect\numberline{}List of Figures}
\listoffigures
\pagestyle{headings}
\chapter{Introduction} \thispagestyle{empty}
\renewcommand{\thepage}{\arabic{page}}
\setcounter{page}{1}
This paper grew out of a conjecture by Benedict~H.~Gross in his paper 'An elliptic curve test for Mersenne primes' \cite{Gr}. On page five of his paper he states ``Corollary 1.4\footnote{Corollary 1.4 states ``Assume that $p$ = $2^l - 1$ is prime. Then the order B = $\mathbb{Z} + p\mathbb{Z}\sqrt{3}$ of the index p in $\mathbb{Z} + \mathbb{Z}\sqrt{3}$ has class number 2 and fundamental unit $\eta = \epsilon^{2^{l-1}}$.'' The fact that the class number is 2 will be very important later. } implies that when $p = 2^l -1$ is prime, the continued fraction of the quadratic irrationality $p\sqrt{3}$ has an unusually long period. It might be interesting to make this more precise.'' I began investigating the period length of continued fractions of the form $z\sqrt{3}$ and this is the result.
For the sake of simplicity I concentrated mainly on the case when $z$ is prime, and I assume $p$ is a prime for the remainder of this paper.
We will proceed as follows, first a short introduction to continued fractions and their utility in solving the Pell equation. We will then use this to find the fundamental unit in a particular real quadratic field. Then we will proceed to quadratic binary forms and show their deep connection to continued fractions. This connection will lead us to the class number, which is a deep and difficult to understand mathematical object. However, the class number will give us the necessary machinery to accomplish our goal of setting bounds on the period of certain continued fractions. The last chapter explains more of the computational aspects of the problem as well as a short introduction to a few ideas that I still don't understand.
\chapter{Continued Fractions} \thispagestyle{empty}
\begin{definition}
\label{def:contfrac}
A simple continued fraction is an expression of the form $$ a_0 + {1 \over {a_1 + {1 \over { a_2 + { 1\over a_3+\ldots}}}}}$$
with $a_0$~$\in$~$\mathbb{Z}$~and~$a_n$~$\in$~$\mathbb{N}$~for~$n \geq 1.$
\end{definition}
In general the phrase continued fraction will mean simple continued fraction unless otherwise stated.
In order to represent continued fractions in a more concise way we will use one of the following notations:
$$ a_0+ {1 \over a_1+} {1\over a_2 +}{1\over a_3 +}\ldots $$
$$[a_0, a_1, a_2, a_3, \ldots ]. $$
The expression for a continued fraction can be either finite (the expression stops after some number of terms), or the expression can have an infinite number of terms. This leads to the following theorem which will be presented without proof.
\begin{theorem}
A number represented by a continued fraction is rational iff the continued fraction is finite.
\end{theorem}
\subsection{Definitions}
We make the following definitions to help construct the theory of continued fractions. A number of the following theorems are presented without proof. For a complete exposition on continued fractions see \cite{Dav} or \cite{Kh}.
\begin{definition}
For a given continued fraction $ [a_0, a_1, a_2, a_3, \ldots ] $ let
$$\left( \begin{array}{cc} A_0 & A_{-1} \\ B_0 & B_{-1} \\ \end{array} \right) = \left( \begin{array}{cc} a_0 & 1 \\ 1 & 0 \\ \end{array} \right)$$
and define $A_n$ and $B_n$ recursively via
$$\left( \begin{array}{c} A_n \\ B_n \\ \end{array} \right) = \left( \begin{array}{cc} A_{n-1} & A_{n-2} \\ B_{n-1} & B_{n-2} \\ \end{array} \right)\left( \begin{array}{c} a_n \\ 1 \\ \end{array} \right).$$
\end{definition}
\begin{theorem}
$\frac{A_n}{B_n}$ is the result of evaluating the first of n terms of the continued fraction and is called the nth convergent.
\end{theorem}
\begin{theorem} \label{thm:whycfconv}
Let ${A_m} \over {B_m}$ be the nth convergent of a continued fraction and suppose the convergents converge to D then
$A_0 \over B_0$, $A_2 \over B_2$, $A_4 \over B_4$ \ldots forms an increasing sequence less than D and
$A_1 \over B_1$, $A_3 \over B_3$, $A_5 \over B_5$ \ldots forms a decreasing sequence greater than D.
\end{theorem}
We also need to make sure that the idea of an infinite continued fraction actually makes sense. In other words if we define a sequence of convergents of an infinite continued fraction, will the sequence converge. Luckily for us it will, the theorem is stated without proof.
\begin{theorem}
All infinite continued fractions converge to some value in $\mathbb{R}$. This is a direct result of Theorem \ref{thm:whycfconv}.
\end{theorem}
Primarily we will be more concerned with infinite continued fractions and particularly with the continued fractions that represent quadratic irrationals, that is numbers of the form $\frac{P \pm \sqrt{D}}{Q}$, where P and Q are integers and D is a non-square positive number. The following important theorem is due to Lagrange.
\begin{theorem}
\label{thm:legrange}
Any quadratic irrational has a simple continued fraction which is periodic after a certain number of terms.
\end{theorem}
A partial proof is stated in the next section.
\section{Continued Fraction Algorithm}
As of yet we have not defined a way to find the continued fraction of a given number. In this section we define such an algorithm and in the process show that a simple continued fraction can be constructed uniquely for any real number.
\begin{algorithm}
\label{algor:contfracalg}
Let $\alpha$ be a real number. We construct our continued fraction as follows. To begin let r=$\alpha$, then follow these steps repeatedly:
\begin{enumerate}
\item{Set $a_n$ equal to $\lfloor r \rfloor$, where $\lfloor r \rfloor$ is the floor function of r.}
\item{Set s=r - $\lfloor r \rfloor$.}
\item{Set r=$s^{-1}$ and goto step 1.}
\end{enumerate}
This process stops if s = 0 and in this case the continued fraction is finite and $\alpha$ is rational. For irrational numbers this process continues indefinitely, but may be periodic as noted in Theorem~\ref{thm:legrange}.
\end{algorithm}
A simple example will illustrate this process. Let's find the continued fraction representation of $\sqrt{3}$.
\begin{eqnarray}
r & = &\sqrt{3} \\
a_0 & = & \lfloor r \rfloor = 1 \\
s & = & r - \lfloor r \rfloor = \sqrt{3} - 1 \label{eqn:beginperiod} \\
r & = & s^{-1} = {1 \over {\sqrt{3} - 1}} = { {\sqrt{3} + 1} \over 2} \\
a_1 & = & \lfloor r \rfloor = 1 \\
s & = & r - \lfloor r \rfloor = {{{\sqrt{3} + 1} \over { 2 }} - 1} = {{\sqrt{3} - 1} \over 2} \\
r & = & s^{-1} = {2 \over {\sqrt{3} -1 }} = {{2(\sqrt{3} + 1)} \over {2}} = {\sqrt{3} + 1} \\
a_2 & = & \lfloor r \rfloor = 2 \\
s & = & r - \lfloor r \rfloor = \sqrt{3} - 1 \label{eqn:endperiod}
\end{eqnarray}
Notice now that (\ref{eqn:endperiod}) is the exact same as (\ref{eqn:beginperiod}). From this point forward the terms of the continued fraction will just keep repeating. Thus $$\sqrt{3} = 1 + {1 \over 1 +}{1\over 2 +}{1\over 1 +}{1\over 2 +}\ldots$$
%%Notice that the continued fraction algorithm can be thought of as a generalization of the Euclidean algorithm. If $\alpha=\frac{p_1}{q_1}$ is rational then $\lfloor \alpha \rfloor = \frac{kq_1}{q_1}$ such that $0<= \frac{p_1}{q_1}-\frac{kq_1}{q_1}<1$. Thus if $r_1 = p_1-kq_1$ then $0<r_1<q_1$ so $r_1$ is the remainder and $\frac{1}{\alpha-\lfloor \alpha \rfloor} = \frac{q_1}{r_1}$ and the process continues.%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{remark}
\label{rem:gl2}
The continued fraction algorithm can be thought of in terms of the groups \emph{$GL_2(\mathbb{Z})$}. Consider the matrix {\tiny $\left( \begin{array}{c} r \\ 1 \\ \end{array} \right)$} which represents $\frac{r}{1}$.
\begin{enumerate}
\item{ Multiply on the left by $\left( \begin{array}{cc} 1 & -\lfloor r \rfloor \\ 0 & 1 \\ \end{array} \right)$}. This sends $\left( \begin{array}{c} r \\ 1 \\ \end{array} \right)$ to $\left( \begin{array}{c} r -\lfloor r \rfloor \\ 1 \\ \end{array} \right) = r -\lfloor r \rfloor$.
\item{ Multiply on the left by $\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right)$}. This sends $\left( \begin{array}{c} s \\ 1 \\ \end{array} \right)$ to $\left( \begin{array}{c} 1 \\ s \\ \end{array} \right) = 1/{}s$.
\item{ At the end of each loop the product of all the matrices is $\left( \begin{array}{cc} B_{n-1} & A_{n-1} \\ B_{n} & A_{n} \\ \end{array} \right)$.
Now the expression $\frac{A_{n}}{B_{n}}$ is the nth convergent of the continued fraction. The expression $\frac{A_{n-1}}{B_{n-1}}$ is the (n-1)th convergent.
}
\end{enumerate}
\end{remark}
Notice that what we have defined is just the M\"obius transform which is an endomorphism of the real numbers. This is also a group action so it makes sense to think of the product of the individual matrices as well as acting by inverses of matrices.
There is another algorithm that uses r=$-s^{-1}$ as the last step. This is equivalent to \emph{$SL_2(\mathbb{Z})$} group action where the second matrix would be {\tiny $\left( \begin{array}{cc} 0 & 1 \\ -1 & 0 \\ \end{array} \right)$}.
In Theorem \ref{thm:legrange} we stated that quadratic irrationals have a continued fraction that is periodic after a certain point. This leads to the following definition.
\begin{definition}
The length of the period of a continued fraction is defined as the number of terms in the period of a periodic infinite continued fraction. It is only defined when the number represented is a quadratic irrational. We denote this function by $\ell(\gamma)$.
\end{definition}
For the remainder of this paper, whenever length is mentioned it is assumed to be the length of the period of a continued fraction. We need to make sure that the length is well-defined. We do that by showing that a number has only a single representation as a continued fraction.
\begin{theorem}
\label{thm:uniquecontfrac}
Two \underline{simple} continued fractions represent the same number iff each term in the continued fraction is equal. (This is not true if the continued fractions are not simple.)
\end{theorem}
\begin{proof}
The if and only if part of this proof is clear. What we need to show for the other direction is that there is only one unique way of expressing a real number as a simple continued fraction. We will do this by showing that Algorithm \ref{algor:contfracalg} is the unique algorithm to find a simple continued fraction.
Lets take a closer look at the algorithm. Notice that $0~<~{1 \over a_n+} {1\over a_{n+1} +}\ldots~<~ 1$ where $a_i \in \mathbb{N}$, so it is clear that if we have a number $r$ which we want to write as $a_i + {1 \over a_{i+1}+} {1\over a_{i+2} +}\ldots$ in order to find $a_i$ we need a way to subtract a whole number from $r$ so that the result is between 0 and 1, but this is just the definition of the floor function so let $a_i = \lfloor r \rfloor$ and $r - \lfloor r \rfloor = s = {1 \over a_{i+1}+} {1\over a_{i+2} +}\ldots$ We have just reconstructed steps 1 and 2 of our algorithm, now we need to look at step 3.
Now $s = {1 \over a_{i+1}+} {1\over a_{i+2} +}\ldots$ and we need to figure out how to calculate the next $a_i$. Our statement implies $\frac{1}{s} = a_{i+1}+ {1\over a_{i+2} +}\ldots$ which brings us right back to where we started and allows us to continue to calculate the next $a_i$, but of course this is just step 3. Thus we have shown that our algorithm is the only way to calculate the continued fraction representation of a given a number and moreover a number must have exactly one representation as a continued fraction.
\end{proof}
\begin{definition}
A quadratic irrational is called purely periodic if the point where it begins to be periodic is the first term.
\end{definition}
For example we saw that $\sqrt{3} = [1,\overline{1,2}]$, where the bar means this part keeps repeating, so $\sqrt{3}$ is periodic, but not purely periodic. Whereas $\sqrt{3} +1 = [\overline{2,1}]$ is purely periodic.
\begin{definition}
A quadratic irrational $\beta$ is called reduced if $\beta > 1$ and $-1 < \overline{\beta} < 0$, where $\overline{\beta}$ is the conjugate of $\beta$.
\end{definition}
\begin{theorem} \label{thm:pureper}
A quadratic irrational is purely periodic iff it is reduced.
\end{theorem}
The proof is omitted.
\begin{proof}[Proof of Theorem \ref{thm:legrange}]
Suppose that a continued fraction is periodic after a certain point. In terms of matrices this means that after acting on {\tiny $\left( \begin{array}{c} \beta \\ 1 \\ \end{array} \right)$} by some matrix we get {\tiny $\left( \begin{array}{c} \beta \\ 1 \\ \end{array} \right)$} back again. So
$$\left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right) \left( \begin{array}{c} \beta \\ 1 \\ \end{array} \right) = \left( \begin{array}{c} \beta \\ 1 \\ \end{array} \right), $$ % \vskip 5pt
After multiplying this out and remembering what the definitions mean we get $$\frac{a\beta + b}{c\beta + d} = \frac{\beta}{1}.$$
This implies that $$c{\beta}^2 + (d - a)\beta - b = 0.$$
We know that $\beta$ is irrational since having a periodic continued fraction implies that the continued fraction is not finite, so $\beta$ must be a quadratic irrational.
If $\beta$ is a quadratic irrational, all that we need to complete the proof is show that after enough steps using the continued fraction algorithm we get a number $r_n$ that satisfies Theorem \ref{thm:pureper}. This portion of the proof is also omitted and the reader is again invited to read further in \cite{Dav}.
\end{proof}
\section{The Pell Equation}
\begin{definition}
The Pell equation is an equation of the form $x^2-Dy^2=1$ where D is a positive non-square integer.
\end{definition}
\begin{theorem}
Every Pell equation has an infinite number of solutions in the integers.
\end{theorem}
\begin{proof} \label{thm:cfandpe}
Pell's equation is very closely related to continued fractions. Suppose we have the equation $x^2 - Dy^2 = 1$, notice that $\sqrt{D}+\lfloor \sqrt{D} \rfloor$ is a reduced number and is thus purely periodic. It is easy to find the continued fraction of $\sqrt{D}+\lfloor \sqrt{D} \rfloor$ through the first period. Now using matrices as we defined earlier we have some element in the group \emph{$GL_2(\mathbb{Z})$} such that
$$\left( \begin{array}{cc} a' & b' \\ c' & d' \\ \end{array} \right) \left( \begin{array}{c} \sqrt{D}+\lfloor \sqrt{D} \rfloor \\ 1 \\ \end{array} \right) = \left( \begin{array}{c} \sqrt{D} + \lfloor \sqrt{D} \rfloor \\ 1 \\ \end{array} \right).$$
We can rewrite this as
$$\left( \begin{array}{cc} a' & b' \\ c' & d' \\ \end{array} \right) \left(\begin{array}{cc} 1 & \lfloor \sqrt{D} \rfloor \\ 0 & 1 \\ \end{array} \right) \left( \begin{array}{c} \sqrt{D} \\ 1 \\ \end{array} \right) = \left(\begin{array}{cc} 1 & \lfloor \sqrt{D} \rfloor \\ 0 & 1 \\ \end{array} \right) \left( \begin{array}{c} \sqrt{D} \\ 1 \\ \end{array} \right).$$
Which gives
$$\left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right) \left( \begin{array}{c} \sqrt{D} \\ 1 \\ \end{array} \right) = \left( \begin{array}{c} \sqrt{D} \\ 1 \\ \end{array} \right),$$
where
$$\left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right) = {\left(\begin{array}{cc} 1 & \lfloor \sqrt{D} \rfloor \\ 0 & 1 \\ \end{array} \right)}^{-1} \left( \begin{array}{cc} a' & b' \\ c' & d' \\ \end{array} \right) \left(\begin{array}{cc} 1 & \lfloor \sqrt{D} \rfloor \\ 0 & 1 \\ \end{array} \right).$$
This means that
$$\frac{a\sqrt{D} +b}{c\sqrt{D} + d} = \frac{\sqrt{D}}{1}$$ or that $$a\sqrt{D} + b = cD + d\sqrt{D}.$$
Since $\sqrt{D}$ is irrational we now have two equations, $a = d$ and $ b = cD$. Substituting this back into our original matrix we get
$$\left( \begin{array}{cc} d & cD \\ c & d \\ \end{array} \right).$$
This matrix is in \emph{$GL_2(\mathbb{Z})$} so its determinant is $\pm 1$, so $d^2-Dc^2 = \pm 1$. If it is 1 then we have constructed a solution $(d,c)$ to the Pell equation. If $d^2 - D c^2 = -1$ then
$$(d - \sqrt{D}c)(d + \sqrt{D}c) = -1,$$ now squaring both sides we get
$$(d^2 + Dc^2 - 2cd\sqrt{D})(d^2 + Dc^2 + 2cd\sqrt{D}) = 1.$$
So
$$(d^2 + Dc^2)^2 - D(2cd)^2 = 1$$ thus $(d^2 + Dc^2, 2cd)$ is a solution to the Pell equation.
Now supposing we have a solution $(x_1,y_1)$ such that $x_1\ne 0$ and $y_1 \ne 0$, we will show how to construct an infinite number of solutions.
if $(x_1,y_1)$ is a solution this means
$${x_1}^2-D{y_1}^2=1$$
which factors as
$$({x_1}+\sqrt{D}{y_1})({x_1}-\sqrt{D}{y_1})=1.$$
Now taking the $n$th power of both sides
$${(x_1+\sqrt{D}y_1)}^n{(x_1-\sqrt{D}y_1)}^n=1.$$
Let ${(x_1+\sqrt{D}y_1)}^n$ = $x_n+\sqrt{D}y_n$ then $(x_n,y_n)$ also solves the Pell equation and $(x_n,y_n)$ is clearly distinct from $(x_1,y_1)$.
\end{proof}
Here is an example of how we can use continued fractions to find solutions to the Pell equation. Consider the equation $x^2-3y^2=\pm 1$. We found earlier that the continued fraction representation of $\sqrt{3} =[1,\overline{1,2}] $. Now let's use the \emph{$GL_2$} action we defined earlier (Remark \ref{rem:gl2}).
According to our algorithm we get
$$\left( \begin{array}{cc}
0 & 1 \\
1 & 0 \\
\end{array} \right)
\left( \begin{array}{cc}
1 & 2 \\
0 & 1
\end{array} \right)
\left( \begin{array}{cc}
0 & 1 \\
1 & 0 \\
\end{array} \right)
\left( \begin{array}{cc}
1 & 1 \\
0 & 1 \\
\end{array} \right)
\left( \begin{array}{cc}
0 & 1 \\
1 & 0 \\
\end{array} \right)
\left( \begin{array}{cc}
1 & 1 \\
0 & 1 \\
\end{array} \right)
= \left( \begin{array}{cc}
1 & 2 \\
3 & 5 \\
\end{array} \right).$$
Now the convergents we are interested in are in the top row, 1 and 2. This implies the fundamental solution to the Pell equation $x^2-3y^2=\pm 1$ is $x = 2$ and $y = 1$. which we can check: $2^2-3*1^2=1$. To find all other solutions we can either use powers of the matrix {\tiny $\left( \begin{array}{cc}
1 & 2 \\
3 & 5 \\
\end{array} \right)$} or we can take powers of $2+\sqrt{3}$.
\subsection{Considering the Pell Equation Modulo Four}
By looking at the Pell equation modulo four we can determine something about the nature of the solutions.
The Pell equation we are interested in is $x^2-3p^2y^2= \pm 1$ with $p$ prime and $x$ and $y$ integers. The reason for this is that finding the solution uses the continued fraction of $p\sqrt{3}$. Now by taking everything modulo 4 we have $$ x^2-3p^2y^2~\equiv~\pm~1~\pmod{4}.$$
\begin{theorem}
\label{thm:mod4}
The solutions of the equation $x^2-3p^2y^2 = \pm 1$ with $p$ an odd prime are of the form $x$ even and $y$ odd, or $x$ odd $y$ even and $ x^2-3p^2y^2$ is never equal to $-1$.
\end{theorem}
\begin{proof}
Assuming $p$ is an odd prime, we now have four cases depending on if $x$ and $y$ are even or odd.
\begin{case}
\label{ca:case1}
If $x$ and $y$ are even then our equation $x^2-3p^2y^2 \equiv \pm 1 \pmod{4}$ simplifies to $0-0 \equiv \pm 1 \pmod{4}$ which is a contradiction.
\end{case}
\begin{case}
\label{ca:case2}
If $x$ is even and $y$ is odd our equation simplifies to $0-3\equiv \pm 1 \pmod{4}$ or $1 \equiv \pm 1 \pmod{4}$.
\end{case}
\begin{case}
\label{ca:case3}
If $x$ is odd and $y$ is even our equation simplifies to $1-0\equiv \pm 1 \pmod{4}$ or $1 \equiv \pm 1 \pmod{4}$.
\end{case}
\begin{case}
\label{ca:case4}
If $x$ and $y$ are odd then we have $1-3\equiv \pm 1 \pmod{4}$ which is a contradiction.
\end{case}
This shows that we have two possible cases, either $x$ is even and $y$ is odd (CASE~\ref{ca:case2}), or $y$ is even and $x$ is odd (CASE~\ref{ca:case3}). In both these cases the equation is equal to 1, and never $-1$. Note also that even in the case $p=2$ the equation reduces to $x^2 \equiv \pm 1 \pmod{4}$ which implies $x$ is odd and we still must get 1.
\end{proof}
\subsection{The Parity of the Length of Continued Fractions of p$\sqrt{3}$}
In the last section we showed that the Pell equation $x^2-3p^2y^2$ is never equal to $-1$ for the special case $D=3p^2$, this has ramifications on the parity of the length of continued fractions representing $\sqrt{3p^2}$.
\begin{theorem}
The length of continued fractions representing numbers of the form $p\sqrt{3}$ is always even.
\end{theorem}
\begin{proof}
We know there exists a matrix in \emph{$GL_2(\mathbb{Z})$} such that $$\left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right) \left( \begin{array}{c} \sqrt{3p^2} \\ 1 \\ \end{array} \right) = \left( \begin{array}{c} \sqrt{3p^2 } \\ 1 \\ \end{array} \right).$$ Using a method similar to Theorem \ref{thm:cfandpe} we find that our matrix becomes $$\left( \begin{array}{cc} d & 3p^2c \\ c & d \\ \end{array} \right)$$ and we know that the determinant of this matrix is $\pm1$ and the determinant is a solution to the equation $d^2-3p^2c^2$. But we know from the previous section that the only possibility is +1. So the determinant of {\tiny $\left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right)$} is 1.
Lets look at how this matrix is constructed. Remark \ref{rem:gl2} tells us that this matrix is a product of matrices of the form $$\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right)\left( \begin{array}{cc} 1 & -\lfloor \alpha_i \rfloor \\ 0 & 1 \\ \end{array} \right)$$ and we have a pair of these matrices for each element in the period of the continued fraction. Now the determinant of this each individual pair of matrices is $-1$ and the determinant of there product, the matrix {\tiny $\left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right)$}, is 1. This implies there must be an even number of element is the period of the continued fraction, so the length must be even.
\end{proof}
\section{Units}
\begin{definition}
\label{def:rqf}
A real quadratic ring is $\mathbb{Z}[\sqrt{D}]$ with $D \in \mathbb{N}$ and D non-square.
This is the ring of algebraic integers when $D\equiv 2 \hbox{ or } 3 \pmod{4}$.
\end{definition}
\begin{definition}
\label{def:norm}
The Norm of an element a+b$\sqrt{D}$ in $\mathbb{Z}[\sqrt{D}]$ is $a^2-Db^2$.
\end{definition}
\begin{definition}
\label{def:unit}
A unit in a real quadratic field is an element $\alpha$ such that Norm($\alpha$) = $\pm 1$.
\end{definition}
Notice that if $(x,y)$ is any solution to the Pell equation $x^2-Dy^2= \pm1$ then $x+y\sqrt{D}$ is a unit in $\mathbb{Q}[\sqrt{D}]$.
\begin{definition}
\label{def:fundunit}
A fundamental unit of a real quadratic field is an element $\eta$ such that all other units in the field can be formed as powers of $\eta$ multiplied by $\pm 1$.
\end{definition}
\begin{theorem}
In the ring $\mathbb{Z}[\sqrt{D}]$ where $D > 0$ and $D \equiv \hbox{ 2 or 3 (mod 4)}$, the fundamental unit is $x+y\sqrt{D}$ where (x,y) is the first solution of the Pell equation $x^2-Dy^2 = \pm 1$. Where by first solution it is meant the first solution found by the continued fraction method.
\end{theorem}
The Proof is omitted
\subsection{Finding the Fundamental Unit in $\mathbb{Z}[\sqrt{3}]$}
The fundamental unit of the ring $\mathbb{Z}[\sqrt{3}]$ will be very important to later calculations and this calculation also shows a concrete example of continued fractions, the Pell equation and units.
\begin{theorem}
\label{thm:fundunit3}
The fundamental unit in $\mathbb{Z}[\sqrt{3}]$ is $2+\sqrt{3}$.
\end{theorem}
\begin{proof}
We calculated earlier that $$\sqrt{3} = 1 + {1 \over 1 +}{1\over 2 +}{1\over 1 +}{1\over 2 +}\ldots$$ and we used that knowledge to find a solution to the Pell Equation $x^2-3y^2=1$, namely $2+\sqrt{3}$, thus the fundamental unit of $\mathbb{Z}[\sqrt{3}]$ is $2+\sqrt{3}$.
\end{proof}
\chapter{Binary Quadratic Forms} \thispagestyle{empty}
\begin{definition}
\label{def:quadform}
A binary quadratic form is an expression $ax^2+bxy+cy^2$ with $a, b, c \in \mathbb{Z}$. To save space we also write this as (a,b,c). %%Also let $\mathcal{Q}$ denote the space of all binary quadratic forms.
\end{definition}
%%!WHY ARE THEY IMPORTANT?!
%%The theory of quadratic forms revolves around the question of which numbers can be represented by a quadratic form.
%%!LATTICE!
\begin{definition}
\label{def:equiv}
Two binary quadratic forms $ax^2+bxy+cy^2$ and $a'x^2+'bxy+c'y^2$ are equivalent if there is a transformation x = pX + qY, y = rX + sY with ps-qr = $\pm 1$ such that $a(pX+qY)^2+b(pX+qY)(rX+sY)+c(rX+sY)^2=a'X^2+b'XY+c'Y^2$.
We express this as (a,b,c) $\sim$ (a',b',c').
\end{definition}
Note that the matrix
{\tiny $\left( \begin{array}{cc} p & q \\ r & s \\ \end{array} \right)$} is in \emph{$GL_2(\mathbb{Z})$}.
\begin{theorem}
$\sim$ forms an equivalence relation.
\end{theorem}
\begin{proof}
Let r, s and t be binary quadratic forms.
We need to show three things.
1. That r $\sim$ r for any quadratic form r. This is trivial since the identity matrix is in \emph{$GL_2(\mathbb{Z})$}.
2. If r $\sim$ s then s $\sim$ r. If r $\sim$ s this means there is a element in \emph{$GL_2(\mathbb{Z})$} that transforms r into s. Since \emph{$GL_2(\mathbb{Z})$} is a group, the inverse of this element is also in \emph{$GL_2(\mathbb{Z})$} and it transforms s back to r so s $\sim$ r.
3. If r $\sim$ s and s $\sim$ t then r $\sim$ t. Again this just follows from the nature of \emph{$GL_2(\mathbb{Z})$}. Since r $\sim$ s and s $\sim$ t this implies there are two elements in \emph{$GL_2(\mathbb{Z})$} that send r to s and s to t respectively. The composition of these two operations which is just their product in \emph{$GL_2(\mathbb{Z})$} (Which is also in \emph{$GL_2(\mathbb{Z})$}) will send r to t, so r $\sim$ t.
These three criteria show that $\sim$ is an equivalence relation.
\end{proof}
Since we have an equivalence relation, it now makes sense to split quadratic forms into equivalence classes based on the following definition.
\begin{definition}
The equivalence class of a given quadratic form x is all quadratic forms that are equivalent to x.
\end{definition}
\section{Discriminant}
\begin{definition}
\label{def:disc}
The discriminant D of the binary quadratic form $ax^2+bxy+cy^2$ is defined as $b^2-4ac$.
\end{definition}
\begin{corollary}
\label{cor:Dis0or1}
Consider the discriminant modulo 4. Then $D \equiv b^2-4ac \pmod{4}$ implies
$$D \equiv b^2 \pmod{4}.$$
Thus $D \equiv 0 \hbox{ or } 1 \pmod{4}$ depending on if b is even or odd respectively. The discriminant must also be congruent to 0 or 1 modulo 4 and is never congruent to 2 or 3.
\end{corollary}
\begin{corollary}
The discriminants of two equivalent quadratic forms are equal.
\end{corollary}
\begin{proof}
We can express the quadratic form $ax^2+bxy+cy^2$ as {\tiny $\left( \begin{array}{cc}
a & b/2 \\
b/2 & c \\
\end{array} \right)$}. Suppose (a',b',c') $\sim$ (a,b,c) then this implies there is a matrix {\tiny $\left( \begin{array}{cc}
p & q \\
r & s \\
\end{array} \right)$} in \emph{$GL_2(\mathbb{Z})$} such that
$$
\left( \begin{array}{cc}
a' & b'/2 \\
b'/2 & c' \\
\end{array} \right) =
\left( \begin{array}{cc}
p & q \\
r & s \\
\end{array} \right)
\left( \begin{array}{cc}
a & b/2 \\
b/2 & c \\
\end{array} \right)
{\left( \begin{array}{cc}
p & q \\
r & s \\
\end{array} \right)}^{\top}.
$$
Since {\tiny $\left( \begin{array}{cc}
p & q \\
r & s \\
\end{array} \right)$} is in \emph{$GL_2(\mathbb{Z})$} this implies that
$$
\left| \begin{array}{cc}
a' & b'/2 \\
b'/2 & c' \\
\end{array} \right| =
\left| \begin{array}{cc}
a & b/2 \\
b/2 & c \\
\end{array} \right|.
$$
Which implies that $a'c' - \frac{{(b')}^2}{4} = ac - \frac{b^2}{4}$, which implies that the discriminants of equivalent forms are equal.
\end{proof}
\section{Reduced Forms}
\begin{definition}
\label{def:posdef}
A quadratic form $ax^2+bxy+cy^2$ is called definite if it's discriminant is less than 0. If its discriminant is greater than 0 it is called indefinite. When the discriminant is 0 it is a degenerate case.
\end{definition}
We will be concerned with quadratic forms which have determinant $12p^2$. The reason for this will become apparent in the next section. $12p^2$ is always a positive number, and hence all such forms are indefinite forms.
\begin{definition}
An indefinite quadratic form $ax^2+bxy+cy^2$ is called reduced if $0 < -b < \sqrt{D} \hbox{ and } b + \sqrt{D} < 2a < -b + \sqrt{D}$, where D is the discriminant of the quadratic form.
\end{definition}
There is also another notion of reduced where $a$ is replaced by $|a|$. The relationship between these two notions is similar to the comments after Remark~\ref{rem:gl2}. The way we defined equivalence is called \emph{$GL_2$}-equivalence, whereas using $|a|$ is called \emph{$SL_2$}-equivalence.
\begin{theorem}
A quadratic form $ax^2 + bxy + cy^2$ is reduced iff $ax^2 + bx + c$ is the minimal polynomial of a reduced number.
\end{theorem}
\begin{proof}
Let $\gamma$ be reduced and suppose $\gamma$ is a root of $ax^2 + bx + c$ with $a$ positive, thus $\gamma > 1$ and $-1 < \overline{\gamma} < 0 $ and $\gamma = \frac{-b + \sqrt{D}}{2a}$ and $\overline{\gamma} = \frac{-b - \sqrt{D}}{2a}$ by the quadratic formula. Now $\frac{-b + \sqrt{D}}{2a} > 1$ and $-1 < \frac{-b - \sqrt{D}}{2a} < 0$, which implies $$-b+\sqrt{D} > 2a \hbox{ and } -2a < -b - \sqrt{D} < 0.$$ So
$$ b + \sqrt{D} < 2a < -b + \sqrt{D} \hbox{ and } 0 < -b < \sqrt{D},$$ which is the definition of $ax^2 + bxy + cy^2$ being reduced.
Now assume $ax^2 + bxy + cy^2$ is reduced. This means $$ b + \sqrt{D} < 2a < -b + \sqrt{D} \hbox{ and } 0 < -b < \sqrt{D},$$ which implies $$1 < \frac{-b + \sqrt{D}}{2a} \hbox{ and } 0 > \frac{-b - \sqrt{D}}{2a} > -1.$$ If $\gamma = \frac{-b + \sqrt{D}}{2a}$ we see that $\gamma$ is reduced and its minimal polynomial is $$(x - \gamma)(x-\overline{\gamma}) = ax^2 + bx + c.$$
\end{proof}
%\begin{lemma}
%There is a 1-1 correspondence between primitive quadratic forms and quadratic irrationals of the form ${-B+\sqrt{B^2-4AC}}{2A}$.
%\end{lemma}
%\begin{proof}
%Send $(a,b,c)$ to $\frac{-b+\sqrt{b^2-4ac}}{2a}$ and vice versa.
%This is a very powerful tool in dealing with quadratic forms.
%\end{proof}
\begin{corollary}
Each quadratic form has a reduced form.
\end{corollary}
\begin{proof}
To each quadratic form $ax^2 + bxy + cy^2$ we can attach a quadratic irrational $\frac{-b+\sqrt{D}}{2a}$ which is simply a root to the equation $ax^2 + bx + c$.
Now we know that under continued fraction action each quadratic irrational will turn into a reduced number after some finite number of steps. But the continued fraction action is generated matrices in \emph{$GL_2(\mathbb{Z})$}. Thus if $\gamma$ is a quadratic irrational and $\gamma'$ is the reduced quadratic irrational that we get after a finite number of steps of the continued fraction algorithm, then the quadratic forms associated with $\gamma$ and $\gamma'$ are equivalent. Thus since any quadratic irrational can be turned into a reduced number then any quadratic form can be made into a reduced form.
\end{proof}
\begin{algorithm} \label{algor:reduceit}
Notice this gives us an effective algorithm for computing a reduced form of a given quadratic form $ax^2 + bxy + cy^2$. Simply let $\gamma = \frac{-b + \sqrt{D}}{2a}$, now perform the continued fraction algorithm (Algorithm \ref{algor:contfracalg}) on $\gamma$ until we reach a $\gamma' = \frac{-b'+\sqrt{D}}{2a'}$ which is purely periodic and thus reduced. Now we go back to $a'x^ + b'xy + c'y^2$ which is an equivalent reduced form.
Note that there is generally not a unique reduced form associated to $\gamma$, but a set of $\ell(\gamma)$ reduced forms, where $\ell$ is the length of the period of the continued fraction of $\gamma$, corresponding to each different reduced quadratic irrational in the period of the continued fraction.
\end{algorithm}
As an example of reducing quadratic forms consider $-x^2+20xy-25y^2$ and note $D=300$. Call the associated quadratic irrational $\gamma = \frac{-20 + \sqrt{300}}{-2}$. Using the continued fraction algorithm it is easy to compute that
$$\gamma = [-1,-2,\overline{-1,-16,-1,-1}].$$
After one step we have
$$\gamma_1 = \frac{18 +\sqrt{300}}{12} = [-2,\overline{-1,-16,-1,-1}].$$
Notice $\gamma_1$ is not purely periodic so it is not a reduced number. This means the associated quadratic form $(6,-18,-11)$ is not reduced which is also easily checked from the definition.
$$\gamma_2 = \frac{6+ \sqrt{300}}{22} = [\overline{-1,-16,-1,-1}]$$
Now $\gamma_2$ is purely periodic and is thus reduced so the associated quadratic form $(11,-6,-6)$ is also reduced, so we have found a reduced form equivalent to our original quadratic form.
However, our process can continue,
$$\gamma_3 = \frac{16 +\sqrt{300}}{2} = [\overline{-16,-1,-1,-1}]$$
is also reduced and is different from $\gamma_2$ and yields $(1,-16,-11)$ which is also a reduced form equivalent to $(-1,20,-25)$. Similarly
$\gamma_4 = [\overline{-1,-1,-1,-16}]$ and $\gamma_5 = [\overline{-1,-1,-16,-1}]$ are also distinct reduced numbers and will give equivalent reduced forms, but now $\gamma_6$ = $\gamma_2$ so this process will not yield any more reduced forms.
So we see that for our original quadratic form $(-1,20,-25)$ we found a set of four equivalent reduced forms. It turns out these are all the equivalent reduced forms and that the forms we found form something called a cycle which will be important to us in the next section.
\begin{theorem} \label{thm:finiterf}
The number of reduced forms of a given discriminant is always finite.
\end{theorem}
\begin{proof}
The conditions that $D = b^2 - 4ac$ and $0 < -b < \sqrt{D}$ is very restrictive. This limits the possibilities for b to a finite number and there are also only a finite number of ways to factor $D-b^2$ into $-4ac$. This implies that the number of reduced forms for each D is also finite.
\end{proof}
\subsection{Primitive Reduced Forms}
\begin{definition}
\label{def:prim}
A binary quadratic form $ax^2+bxy+cy^2$ is called primitive if $a$, $b$ and $c$ have no common factor.
\end{definition}
Which quadratic forms with discriminant $12p^2$ with $p$ prime are not primitive?
\begin{theorem}
\label{thm:allbut2}
if $D = 12p^2$ then all the reduced forms of discriminant $D$ are primitive except two.
\end{theorem}
We'll first need a lemma to prove this.
\begin{lemma}
The only reduced forms with discriminant twelve are $(1,-2,-2)$ and $(2,-2,-1)$.
\end{lemma}
\begin{proof}
We know $12 = D = b^2-4ac$, this implies that 4 divides $b^2$ or that 2 divides $b$. Since $(a,b,c)$ is a reduced quadratic form this also means that $0 < -b < \sqrt{D} = \sqrt{12}$, so $b$ must be $-2$. Now $12 = 4 - 4ac$, this reduces to $ -2 = ac$, since we also know $-2 + \sqrt{12} < 2a < 2 + \sqrt{12}$ which means $a$ is 1 or 2. This implies that $c$ is $-2$ or $-1$ respectively, so $(1,-2,-2)$ and $(2,-2,-1)$ are the only reduced forms of discriminant 12.
\end{proof}
\begin{proof}[Proof of Theorem \ref{thm:allbut2}]
Let $12p^2=D=b^2-4ac$, if $g=GCD(a,b,c)$ then $g^2$ divides $12p^2$. Since $p$ is prime, if $g$ is greater than 1 then either $g = 2$, $g = p$ or $g = 2p$. Lets consider the three cases.
\begin{case2} $g = 2$
\label{ca1:case1}
Lets factor 2 out: $$D'={\left(\frac{b}{2}\right)}^2-4 \left( \frac{a}{2} \right) \left( \frac{c}{2} \right) = 3p^2.$$ Corollary \ref{cor:Dis0or1} showed $D'$ is always congruent to 0 or 1 modulo 4 so this implies that in this case $p = 2$.
Since $p = 2$ we get $D' = 12$ which has reduced quadratic forms $(1,-2,-2)$ and $(2,-2,-1)$ from the lemma, so our original discriminant $D=12p^2$ or D=48 has only two non-primitive reduced forms, $(2,-4,-4)$ and $(4,-4,-2)$ or written another way, $(p,-2p,-2p)$ and $(2p,-2p,-p)$.
\end{case2}
\begin{case2} $g = p$
\label{ca1:case2}
Lets factor p out: $$D'={\left(\frac{b}{p}\right)}^2-4 \left (\frac{a}{p} \right) \left( \frac{c}{p} \right) = 12.$$ So again we have the case D'=12. So $D=12p^2$ again only has two non-primitive reduced forms $(p,-2p,-2p)$ and $(2p,-2p,-p)$.
\end{case2}
\begin{case2} $g = 2p$
\label{ca1:case3}
Lets factor $2p$ out: $$D'={ \left(\frac{b}{2p} \right) }^2-4 \left( \frac{a}{2p} \right) \left( \frac{c}{2p} \right) = 3.$$ Here we have the case that $D'=3$, but this is a contradiction since $D' \equiv 0$ or $1~\pmod{4}$.
\end{case2}
So there are only two non-primitive equivalence classes of reduced forms with discriminant $12p^2$, namely $(p,-2p,-2p)$ and $(2p,-2p,-p)$.
\end{proof}
These examples also show an interesting property of reduced forms. It appears for any reduced form $(a,b,c)$ then $(-c,b,-a)$ is also a reduced form. This fact is stated in the following theorem.
\begin{theorem} \label{thm:times2}
If a quadratic form $(a,b,c)$ with discriminant $D = 12p^2$ is reduced then there is another distinct reduced form associated with it, namely $(-c,b,-a)$.
\end{theorem}
\begin{proof}
First we want to show that $(-c,b,-a)$ is also a reduced form, then we need to show that it is also distinct from $(a,b,c)$.
Clearly this quadratic form still has discriminant D, since $D - b^2 = -4ac$ this implies $(\sqrt{D} - b)(\sqrt{D} + b) = -4ac$. Since $0 < -b < \sqrt{D}$ this implies that $-4ac$ is positive and since $a$ is positive ($0 < \sqrt{D} + b < 2a$) it is clear $c$ must be negative, so $(\sqrt{D} - b)(\sqrt{D} + b) = (2a)(2(-c))$. Since $\sqrt{D} + b< 2a < \sqrt{D} - b$ this implies that $\sqrt{D} + b< 2(-c) < \sqrt{D} - b$. This implies that $(-c,b,-a)$ is a reduced form.
In order to check the that the forms are all distinct we need to show that $a \neq -c$. If $a = -c$ then $b^2 + 4a^2 = D = 12p^2$. This implies $(\frac{b}{2})^2 + a^2 = 3p^2$ So $3p^2$ is the sum of two squares, but an integer with a three in it's square-free part can never be a sum of two squares which implies $a \neq -c$, completing the proof.
Notice that if $D \neq 12p^2$ there is no reason the forms need to be distinct.
\end{proof}
\begin{corollary}
This theorem yields the obvious corollary: The number of reduced forms of a given discriminant of the form $12p^2$ is always divisible by 2.
\end{corollary}
\chapter{The Class Number} \thispagestyle{empty}
\section{What is the Class Number?}
\begin{definition}
For the purposes of our discussion we define the class number $h(D)$ to be the number of equivalence classes of primitive binary quadratic forms of a given discriminant $D$.
\end{definition}
The class number is a much more general object that can be defined in any number field, but in a quadratic number field it can be defined as the equivalence classes of full modules of discriminant D. In particular the modules we are interested in have the structure $\mathbb{Z} + p\sqrt{3}\mathbb{Z}$ which have discriminant $4(3p^2) = 12p^2$.
There is a bijective map between equivalence classes of modules and equivalence classes of reduced forms. Thus in order to calculate the class number $h(D)$ we will try to count the number of equivalence classes of quadratic forms with discriminant $D$. Since each quadratic form is equivalent to a reduced form we can look at the number of equivalence classes of reduced forms.
\begin{corollary}
The class number of a given discriminant is always finite.
\end{corollary}
\begin{proof}
Theorem \ref{thm:finiterf} states the there are only a finite number of reduced forms of any discriminant. It immediately follows that the class number of any discriminant is also finite.
\end{proof}
\subsection{The Underlying Structure} \label{subsec:structure}
The structure of real quadratic fields is much more complex and beautiful than that of imaginary quadratic fields. In imaginary quadratic fields each reduced form is in its own equivalence class\footnote{The way reduced forms are defined in the imaginary case is different, but the idea is the same, namely to find a representative binary form in each equivalent class.}, but in real quadratic fields this is not true. Instead the reduced forms form cycles, and the class number is the number of such cycles. First a couple of definitions,
\begin{definition}
Two reduced numbers $\alpha$ and $\beta$ are called adjacent if $\beta = \frac{1}{\alpha - \lfloor \alpha \rfloor}$, that is if we perform one loop of the continued fraction algorithm on $\alpha$ and we get $\beta$. Specifically we say $\beta$ is right adjacent of $\alpha$ and $\alpha$ is left adjacent of $\beta$.
\end{definition}
\begin{definition}
Two reduced forms $(a,b,c)$ and $(a',b',c')$ are called adjacent if their associated quadratic irrationals $\alpha$ and $\alpha'$ are adjacent.
\end{definition}
\begin{theorem}
Let $\alpha$ be a reduced number. Then there always exists a unique reduced number that is right adjacent of $\alpha$ and a unique reduced number that is left adjacent of $\alpha$.
\end{theorem}
\begin{proof}
Let $\alpha$ be a reduced number. One direction is easy, let $\beta = \frac{1}{\alpha - \lfloor \alpha \rfloor}$. To show $\beta$ is right adjacent of $\alpha$ we just need to show $\beta$ is reduced. $0 < \alpha - \lfloor \alpha \rfloor < 1$ thus $\beta = \frac{1}{\alpha - \lfloor \alpha \rfloor} > 1$.
Now
$$\overline{\beta} = \overline{\frac{1}{\alpha - \lfloor \alpha \rfloor}} = \frac{1}{\overline{\alpha} - \lfloor \alpha \rfloor}$$
so lets consider $\overline{\alpha} - \lfloor \alpha \rfloor$. Since $\alpha > 1$ and $\lfloor \alpha \rfloor \in \mathbb{N}$, then $-1 < \overline{\alpha} < 0$ implies $-1 - \lfloor \alpha \rfloor < \overline{\alpha} - \lfloor \alpha \rfloor < -\lfloor \alpha \rfloor$ which means
$$ 0 > \frac{1}{-1 - \lfloor \alpha \rfloor} > \frac{1}{\overline{\alpha} - \lfloor \alpha \rfloor} > \frac{1}{-\lfloor \alpha \rfloor} \ge -1.$$
So $0 > \overline{\beta} > -1$ which means $\beta$ is reduced and $\beta$ is right adjacent of $\alpha$. Uniqueness in this case is obvious.
Now in order to show there is an element left adjacent of $\alpha$ we need to find a reduced number $\beta$ such that $$\frac{1}{\beta - \lfloor \beta \rfloor} = \alpha.$$ This would mean $$\beta = \frac{1}{\alpha} + \lfloor \beta \rfloor.$$ So far we would have many choices for $\beta$, but now we want to impose the additional condition that $-1 < \overline{\beta} < 0$.
$$\overline{\beta} = \frac{1}{\overline{\alpha}} + \lfloor \beta \rfloor \hbox{ where } \frac{1}{\overline{\alpha}} < -1,$$ thus $\lfloor \beta \rfloor$ is the unique natural number such that $$-1 < \frac{1}{\overline{\alpha}} + \lfloor \beta \rfloor < 0.$$ In fact this number is $- \lfloor \frac{1}{\overline{\alpha}} \rfloor - 1$. Thus $$\beta = \frac{1}{\alpha} - \lfloor \frac{1}{\overline{\alpha}} \rfloor - 1$$ and $\beta$ is reduced by our construction.
\end{proof}
\begin{corollary} \label{cor:adj}
It immediately follows that any reduced form has a unique right and left adjacent reduced form.
\end{corollary}
\begin{theorem}
Reduced forms in real quadratic fields can be partitioned into cycles.
\end{theorem}
\begin{proof}
Pick a reduced form, the next element in the cycle is simply the next right adjacent reduced form. Since there are only a finite number of reduced forms eventually we must come back to a reduced form that we have already used, but since each reduced form has a unique form to its left and right, the first time that we have repetition we must get our original reduced form, thus we have formed a cycle. If there are reduced forms we haven't used yet then continue the process to form more cycles, otherwise we are done.
\end{proof}
\begin{corollary} \label{cor:nonprimcyc}
If $D=12p^2$ the two non-primitive reduced forms, $(p,-2p,-2p)$ and $(2p,-2p,-p)$, form their own cycles.
\end{corollary}
\begin{proof}
Consider $(p,-2p,-2p)$, this reduced form corresponds to
$$\frac{2p+\sqrt{12p^2}}{2p} = 1 + \sqrt{3}.$$
So its floor is 2. Under continued fraction action we get
$$\frac{1}{\frac{2p+\sqrt{12p^2}}{2p} - 2} = \frac{2p}{-2p+\sqrt{12p^2}} = \frac{2p + \sqrt{12p^2}}{4p}$$
which corresponds to $(2p,-2p,-p)$. Now
$$\frac{2p + \sqrt{12p^2}}{4p} = \frac{1 + \sqrt{3}}{2}$$
so its floor is 1. After another step we get
$$\frac{1}{\frac{2p+\sqrt{12p^2}}{4p} - 1} = \frac{4p}{-2p+\sqrt{12p^2}} = \frac{2p + \sqrt{12p^2}}{2p}$$
which corresponds to $(p,-2p,-2p)$ which is our original reduced form. So we have a 2-cycle which we write as $(p,-2p,-2p)\sim(2p,-2p,-p)\sim(p,-2p,-2p)$.
\end{proof}
\begin{theorem}
Two reduced forms are equivalent iff they are in the same cycle.
\end{theorem}
\begin{proof}
One direction is easy. Suppose we have two reduced forms in a cycle. Then we can use continued fraction action to go from one form to the other, thus the two reduced forms are equivalent.
The other direction is omitted. The reader is invited to read a full proof in \cite{Bu}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%FINISH PROOF%%%%%%
\end{proof}
A couple examples of the cycle structure will also be elucidating. First consider $D = 12$. We already found that there are only two reduced forms namely $(1,-2,-2)$ and $(2,-2,-1)$. $(1,-2,-2)$ corresponds to $\frac{2+\sqrt{12}}{2}$, subtracting by the floor and inverting yields $$\frac{1}{\frac{2+\sqrt{12}}{2}-2} = \frac{2}{-2+\sqrt{12}} = \frac{2+\sqrt{12}}{4}$$ which corresponds to $(2,-2,-1)$. Another step yields $$\frac{1}{\frac{2+\sqrt{12}}{4}-1} = \frac{4}{-2+\sqrt{12}} = \frac{2+\sqrt{12}}{2}$$ which corresponds to $(1,-2,2)$ thus showing there is only one cycle with discriminant 12 namely $(1,-2,-2)\sim(2,-2,-1)\sim(1,-2,-2)$. This would also follow directly from the previous corollary.
Notice that this can quickly become quite complicated and tedious, it would be nice if we could tell when two forms are adjacent without looking at the accompanying quadratic irrational.
\begin{theorem}
if $(a,b,c)\sim(a',b',c')$ then $b + b' \equiv 0 \pmod{2a}$ and $c' = -a$.
\end{theorem}
\begin{proof}
$(a,b,c)$ corresponds to $\frac{-b+\sqrt{D}}{2a}$. Let $x = \lfloor \frac{-b+\sqrt{D}}{2a} \rfloor$, then one step of the continued fraction algorithm yields$$\frac{1}{\frac{-b+\sqrt{D}}{2a} - x} = \frac{1}{\frac{-b+\sqrt{D}-2ax}{2a}} = \frac{2a}{-b-2ax+\sqrt{D}}.$$
Now after rationalizing the denominator
$$\frac{2a(-b-2ax-\sqrt{D})}{b^2+4abx+4a^2x^2-D} = \frac{2a(-b-2ax-\sqrt{D})}{b^2+4abx+4a^2x^2-b^2+4ac} = \frac{-b-2ax-\sqrt{D}}{2bx+2ax^2+2c},$$
but this is just $$\frac{b+2ax+\sqrt{D}}{2(-bx-ax^2-c)}.$$
Thus $-b' = b +2ax$ and $a' = -bx-ax^2-c$.
Clearly $b + b' \equiv 0 \pmod{2a}$ since $b+b'+2ax=0$. Now consider $$c'=\frac{D-(b')^2}{-4a'} = \frac{b^2-4ac-(b +2ax)^2}{-4(-bx-ax^2-c)} = \frac{b^2-4ac-b^2 -4a^2x^2 - 4bax}{4bx+4ax^2+4c} $$
$$= -a\frac{4c+4ax^2+4bx}{4bx+4ax^2+4c} = -a,$$
So $c' = -a$.
\end{proof}
Now for a more complicated case, consider $D = 300 = 12(5)^2$ Using an implementation of Algorithm \ref{algor:redform} (see Section \ref{subsec:redformalg}) we find there are 10 reduced forms: $(6,-6,-11)$, $(11,-6,-6)$, $(5,-10,-10)$, $(10,-10,-5)$, $(3,-12,-13)$, $(13,-12,-3)$, $(2,-14,-13)$, $(13,-14,-2)$, $(1,-16,-11)$ and $(11,-16,-1)$. Firstly we can take out the non-primitive reduced forms which form their own 2-cycle as in Corollary \ref{cor:nonprimcyc}.
Now lets pick an element, for example $(6,-6,-11)$. The next reduced form in the cycle must end with an $-6$ so we have $(11,-6,-6)$, followed by a form which ends in $-11$. Here we have two choices, however we also know $-6+b'\equiv 0 \pmod{22}$ so our only choice is $(1,-16,-11)$ followed by $(11,-16,-1)$. Now again we want a form which ends with $-11$, but since we can't choose $(1,-16,-11)$, we already know what unique elements lie on either side, so we must have $(6,-6,-11)$ completing our cycle.
We still have four reduced forms left, it is left to the reader show these forms create another 4-cycle.
So we have 3 cycles, a non-primitive 2-cycle
$(5,-10,-10)\sim(10,-10,-5)\sim(5,-10,-10)$ and two 4-cycles,
$(6,-6,-11)\sim(11,-6,-6)\sim(1,-16,-11)\sim(11,-16,-1)\sim(6,-6,-11)$ and
$(13,-12,-3)\sim(2,-14,-13)\sim(13,-14,-2)\sim(3,-12,-13)\sim(13,-12,-3)$.
\section{Calculating the Class Number} \label{subsec:calccn}
The following formula is from \cite{BS}. Let $R = \mathbb{Z} + \mathbb{Z}\sqrt{3}$ and let $\eta = 2 + \sqrt{3}$ which is the fundamental unit in this ring. Assume $p>3$ then
$$h(12p^2) = h(12)\frac{\Phi_R (p)}{o(p)\Phi_\mathbb{Z}(p)}$$
where $\Phi$ is the Euler function over a specific ring $R$ defined by $\Phi_R(p) = |(R / pR)^\times |$ and $o(p)$ is the smallest integer such that $\eta^{o(p)} \in \mathbb{Z} + p\mathbb{Z}\sqrt{3}$.
Since $p$ is prime in $\mathbb{Z}$ we know that $\Phi_\mathbb{Z}(p) = p - 1$, in order to calculate $\Phi_R (p)$ we need to investigate if 3 splits over $\mathbb{Z}\sqrt{3}$. If $p$ does not split then $\Phi_R (p) = p^2 - 1$, if p does split then $p =\pi \overline{\pi}$ where $\pi$ and $\overline{\pi}$ are primes and $$\Phi_R (p) = \Phi_R(\pi)\Phi_R(\overline{\pi}) = (p-1)(p-1) = (p-1)^2.$$ It is fairly easy to calculate the $h(12)$ and how $p$ splits over $\mathbb{Z}\sqrt{3}$. Calculating $o(p)$ is considerably more difficult, but an effective algorithm exists for calculating it.
%Borevich shaferich %%%%%%%%%%%%%%%% NEED to show these two methods are equivalent
\subsection{What is $h(12)$?} \label{subsubsec:h12}
This question is most easily answered using reduced quadratic forms. As an example in Subsection \ref{subsec:structure} we found out that the reduced forms of discriminant 12 form a single cycle $(1,-2,-2)\sim(2,-2,-1)\sim(1,-2,-2)$. Thus by definition of the class number $h(12) = 1$.
\subsection{How does $\sqrt{3}$ split over different fields?}
\label{subsec:splits}
In order to determine the class number we need to determine over which finite fields $\mathbb{F}_p$ the $\sqrt{3}$ exists. This is equivalent to asking if 3 is a square over these fields. We can calculate this using quadratic reciprocity:
$$\biggl(\frac{3}{p} \biggr) = \biggl(\frac{p}{3}\biggr)(-1)^{{\frac{p-1}{2}}*{\frac{2}{2}}} = \biggl(\frac{p}{3}\biggr)(-1)^{\frac{p-1}{2}}.$$
Now we have a couple of possibilities. Since p is prime, $p\equiv 1,5,7 \hbox{ or } 11\pmod{12}$
If $p\equiv 1\pmod{12}$
$$ \biggl(\frac{p}{3}\biggr)(-1)^{\frac{p-1}{2}} = \biggl(\frac{1}{3}\biggr) = 1,$$
$$ \hbox{ so 3 is a square.} $$
If $p\equiv 5\pmod{12}$
$$ \biggl(\frac{p}{3}\biggr)(-1)^{\frac{p-1}{2}} = \biggl(\frac{2}{3}\biggr) = -1, $$
$$ \hbox{ so 3 is not a square. } $$
If $p\equiv 7 \pmod{12}$
$$ \biggl(\frac{p}{3}\biggr)(-1)^{ \frac{p-1}{2}} = -\biggl(\frac{1}{3}\biggr) = -1, $$
$$ \hbox{ so 3 is not a square. } $$
If $p\equiv 11 \pmod{12}$
$$ \biggl(\frac{p}{3}\biggr)(-1)^{\frac{p-1}{2}} = -\biggl(\frac{2}{3}\biggr) = 1, $$
$$ \hbox{ so 3 is a square. } $$
This calculation show that 3 splits in the field $\mathbb{F}_p$ iff
$p \equiv 1 \hbox{ or } 11 \pmod {12}$.
Now we can state the class number formula in its full simplicity $$h(12p^2) = h(12)\frac{\Phi_R (p)}{o(p)\Phi_\mathbb{Z}(p)}$$
$$ = \frac{p-1}{o(p)} \hbox{ if } p \equiv 1 \hbox{ or } 11 \pmod {12}$$
$$ = \frac{p+1}{o(p)} \hbox{ if } p \equiv 5 \hbox{ or } 7 \pmod {12}.$$
Since h(d) is always a positive integer this leads to the following corollary:
\begin{corollary} \label{cor:idivides}
$o(p)$ divides $p-1$ if $p \equiv 1 \hbox{ or } 11 \pmod {12}$ and $o(p)$ divides $p+1$ if $p \equiv 5 \hbox{ or } 7 \pmod {12}$.
\end{corollary}
Now that we understand how to calculate the class number using this method, lets do a quick example. In Subsection \ref{subsec:structure} we found that for $D=300=12(5)^2$ there are two non-primitive cycles, so the class number $h(300)=2$. Now lets try our new method.
$$h(12p^2)=\frac{h(12)(p\pm1)}{o(p)}$$
Now $p=5$, $h(12)=1$ and $p \equiv 5 \pmod{12}$ so we have
$$h(12p^2)=\frac{p+1}{o(p)}=\frac{6}{o(p)}.$$
Now we need to calculate $o(p)$. Recall $o(p)$ is the smallest integer such that $$(2+\sqrt{3})^{o(p)} \in \mathbb{Z} + p\sqrt{3}\mathbb{Z} = \mathbb{Z} + 5\sqrt{3}\mathbb{Z}.$$
Clearly $o(p) \neq 1$ so by Corollary \ref{cor:idivides} $o(p)$ could be 2, 3 or 6.
$$(2+\sqrt{3})^2 = 7 + 4\sqrt{3} \notin \mathbb{Z} + 5\sqrt{3}\mathbb{Z}$$
$$(2+\sqrt{3})^3 = 26 + 15\sqrt{3} \in \mathbb{Z} + 5\sqrt{3}\mathbb{Z}$$ so $o(p)$ = 3, thus $h(300) = 2$.
There are a number of good sources for quadratic forms and the class number. \cite{Dav} gives an elementary introduction to quadratic forms, \cite{Bu} contains a very in-depth study of quadratic forms and explains more of the relationship to the class number. \cite{BS} also discusses quadratic forms and class number.
\chapter{Bounds on the Length of Continued Fractions} \thispagestyle{empty}
Now we have developed enough machinery to accomplish our goal, to place bounds on the length of the period of a periodic continued fraction. In \cite{SSW} it is shown that
$$\ell(\sqrt{D})<\frac{\mu log \eta}{log \alpha}$$
for $D$ square-free, where $\eta = \frac{u_0 +v_0\sqrt{D}}{2}$ is the fundamental unit in $\mathbb{Z}\sqrt{D}$, $\alpha = \frac{1+\sqrt{5}}{2}$, and $\mu = 3 \hbox{ if } 2 \nmid u_0 \hbox{ or }\mu = 1 \hbox{ if } 2 \mid u_0$. We want to apply this to the case $D$ not square-free as well as give a lower bound on the length.
Let $p$ be a prime greater then $3$.
Let $[ a_0=[p \sqrt{3}], a_1, a_2, \ldots ] $ be the elements of
the continued fraction of $p \sqrt{3}$ as in Definition \ref{def:contfrac}, and define
$$
\left\{
\begin{array}{ll} A_{k} = a_k A_{k-1} + A_{k-2} \\
B_{k} = a_k B_{k-1} + B_{k-2}.
\end{array}
\right.
$$
In particular, if $\ell(p\sqrt{3})$ is the period of the said continued fraction, then
$$
\eta_{p} = A_{p-1} + p\sqrt{3} B_{p-1}
$$
is the fundamental unit in the order of discriminant $12p^2$.
Recall that the class number of that order is given by
$$
h(p)= (p \pm 1)/ o(p),
$$
where $o(p)$ is the integer such that $\eta_{p}=
\eta^{o(p)}$.
We shall now relate the period $\ell(p\sqrt{3})$ with the class number.
We need the following theorem due to Liouville:
\begin{theorem}
There exists a positive real number $c$ such that for every pair
of integers $p$ and $q>0$,
$$
|\sqrt{3} - \frac{p}{q} | \geq \frac{c}{q^2}.
$$
\end{theorem}
Now let $a_0=\lfloor p \sqrt{3}\rfloor, a_1, a_2, \ldots$ be the elements of
the continued fraction of $p \sqrt{3}$. Let $A_k/B_k$ be
the corresponding convergents, defined above.
Then it is well known \cite{Kh} that
$$
|p \sqrt{3} - \frac{A_k}{B_k}| \leq \frac{1}{a_{k+1} B_k^2}.
$$
After dividing both sides by $p$ we arrive to
$$
|\sqrt{3} - \frac{A_k}{p B_k}| \leq \frac{p}{a_{k+1} (pB_{k})^2}.
$$
It follows that ${ p / {a_{k}}}$ must be bigger then the constant
$c$ in the theorem. In fact this can be made explicit, and it follows that
$a_{k} \leq 4p$. By replacing $a_{k}$ by $1$ and $4p$, in the
defining equations for $A_k$ and $B_k$, we can
obtain a lower and upper bound on $\eta_{p}$, respectively:
$$
\alpha^{\ell(p\sqrt{3})} \leq \eta_{p} \leq (4p)^{\ell(p\sqrt{3})}.
$$
Taking $\log$ of all three terms, and dividing by $\log(\eta)$
it follows that
$$
\ell(p\sqrt{3}) \frac{\log(\alpha)}{\log(\eta)} \leq o(p)
\leq \ell(p\sqrt{3}) \frac{\log(4p)}{\log(\eta)}
$$
and
$$
\frac{(p \pm 1)\log(\eta)}{h(12p^2) \log(4p)} \leq \ell(p\sqrt{3})
\leq \frac{(p \pm 1)\log(\eta)}{h(12p^2) \log(\alpha)}.
$$
Note $\ell(p\sqrt{3})$ is approximately $p/h$.
\chapter{Algorithms and Experimental Results} \thispagestyle{empty}
This section explains the algorithms I used to calculate different results like the continued fraction of $p\sqrt{3}$, the class number, or the number of reduced forms of a given discriminant. These results, especially those for continued fraction helped me to see interesting patterns that led me to study this topic more in-depth.
\section{Length of Continued Fraction Period}
As referenced in the introduction, I began looking into this topic after a reading a paper by Benedict H. Gross concerning the relative length of a continued fraction of the type $p\sqrt{3}$ where $p$ is a Mersenne prime. In order to be able to quantify and understand what this really means it was necessary to understand the length of continued fractions for other values of $p$. Since I have already explained the method for finding the continued fraction of a given number in Algorithm \ref{algor:contfracalg}, I will go straight to the results.
\newpage
\begin{figure}[ht!]
\begin{center}
\includegraphics[width=5.5in]{allnumbers.eps}
\end{center}
\caption{A dataplot of the period of continued fractions of $n\sqrt{3}$ for numbers $n$}
\label{myfig}
\end{figure}
The first thing I tried was to look a the period of $n\sqrt{3}$ where $n$ was simply any number. I wrote some code in Matlab that could find the period of any given quadratic irrational and Figure \ref{myfig} was the result.
Notice that there is definitely some structure in this figure, for instance all the isolated points appeared to be some prime times a power of three and there are these interesting ``wedges'' of numbers. In order to try understand what was happening better we tried just looking at primes. This result is Figure \ref{myfig1}.
\begin{figure}[ht!]
\begin{center}
\includegraphics[width=5.5in]{allprimes.eps}
\end{center}
\caption{A dataplot of the period of continued fractions of $p\sqrt{3}$ for prime $p$}
\label{myfig1}
\end{figure}
Notice that the structure here is much more well defined. All the points in the upper portion of the graph seem to lie in these rays emanating from the origin, even the points near the bottom of the graph will end up in a ray if one continues the graph for larger and larger primes.
Trying to find a connection in the points was difficult at first, but we discovered (empirically) that all the points in the top ray have class number 2, all the points in the second ray have class number 4, all the points in the third ray have class number 6 etc... Also notice that the slope of a line fitted to each row will have approximate slope $1/{}h$ where $h$ is the class number.
Also notice that for $p\sqrt{3}$ where $p$ is a Mersenne prime the class number is always two \cite{Gr}, which justifies the statement by Gross that $p\sqrt{3}$ for Mersenne primes have unusually large continued fraction periods.
There are still a number of things I don't understand, for instance the numerical data suggests that we should be able to get much tighter bounds on the period of continued fractions, also it wasn't shown that all the elements with class number 2 live in the first ray etc...
One more thing that I found very interesting was look at only primes in certain congruence classes modulo 24. Notice in Figures \ref{myfig2} and \ref{myfig3} that only certain rays appear in each congruence class. For example when $p \equiv 7 \pmod{24}$ then the rays corresponding to class number 2, 10 and 14 appear prominently while those corresponding to 4, 6, 8 and 12 are no longer present. Currently I have no explanation for this phenomena.
%\newpage
\vfill
\begin{figure}[hb!]
\begin{center}
\includegraphics[height=2.25in]{one.eps} \hskip 8pt
\includegraphics[height=2.25in]{five.eps}
\\ \vskip 8pt
\includegraphics[height=2.25in]{seven.eps} \hskip 8pt
\includegraphics[height=2.25in]{eleven.eps}
\caption{Dataplots of continued fraction of $p\sqrt{3}$ for primes $p$ modulo 24}\label{myfig2}
\end{center} \end{figure} \vfill
\begin{figure}[ht!] \begin{center}
%\\
\includegraphics[height=2.25in]{thirteen.eps} \hskip 8pt
\includegraphics[height=2.25in]{seventeen.eps}
\\ \vskip 8pt
\includegraphics[height=2.25in]{nineteen.eps} \hskip 8pt
\includegraphics[height=2.25in]{twentythree.eps}
\end{center}
\caption{Continuation of Figure \ref{myfig2}}
\label{myfig3}
\end{figure}
\section{The Class Number}
\begin{algorithm}
\label{algor:classnum}
Recall the method from Subsection \ref{subsec:calccn}:
$$h(12p^2)=\frac{h(12)(p \pm 1)}{o(p)}.$$
In Subsection \ref{subsubsec:h12} we found that h(12) = 1 and to determine the sign we need to know if 3 splits in $\mathbb{F}_p$. It was shown in Subsection \ref{subsec:splits} that if $p \equiv 1 \hbox{ or } 11 \pmod{12}$ then 3 splits, otherwise it doesn't.
let q=p-1 if $p \equiv 1 \hbox{ or } 11 \pmod{12}$
otherwise let q=p+1.
%%%%%%%%%%%%% enumerate%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
Now we need to calculate $o(p)$ which is defined to be the smallest integer such that $(2+\sqrt{3})^{o(p)} \in \mathbb{Z} + p\mathbb{Z}\sqrt{3}$. In Corollary \ref{cor:idivides} we saw that $o(p) \mid q$. In order to calculate $o(p)$ we need to find the positive divisors of q and test each, starting with the smallest factor bigger than 1 to see if the factor satisfies the property required for $o(p)$. This number can get very large very quickly requiring very large precision. It is often effective to perform the required operations modulo $q$ and check that the solution is 0.
Once $o(p)$ is found then $h(p) = q$/$o(p)$.
\end{algorithm}
\section{Calculating the Number of Reduced Forms} \label{subsec:redformalg}
\begin{algorithm}
\label{algor:redform}
We have already given a way to find a reduced form of any given binary quadratic form (Algorithm \ref{algor:reduceit}). This algorithm computes the number of reduced forms of a given discriminant. It is specifically for $D = 12p^2$, but can easily be adjusted.
\begin{enumerate}
\item{Fix the discriminant $D$.}
\item{Let $r = 0$.}
\item{Let $b = 0$. (since $12p^2 = D \equiv 0 \pmod{4}$.)}
\item{Let $s = (D - b^2)/4$. (This is always a positive integer.)}
\item{Consider all the factors of s. Let $r_b$ be the number of positive factors a such that $b + \sqrt{D} < 2a < -b + \sqrt{D}$. Because of Theorem \ref{thm:times2}, we can actually just consider the number of positive factors less than $\sqrt{D}$ and them multiply this number by two. }
\item{Let $r = r + r_b$.}
\item{Let $b = b - 2$. (Recall from Corollary \ref{cor:Dis0or1} that $D \equiv b^2 \pmod{4}$.)}
\item{If $b< \sqrt{D}$ repeat the process. }
\end{enumerate}
Now $r$ is the total number of reduced forms of a given discriminant $D = 12p^2$. In order to get the number of primitive reduced forms we need to subtract by two because of Theorem \ref{thm:allbut2}.
It also was shown in Theorem \ref{thm:finiterf} that this number is always finite, the fact that this is a finite algorithm is basically the reason this quantity is finite.
Note we could also now use this algorithm to compute the class number by computing the number of primitive cycles.
\end{algorithm}
%\newpage
\begin{thebibliography}{99}
\thispagestyle{empty}
\addcontentsline{toc}{chapter}{\protect\numberline{}Bibliography}
%\addcontentsline{toc}{section}{References}
\bibitem{BS} Z.~I.~Borevich, I.~R.~Shafarevich. Number Theory. Transl. by N. Greenleaf. New York: Academic Press, 1966.
\bibitem{Bu} D.~A.~Buell. Binary Quadratic Forms: Classical Theory and Modern computations. New York: Springer-Verlag, 1989.
\bibitem{Dav} H.~Davenport. The Higher Arithmetic: an Introduction to the Theory of Number. New York: Cambridge University Press, 1999.
\bibitem{Gr} B.~H.~Gross. An elliptic curve test for Mersenne primes, Preprint.
\bibitem{Kh} A.~I.~Khinchin. Continued Fractions. Transl. by Scripta Technica, inc. Edited by H. Eagle. Chicago: University of Chicago Press, 1964.
\bibitem{Zag} D.~B.~Zagier. Zetafunktionen und quadratische K\"orper. Eine Einf\"uhrung in die h\"ohere Zahlentheorie. Springer-Verlag, 1981.
\bibitem{SSW} R.~G.~Stanton, C.~Sudler~Jr., H.~C.~Williams. An upper bound for the period of the simple continued fraction for $\sqrt{D}$. \textit{ Pacific J. of Math.} \textbf{67} (1976), 525-536.
%%\bibitem{MW} Mathworld
\end{thebibliography}
%%%%%%%%%%%%%%%% - to $-$
% mathworld
% gross
% savin
%\newpage
\finalpage{February 26, 1981}{Salt Lake City, Utah}{2675 South 1800 East Salt Lake City, Utah 84106}
\end{document}