\documentclass[%
version=last,%
a5paper,
12pt,%
headings=small,%
%titlepage=no,%
toc=graduated,% default
listof=leveldown,%
listof=nochaptergap,%
bibliography=totoc,%
index=totoc,%
twoside,%
reqno,%
cleardoublepage=empty,%
open=any,%
draft=true,%
DIV=12,%
headinclude=false,%
pagesize]%
{scrbook}

%\usepackage[notcite,notref]{showkeys}

\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ofoot{\pagemark}
\ifoot{\headmark}

\usepackage[OT2,T1]{fontenc}
\usepackage{gfsporson}
\usepackage[russian,polutonikogreek,english]{babel}
\newcommand{\ru}[1]{\foreignlanguage{russian}{#1}}
\newcommand{\gk}[1]{\foreignlanguage{polutonikogreek}{\textporson{#1}}}

\usepackage{multicol}
\usepackage{moredefs,lips}

\usepackage{amsmath,amssymb,amsthm}
%\allowdisplaybreaks
\usepackage{verbatim}  % allows a comment environment:
\newcommand{\abs}[1]{\left|#1\right|}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\setminus}{\smallsetminus}
%\renewcommand{\phi}{\varphi}

\renewcommand{\emptyset}{\varnothing}
\renewcommand{\epsilon}{\varepsilon}


\usepackage{relsize}
\usepackage{rotating}
\usepackage{url}
\usepackage[all]{xy}
\usepackage{pstricks,pst-node,pst-eucl}
\usepackage{pst-plot}
\usepackage{textcomp}  % supposedly useful with \oldstylenums
\usepackage{upgreek}

\usepackage{layout}
\usepackage{hfoldsty} % this didn't work until I added missing
		      % brackets to some of the files.

%\newcommand{\mypreface}{\addchap*{Preface}}
\newcommand{\conventions}{\addchap{Conventions}}
%\newcommand{\myweek}{\part{Week}}
\newcommand{\myweek}{}
\newcommand{\myday}[1]{\chapter{#1}}

%\makeglossary  % should be turned off to make the glossary appear
%\newcommand{\topic}[1]{\addsec{#1}\glossary{#1}}
\newcommand{\topic}[1]{\addsec{#1}}

%\newcommand{\glossaryentry}[2]{#1\dotfill#2\\}
%\newcommand{\tableoftopics}{%
%%\begin{center}\textsc{List of Topics}\end{center}
%%\addcontentsline{toc}{section}{List of Topics}
%\section*{List of Topics}
%\input{number-theory-ii-metu.glo}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\lor}{\mathrel{\mathrm{or}}}
\newcommand{\xsize}[1]{\Bigl|#1\Bigr|}
\newcommand{\size}[1]{\lvert#1\rvert}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{makeidx}
\makeindex

\newcommand{\defn}[2]{\textbf{#1#2}\index{#1}}
\newcommand{\defnplain}[2]{\textbf{#1#2}}
\newcommand{\tech}[2]{\textsl{#1#2}\index{#1}}
%\newcommand{\conv}[1]{\begin{center}\fbox{#1}\end{center}}

\usepackage[neverdecrease]{paralist}
%\renewcommand{\theenumi}{\alph{enumi}}
%\renewcommand{\labelenumi}{\textnormal{(\theenumi)}}
\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{\textnormal{(\theenumi)}}

%\renewcommand{\theenumii}{\roman{enumii}}
%\renewcommand{\labelenumii}{\textnormal{(\theenumii)}}

%%%%%%%%%%%%%%%

\newcommand{\divides}{\mathrel{|}}
\newcommand{\ndivides}{\mathrel{\nmid}}

\newcommand{\ls}[2]{\Bigl(\displaystyle\frac{#1}{#2}\Bigr)}

% set-theoretic relations:

\newcommand{\included}{\subseteq}      % [the name suggests the meaning here]
\newcommand{\nincluded}{\not\subseteq} % not included
\newcommand{\pincluded}{\subset}       % proper inclusion    
\newcommand{\includes}{\supseteq}

\newcommand{\stnd}[1]{\mathbb{#1}}
\newcommand{\N}{\stnd{N}}         % counting numbers
\newcommand{\Z}{\stnd{Z}}         % integers
\newcommand{\Q}{\stnd{Q}}         % rationals
\newcommand{\R}{\stnd{R}}         % reals
\newcommand{\C}{\stnd{C}}         % complex numbers

\DeclareMathOperator{\dee}{d}      % 

\newcommand{\mi}{\,\mathrm i\,}
\newcommand{\mpi}{\uppi}
\newcommand{\gr}{\upphi}  % golden ratio

\newcommand{\cc}[1]{\overline{#1}}  % complex conjugate
\newcommand{\norm}[1]{\operatorname{N}\left(#1\right)}
\newcommand{\tr}[1]{\operatorname{Tr}(#1)}
\newcommand{\inv}[1][]{#1^{-1}}
\newcommand{\edeg}[1]{\operatorname d(#1)}  % degree for Euclidean domain
\newcommand{\gi}{\Z[\mi]}
\newcommand{\roi}[1][K]{\mathfrak O_{#1}}  % ring of integers
\newcommand{\latt}[1][\alpha,\beta]{\left\langle#1\right\rangle} % lattice
%\newcommand{\xlat}[1][\alpha,\beta]{\Bigl\langle#1\Bigr\rangle} % lattice
\newcommand{\Disc}{D} % discriminant
\newcommand{\disc}[1]{\Delta(#1)}      % discriminant
\newcommand{\mLambda}{\mathit{\Lambda}}
\newcommand{\mPi}{\mathit{\Pi}}
\newcommand{\mSigma}{\mathit{\Sigma}}
\newcommand{\mMu}{M}
\newcommand{\mDelta}{\mathit{\Delta}}
%\newcommand{\End}[1][\mLambda]{\operatorname{End}(#1)}  % Endomorphism-ring
\newcommand{\ord}[1][\mLambda]{\mathfrak O_{#1}}
\newcommand{\funit}[1][\mLambda]{\epsilon_{#1}}

\let\oldsqrt\sqrt
%\renewcommand{\sqrt}[2][1]{\oldsqrt{\vphantom{#1}}#2}

\newcommand{\sqf}{square-free}

\newcommand{\Fib}[1]{\mathrm{F}_{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Theorem-like environments  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newtheorem*{corollary}{Corollary}
\newtheorem*{porism}{Porism}
\newtheorem{lemma}{Lemma}
\newtheorem{problem}{Problem}
%\newtheorem*{fact}{Fact}
%\newtheorem*{exercise}{Exercise}
%\newtheorem*{remark}{Remark}

\theoremstyle{definition}
\newtheorem{example}{Example}
\newtheorem{xca}{Exercise}
\newtheorem{prob}{Problem}

\newenvironment{solution}%
{\begin{proof}[Solution.]}%
{\end{proof}}


\theoremstyle{remark}


\newtheorem*{sol}{Solution}

\newtheorem*{instructions}{Instructions}
\newtheorem*{remark}{Remark}

%\numberwithin{equation}{section}
%\renewcommand{\theequation}{\fnsymbol{equation}}


\begin{document}
\title{Continued Fractions}
\subtitle{A course at the Nesin Mathematics Village}
\author{David Pierce}
\date{August 13--19, 2018\\
Last edited August 22, 2018}
\publishers{Matematik B\"ol\"um\"u\\
  Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
  \url{dpierce@msgsu.edu.tr}\\
  \url{http://mat.msgsu.edu.tr/~dpierce/}\\
\url{polytropy.com}}
  \maketitle
  \thispagestyle{empty}
  
  \addchap*{Preface}
  
  Much of the present document is cannibalized
  from the notes I kept while teaching Elementary Number Theory II
  at \textsc{metu} in Ankara, Spring 2008.
  I edited those notes in the winter of this year.
  There were 33 hours of lectures for that course.
  
  The present document reflects the content of the twelve hours of lectures
  constituting Continued Fractions,
  given at the Math Village,
  8--10 \textsc{a.m.},
  Monday to Sunday (except Thursday),
  August 13--19, 2018.
  The order of presentation in class was often different,
  and I did not give all of the proofs.

  I focussed on the practical problem
  of finding integer points of conic sections, especially hyperbolas,
  using continued fractions.
  I presented a complete method;
  in this sense, the course constituted a whole.
  I showed how to find \emph{all} integer points
  from \emph{one} nontrivial point.
  I did not prove that the point had to exist
  (though the proof is here);
  nor did I prove that such a point could be obtained
  from a convergent of a square root
  (though the proof is in the notes from ten years ago).

  I had expected to work through the proof that,
  for nonsquare positive $d$,
    \begin{equation*}
    \surd d=[a_0;\overline{a_1,\dots,a_{n-1},2a_0}],
  \end{equation*}
where $a_k=a_{n-k}$ when $0<k<n$.
In the event,
there was no time for the proof, and I doubted whether there was interest.

  Since some students had little university experience,
  I ended up discussing the Euclidean Algorithm
  and its usual number-theoretic consequences, as in Chapter \ref{ch:Euclid}.
  For fun, I found the Pythagorean triples, as in Chapter \ref{ch:circle}.

  The lectures actually started
  with the question of the meaning of $\surd2$
  at the head of Chapter \ref{ch:root-2}.
  One student described it as a supremum.
  He also had Euclid from the library,
  and this is a reason why I felt free to talk about
  Euclid's theories of proportion, as in Chapter \ref{ch:Euclid};
  other students became curious here, though perplexed.

  On Tuesday I had 16 students:
 % \begin{inparaenum}[(i)]
 % \item
    five from Bo\u gazi\c ci,
  %\item
    four from \textsc{odt\"u},
  %\item
    two from Bilkent,
    and one each from
  %\item
    DP\"U (Dumlup\i nar?),
  %\item
    CB\"U (Celal Bayar?),
  %\item
    Galatasaray, and
  %\item
    \.IT\"U, and
  %\item
    one not yet at university.
 % \end{inparaenum}
  I know this because I had them write down the information;
  I then assigned each student a different number $d$
  for which to find the continued fraction expansion of $\surd d$.
  Most of them brought the correct solutions the next day.
  One of them had checked his work with me, the previous evening.
  
  Most students were from English-language universities;
  but I spoke mainly in Turkish, while writing in English.
  Students asked questions in both languages.
  
  On the last day, five students attended.
  Later in the day, I saw two who had not attended.
  One said that, even had he arisen in time for class,
  fields and lattices were alien to him;
  the other had been seeing off friends,
  though he was staying longer,
  and did I suggest he take my course of the next week
  (The Prime Number Theorem)?

The course might be called an introduction to quadratic fields.
I avoided most suggestions of where further generalization might lead.
I did point out we were finding integer points of curves of genus zero;
the problem of genus one---elliptic curves---was harder.


  \tableofcontents
%\addchap*{Figures and the Table} 
\listoffigures
\listoftables

\chapter{The Euclidean Algorithm}\label{ch:Euclid}

For notation, we shall use
\begin{compactitem}
\item
  $\N$ for the set $\{1,2,3,\dots\}$ of \textbf{counting numbers,}
  \item
  $\upomega$ (``omega'') for
  the set $\{0,1,2,\dots\}$ of \textbf{natural numbers,}
  and
\item
  $\Z$ for the set
    $\{\dots,-2,-1,0,1,2,\dots\}$
  of \textbf{integers.}
\end{compactitem}
Given two counting numbers $a_0$ and $a_1$,
where $a_0>a_1$,
we define natural numbers $a_{n+2}$ and $x_n$ recursively by the rule
\begin{equation*}
  a_n=a_{n+1}x_n+a_{n+2}\And a_{n+2}<a_{n+1}.
\end{equation*}
This is the \textbf{Euclidean Algorithm.}
Here $ax$ means $a$, $x$ times,
so that $x$ is the \textbf{multiplier,}
and $a$ the \textbf{multiplicand;}
symbolically,
\begin{equation*}
  ax=\underbrace{a+\dots+a}_x.
\end{equation*}
If $ax=b$,
two conclusions are that $a$ \textbf{measures} $b$,
and $x$ \textbf{divides} $b$.
These are equivalent notions, since $ax=xa$.
However, we are going to prove this, as Euclid does in the \emph{Elements.}

Meanwhile, since the sequence of natural numbers $a_n$ is decreasing,
it must eventually stop.
It stops when it reaches zero.
If $a_{n+2}=0$, then $x_{n+1}$ cannot be defined.
Thus we have
\begin{gather*}
  a_0=a_1x_0+a_2,\\
  a_1=a_2x_1+a_3,\\
  \makebox[3cm]{\dotfill}\\
  a_{n-1}=a_nx_{n-1}+a_{n+1},\\
  a_n=a_{n+1}x_n.
\end{gather*}
Here
$a_{n+1}$ is the \textbf{greatest common measure} of $a_0$ and $a_1$,
since
\begin{compactitem}
  \item
  $a_{n+1}$ measures itself, and $a_n$, and then $a_{n-1}$,
    and so on to $a_1$ and $a_0$, and moreover
  \item
    any common measure of $a_0$ and $a_1$
  measures also $a_2$, then $a_3$, and so on to $a_{n+1}$.
\end{compactitem}
For example,
\begin{gather*}
  151=71\cdot2+9,\\
  71=9\cdot7+8,\\
  9=8\cdot1+1,\\
  8=1\cdot8,
\end{gather*}
and so the greatest common measure of $151$ and $71$ is $1$,
or in other words $151$ and $71$ are \textbf{prime to one another.}
Moreover, working backwards through the computations, we have
\begin{gather*}
  1=9-8\cdot1=9-(71-9\cdot7)\cdot1\\
  =9\cdot8-71\cdot1=(151-71\cdot2)\cdot8-71\cdot1\\
  =151\cdot8-71\cdot17.
\end{gather*}
In this way, we obtain:

\begin{theorem}[B\'ezout]\label{thm:Bezout}
  Counting numbers $a$ and $b$ are prime to one another
  if and only if the equation
  \begin{equation*}
    ax+by=1
  \end{equation*}
  is soluble in $\Z$.
\end{theorem}

The Euclidean Algorithm is an application of what Euclid calls
\textbf{anthyphaeresis} (\gk{>anjufa'iresis}) or alternating subtraction.
The Greek word comes from \emph{anti + hypo + haire-}
(\gk{>ant'i} + \gk{<up'o} + \gk{a<ir'e-});
the last two parts in Latin are \emph{sub + tract.}
Let the sequence of numbers $x_n$ obtained above
be called the \textbf{anthyphaeretic sequence}
of the ordered pair $(a_0,a_1)$.

For Euclid, a number is a ``multitude of units,''
and units are implicitly magnitudes, all of the same size.
There are several ways to express the same possible relation among
four magnitudes $a$, $b$, $c$, and $d$:
\begin{compactitem}
\item 
  $a$, $b$, $c$, and $d$ are \textbf{proportional,}
  \item
the \textbf{ratio} of $a$ to $b$ is the same as that of $c$ to $d$, or
\item
$a$ is to $b$ as $c$ is to $d$.
\end{compactitem}
For these, in modern symbolism we write
\begin{equation}\label{eqn:abcd}
  a:b::c:d.
\end{equation}
There is good evidence that, by the original definition,
this means $(a,b)$ and $(c,d)$ have the same anthyphaeretic sequence.
However,
there are other possible definitions,
and Euclid gives two of them:
one for arbitrary magnitudes, and one for numbers alone.

Euclid's definition of proportion of arbitrary magnitudes
is attributed to Eudoxus of Cnidus
by a scholium in a manuscript of Euclid's text.
By this definition,
a ratio is what we now understand to be a \emph{Dedekind cut,}
because we know the ratio of $A$ to $B$,
once we know, for each pair $(k,\ell)$ of counting numbers,
whether $Ak>B\ell$, or $Ak=B\ell$, or $Ak<B\ell$.
(See page \pageref{sect:cuts} for more on Dedekind cuts.)

Euclid defines four \emph{numbers} to be in proportion
if the first number is the same \emph{multiple,}
or \emph{part,} or \emph{parts,}
of the second
that the third is of the fourth.
The words may seem ambiguous to us today,
but I think the meaning can only be as follows.

Given the numbers $a$ and $b$,
we can find their greatest common measure, $e$,
using the Euclidean algorithm.
There are then multipliers $x$ and $y$ such that
\begin{align*}
  a&=ex,&b&=ey.
\end{align*}
\begin{compactitem}
\item
  If $y=1$, then $a$ is a \textbf{multiple} of $b$;
  \item
    if $x=1$, then $a$ is a \textbf{part} of $b$;
    \item
  otherwise, $a$ is \textbf{parts} of $b$.
\end{compactitem}
In any case, $x$ and $y$ are prime to one another;
otherwise, $e$ would not be the greatest of their common measures.
Thus the meaning of \eqref{eqn:abcd} for numbers is that,
for some multipliers $x$ and $y$,
\begin{align*}
  a&=ex,&b&=ey,&c&=fx,&d&=fy,
\end{align*}
where 
\begin{compactitem}
  \item
    $e$ is the greatest common measure of $a$ and $b$, and
    \item
  and $f$ is the greatest common measure of $c$ and $d$,
\end{compactitem}
or equivalently
\begin{compactitem}
\item
  $x$ and $y$ are prime to one another.
\end{compactitem}
Thus every proportion of numbers can be written in the form
\begin{equation}\label{eqn:prop-gen}
  ex:ey::fx:fy,
\end{equation}
where again $x$ and $y$ are prime to one another.

Some modern mathematicians
do not seem to think the condition on $e$ and $f$
(or on $x$ and $y$) is implied by Euclid's words
\cite{MR2204484,Mazur-Th-pub}.
One reason to think that it \emph{is} implied is that,
with the definition as I have stated it,
we have immediately
\begin{equation*}
  a:b::c:d\And c:d::g:h\implies a:b::g:h.
\end{equation*}
This is transitivity of sameness of ratio;
and Euclid would not define any relation as a \emph{sameness} of something,
unless the relation were obviously transitive.

In Euclid's definition, as I interpret it,
the pair $(x,y)$ is uniquely determined by $(a,b)$;
moreover, again, $x$ and $y$ are prime to one another.

Even without the condition on $e$ and $f$ above,
we immediately have that sameness of ratio
is reflexive and symmetric:
\begin{gather*}
  a:b::a:b,\\
  a:b::c:d\implies c:d::a:b.
\end{gather*}
There is also another kind of symmetry:
\begin{equation*}
  a:b::c:d\implies b:a::d:c.
\end{equation*}
Thus, in \eqref{eqn:abcd}, we may assume $a>b$,
and also $a>c$, if this is convenient.

\begin{lemma}\label{lem:add}
  For all counting numbers $a$, $b$, $c$, and $d$,
  \begin{equation*}
  a:b::c:d\implies a:b::a\pm c:b\pm d.
\end{equation*}
\end{lemma}

\begin{proof}
  If $(a,b)$ and $(c,d)$
  have the same anthyphaeretic sequence,
  it will be the anthyphaeretic sequence of $(a+c,b+d)$ and $(a-c,b-d)$,
  since, for example,
  \begin{equation*}
    (a+c)-(b+d)=(a-b)+(c-d).
  \end{equation*}
  However, Euclid's proof uses Euclid's official definition
  of proportion of numbers.
  By definition, as in the general form \eqref{eqn:prop-gen}, we have
  \begin{gather*}
    ax:ay::cx:cy,\\
    ax:ay::(a\pm c)x:(a\pm c)y,
  \end{gather*}
  at least if $x$ and $y$ are prime to one another.
  We can conclude
  \begin{equation*}
    ax:ay::ax\pm cx:ay\pm cy,
  \end{equation*}
  by distributivity of multiplication over addition.
  This itself is a consequence of commutativity of addition:
  \begin{equation*}
    (a+c)\cdot2=a+c+a+c=a+a+c+c=a\cdot2+c\cdot2,
  \end{equation*}
  and so on.
\end{proof}

\begin{lemma}\label{lem:ax:cx}
  For all counting numbers $a$ and $c$, for all multipliers $x$,
  \begin{equation}\label{eqn:abaxbx}
    a:c::ax:cx.
  \end{equation}
\end{lemma}

\begin{proof}
  By repeated application of Lemma \ref{lem:add}
  to the proportion
  \begin{equation*}
    a:c::a:c,
  \end{equation*}
  we have
  \begin{equation*}
a:c::\underbrace{a+\dots+a}_x:\underbrace{c+\dots+c}_x.\qedhere
  \end{equation*}
\end{proof}

\begin{theorem}[Alternation]\label{thm:alt}
  For all counting numbers $a$, $b$, $c$, and $d$,
\begin{equation*}
  a:b::c:d\implies a:c::b:d.
\end{equation*}  
\end{theorem}

\begin{proof}
  Again by Euclid's definition,
  \begin{equation*}
    a:ax::c:cx.
  \end{equation*}
  We also have \eqref{eqn:abaxbx}
    in Lemma \ref{lem:ax:cx}.
  This proves the claim in case $a$ is part of $b$.
  For the general case, we use transitivity, which from \eqref{eqn:abaxbx}
  yields
  \begin{equation*}
    ax:cx::ay:cy,
  \end{equation*}
  while again from Euclid's definition,
  \begin{equation}\label{eqn:ax:ay}
    ax:ay::cx:cy,
  \end{equation}
  if $x$ and $y$ are prime to one another.
  Since \eqref{eqn:ax:ay} then is the general form of a proportion,
  the proof is complete.
\end{proof}

\begin{theorem}\label{thm:comm}
  Multiplication is commutative:
  \begin{equation*}
    ab=ba.
  \end{equation*}
\end{theorem}

\begin{proof}
  From the definition, and by Theorem \ref{thm:alt},
  \begin{gather*}
    1:a::b:ba,\\
    1:b::a:ba.
  \end{gather*}
  Therefore,
  as $b$ is the multiple of $1$ by $b$,
  so $ba$ must be the multiple of $a$ by $b$, namely $ab$.
\end{proof}

If $a$ measures $b$, or equivalently now if $a$ divides $b$, we may write
\begin{equation*}
  a\divides b.
\end{equation*}
We usually refer to the greatest common measure of $c$ and $d$
as the \textbf{greatest common divisor,} writing this as
\begin{equation*}
  \gcd(c,d).
\end{equation*}
A counting number $p$ is \textbf{prime,} simply, if it is not $1$, and
\begin{equation}\label{eqn:irred}
  p=ab\And p\neq a\implies p=b.
\end{equation}
Since
\begin{equation*}
  a=bc\implies b\divides a,
\end{equation*}
and in $\N$ also
\begin{equation*}
  a\divides b\And b\divides a\implies a=b,
\end{equation*}
we can write \eqref{eqn:irred} also as
\begin{equation}\label{eqn:irred'}
  p=ab\And p\ndivides a\implies p\divides b.
\end{equation}
Using B\'ezout's Theorem,
we can prove the following strengthening of \eqref{eqn:irred'}.

\begin{theorem}[Euclid]\label{thm:Euclid}
  For all primes $p$,
  \begin{equation}\label{eqn:prime}
    p\divides ab\And p\ndivides a\implies p\divides b.
  \end{equation}
\end{theorem}

\begin{proof}
  If $p\ndivides a$, then $p$ and $a$ are prime to one another,
  and therefore, for some $x$ and $y$,
  \begin{gather*}
    px+ay=1,\\
    pbx+aby=b.    
  \end{gather*}
  If $p\divides ab$, then $p$ divides both terms on the left,
  and hence their sum; thus $p\divides b$.
\end{proof}

A subset $R$ of $\C$ that is closed under addition,
subtraction, and multiplication is called a \textbf{ring}\label{ring}
(as also on page \pageref{ring2}).
Suppose $p$ is a nonzero element with no inverse in $R$.
\begin{compactitem}
\item
  If \eqref{eqn:irred'} holds in $R$,
  then $p$ is \textbf{irreducible} in $R$;
\item
  if \eqref{eqn:prime} holds in $R$,
  then $p$ is \textbf{prime} in $R$.
\end{compactitem}
Thus irreducibles are always prime.
We shall see (on page \pageref{irred})
an example where the converse fails.

Meanwhile, we give Euclid's proof of Theorem \ref{thm:Euclid}.
We shall need a couple of lemmas.

\begin{lemma}\label{lem:cross}
    For all counting numbers $a$, $b$, $c$, and $d$,
  \begin{equation*}
    ab=cd\implies a:c::d:b.
  \end{equation*}
\end{lemma}

\begin{proof}
  Assuming $ab=cd$,
  and using transitivity, we have
  \begin{align*}
    a:c
    &::ad:cd&&\text{[by Lemma \ref{lem:ax:cx}]}\\
    &::ad:ab&&\text{[by assumption]}\\
    &::da:ba&&\text{[by Theorem \ref{thm:comm}]}\\
    &::d:b.&&\text{[by Lemma \ref{lem:ax:cx} again]}\qedhere
  \end{align*}
\end{proof}

\begin{lemma}\label{lem:min}
  If \eqref{eqn:abcd} holds,
  and $a$ and $b$ are prime to one another,
  then $a\divides c$.
\end{lemma}

\begin{proof}
  If \eqref{eqn:abcd} holds, so that also
  \begin{equation*}
    a:c::b:d
  \end{equation*}
  by Theorem \ref{thm:alt},
  then the Euclidean Algorithm has the same steps,
  whether applied to $(a,c)$ or $(b,d)$.
  Applying the Euclidean Algorithm to \eqref{eqn:abcd},
  by Lemma \ref{lem:add} we have
  \begin{equation*}
    a:b::\gcd(a,c):\gcd(b,d),
  \end{equation*}
  and so by Theorem \ref{thm:alt}
  \begin{equation*}
    a:\gcd(a,c)::b:\gcd(b,d).
  \end{equation*}
  This means
  \begin{align*}
    a&=\gcd(a,c)x=x\gcd(a,c),&b&=\gcd(b,d)x=x\gcd(b,d)
  \end{align*}
  for some $x$.
  If $a$ and $b$ are prime to one another,
  then $x=1$, and $\gcd(a,c)=a$, so $a\divides c$.
\end{proof}

\begin{proof}[Euclid's proof of Theorem \ref{thm:Euclid}.]
  Suppose now $pc=ab$, but $p\ndivides a$.
  Then $p$ and $a$ are prime to one another, and also
  \begin{equation*}
    p:a::b:c
  \end{equation*}
  by Lemma \ref{lem:cross},
  and therefore $p\divides b$ by Lemma \ref{lem:min}.
\end{proof}

An important theoretical consequence of Theorem \ref{thm:Euclid}
that Euclid does \emph{not} prove is the following.

\begin{theorem}[Fundamental Theorem of Arithmetic]\label{thm:FTA}
  Every counting number is \emph{uniquely} a product
  \begin{equation*}
    p_0p_1\cdots p_{n-1}
  \end{equation*}
  of primes, where
  \begin{equation}\label{eqn:p's}
    p_0\leq p_1\leq\dots\leq p_{n-1}.
  \end{equation}
\end{theorem}

If $n=0$, then the product in \eqref{eqn:p's} is $1$.
A \textbf{square} number is any $n^2$,
where $n$ is an integer.
A \textbf{nonsquarefree} number
is one that is indivisible by the square of any prime.

\begin{theorem}
  If $D$ is nonsquare, then the equation
  \begin{equation*}
    x^2-Dy^2=0
  \end{equation*}
  has no solution in $\N$.
\end{theorem}

\begin{proof}
  We may write
  \begin{equation*}
    D=s^2d,
  \end{equation*}
  where $d$ is squarefree and greater than $1$.
  It is then enough to show that
  \begin{equation}\label{eqn:=0}
    x^2-dy^2=0
  \end{equation}
  is insoluble.
  If $(a,b)$ is a solution,
  then $d\divides a^2$.
  However,
  \begin{equation*}
    d=p_0p_1\dots p_{n-1},
  \end{equation*}
  where
  \begin{equation*}
    p_0<p_1<\dots<p_{n-1}.
  \end{equation*}
  Thus in each case
  \begin{equation*}
    p_k\divides a^2,
  \end{equation*}
  so by Theorem \ref{thm:Euclid}
  \begin{equation*}
    p_k\divides a.
  \end{equation*}
  In particular then, for some $x_k$,
  \begin{gather*}
    a=p_0x_0,\\
    p_1\divides x_0,\\
    a=p_0p_1x_1,\\
    \makebox[2cm]{\dotfill},\\
    a=p_0p_1\cdots p_{n-1}x_{n-1}=dx_{n-1},\\
    d^2x_{n-1}{}^2-db^2=0,\\
    dx_{n-1}{}^2-b^2=0,
  \end{gather*}
  so $(b,x_{n-1})$ is a solution to \eqref{eqn:=0}.
  Also $b<a$.
  Continuing, we contain an infinite decreasing sequence of counting numbers,
  which is impossible.  So \eqref{eqn:=0} has no solution from $\N$.
\end{proof}


\chapter{The Circle}\label{ch:circle}

We find all integer solutions of
  \begin{equation}\label{eqn:Pyth}
    x^2+y^2=z^2,
  \end{equation}
The following are equivalent:
\begin{compactenum}
\item
  $(a,b,c)$ is a solution;
\item
$(\size a,\size b,\size c)$
  is a solution;
\item
$(na,nb,nc)$ is a solution for all nonzero $n$;
\item
$(b,a,c)$ is a solution.
\end{compactenum}
Also,~\eqref{eqn:Pyth} is equivalent to 
\begin{equation*}
x^2=(z+y)(z-y).
\end{equation*}
Suppose $(a,b,c)$ is a solution of~\eqref{eqn:Pyth} such that
$a,b,c>0$ and $\gcd(a,b,c)=1$.  
Then $(a,b,c)$ may be called a \defn{primitive solution}, 
and all solutions can be obtained from primitive solutions.
Observe that not both $a$ and $b$ are even.  
Also, if $a,b\equiv1\pmod 2$, then
$c^2\equiv a^2+b^2\equiv2\pmod4$, which is absurd.  
So exactly one of $a$ and $b$ is even.  Say $a$ is even.  
Then $b$ and $c$ are odd, and
\begin{equation*}
  \left(\frac a2\right)^2=\left(\frac{c+b}2\right)\left(\frac{c-b}2\right).
\end{equation*}
Also $(c+b)/2$ and $(c-b)/2$ are co-prime, since their sum is $c$ and
their difference is $b$.  Hence each must be a square,
by Theorem \ref{thm:FTA}; say
\begin{equation*}
  \frac{c+b}2=n^2,\qquad\frac{c-b}2=m^2,
\end{equation*}
where $n,m>0$.  Then
\begin{align*}
  c&=n^2+m^2,& b&=n^2-m^2, &a&=2nm.	
\end{align*}
Moreover, $n$ and $m$ are co-prime, and exactly one of them is odd
(since $c$ is odd).

Conversely, suppose $n$ and $m$ are co-prime, exactly one of them is
odd, and $0<m<n$.  Then the triple $(2nm,n^2-m^2,n^2+m^2)$
solves~\eqref{eqn:Pyth}.
Moreover, every common prime factor of $n^2-m^2$ and $n^2+m^2$ 
is a factor of the sum $2n^2$ and the difference $2m^2$,
and is odd,
so it is a common factor of $n$ and $m$.  
Thus there is no common prime factor, and the
triple is a \emph{primitive} solution.

We conclude that there is a one-to-one correspondence between:
\begin{compactenum}
  \item
pairs $(m,n)$ of co-prime integers, where $0<m<n$, and exactly
one of $m$ and $n$ is odd;
\item
primitive solutions $(a,b,c)$ to~\eqref{eqn:Pyth}, where $a$ is even.
\end{compactenum}
The correspondence is $(x,y)\mapsto(2xy,y^2-x^2,y^2+x^2)$.



\chapter{Irrational Numbers}\label{ch:root-2}

We say that the equation \eqref{eqn:=0} has \emph{real} solutions,
such as $(\surd d,1)$.
For example, we say that the equation
\begin{equation}\label{eqn:x^2=2}
  x^2=2
\end{equation}
has the solution denoted by
\begin{equation*}
  \surd2.
\end{equation*}
what do we mean by this?

\section{Geometry}

One approach to solving \eqref{eqn:x^2=2}
is to let the solution be
the length of the diagonal of a square whose side has length $1$.
In this approach to arithmetic,
we assume Euclidean geometry,
in which there is a notion of congruence of line segments.
Congruence being an equivalence relation,
we can define the \textbf{length} of a segment
to be the class of segments congruent to it.
We can add two lengths in the obvious way,
by placing two representative segments end to end.
To multiply one segment by another,
we can use what is called Thales's Theorem.
Descartes did this in the \emph{Geometry} \cite{Descartes-Geometry},
and Hilbert worked out the details rigorously in
\emph{The Foundations of Geometry} \cite{MR0116216}.

In a paper called ``Thales and the Nine-point Conic'' \cite{Pierce-Thales-9},
I review what is needed, and suggest an alternative approach,
making use of \emph{areas,} as Apollonius did.
The point is that, although Thales's Theorem is generally accepted today,
it is nontrivial, because the concept of proportion is nontrivial.
For example, in Figure \ref{fig:Thales},
\begin{figure}
  \centering
  \begin{pspicture}(-1,-0.5)(4.6,4.5)
%    \psgrid
    \pstGeonode[PosAngle={-90,180,90}](0,0)A(-1,4)B(3,4)C
    \pstRotation[RotAngle=-30]AC[D]
    \pstHomO[HomCoef=0.4,PosAngle={180,90,-75}]A{B,C,D}[E,F,G]
    \ncline AB\ncline AC\ncline AD
    \ncline BC\ncline CD\ncline DB
    \ncline EF\ncline FG\ncline GE
  \end{pspicture}
  \caption{A consequence of Thales's Theorem}
  \label{fig:Thales}
\end{figure}
$AD=AC$, $AG=AF$, and $EF\parallel BC$.
We can use Thales's Theorem to prove that $EG\parallel BD$.
This result has nothing obvious to do with proportion,
and yet it is not clear how to prove the result
\emph{without} using proportions.

\section{Dedekind Cuts}\label{sect:cuts}

An alternative approach to arithmetic is Dedekind's,
worked out in \emph{Continuity and Irrational Numbers} \cite{MR0159773}.
We start with the rational numbers as an \textbf{ordered field,}
namely an ordered set equipped also with operations of addition and multiplication that are compatible with the ordering in the usual way.
We obtain each real number as a \textbf{cut,}
namely a partition of $\Q$ into two nonempty parts,
each member of the first part
being less than each member in the second part.
Two such partitions are considered the same
if they differ at a single point.
This point will be the greatest member of the first part of one partition,
but the least member of the second part of the other partition.
That point will be a rational number,
which we can identify with the cut just described.
In this way, every rational number becomes a real number;
but some real numbers are not determined by rational numbers in this way.

Dedekind's procedure gives $\R$ as an ordered set
satisfying the \textbf{Completeness Axiom,}
whereby every nonempty set of real numbers that has an upper bound
has a least upper bound, or supremum.
We have to define addition and multiplication on $\R$
so that each of the functions
\begin{align*}
  x&\mapsto a+x,&x&\mapsto ax
\end{align*}
is continuous.
This will give us $\R$ as an ordered field.
We can then define
\begin{equation*}
  \surd2=\sup\{x\in\Q\colon x^2<2\}.
\end{equation*}
Continuity will ensure that this solves \eqref{eqn:x^2=2}.

\section{Cauchy Sequences}

There are other approaches to the real numbers.
For example, we can define a real number
to be an equivalence class of Cauchy sequences of rational numbers,
two sequences being equivalent
if the sequence of differences of their terms has limit $0$.

\chapter{The Square Root of Two}

Without going into the details of any particular development of $\R$,
we shall now find a sequence of rational numbers
whose limit is $\surd2$.  We note that
\begin{align*}
  \surd2&=1+(\surd2-1),&
  \frac1{\surd2-1}&=\surd2+1,
\end{align*}
so that
\begin{equation}\label{eqn:root-2-cf}
\surd2
=1+\frac1{\surd2+1}
=1+\cfrac1{2+\cfrac1{\surd2+1}}
=1+\cfrac1{2+\cfrac1{2+\cfrac1{\surd2+1}}}
\end{equation}
and so on.
Replacing each instance of $1/(\surd2+1)$ with $0$,
we define
\begin{align*}
  \frac{p_0}{q_0}&=1,&
  \frac{p_1}{q_1}&=1+\frac12=\frac32,&
  \frac{p_2}{q_2}&=1+\cfrac1{2+\cfrac1{2}}=\frac75,
\end{align*}
and in general
\begin{equation*}
  \frac{p_{n+1}}{q_{n+1}}
  =1+\cfrac1{1+\cfrac{p_n}{q_n}}
  =\frac{p_n+2q_n}{p_n+q_n}.
\end{equation*}
The equations alone do not define $p_n$ and $q_n$ separately.
We require also that each of them be positive,
and that the two of them be prime to one another.
In this case,
\begin{align}\label{eqn:pq-2}
&
  \begin{gathered}
    p_0=1,\\q_0=1,
  \end{gathered}&
&
  \begin{gathered}
    p_1=3,\\q_1=2,
  \end{gathered}&
&
  \begin{gathered}
    p_{n+2}=p_n+2q_n,\\q_{n+2}=p_n+q_n.
  \end{gathered}
\end{align}
We compute some values in Table \ref{tab:pq-2}.
\begin{table}
  \centering
  \begin{math}
    \begin{array}{c|*8c}
        n&0&1&2&3& 4& 5& 6&  7\\\hline
        p_n&1&3&7&17&41&99&239&577\\\hline
        q_n&1&2&5&12&29&70&169&408
    \end{array}
  \end{math}
  \caption[Convergents of $\surd2$]
          {Numerators and denominators of convergents of $\surd2$}
  
  \label{tab:pq-2}
\end{table}
Testing them suggests the following.

\begin{theorem}
  When $p_n$ and $q_n$ are as in \eqref{eqn:pq-2}, then
  \begin{equation}\label{eqn:pq-diff-for-2}
    p_n{}^2-2q_n{}^2=(-1)^{n+1},
  \end{equation}
  so that
\begin{equation*}
  \abs{\left(\frac{p_n}{q_n}\right)^2-2}=\frac1{q_n{}^2}.
\end{equation*}
Since also the sequence of $q_n$ increases without bound, 
  \begin{equation}\label{eqn:alt}
    \frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\dots<\surd2
    <\dots<\frac{p_5}{q_5}<\frac{p_3}{q_3}<\frac{p_1}{q_1},
  \end{equation}
  and the sequence of $p_n/q_n$ is Cauchy,
  with limit $\surd2$.
\end{theorem}

\begin{proof}
  We use induction.
  The claim \eqref{eqn:pq-diff-for-2}
  holds when $n=0$.
  If it holds when $n=m$, then
  \begin{multline*}
    p_{m+1}{}^2-2q_{m+1}{}^2
    =(p_m+2q_m)^2-2(p_m+q_m)^2\\
    =-p_m{}^2+2q_m{}^2
    =-(-1)^{m+1}
    =(-1)^{m+2},
  \end{multline*}
so   \eqref{eqn:pq-diff-for-2}
  holds when $n=m+1$.
\end{proof}

We may now refer to the fractions $p_n/q_n$
as \textbf{convergents} of $\surd2$.
According to the theorem, $(p_n,q_n)$ is a point on the hyperbola given by
\begin{equation}\label{eqn:pell-2}
  x^2-2y^2=1,
\end{equation}
when $n$ is odd, and
\begin{equation*}
  2y^2-x^2=1,
\end{equation*}
when $n$ is even.
Each hyperbola has asymptotes
\begin{equation*}
  y=\pm\frac1{\surd2}x,
\end{equation*}
as in Figure \ref{fig:2-hyp}.
\begin{figure}
  \centering
  \psset{unit=13mm}
%  \def\pshlabel#1{\small$#1$}
%  \def\psvlabel#1{\tiny$#1$}
  \begin{pspicture}*(-0.3,-0.4)(7.78,5.5)
    \psgrid[subgriddiv=1,griddots=8,%gridlabels=0pt
    ]
    \psaxes[labels=none]
    (8,6)
  \psline[linestyle=dashed](0,0)(! 8 dup 2 sqrt div)
  \psdots(1,1)(3,2)(7,5)
  \psplot{0}{7.78}{x dup mul 1 add 2 div sqrt}
  \parametricplot{0}{5.5}{t dup mul 2 mul 1 add sqrt t}
  \end{pspicture}
  \caption{Integer points of hyperbolas $x^2-2y^2=\pm1$}
\label{fig:2-hyp}  
\end{figure}

\chapter{The Pell Equation}

Equation \eqref{eqn:pell-2} is an example of a \textbf{Pell equation.}
The general form of a Pell equation is
\begin{equation}\label{eqn:pell}
  x^2-dy^2=1,
\end{equation}
where $d$ is a positive nonsquare integer.
We are interested in integer solutions,
and among these, \textbf{positive} solutions,
meaning each entry is positive.
There are trivial solutions, namely $(\pm1,0)$.
Every other integer solution is $(-a,\pm b)$ or $(a,-b)$,
where $(a,b)$ is a positive solution.

\begin{theorem}\label{thm:>1}
  If $(a,b)$ is a solution to \eqref{eqn:pell} and
  \begin{equation}\label{eqn:>1}
    a+b\surd d>1,
  \end{equation}
  then $(a,b)$ is a \emph{positive} solution to \eqref{eqn:pell}.
\end{theorem}

\begin{proof}
We are given
  \begin{equation*}
    1=a^2-db^2=(a+b\surd d)(a-b\surd d),
  \end{equation*}
  along with \eqref{eqn:>1}, and this implies
  \begin{equation*}
    0<a-b\surd d<1<a+b\surd d.
  \end{equation*}
Hence $b$ must be positive, and then $a$ must be positive.
\end{proof}

There is more along the same lines:

\begin{theorem}\label{thm:prod}
  If $(a,b)$ and $(s,t)$ are solutions to \eqref{eqn:pell},
  then so is
  \begin{equation*}
    (as+dbt,bs+at),
  \end{equation*}
  which is obtained from the equation
    \begin{equation*}
    as+dbt+(bs+at)\surd d=(a+b\surd d)(s+t\surd d).
  \end{equation*}
\end{theorem}

\begin{proof}
Write the proposed solution as $(\ell,m)$.  Then
  \begin{equation*}
    \ell\pm m\surd d=(a\pm b\surd d)(s\pm t\surd d),
  \end{equation*}
and so
  \begin{multline*}
    1=(a^2-db^2)(s^2-dt^2)\\
    =(a+b\surd d)(a-b\surd d)(s+t\surd d)(s-t\surd d)\\
    =(a+b\surd d)(s+t\surd d)(a-b\surd d)(s-t\surd d)\\
    =(\ell+m\surd d)(\ell-m\surd d)
    =\ell^2-dm^2.
  \end{multline*}
  Thus $(\ell,m)$ is a solution of \eqref{eqn:pell}.
\end{proof}

\begin{theorem}\label{thm:pell-sol}
  If, for some positive nonsquare $d$,
  \eqref{eqn:pell} has a positive solution,
  then it has a positive solution $(a,b)$ such that,
  for every positive solution $(s,t)$,
  for some positive $n$,
  \begin{equation*}
    s+t\surd d=(a+b\surd d)^n.
  \end{equation*}
\end{theorem}

\begin{proof}
We let $(a,b)$ be the positive solution that minimizes $x+y\surd d$.
  Since $a+b\surd d>1$, the sequence of $(a+b\surd d)^n$
  increases without bound, and so, for some $n$,
  \begin{gather*}
    (a+b\surd d)^n\leq s+t\surd d<(a+b\surd d)^{n+1},\\
  1\leq(s+t\surd d)(a-b\surd d)^n<a+b\surd d.
  \end{gather*}
For some integers $\ell$ and $m$,
\begin{equation*}
  (s+t\surd d)(a-b\surd d)^n=\ell+m\surd d.
\end{equation*}
This makes $(\ell,m)$ a solution of~\eqref{eqn:pell},
by Theorem \ref{thm:prod}.
It cannot be a positive solution,
by minimality of $(a,b)$;
therefore, by Theorem \ref{thm:>1},
$(\ell,m)$ is the trivial solution $(1,0)$,
so $(s,t)$ is as claimed.
\end{proof}

By Theorem \ref{thm:pos-sol} on page \pageref{thm:pos-sol},
\eqref{eqn:pell} \emph{will} always have a positive solution.
Meanwhile, we can just hunt for solutions in particular cases.

\begin{example}\label{example:pell-2}
  We can see by inspection that $(3,2)$ is the solution of \eqref{eqn:pell-2}
  that minimizes $x+y\surd2$.  Indeed,
  \begin{align*}
    4/3<\surd2&<3/2,& 3+2\surd2&<6,
  \end{align*}
  so the only possible solutions to check are
  \begin{align*}
    &1+\surd2,&
    &2+\surd2,&
    &4+\surd2,&
    &1+3\surd2,
  \end{align*}
  and none of these is actually a solution.
  By the theorem,
  we now know all positive solutions of \eqref{eqn:pell-2}:
  they are $(a_n,b_n)$, where $n\in\N$ and
  \begin{equation*}
    a_n+b_n\surd2=(3+2\surd2)^n.
  \end{equation*}
  Allowing $n$ to be also zero or negative,
  we obtain all solutions where $x>0$.
  We have $(a+b\surd d)\inv =a-b\surd d$ and
  \begin{equation*}
    (3\pm2\surd2)(x+y\surd2)=3x\pm4y+(\pm2x+3y)\surd2.
  \end{equation*}
  Applying the latter repeatedly, we can find all solutions just mentioned.
  See Figure \ref{fig:line}.
  \begin{figure}
  \centering
  \psset{unit=13mm}
%  \def\pshlabel#1{\small$#1$}
%  \def\psvlabel#1{\tiny$#1$}
  \begin{pspicture}*(-0.4,-2.4)(6.4,2.4)
    %\psgrid%[subgriddiv=1,griddots=8]
    \psaxes[labels=none]
    (0,0)(0,-3)(7,3)
  %\psline[linestyle=dashed](0,0)(! 2 dup sqrt mul 2)
  \psdots(1,0)(3,2)(3,-2)(! 3 2 dup sqrt mul add 0)(! 3 2 dup sqrt mul sub 0)
  \parametricplot{-3}{3}{t dup mul 2 mul 1 add sqrt t}
  \psset{linestyle=dotted}
  \psline(0,2)(3,2)(3,-2)(0,-2)
  \psline(3,2)(! 3 2 dup sqrt mul add 0)
  \psline(3,-2)(! 3 2 dup sqrt mul sub 0)
  \uput[d]{35}(! 3 2 dup sqrt mul add 0){$3+2\surd2$\ }
  \uput[u]{35}(! 3 2 dup sqrt mul sub 0){\ \ $3-2\surd2$}
  \end{pspicture}
  \caption{Integer points of hyperbola $x^2-2y^2=1$}
\label{fig:line}  
\end{figure}
  Alternatively, from \eqref{eqn:pq-2} we obtain
  \begin{gather*}
    p_{n+2}
    =p_{n+1}+2q_{n+1}
    =p_n+2q_n+2(p_n+q_n)
    =3p_n+4q_n,\\
    q_{n+2}
    =p_{n+1}+q_{n+1}
    =p_n+2q_n+p_n+q_n
    =2p_n+3q_n,
  \end{gather*}
  and so, by induction,
  \begin{equation*}
    (a_n,b_n)=(p_{2n-1},q_{2n-1}).
  \end{equation*}
  Thus all positive solutions of \eqref{eqn:pell-2}
  correspond to certain convergents of $\surd2$.
  We may note
  \begin{equation*}
    \begin{pmatrix}
      a_n\\b_n
    \end{pmatrix}
    =
    \begin{pmatrix}
      3&4\\2&3
    \end{pmatrix}^n
    \begin{pmatrix}
      1\\0
    \end{pmatrix}.
  \end{equation*}
  This is meaningful, even if $n\leq0$,
  and then it yields the remaining solutions of \eqref{eqn:pell-2}
  in which $x>0$;
  the solutions in which $x<0$ are $(-a_n,-b_n)$, where $n\in\Z$.
\end{example}

\chapter{Continued Fractions}

The method of Example \ref{example:pell-2}
will work for arbitrary positive nonsquare $d$ in \eqref{eqn:pell}.
Given any real number $x$, such as $\surd d$,
  we define sequences of real numbers $a_n$ and $\xi_n$,
  where each $a_n$ is an integer,
  \begin{equation*}
    0\leq\xi_n<1,
  \end{equation*}
  and
\begin{equation*}
  x
  =a_0+\xi_0
=a_0+\frac1{a_1+\xi_1}
=a_0+\cfrac1{a_1+\cfrac1{a_2+\xi_2}}
%a_0+\cfrac1{a_1+\cfrac1{a_2+\cfrac1{a_3+\xi_3}}}
\end{equation*}
and so on, as long as $\xi_n$ is not zero
(which it will never be, if $x$ is irrational).
In general,
\begin{equation}\label{eqn:cont}
  x
=a_0+\cfrac1{a_1+\cfrac1{a_2+\ddots \cfrac1{a_{n-1}+\cfrac1{a_n+\xi_n}}}},
\end{equation}
and we may write this also as
\begin{equation*}
  a_0+\frac1{a_1+}\;\frac1{a_2+}\dots\;\frac1{a_{n-1}+}\;\frac1{a_n+\xi_n}.
\end{equation*}
Thus
\begin{align*}%\label{eqn:a_0}
a_0&=[x], & \xi_0&=x-a_0,
\end{align*}
square brackets denoting the
greatest-integer function; and by recursion,
\begin{align*}%\label{eqn:a_n}
a_{n+1}&=\left[\frac1{\xi_n}\right],\quad& \xi_{n+1}&=\frac1{\xi_n}-a_{n+1},
\end{align*}
where $\xi_n$ must be non-zero for $a_{n+1}$ to be defined.
In \eqref{eqn:root-2-cf} on page \pageref{eqn:root-2-cf},
we performed the computations when $x=\surd2$,
obtaining $a_0=1$, but $a_n=2$ when $n>0$.

\begin{example}
  When $x=\surd6$, we compute
  \begin{gather*}
    \surd6=2+(\surd6-2),\\
    \frac1{\surd6-2}=\frac{\surd6+2}2=2+\frac{\surd6-2}2,\\
    \frac2{\surd6-2}=\surd6+2=4+(\surd6-2),
  \end{gather*}
  so that $a_n=2$ when $n=0$ or $n$ is odd,
  and $a_n=4$ when $n$ is positive and even.
\end{example}

In the right-hand side of \eqref{eqn:cont},
if we replace $\xi_n$ with $0$,
we obtain the number that we shall denote by
\begin{equation*}
  [a_0;a_1,\dots,a_n].
\end{equation*}
Thus
\begin{align}\label{eqn:a2}
	  [a_0]&=a_0,&
[a_0;a_1]&=a_0+\cfrac1{a_1},&
[a_0;a_1,a_2]&=a_0+\cfrac1{a_1+\cfrac1{a_2}},
\end{align}
and so forth;
the general term is given recursively by
\begin{equation}\label{eqn:brackets}
[a_0;a_1,\dots,a_{n+1}]
=\left[a_0;a_1,\dots,a_{n-1},a_n+\frac1{a_{n+1}}\right].
\end{equation}
By studying \eqref{eqn:cont}, we can see that,
as in \eqref{eqn:alt}, so generally,
\begin{equation*}
  [a_0]<[a_0;a_1,a_2]%<[a_0;a_1,a_2,a_3,a_4]
  <\dots<x<\dots%<[a_0;a_1,a_2,a_3,a_4,a_5]
  <[a_0;a_1,a_2,a_3]<[a_0;a_1].
\end{equation*}
We shall work out a formal proof of this,
by finding integers $p_n$ and $q_n$ such that
\begin{equation}\label{eqn:apq}
  [a_0;a_1,\dots,a_n]=\frac{p_n}{q_n},
\end{equation}
as we have already done when considering the example $x=\surd2$.
From \eqref{eqn:a2}, we want
\begin{align*}
	  \frac{p_0}{q_0}&=a_0,&
\frac{p_1}{q_1}&=\frac{a_0a_1+1}{a_1},&
\frac{p_2}{q_2}&=\frac{a_0a_1a_2+a_0+a_2}{a_1a_2+1}.
\end{align*}
Hence we may define
\begin{align*}
  &\begin{gathered}
  p_0=a_0,\\  
  q_0=1,
  \end{gathered}&
  &\begin{gathered}
  p_1=p_0a_1+1,\\  
  q_1=a_1,
  \end{gathered}&
  &\begin{gathered}
  p_2=p_1a_2+p_0,\\  
  q_2=q_1a_2+q_0.
   \end{gathered}
\end{align*}


\begin{theorem}%\label{thm:pq}
  For all $n$ in $\upomega$,
  the definitions
  \begin{align*}
    p_{n+2}&=p_{n+1}a_{n+2}+p_n,&
    q_{n+2}&=q_{n+1}a_{n+2}+q_n
  \end{align*}
   satisfy \eqref{eqn:apq}.
\end{theorem}

\begin{proof}
  We use induction.
  We have just seen that the claim holds when $n=0$.
  Supposing, for some $m$, the claim holds when $n=m$,
  we have
\begin{multline*}
[a_0;a_1,\dots,a_{m+3}]
=\left[a_0;a_1,\dots,a_{m+1},a_{m+2}+\frac1{a_{m+3}}\right]\\
=\frac{p_{m+1}\cdot
  \left(a_{m+2}+\displaystyle\frac1{a_{m+3}}\right)+p_m}
     {q_{m+1}\cdot\left(a_{m+2}+\displaystyle\frac1{a_{m+3}}\right)+q_m}\\
=
\frac{p_{m+1}a_{m+2}a_{m+3}+p_{m+1}+p_ma_{m+3}}
     {q_{m+1}a_{m+2}a_{m+3}+q_{m+1}+q_ma_{m+3}}\\
=
\frac{p_{m+2}a_{m+3}+p_{m+1}}{q_{m+2}a_{m+3}+q_{m+1}}
=\frac{p_{m+3}}{q_{m+3}}.
\end{multline*}
By induction,
the claim holds for all $n$ in $\upomega$.
\end{proof}

We now confirm the additional property that we wanted.

\begin{theorem}\label{thm:-1}
For all $n$ in $\upomega$,
  \begin{equation*}
    \frac{p_{n+1}}{q_{n+1}}-\frac{p_n}{q_n}=\frac{(-1)^n}{q_{n+1}q_n}.
  \end{equation*}
\end{theorem}

\begin{proof}
We prove the equivalent statement
\begin{equation}\label{eqn:=-1}
  p_{n+1}q_n-p_nq_{n+1}=(-1)^n.
\end{equation}
Again we use induction.  We have
\begin{equation*}
  p_1q_0-p_0q_1=p_0a_1+1-a_0a_1=1,
  \end{equation*}
  so the claim holds when $n=0$.
  Supposing it holds when $n=m$, we have
\begin{multline*}
  p_{m+2}q_{m+1}-p_{m+1}q_{m+2}\\
  =(p_{m+1}a_{m+2}+p_m)q_{m+1}-p_{m+1}(q_{m+1}a_{m+2}+q_m)\\
  =p_mq_{m+1}-p_{m+1}q_m,
\end{multline*}
which is $-(-1)^m$, that is, $(-1)^{m+1}$.  Thus
the claim holds for all $n$ in $\upomega$.
\end{proof}

\begin{corollary}
  $p_n$ and $q_n$ are prime to one another.
\end{corollary}

\begin{proof}
  Apply Theorem \ref{thm:Bezout} to \eqref{eqn:=-1}.
\end{proof}

\begin{corollary}
  The sequence of $p_n/q_n$ is Cauchy, with limit $x$.
\end{corollary}

The latter corollary justifies referring to the $p_n/q_n$
as the \textbf{convergents} of $x$.

\chapter{Solubility of the Pell Equation}

As usual, $d$ is a positive nonsquare.

\begin{lemma}\label{lem:k}
For some positive $k$, the equation
  \begin{equation}\label{eqn:pell-k}
    x^2-dy^2=k
  \end{equation}
has infinitely many solutions.
\end{lemma}

\begin{proof}
  Let $(p_n/q_n\colon n\in\upomega)$ be the sequence of convergents for
  $\surd d$.
  When $n$ is odd, then
  \begin{gather*}
    0<\frac{p_n}{q_n}-\surd d<\frac{p_n}{q_n}-\frac{p_{n+1}}{q_{n+1}}=
    \frac1{q_{n+1}q_n}<\frac1{q_n{}^2}, \\
    0<\frac{p_n}{q_n}+\surd d<\frac{2p_n}{q_n}.
  \end{gather*}
Multiplying gives
\begin{align*}
0&<  \frac{p_n{}^2}{q_n{}^2}-d<\frac{2p_n}{q_n{}^3},&
0&<p_n{}^2-dq_n{}^2<\frac{2p_n}{q_n}<\frac{2p_1}{q_1}.  
\end{align*}
Thus there are finitely many possibilities for $p_n{}^2-dq_n{}^2$, so
one of them must be realized infinitely many times.
\end{proof}

\begin{theorem}\label{thm:pos-sol}
The Pell equation \eqref{eqn:pell} has a positive solution.  
\end{theorem}

\begin{proof}
  By Lemma \ref{lem:k},
  we may let $k$ be a positive integer such that
  \eqref{eqn:pell-k} has infinitely many solutions.
  There are just finitely many pairs $(a,b)$
  such that $0\leq a<k$ and $0\leq b<k$.
  Hence there must be one such pair for which
  \eqref{eqn:pell-k} and the congruences
  \begin{equation*}
    x\equiv a\And y\equiv b\pmod k
  \end{equation*}
  simultaneously have infinitely many solutions.
  Let $(m,n)$ and $(s,t)$ be two solutions.
  By computations as for Theorem \ref{thm:prod},
\begin{equation}\label{eqn:k^2}
  k^2=(m^2-dn^2)(s^2-dt^2)=(ms-dnt)^2-d(mt-ns)^2.
\end{equation}
Moreover, $m\equiv s$ and $n\equiv t$ \emph{modulo} $k$,
so that
\begin{align*}
  ms-dnt&\equiv m^2-dn^2\equiv0,&mt-ns&\equiv mn-nm\equiv0.
\end{align*}
Therefore,
in \eqref{eqn:k^2} we can divide by $k^2$, obtaining
\begin{equation*}
  1=\left(\frac{ms-dnt}k\right)^2-d\left(\frac{mt-ns}k\right)^2.
\end{equation*}
Changing signs as needed gives
%Thus $(\size{ms-dnt}/k,\size{mt-ns}/k)$ is 
a positive solution
to~\eqref{eqn:pell}. 
\end{proof}


\chapter{Quadratic Fields}

We can write the Pell equation \eqref{eqn:pell} as
\begin{equation}\label{eqn:pell-fac}
  (x+y\surd d)(x-y\surd d)=1.
\end{equation}
We consider the factors here individually.
We define
\begin{equation*}
  \{u+v\surd d\colon(u,v)\in\Q^2\}=\Q(\surd d)=K.
\end{equation*}
We define on $K$ the operation
  $\xi\mapsto\xi'$,
where
  \begin{equation*}
    (u+v\surd d)'=u-v\surd d.
  \end{equation*}
  We may assume $d$ is a squarefree integer;
  it may be negative.
  In any case, $K\included\C$.
  If $d<0$, then $\xi'=\overline{\xi}$
(the complex conjugate of $\xi$).
  If $d>0$,
  then $K\included\R$.

\begin{theorem}
  $K$ is closed under addition,
  subtraction, multiplication, and division.
  The operation $\xi\mapsto\xi'$ on $K$
  distributes over addition and multiplication,
  so that
  \begin{align*}%\label{eqn:dist}
    (\xi+\eta)'&=\xi'+\eta',&
    (\xi\eta)'&=\xi'\eta'.
  \end{align*}
\end{theorem}

The proof is an exercise.
In technical algebraic terminology,
the theorem is that $K$ is a \textbf{subfield} of $\C$,
and $\xi\mapsto\xi'$ is an \textbf{automorphism} of $K$.

We now define two functions from $K$ to $\Q$,
called \textbf{trace} and \textbf{norm,}
given respectively by
\begin{align*}%\label{eqn:tr-n}
  \tr{\xi}&=\xi+\xi',&\norm{\xi}&=\xi\xi'.
\end{align*}
Then
\begin{align*}
  \tr{\xi+\eta}&=\tr{\xi}+\tr{\eta},&
  \norm{\xi}\norm{\eta}&=\norm{\xi\eta}.
\end{align*}
For any two elements $\alpha$ and $\beta$ of $K$,
we define
\begin{equation*}
  \{\alpha x+\beta y\colon(x,y)\in\Z^2\}=\latt.
\end{equation*}
Normally $\alpha\neq0$ and $\beta/\alpha\notin\Q$;
this means, in $\Z$,
\begin{equation}\label{eqn:ab-ind}
  \alpha x+\beta y=0\implies (x,y)=(0,0);
\end{equation}
in this case, $\latt$ is a \textbf{lattice} of $K$.
A lattice is closed under addition and subtraction,
but not necessarily under multiplication.
However, $\latt[1,\surd d]$ is closed under multiplication.
Now can give an example promised in Chapter \ref{ch:Euclid}.

\begin{example}\label{irred}
  In $\latt[1,\surd{-5}]$ we have
  \begin{equation*}
    2\cdot3=(1+5\surd{-5})(1-5\surd{-5}), 
  \end{equation*}
  and therefore
  \begin{equation*}
    2\divides(1+5\surd{-5})(1-5\surd{-5}),
  \end{equation*}
  although
  \begin{equation*}
    2\ndivides1\pm5\surd{-5}.
  \end{equation*}
  Thus $2$ is not prime in $\latt[1,\surd{-5}]$,
  according to the definition \eqref{eqn:prime}
  on page \pageref{eqn:prime}.
  However, $2$ is irreducible, according to \eqref{eqn:irred'}.
  For suppose $2=\alpha\beta$.  We have
  \begin{equation*}
    4=\norm2=\norm{\alpha}\norm{\beta}.
  \end{equation*}
  Since in general
  \begin{equation*}
    \norm{x+y\surd{-5}}=x^2+5y^2,
  \end{equation*}
  norms of nonzero elements of $\latt[1,\surd{-5}]$ are positive integers,
  but never $2$.  Thus we may assume $\norm{\alpha}=1$,
  and therefore $\alpha=\pm1$,
  so $\beta=\pm2$, and $2\divides\beta$.
\end{example}

We can write \eqref{eqn:pell-fac} as
\begin{equation}\label{eqn:pell-norm}
  \norm{\xi}=1\And\xi\in\latt[1,\surd d].
\end{equation}
That is, solutions to \eqref{eqn:pell}, or \eqref{eqn:pell-fac},
and \eqref{eqn:pell-norm}
are in one-to-one correspondence under the map
\begin{equation*}
  (x,y)\mapsto x+y\surd d.
\end{equation*}
The product of solutions of \eqref{eqn:pell-norm} is a solution,
as we have seen in effect in Theorem \ref{thm:prod} on page \pageref{thm:prod}.
Equation \eqref{eqn:pell} may seem simpler than \eqref{eqn:pell-norm}.
However,
in case $d>0$, so that $K\included\R$,
the solutions to \eqref{eqn:pell},
known from Theorems \ref{thm:pell-sol} and \ref{thm:pos-sol},
become, for \eqref{eqn:pell}, 
the solutions $\pm\alpha^n$, where $n\in\Z$,
and $\alpha$ is the least solution that exceeds $1$.

For our purposes, a \textbf{quadratic form} is a polynomial
\begin{equation}\label{eqn:quad}
  ax^2+bxy+cy^2,
\end{equation}
where the coefficients $a$, $b$, and $c$ are integers.
The Pell equation \eqref{eqn:pell} is just one example of an equation
\begin{equation}\label{eqn:f=m}
f(x,y)=m,
\end{equation}
where $f$ is a quadratic form.

\begin{example}\label{example:4xx}
  We solve the quadratic Diophantine equation
  \begin{equation}\label{eqn:qDe3}
    4x^2+2xy-y^2=4.
  \end{equation}
  We start by completing the square in $x$:
  \begin{multline*}
    4x^2+2xy
    =4\left(x^2+\frac{xy}2\right)
    =4\left(x^2+\frac{xy}2+\frac{y^2}{16}\right)-\frac{y^2}4y\\
    =4\left(x+\frac y4\right)^2-\frac{y^2}4.
  \end{multline*}
  Thus our equation becomes
  \begin{equation*}
    \left(2x+\frac y2\right)^2-5\left(\frac{y}2\right)^2=4
  \end{equation*}
  and then
  \begin{equation*}
    \left(2x+\frac{1+\surd 5}2y\right)
    \left(2x+\frac{1-\surd 5}2y\right)=4.
  \end{equation*}
  We let $d=5$, so that $K=\Q(\surd 5)$.
  We want then to solve
  \begin{equation}\label{eqn:norm=4}
    \norm{\xi}=4\And\xi\in\latt[2,\frac{1+\surd 5}2],
  \end{equation}
  which resembles \eqref{eqn:pell-norm}.
\end{example}

We shall develop a general method encompassing \eqref{eqn:pell-norm}
and \eqref{eqn:norm=4}.
Meanwhile, for the sake of solving \eqref{eqn:norm=4} in particular,
  we define
  \begin{equation*}
    \frac{1+\surd 5}2=\gr;
  \end{equation*}
  this is the so-called \textbf{Golden Ratio.}
It has an intimate connexion with the sequence $(\Fib n\colon n\in\upomega)$
of \defn{Fibonacci number}{s,}%
\index{$\Fib n$}
 given by 
 \begin{align*}
   \Fib 0&=0,&
\Fib 1&=1,&
\Fib {n+2}&=\Fib n+\Fib {n+1}.
 \end{align*}
We can continue the sequence backwards by writing the last rule as
\begin{equation*}
  \Fib{n-2}=\Fib n-\Fib {n-1}.
\end{equation*}
Some terms of the bi-directional sequence
are as in Table \ref{tab:Fib}.
\begin{table}
  \begin{equation*}
    \begin{array}{c|*{12}r}
           n&0&1&2&3&4&5&6& 7& 8& 9&10&11\\\hline
      \Fib n&0&1&1&2&3&5&8&13&21&34&55&89\\\hline
      \Fib{-n}&0&1&-1&2&-3&5&-8&13&-21&34&-55&89
    \end{array}
  \end{equation*}
  \caption{Terms of the Fibonacci sequence}
  \label{tab:Fib}
\end{table}
It will be useful later (page \pageref{Fib})
to note the following.

\begin{theorem}\label{thm:Fib}
  For all $n$ in $\Z$,
\begin{equation}\label{eqn:Fib}
  \gr^n=\Fib {n-1}+\Fib n\gr.
\end{equation}
\end{theorem}

\begin{proof}
Trivially~\eqref{eqn:Fib} holds when $n=1$.  
Also, since
  \begin{equation}\label{eqn:gr^2=1+gr}
    \gr^2=1+\gr,
  \end{equation}
we have
\begin{equation}\label{eqn:gr-mult}
  (x+y\gr)\gr=x\gr+y\gr^2=y+(x+y)\gr.
\end{equation}
Hence, if~\eqref{eqn:Fib} holds when $n=k$,
then
\begin{equation*}
  \gr^{k+1}
=(\Fib {k-1}+\Fib k\gr)\gr=\Fib k+(\Fib {k-1}+\Fib k)\gr=\Fib k+\Fib {k+1}\gr,
\end{equation*}
so \eqref{eqn:Fib} holds when $n=k+1$.  
Therefore it holds for all positive $n$.  
Moreover, since
\begin{equation*}
  \gr\inv=\gr-1,
\end{equation*}
we have
\begin{multline*}
  (x+y\gr)\gr\inv
=(x+y\gr)(\gr-1)\\
=-x+y\gr^2+(x-y)\gr
=y-x+x\gr,  
\end{multline*}
so that if \eqref{eqn:Fib} holds when $n=k$,
it holds when $n=k-1$.
\end{proof}

One can understand Theorem~\ref{thm:Fib} in terms of matrices.
By \eqref{eqn:gr-mult},
multiplication in $\latt[1,\gr]$ by $\gr$ corresponds,
under the map
\begin{equation*}
  x+y\gr\mapsto
\begin{pmatrix}
x\\y
  \end{pmatrix},
\end{equation*}
to the multiplication given by
\begin{equation*}
\begin{pmatrix}
  0&1\\1&1
\end{pmatrix}
\begin{pmatrix}
  x\\y
\end{pmatrix}
=
  \begin{pmatrix}
    y\\x+y
  \end{pmatrix}.
\end{equation*}
Inverting the square matrix, we have
\begin{equation*}
\begin{pmatrix}
  -1&1\\1&0
\end{pmatrix}
\begin{pmatrix}
  x\\y
\end{pmatrix}
=
  \begin{pmatrix}
    y-x\\x
  \end{pmatrix},
\end{equation*}
corresponding to multiplication by $\gr\inv$.

We generalize Example \ref{example:4xx}:
  
\begin{theorem}\label{thm:quad}
  If $f$ is the quadratic form in \eqref{eqn:quad},
  where $a\neq0$,
  and
  \begin{equation*}
    b^2-4ac=D,
  \end{equation*}
  where $D=s^2d$, and $d$ is a squarefree integer different from $1$,
  then the solutions to \eqref{eqn:f=m}
  correspond, under the map
  \begin{equation*}
    (x,y)\mapsto\alpha x+\beta y,
  \end{equation*}
  where
  \begin{align*}
    \alpha&=a,&\beta&=\frac{b+\surd D}2,
  \end{align*}
  to the solutions from $\Q(\surd d)$ of
  \begin{equation}\label{eqn:quad-gen}
    \norm{\xi}=am\And\xi\in\mLambda,
  \end{equation}
  where
  \begin{equation}\label{eqn:L}
    \mLambda=\latt.
  \end{equation}
\end{theorem}

\begin{proof}
We complete the square:
\begin{multline*}
  af(x,y)
  =\Bigl((ax)^2+b(ax)y+\frac{b^2y^2}{4}\Bigr)
  -\Bigl(\frac{b^2}{4}-ac\Bigr)y^2 \\
  =\Bigl(ax+\frac{by}{2}\Bigr)^2
  -\frac{Dy^2}{4}\\
=\Bigl(ax+\frac{b+\surd D}2\cdot y\Bigr)
\Bigl(ax+\frac{b-\surd D}2\cdot y\Bigr)\\
=(\alpha x+\beta y)(\alpha x+\beta'y)
=\norm{\alpha x+\beta y}.\qedhere
\end{multline*}
\end{proof}

In Example \ref{example:4xx},
had we strictly followed the method of Theorem \ref{thm:quad},
we should have arrived at the system
  \begin{equation*}%\label{eqn:norm=4}
    \norm{\xi}=16\And\xi\in\latt[4,1+1\surd 5].
  \end{equation*}
  By replacing $\xi$ here with $2\xi$,
  we obtain \eqref{eqn:norm=4}.


Suppose $\alpha$ is one solution of \eqref{eqn:quad-gen},
and some $\epsilon$ in $K$ is a solution of
\begin{equation}\label{eqn:new-form}
  \norm{\eta}=1\And\eta\mLambda\included\mLambda.
\end{equation}
Then $\epsilon^n\alpha$ is a solution of \eqref{eqn:quad-gen}
whenever $n\in\upomega$.
We shall see that the same is true, even when $n\in\Z$,
and moreover there is $\epsilon$ such that every solution is of the given form.

\chapter{Orders}

For some squarefree integer $d$,
we let $K$ is the field $\Q(\surd d)$,
and $\mLambda=\latt$ as in \eqref{eqn:L}
for some $\alpha$ and $\beta$ in $K$ satisfying \eqref{eqn:ab-ind}.
We now define
\begin{equation*}
  \{\eta\in K\colon\eta\mLambda\included\mLambda\}=\ord;
\end{equation*}
this is the \textbf{order} of $\mLambda$.
We can rewrite \eqref{eqn:new-form} as
\begin{equation}\label{eqn:N-ord}
  \norm{\eta}=1\And\eta\in\ord.
\end{equation}
We need to understand $\ord$.
We note first that $\ord$ is closed under addition,
subtraction, and multiplication;
this means it is a \textbf{ring}\label{ring2}
(as also on page \pageref{ring}).

\begin{theorem}\label{thm:conductor}
  $\ord=\latt[1,a\tau]$,
  where $\tau=\beta/\alpha$ and
  \begin{equation}\label{eqn:tau}
    a\tau^2+b\tau+c=0,
  \end{equation}
  where $a$, $b$, and $c$ are integers prime to one another.
\end{theorem}

\begin{proof}
We have first
\begin{align*}
  %&\phantom{{}\iff{}}
  \theta\in\ord
&\iff\theta\latt\included\latt\\
  &\iff\theta\alpha\in\latt\And\theta\beta\in\latt\\
  &\iff\theta\in\latt[1,\tau]\And\theta\tau\in\latt[1,\tau].
\end{align*}
Any element $\theta$ of $\latt[1,\tau]$ is $x+y\tau$
for some $x$ and $y$ in $\Z$, and then
\begin{align*}
  \theta\tau\in\latt[1,\tau]
&\iff x\tau+y\tau^2\in\latt[1,\tau]\\
&\iff y\tau^2\in\latt[1,\tau]\\
&\iff\frac{yb}a\tau+\frac{yc}a\in\latt[1,\tau]\\
&\iff a\divides{yb}\And a\divides{yc}\\
&\iff a\divides y.
\end{align*}
In short, $\theta\in\ord\iff\theta\in\latt[1,a\tau]$.
\end{proof}

\begin{corollary}
  $\ord$ is closed under $\xi\mapsto\xi'$,
  and therefore $\ord$ contains the inverse of its every element
  that has norm $1$.
  Also, the trace of every element of $\ord$ is an integer.
\end{corollary}

\begin{proof}
  We rewrite \eqref{eqn:tau} as
  \begin{equation}\label{eqn:at^2}
    (a\tau)^2+b(a\tau)+ac=0.
  \end{equation}
  For any element $\gamma$ of $K$, we have
  \begin{equation}\label{eqn:x-gamma}
(x-\gamma)(x-\gamma')=x^2-\tr{\gamma}x+\norm{\gamma}.
  \end{equation}
  In particular, $a\tau$ is a zero of the polynomial
  \begin{equation*}
    x^2-\tr{a\tau}x+\norm{a\tau}.
  \end{equation*}
  Comparison with \eqref{eqn:at^2} shows
  \begin{equation*}
    \tr{a\tau}=-b,
  \end{equation*}
  which is in $\ord$.  Since
  \begin{equation*}
    a\tau'=\tr{a\tau}-a\tau,
  \end{equation*}
this is in $\ord$.
\end{proof}

\begin{theorem}\label{thm:units}
  When $d>0$, then $\ord$ has an element whose integral powers
  are precisely the positive elements of $\ord$ having norm $1$.
\end{theorem}

\begin{proof}
  For some positive integer $c$,
  \begin{equation*}
    \latt[1,c\surd d]\included\ord.
  \end{equation*}
  If $\norm{a+bc\surd d}=1$ and $a+bc\surd d>1$,
  this means precisely that
  $(a,b)$ is a positive solution of the Pell equation
  \begin{equation*}
  x^2-dc^2y^2=1.  
  \end{equation*}
  Such a solution $(a,b)$ exists by Theorem \ref{thm:pos-sol}.
  Let
  \begin{equation*}
    a+bc\surd d=\epsilon.
  \end{equation*}
  Then $\epsilon\epsilon'=1$, so
  \begin{align*}
    \epsilon^2-\tr{\epsilon}\epsilon+1&=0,&
    0&<\epsilon\inv<1<\epsilon.
  \end{align*}
  Suppose $n$ is an integer exceeding $\epsilon$.
  Then
  \begin{equation*}
    1<\tr{\epsilon}=\epsilon+\epsilon'<n+1.
  \end{equation*}
  Since, finally, $\tr{\epsilon}$ is an integer,
  only finitely many elements of $\ord$ having norm $1$
  can exceed $1$, but not $\epsilon$.
  Let $\epsilon_{\mLambda}$ be the least of them.
  As in the proof of Theorem \ref{thm:pell-sol},
  for any positive element $\gamma$ of $\ord$,
  for some integer $n$,
  \begin{gather*}
    \epsilon_{\mLambda}{}^n\leq\gamma<\epsilon_{\mLambda}{}^{n+1},\\
    1\leq\gamma\epsilon_{\mLambda}{}^{-n}<\epsilon_{\mLambda}.
  \end{gather*}
  If $\norm{\gamma}=1$, then $\gamma=\epsilon_{\mLambda}{}^n$.
\end{proof}

We can now state a method for solving systems \eqref{eqn:quad-gen}
when $d>0$.
If $\gamma$ is a solution, then so are all
$\pm\gamma\epsilon_{\mLambda}{}^n$,
when $\epsilon_{\mLambda}$ is as in the proof of Theorem \ref{thm:units}.
Therefore we may assume
\begin{equation*}
  1\leq\gamma<\epsilon_{\mLambda}.
\end{equation*}
Say $\gamma=\alpha k+\beta\ell$.
Then $(k,\ell)$ satisfies
\begin{equation*}
  1\leq\alpha x+\beta y<\epsilon_{\mLambda},
\end{equation*}
that is, $(k,\ell)$ lies between the two straight lines given respectively by
\begin{align}\label{eqn:bounds}
  1&=\alpha x+\beta y,&
  \alpha x+\beta y&=\epsilon_{\mLambda}.
\end{align}
Moreover, from the proof of Theorem \ref{thm:quad},
$(k,\ell)$ lies on the hyperbola that can be given by
\begin{equation*}
am=  (\alpha x+\beta y)(\alpha x+\beta'y);
\end{equation*}
the asymptotes of this hyperbola are given respectively by
\begin{align*}
  0&=  \alpha x+\beta y,&
  0&=\alpha x+\beta'y.
\end{align*}
Thus the straight lines given in \eqref{eqn:bounds}
are parallel to the first asymptote
and cut off a segment of one branch of the hyperbola.
This segment lies in the parallelogram bounded by
the parallel lines given in \eqref{eqn:bounds},
by the second asymptote,
and by the line parallel to this given by
\begin{equation*}
am=\alpha x+\beta'y.  
\end{equation*}
We can see how this works in the following.

  
\begin{example}
  We continue with Example \ref{example:4xx}.
  In $\Q(\surd5)$, we want to solve
  \begin{equation}\label{eqn:Nx=4,x-in-L}
    \norm{\xi}=4\And\xi\in\mLambda,
  \end{equation}
  where
  \begin{equation*}
    \mLambda=\latt[2,\gr].
  \end{equation*}
  Thus we are looking for $2x+\gr y$,
  where $(x,y)$ lies on the hyperbola given by
  \begin{equation*}
    (2x+\gr y)(2x+\gr'y)=4,
  \end{equation*}
  shown in Figure \ref{fig:hyperbola}.
  \begin{figure}
    \centering
    \psset{unit=15mm}
    \begin{pspicture}(-2,-2)(2,2)
      %\psgrid[subgriddiv=1,griddots=4,gridlabels=0pt](0,0)(-1,-2)(5,9)
      \psaxes[labels=none](0,0)(-2,-2)(2,2)
      \parametricplot{-2}{2}{t neg 5 t dup mul mul 16 add sqrt add 4 div t}
      \parametricplot{-2}{2}{t neg 5 t dup mul mul 16 add sqrt sub 4 div t}
      \psline[linestyle=dashed](-0.5,2)(0.5,-2)
      \psline[linestyle=dotted](! 0.5 5 sqrt 1 add mul -2)(! -0.5 5 sqrt 1 add mul 2)
      \psline[linestyle=dotted](! 0.5 5 sqrt 1 sub mul 2)(! -0.5 5 sqrt 1 sub mul -2)
      \pspolygon[linestyle=dotted]
      (! 1 5 sqrt 0.2 mul add -0.8 5 sqrt mul)
      (! -1 5 sqrt -0.2 mul sub -0.8 5 sqrt mul)
      (! -1 5 sqrt -0.2 mul add 0.8 5 sqrt mul)
      (! 1 5 sqrt 0.2 mul sub 0.8 5 sqrt mul)
      \psdots(1,0)(1,2)(2,-2)(-1,0)(-1,-2)(-2,2)
    \end{pspicture}
    \caption{Hyperbola $(2x+\gr y)(2x+\gr'y)=4$
      %$(2x+\frac12y)^2-\frac54y^2=4$
    }\label{fig:hyperbola}
  \end{figure}
  Since $\ord$ is also the order of $\latt[1,\gr/2]$, and
  \begin{equation*}
    4\Bigl(\frac{\gr}2\Bigr)^2-2\cdot\frac{\gr}2-1=0,
  \end{equation*}
  we have by Theorem~\ref{thm:conductor}
  \begin{equation*}
    \ord=\latt[1,2\gr]=\latt[1,\surd 5].
  \end{equation*}
  We want elements of norm $1$,
  and these come from solutions of
  \begin{equation}\label{eqn:pell-5}
    x^2-5y^2=1,
  \end{equation}
  and these solutions come from convergents of $\surd5$
  (though we have not proved this).
  We compute
  \begin{gather*}
    \surd5=2+(\surd5-2),\\
    \frac1{\surd5-2}=\surd5+2=4+(\surd5-2),
  \end{gather*}
  so
  \begin{equation*}
    \surd5=[2;\overline4].
  \end{equation*}
  The first two convergents are $2$ and $9/4$.
  We have
  \begin{align*}
    2^2-5&=-1,&9^2-5\cdot4^2&=1.
  \end{align*}
  Thus $(9,4)$ is a positive solution of \eqref{eqn:pell-5},
  and we can check that there are no positive solutions
  with
  \begin{equation*}
    x+y\surd5<9+4\surd5.
  \end{equation*}
  It will be useful to note
  \begin{equation*}
    9+4\surd5=5+8\gr.
  \end{equation*}
  By Theorem \ref{thm:units},
  every element of $\ord$ of norm $1$ is $\pm(5+8\gr)^n$ for some $n$
  in $\Z$.
  This means, if $\gamma$ is a solution of \eqref{eqn:Nx=4,x-in-L},
  then so is $\pm(5+8\gr)^n\gamma$.
  We may thus assume
  \begin{equation*}
    1<\gamma<5+8\gr.
  \end{equation*}
  Let $\gamma=2k+\ell\gr$.  
  Then $(k,\ell)$ lies between the parallel lines given by
  \begin{align*}
    2x+y\gr&=1,& 2x+y\gr&=5+8\gr
  \end{align*}
  and the parallel lines given by
  \begin{align*}
    2x+y\gr'&=0,&2x+y\gr'&=4,
  \end{align*}
  shown in Figure~\ref{fig:parallelogram}.
  \begin{figure}
    \centering
    \psset{unit=13mm}
    \begin{pspicture}(-1,-2)(5,9)
      %\psgrid[subgriddiv=1,griddots=4,gridlabels=0pt](0,0)(-1,-2)(5,9)
      \psaxes[labels=none](0,0)(-1,-2)(5,9)
      \psline(-1,1.854)(2.118,-2)
      \psdots
      (1,0)(2,0)
      (1,1)(2,1)
      (1,2)(2,2)
      (1,3)(2,3)
      (2,4)(3,4)
      (2,5)(3,5)
      (2,6)(3,6)
      (3,7)
      \uput[ur](1,0){$4$}
      \uput[r](1,1){$5$}
      \uput[r](1,2){$4$}
      \uput[d](1,3){$1$}
      %\uput[dr](2,0){$16$}
      %\uput[u](2,1){$19$}
      %\uput[ur](2,2){$20$}
      \uput[r](2,3){$19$}
      \uput[r](2,4){$16$}
      \uput[r](2,5){$11$}
      \uput[r](2,6){$4$}
      %\uput[u](3,4){$44$}
      %\uput[ur](3,5){$41$}
      %\uput[ur](3,6){$36$}
      \uput[l](3,7){$29$}
      \parametricplot[linestyle=dashed]{-2}{9}{t -1 mul 5 t t mul mul 16 add
        sqrt add 4 div t} 
      \parametricplot[linestyle=dashed]{-2}{0}{t -1 mul 5 t t mul mul 16 add
        sqrt sub 4 div t} 
      \pcline(-0.618,-2)(2.781,9)
      \naput*[nrot=:U]{$2x+y\gr'=0$}
      \pcline(1.382,-2)(4.781,9)
      \nbput*[nrot=:U]{$2x+y\gr'=4$}
      \pcline(1.69,9)(5,4.910)
      \naput*[nrot=:U]{$2x+y\gr=5+8\gr\qquad$}
      \pcline(-1,1.236)(1.618,-2)
      \nbput*[nrot=:U]{$2x+y\gr=0$}
      \pcline(-1,1.854)(0.5,0)
      \naput*[nrot=:U]{$2x+y\gr=1$}
    \end{pspicture}
    \caption{Small solutions of $4x^2+2xy-y^2=4$}\label{fig:parallelogram}
  \end{figure}
  There are finitely many integer points in that parallelogram; for
  every such point $(x,y)$, we compute $\norm{2x+y\gr}$.  In fact, once
  we have computed the norms indicated in the figure, we can see that
  the only points for which the corresponding norm is $4$ are $(1,0)$,
  $(1,2)$, and $(2,6)$.  Therefore the solutions to~\eqref{eqn:qDe3} are
  those $(x,y)$ such that $2x+y\gr=\pm(5+8\gr)^n\gamma$, where $n\in\Z$
  and $\gamma\in\{2,2+2\gr,4+6\gr\}$.  
Moreover,
by Theorem \ref{thm:Fib},\label{Fib}
  \begin{equation*}
\{2,2+2\gr,4+6\gr\}=\{2\gr^0,2\gr^2,2\gr^4\}.  
\end{equation*}
Thus the solutions to \eqref{eqn:Nx=4,x-in-L} are $\pm2\gr^{2k}$,
where $k\in\Z$;
hence these solutions are
\begin{equation*}
\pm(2\Fib{2k-1}+2\Fib{2k}\gr).  
\end{equation*}
Under the correspondence $(x,y)\mapsto 2x+y\gr$ 
between solutions to~\eqref{eqn:qDe3} 
and solutions from $\latt[2,\gr]$ to \eqref{eqn:Nx=4,x-in-L},
the solutions of the former,
shown in Figure \ref{fig:qDe3},
\begin{figure}
  \centering
  \psset{unit=4.7mm}
  \begin{pspicture}(-5,-16)(13,16)
%\psgrid[subgriddiv=1,griddots=4,gridlabels=0pt](0,0)(-1,-2)(5,9)
\psaxes[labels=none](0,0)(-5,-16)(13,16)
\psdots(13,-16)(5,-6)(2,-2)( 1,0)( 1, 2)( 2, 6)( 5, 16)
\psdots        (-5,6)(-2,2)(-1,0)(-1,-2)(-2,-6)(-5,-16)
\parametricplot{-16}{16}{t neg 5 t dup mul mul 16 add
  sqrt add 4 div t}
\parametricplot{-16}{6}{t neg 5 t dup mul mul 16 add
  sqrt sub 4 div t}
\psset{linestyle=dotted}
\psline(-5,16)(5,16)(5,-6)(-2,-6)(-2,2)(1,2)(1,0)
(-1,0)(-1,-2)(2,-2)(2,6)(-5,6)(-5,-16)(13,-16)(13,16)
  \end{pspicture}
\caption{Solutions of $4x^2+2xy-y^2=4$}\label{fig:qDe3}

\end{figure}
are $(\pm\Fib{2k-1},\pm2\Fib{2k})$.
As suggested in the figure,
we can form these into a single bi-directional sequence.
Since
\begin{equation*}
\begin{pmatrix}
  0&1\\1&1
\end{pmatrix}^2
=
  \begin{pmatrix}
1&1\\1&2    
  \end{pmatrix},
\end{equation*}
the solutions to \eqref{eqn:qDe3} are
\begin{equation*}
\pm2  \begin{pmatrix}
1&1\\1&2        
\end{pmatrix}^n
\begin{pmatrix}
  1\\0
\end{pmatrix}.
\end{equation*}
\end{example}



\chapter{Integers}

We define yet another subset of $K$;
it will turn out to be an order that includes all others.
Meanwhile, the definition is
\begin{equation*}
  \{\xi\in K\colon\tr{\xi}\in\Z\And\norm{\xi}\in\Z\}=\roi.
\end{equation*}
The elements of $\roi$ are called the \textbf{integers} of $K$.
The elements of $\Z$ can henceforth be called \textbf{rational integers.}

\begin{example}
  $\latt[1,\surd d]\included\roi$;
  but when $d=5$, then $\gr\in\roi$.
\end{example}

\begin{theorem}\label{thm:roi-monic}
  The integers of $K$ are precisely the solutions in $K$
  of polynomial equations
  \begin{equation*}
    x^2+bx+c=0,
  \end{equation*}
  where $b$ and $c$ are rational integers.
\end{theorem}

\begin{proof}
  We need only look at \eqref{eqn:x-gamma}
  in the proof of the corollary of Theorem \ref{thm:conductor}.
\end{proof}

\begin{lemma}\label{lem:end-in-roi}
  For every lattice $\mLambda$ of $K$,
  \begin{equation*}
\ord\included\roi.
  \end{equation*}
\end{lemma}

\begin{proof}
  This also follows
  from the proof of the corollary of Theorem \ref{thm:conductor}.
\end{proof}

In order to characterize $\roi$ more precisely
than in the definition or Theorem \ref{thm:roi-monic},
we define\index{$\omega$ (generator of $\roi$ over $\Z$)}
  \begin{equation}\label{omega}
    \omega=
    \begin{cases}
      \surd d,& \text{ if }d\equiv 2 \text{ or }3\pmod 4;\\
\displaystyle\frac{1+\surd d}2,& \text{ if }d\equiv1\pmod 4.
    \end{cases}
  \end{equation}
  We continue to assume that $d$ is squarefree.
  In either case of \eqref{omega},
  \begin{equation}\label{eqn:d-in-w}
    \latt[1,\surd d]\included\latt[1,\omega].
  \end{equation}
  
\begin{theorem}\label{thm:roi}
  $\roi=\latt[1,\omega]$,
  and this is closed under multiplication.
\end{theorem}

\begin{proof}
Let $\alpha$ be an element $a+b\surd d$ of $K$,
so that $\alpha$ is a zero of the polynomial
\begin{equation}\label{eqn:x}
  x^2-2ax+a^2-b^2d.
\end{equation}
Suppose first $\alpha\in\roi$.  
Then $2a$ and $a^2-b^2d$ are in $\Z$ by Theorem \ref{thm:roi-monic}.
There are two cases.
\begin{compactenum}
  \item
If $2a$ is even, then $a\in\Z$, so $b^2d\in\Z$,
and hence $b\in\Z$ since $d$ is \sqf;
consequently $\alpha\in\Z[\surd d]$,
and so $\alpha\in\latt[1,\omega]$ by \eqref{eqn:d-in-w}.
\item
Suppose $2a$ is odd.
\emph{Modulo} $4$ we have $4a^2\equiv(2a)^2\equiv1$.  
But also $4a^2-4b^2d\equiv0$, so that
$(2b)^2d\equiv4b^2d\equiv4a^2\equiv1$.  
Since $2b\in\Z$, again because $d$ is \sqf,
we have $(2b)^2$ congruent to $0$ or $1$,
and therefore $(2b)^2\equiv1$. 
We conclude both that $2b$ is odd and that $d\equiv1$.
Again we obtain $\alpha\in\latt[1,\omega]$.
\end{compactenum}
Suppose conversely $\alpha\in\latt[1,\omega]$.
\emph{Modulo} $4$,
if $d$ is not congruent to $1$,
then $a$ and $b$ are rational integers,
so the polynomial in \eqref{eqn:x} is over $\Z$,
and thus $\alpha\in\roi$.
If $d$ \emph{is} congruent to $1$,
then both $2a$ and $2b$ must be integers,
and moreover $2a\equiv2b\pmod2$,
so that
\begin{equation*}
  4(a^2-b^2d)\equiv(2a)^2-(2b)^2\equiv0\pmod4,
\end{equation*}
and again the polynomial in \eqref{eqn:x} is over $\Z$.

Finally, in case $d\equiv1$ \emph{modulo} $4$,
so that $d=4k+1$ for some integer $k$, we have
\begin{equation*}
  \omega^2=\frac{1+2\surd d+d}4=\frac{2k+1+\surd d}2=k+\omega,
\end{equation*}
which is in $\roi$.
\end{proof}

The invertible elements of a ring are called its \textbf{units.}
Then the invertible elements of $\roi$
(and therefore also of every $\ord$,
by the corollary of Theorem \ref{thm:conductor})
are just the elements having norm $\pm1$.


%\bibliographystyle{plain}
%\bibliography{../../../references}

\begin{thebibliography}{1}

\bibitem{MR0159773}
Richard Dedekind.
\newblock {\em Essays on the Theory of Numbers. {I}: {C}ontinuity and
  Irrational Numbers. {II}: {T}he Nature and Meaning of Numbers}.
\newblock Dover Publications, New York, 1963.
\newblock Authorized 1901 translation by Wooster Woodruff Beman of ``Stetigkeit
  und irrationale Zahlen'' and ``Was sind und was sollen die Zahlen'' (second
  edition, 1893; first, 1887).

\bibitem{Descartes-Geometry}
Ren{\'e} Descartes.
\newblock {\em The Geometry of {R}en{\'e} {D}escartes}.
\newblock Dover Publications, New York, 1954.
\newblock Translated from the French and Latin by David Eugene Smith and Marcia
  L. Latham, with a facsimile of the first edition of 1637.

\bibitem{MR0116216}
David Hilbert.
\newblock {\em The Foundations of Geometry}.
\newblock Authorized translation by E. J. Townsend. Reprint edition. The Open
  Court Publishing Co., La Salle, Ill., 1959.
\newblock Based on lectures 1898--99. Translation copyrighted 1902. Project
  Gutenberg edition released December 23, 2005 (\url{www.gutenberg.net}).

\bibitem{Mazur-Th-pub}
Barry Mazur.
\newblock How did {T}heaetetus prove his theorem?
\newblock In P.~Kalkavage and E.~Salem, editors, {\em The Envisioned Life:
  {E}ssays in honor of {E}va {B}rann}. Paul Dry Books, 2007.
\newblock \url{www.math.harvard.edu/~mazur/preprints/Eva.pdf}, accessed
  September 20, 2012.

\bibitem{MR2204484}
David Pengelley and Fred Richman.
\newblock Did {E}uclid need the {E}uclidean algorithm to prove unique
  factorization?
\newblock {\em Amer. Math. Monthly}, 113(3):196--205, 2006.

\bibitem{Pierce-Thales-9}
David Pierce.
\newblock Thales and the nine-point conic.
\newblock {\em The De Morgan Gazette}, 8(4):27--78, 2016.
\newblock \url{education.lms.ac.uk/2016/12/thales-and-the-nine-point-conic/},
  accessed June 1, 2017.

\end{thebibliography}


\end{document}

