\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{amsmath,amssymb,amsthm}
%\allowdisplaybreaks
\usepackage{verbatim}  % allows a comment environment:

\usepackage{relsize}
\usepackage{rotating}
\usepackage{url}
\usepackage[all]{xy}
\usepackage{pstricks,pst-node}
\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{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\setminus}{\smallsetminus}
%\renewcommand{\phi}{\varphi}

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

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

\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{\ord}[2]{\operatorname{ord}_{#1}(#2)}

\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]{\langle#1\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{\rft}{\sqrt{14}}
%\newcommand{\rtt}{\sqrt{13}}

\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{Elementary Number Theory II}
\author{David Pierce}
\date{Spring 2008\\
Edited January 5, 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/}}
  \maketitle
  \thispagestyle{empty}
  
\mypreface

These are notes from Elementary Number Theory~II 
(Math 366) in the Mathematics Department
of Middle East Technical University, Ankara, 
spring semester, 2007-8.
The catalogue description was,
\begin{quote}\relscale{0.9}
  Arithmetic in Quadratic fields.
  Factorization theory, Continued fractions, Periodicity.
  Transcendental numbers. 
\end{quote}
Class met Tuesdays at
13:40 for two hours
and Fridays at 13:40 (originally 12:40) for one hour.
I typeset the notes after class, 
relying on memory and
the handwritten notes that I had prepared before class.  
I did some polishing, correcting, and rearrangement.
Now, ten years later, I have done some more.

The main published reference for the course was
Adams and Goldstein \cite{MR0476613}, 
which had apparently been on reserve in the library 
since the last time the course had offered, several years earlier.  
I had that text only in the form of a photocopy of chapters 6--11, 
used by Ay\c se Berkman when she was a student.  
The text was a rough guide only.

Special symbols used in these notes are found at the head of the
index.

For continued fractions, the Burton text \cite{Burton} used for
Math 365 is useful, as are Hardy and Wright \cite{MR568909} 
and Shockley \cite{MR0210649}.  I
also consulted
Everest and Ward \cite{MR2135478},
Landau \cite{MR0092794}, 
and occasionally other works. 

Class was cancelled Friday, February 29, 2008 because I was in Istanbul
for my \emph{do\c centlik} exam.  Ay\c se taught for me on the
following Tuesday, since I was sick with a gastro-intestinal infection
from the trip.  I was sick again, with the flu, on May 13 and 16;
class was cancelled. 

There were examinations on the Mondays March 24, April 28, and May 26,
so there were no lectures covering new material on the previous Fridays.

Class on Tuesday, April 8, was only one hour, because of a special
seminar that day (on teaching conic sections). 

The chapter for April 22 is a reworking of what I presented vaguely
and incorrectly in class.  Theorem~\ref{thm:ultimate} was not given at
all in class.

The notes were formatted originally for A4 paper;
I have now changed over to A5,
which allows whole pages---even two pages, side by side---%
to be read in a computer screen.

I have also edited the mathematical presentation.
I have added the overview on page \pageref{overview},
the summary on page \pageref{summary},
and just after this, Theorem \ref{thm:all-cond},
which can now be appealed to in Problem \ref{prob:qDe2}.

I had originally used both $\N$ and $\upomega$ 
for the set $\{0,1,2,\dots\}$ of natural numbers;
now only $\upomega$ is used.
I have decided that,
if one wants a symbol for the set $\{1,2,3,\dots\}$
of counting numbers, this is where $\N$ should be used.

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

\conventions

\begin{itemize}
\item 
In the Pell equation $x^2-dy^2=1$ 
(namely \eqref{eqn:pell}, page \pageref{eqn:pell}),
$d$ is a positive non-square (pages \pageref{d-nsq} and \pageref{d-nsq-2}).
\item
$K$ is a quadratic field (page \pageref{K}).
\item
$K$ is more precisely the field $\Q(\sqrt d)$,
where $d$ is now a \sqf{} integer, possibly negative, 
different from $1$ (page \pageref{d}).
\item
$(a+b\sqrt d)'=a-b\sqrt d$ in $K$ (\eqref{eqn:prime}, page \pageref{eqn:prime}).
\item
$\norm{\alpha}=\alpha\alpha'$ (\eqref{eqn:norm}, page \pageref{eqn:norm}).
\item
$\roi$ is the set of integers of $K$ (page \pageref{roi}).
\item
  \begin{math}
    \omega=
\left\{
    \begin{array}{ll}
      \sqrt d,& \text{ if }d\equiv 2 \text{ or }3\pmod 4\\
\displaystyle\frac{1+\sqrt d}2,& \text{ if }d\equiv1\pmod 4
    \end{array}
  \right\}
\end{math} (page \pageref{omega}).
\item
$\roi$ is the ring $\Z[\omega]$ by Theorem \ref{thm:roi} 
(page \pageref{thm:roi}).
\item
$\alpha$ and $\beta$ are elements of $K$ (page \pageref{ab}).
\item
$\Disc$ is the discriminant of a quadratic form
(pages \pageref{Disc}--\pageref{last-Disc}),
either 
\begin{itemize}[$*$]
\item 
$b^2-4ac$ when the form is $ax^2+bxy+cy^2$ 
(\eqref{eqn:abc}, page \pageref{eqn:abc})),
or 
\item
\begin{math}
\begin{vmatrix}
  \alpha&\alpha'\\\beta&\beta'
\end{vmatrix}^2
\end{math}
when the form is $\norm{\alpha x+\beta y}$ 
(\eqref{eqn:D-as-det}, \pageref{eqn:D-as-det}).
\end{itemize}
\item
$\mLambda$ is the lattice $\Z\alpha\oplus\Z\beta$ (page \pageref{Lambda}).
\item
$\End$ is the ring of endomorphisms of $\mLambda$ (page \pageref{End}).
\item
$\disc{\mLambda}$ is the discriminant
\begin{math}
\begin{vmatrix}
  \alpha&\alpha'\\\beta&\beta'
\end{vmatrix}^2
\end{math}
of $\mLambda$ (\eqref{eqn:disc} 
and pages \pageref{eqn:disc}--\pageref{last-disc}).
\item
$\ord$ is $\End$ (page \pageref{ord}).
\item
$\ord=\latt[1,c\omega]$ for some $c$ 
(Theorem \ref{thm:cond}, page \pageref{thm:cond}), 
the conductor of $\ord$.
\item
We may assume $\mLambda$ is the lattice $\latt[1,\tau]$,
where $\tau=\beta/\alpha$ and also $a\tau^2=-b\tau-c$
for some rational integers $a$, $b$, and $c$ with no common nontrivial factor
(page \pageref{tau}).
\item
$\funit$ is the fundamental unit of $\ord$ (page \pageref{funit}).
\end{itemize}

\myweek

\myday{February 19, 2008 (Tuesday)}

\topic{Diophantine equations}\label{overview}

We shall be solving some \defn{Diophantine equation}{s,} that is, 
polynomial equations in which all constants and variables are integers.
\begin{compactitem}
\item
The solution of the Fermat equation
$x^4+y^4=z^4$ or \eqref{eqn:Fermat} in Problem \ref{prob:Fermat}
is that there is no solution.
\item
A solution of \eqref{eqn:Fermat}
\emph{would} provide a solution of the Pytha\-gorean equation
$x^2+y^2=z^2$ or \eqref{eqn:Pyth} in Problem \ref{prob:Pyth}.
\item
Restricting ourselves to two variables,
we solve the equations of the form
$x^2+y^2=n$ or \eqref{eqn:n} in Problem \ref{prob:n}.
\end{compactitem}
As illustrations of a general method,
we give solutions of
\begin{compactitem}
\item
$x^2-14y^2=1$ or \eqref{eqn:14} in Problem \ref{prob:14} 
(page \pageref{prob:14});
\item
$x^2+xy+y^2=3$ or \eqref{eqn:qDe1} in Problem \ref{prob:qDe1} 
(page \pageref{prob:qDe1});
\item
$4x^2+2xy+y^2=7$ or \eqref{eqn:qDe2} in Problem \ref{prob:qDe2} 
(page \pageref{prob:qDe2});
\item
$4x^2+2xy-y^2=4$ or \eqref{eqn:qDe3} in Problem \ref{prob:qDe3} 
(page \pageref{prob:qDe3}).
\end{compactitem}
The method will involve passing to \tech{quadratic extension}s
of the field $\Q$ of rational numbers.

\topic{Pythagorean triples}

\begin{problem}\label{prob:Pyth}
  Solve (that is, find all solutions of)
  \begin{equation}\label{eqn:Pyth}
    x^2+y^2=z^2,
  \end{equation}
\end{problem}

\begin{solution}
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; 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)$.
\end{solution}

\topic{Infinite descent}

\begin{problem}\label{prob:Fermat}
  Solve
  \begin{equation}\label{eqn:Fermat}
    x^4+y^4=z^4.
  \end{equation}
\end{problem}

\begin{solution}
  Let $(a,b,c)$ be a solution, where $a,b,c>0$, and $\gcd(a,b,c)=1$.
  Then $(a^2,b^2,c^2)$ is a primitive \defn{Pythagorean triple},
  that is, a solution to~\eqref{eqn:Pyth}.  We may assume $a$ is even,
  and so
	\begin{align*}
    a^2&=2mn,& b^2&=n^2-m^2,& c^2&=n^2+m^2
	\end{align*}
	for some positive $m$ and $n$.
In particular,
\begin{equation*}
  m^2+b^2=n^2.
\end{equation*}
Since $\gcd(a,b)=1$, and every prime factor of $m$ divides $a$, we
have $\gcd(m,b)=1$.  Hence $(m,b,n)$ is a primitive Pythagorean
triple.  Also $m$ is even, since $b$ is odd.  Hence
\begin{align*}
  m&=2de,& b&=e^2-d^2,& n&=e^2+d^2	
\end{align*}
for some $d$ and $e$.  Then
\begin{equation*}
  a^2=2mn=4de(e^2+d^2).
\end{equation*}
But $\gcd(d,e)=1$, so $e^2+d^2$ is prime to both $d$ and $e$.
Therefore each of $d$, $e$, and $e^2+d^2$ must be square: say
\begin{align*}
  d&=r^2,& e&=s^2,& e^2+d^2&=t^2.	
\end{align*}
This gives $t^2=e^2+d^2=s^4+r^4$; that is, $(s,r,t)$ is a solution to
\begin{equation}\label{eqn:F2}
  x^4+y^4=z^2.
\end{equation}
But $(a,b,c^2)$ is also a solution to this; moreover,
\begin{equation*}
  1\leq\size t\leq t^2=e^2+d^2=n\leq n^2<n^2+m^2=c^2.
\end{equation*}
We never used that $c^2$ is a square.  Thus, for every solution
to~\eqref{eqn:F2} with positive entries, there is a solution with
positive entries in which the third entry is smaller.  This is absurd;
therefore there is no such solution to~\eqref{eqn:F2}, or
to~\eqref{eqn:Fermat}. 
\end{solution}

We used here Fermat's method of \defn{infinite descent}. 

In Elementary Number Theory I, we proved that the Diophantine equation
\begin{equation*}
  x^2+y^2+z^2+w^2=n
\end{equation*}
is soluble for every positive integer $n$.

\begin{problem}\label{prob:n}
  Find those $n$ for which
  \begin{equation}\label{eqn:n}
    x^2+y^2=n
  \end{equation}
is soluble.
\end{problem}

\begin{solution}
  Let $S$ be the set of such $n$.  Since%
\label{mi}\index{$\mi$ (not the variable $i$, but $\sqrt{{-1}}$)}
  \begin{align*}
    (a^2+b^2)(c^2+d^2)
&=\size{a+b\mi}^2\size{c+d\mi}^2\\
&=\size{(a+b\mi)(c+d\mi)}^2\\
&=\size{(ac-bd)+(ad+bc)\mi}^2\\
&=(ac-bd)^2+(ad+bd)^2,
  \end{align*}
$S$ is closed under multiplication.  We ask now:  Which primes are in
  $S$?

All squares are congruent to $0$ or $1$ \emph{modulo} $4$.  Hence elements of
$S$ are congruent to $0$, $1$, or $2$ \emph{modulo} $4$.  Therefore
$S$ contains no primes that are congruent to $3 \pmod 4$.
However, $S$ does contain $2$, since $2=1^2+1^2$.

Suppose conversely $p\equiv1\pmod 4$.
We shall show $p\in S$.
We have that $-1$ is a quadratic residue
\emph{modulo} $p$, so
\begin{equation*}
  -1\equiv a^2\pmod p
\end{equation*}
for some $a$, where we may assume $\size a<p/2$.  Hence
\begin{equation*}
  a^2+1=tp
\end{equation*}
for some positive $t$.  In particular, $tp\in S$.  
Also,
\begin{equation*}
  0<t=\frac{a^2+1}p<\frac{(p/2)^2+1}p=\frac p4+\frac 1p<p.
\end{equation*}
Thus,
letting $k$ be simply the least positive $t$ such that $tp\in S$,
we have $0<k<p$.  
By definition,
\begin{equation}\label{eqn:kp}
  kp=b^2+c^2
\end{equation}
for some $b$ and $c$.  There are $d$ and $e$ such that
\begin{align*}
  d&\equiv b\And e\equiv c\pmod k,& \size d,\size e&\leq \frac k2.	
\end{align*}
Then 
$d^2+e^2\equiv b^2+c^2\equiv0\pmod k$, so
\begin{equation}
\label{eqn:km}
d^2+e^2=km
\end{equation}
for some $m$, where
\begin{equation*}
  0\leq m=\frac{d^2+e^2}k\leq\frac{2(k/2)^2}k=\frac k2<k.
\end{equation*}
But multiply~\eqref{eqn:kp} and~\eqref{eqn:km}, getting
\begin{equation*}
  k^2mp
=(b^2+c^2)(d^2+e^2)
=(bd+ce)^2+(be-cd)^2.
\end{equation*}
We can divide by $k^2$, since
\begin{equation*}
  bd+ce\equiv b^2+c^2\equiv0\And
be-cd\equiv bc-cb\equiv 0\pmod k.
\end{equation*}
Thus we obtain
\begin{equation*}
  mp=\left(\frac{bd+ce}k\right)^2+\left(\frac{be-cd}k\right)^2.
\end{equation*}
This implies $mp\in S$.  By minimality of $k$, we have $m=0$.
Therefore $d^2+e^2=0$, so $d=0=e$.  Then $b,c\equiv 0\pmod k$, so
\begin{equation*}
  k^2\divides kp,
\end{equation*}
and therefore $k\divides p$.  This means $k=1$, so $p\in S$.

Finally, suppose $n\in S$ and $p\divides n$.  Then $n=a^2+b^2$ for
some $a$ and $b$, so
\begin{equation*}
  a^2+b^2\equiv 0\pmod p.
\end{equation*}
If $p\divides a$, then $p\divides b$, so $p^2\divides n$, which means
$n$ is not \sqf{}.  If $p\ndivides a$, then $a$ is invertible
\emph{modulo} $p$, so $1+(b/a)^2\equiv0\pmod p$, which means $-1$ is a
quadratic residue \emph{modulo} $p$, and so $p=2$ or else
$p\equiv1\pmod 4$. 

The conclusion is that $S$ contains just those numbers of the form
$n^2m$, where $m$ is \sqf{} and has no prime factors congruent to
$3$ \emph{modulo} $4$.
\end{solution}

We shall develop an alternative solution by means of 
Theorem \ref{thm:G-primes} on page \pageref{thm:G-primes}.
This will let us count the solutions of \eqref{eqn:n}
as in Theorem \ref{thm:count},
and \emph{this} will give us the series for $\uppi$ in Theorem \ref{thm:pi}.

\myday{February 22, 2008 (Friday)}

\topic{Rational points of the circle}

Solving~\eqref{eqn:Pyth} in integers is related to
integrals like
\begin{equation*}
\int\frac{\dee\theta}{2+3\sin\theta},
\end{equation*}
which one can solve by the substitution
\begin{align*}
	t&=\tan\frac{\theta}2,&
	\dee t=\frac12\sec^2\frac{\theta}2\dee\theta,
\end{align*}
so that
\begin{align*}
	\sin\theta&=\frac{2t}{1+t^2},&
	\cos\theta&=\frac{1-t^2}{1+t^2},&
	\dee\theta&=\frac{2\dee t}{1+t^2}.
\end{align*}
Concerning \eqref{eqn:Pyth}, we have
\begin{equation*}
  x^2+y^2=z^2\iff \left(\frac xz\right)^2+\left(\frac
  yz\right)^2=1\lor x=y=z=0.
\end{equation*}
So finding Pythagorean triples corresponds to solving
\begin{equation*}
  x^2+y^2=1
\end{equation*}
in \emph{rationals.}  To do so, since the equation defines the unit
circle, consider also the line through $(-1,0)$ with slope $t$, 
\begin{figure}[ht]
\centering
\psset{unit=20mm}
    \begin{pspicture}*(-2.5,-0.6)(2.5,2.5)
      \pscircle(0,0){2}
      \psline{->}(-2.5,0)(2.5,0)
      \psline{->}(0,-2.5)(0,2.5)
      \psline(-2.5,-0.25)(2.5,2.25)
      \psdots(-2,0)(0,1)(1.2,1.6)(1.2,0)(0,1.6)
			\psset{linestyle=dotted}
			\psline(1.2,0)(1.2,1.6)(0,1.6)
      \uput[dr](0,1){$t=\displaystyle\frac y{x+1}$}
      \uput[ul](-2,0){$-1$}
			\uput[d](1.2,0){$x=\displaystyle\frac{1-t^2}{1+t^2}$}
			\uput[l](0,1.6){$y=\displaystyle\frac{2t}{1+t^2}$}
      \uput[dl](2.5,0){$X$}
      \uput[dl](0,2.5){$Y$}
%      \uput[u](1.2,1.6){$(x,y)$}
    \end{pspicture}
\caption{Rational points of the circle}\label{fig:circle}
\end{figure}
so
that its $Y$-intercept is also $t$, as in Figure~\ref{fig:circle}:
this line is given by 
\begin{equation}\label{eqn:Pyth-line}
  y=tx+t.
\end{equation}
The circle and the line meet at $(-1,0)$ and also $(x,y)$, where
\begin{gather*}
  x^2+(tx+t)^2=1,\\
(1+t^2)x^2+2t^2x+t^2-1=0,\\
x^2+\frac{2t^2}{1+t^2}\cdot x-\frac{1-t^2}{1+t^2}=0.
\end{gather*}
The constant term in the left member of the last equation is the
product of the roots; one of the roots is $-1$; so we get
\begin{equation*}
  (x,y)=\left(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2}\right).
\end{equation*}
If $t$ is rational, then so are the coordinates of this point, which
is therefore a \defn{rational point}{} of the circle.  Conversely, if
$x$ and $y$ are rational, then so is $t$, by~\eqref{eqn:Pyth-line}.
Hence the function
\begin{equation*}
  t\mapsto\left(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2}\right)
\end{equation*}
is a one-to-one correspondence, with inverse 
\begin{equation*}
(x,y)\mapsto\frac y{x+1},
\end{equation*}
between $\Q$\index{$\Q$ (the field of rational numbers)} 
and the set of rational points,
other than $(-1,0)$,
of the unit circle.

Hence we can conclude that every integral solution of~\eqref{eqn:Pyth}
is a multiple of
\begin{equation*}
  (1-t^2,2t,1+t^2).
\end{equation*}
Taking $t=m/n$ and multiplying by $n^2$, we get
\begin{equation*}
  (n^2-m^2,2mn,n^2+m^2),
\end{equation*}
the solution we found before.


\topic{Continued fractions}
We can convert $\sqrt 2$ into a \tech{continued fraction}{} as
follows.
First
\begin{equation*}
\sqrt2=1+(\sqrt 2-1)=1+\cfrac1{\left(\cfrac1{\sqrt2-1}\right)}
=1+\frac1{\sqrt2+1}.
\end{equation*}
Note that $0<\sqrt2-1<1$.
We now have
\begin{equation*}
\sqrt2+1=2+\frac1{\sqrt2+1},
\end{equation*}
so we can substitute repeatedly:
\begin{equation*}
\sqrt2
=1+\frac1{\sqrt2+1}
=1+\cfrac1{2+\cfrac1{\sqrt2+1}}
=1+\cfrac1{2+\cfrac1{2+\cfrac1{\sqrt2+1}}}
\end{equation*}
and so on.
In the general procedure, given a real number $x$,
we first write
\begin{equation*}
x=a_0+\xi_0,
\end{equation*}
where
\begin{align}\label{eqn:a_0}
a_0&=[x], & \xi_0&=x-a_0,
\end{align}
square brackets denoting the
greatest-integer function.  Now
\begin{equation*}
\xi_0=\cfrac1{\left(\cfrac1{\xi_0}\right)}=\frac1{a_1+\xi_1},
\end{equation*}
\begin{align}
a_1&=\left[\frac1{\xi_0}\right],& \xi_1&=\frac1{\xi_0}-a_1.
\end{align}
We continue recursively, letting
\begin{align}\label{eqn:a_n}
a_n&=\left[\frac1{\xi_{n-1}}\right],\quad& \xi_n&=\frac1{\xi_{n-1}}-a_n,
\end{align}
where $\xi_{n-1}$ must be non-zero for $a_n$ to be defined.
Then
\begin{equation*}
  x=a_0+\xi_0=a_0+\cfrac1{a_1+\xi_1}
	=a_0+\cfrac1{a_1+\cfrac1{a_2+\xi_2}}
\end{equation*}
and so on.
We thus obtain \defn{continued fraction}s for $x$.  
For example, when $x=\sqrt 3$, we get
\begin{align*}
             &                  &a_0&=1,&\xi_0&=\sqrt 3-1,\\
\frac1{\xi_0}&=\frac{\sqrt3+1}2,&a_1&=1,&\xi_1&=\frac{\sqrt 3-1}2,\\
\frac1{\xi_1}&=\sqrt 3+1,       &a_2&=2,&\xi_2&=\sqrt 3-1,
\end{align*}
and now the process repeats:
\begin{multline*}
  \xi_n=
  \begin{cases}
    \sqrt 3-1,&\text{ if $n$ is even};\\
    \displaystyle\frac{\sqrt 3-1}2,&\text{ if $n$ is odd};\\
  \end{cases}\\
a_n=
\begin{cases}
  1,&\text{ if $n=0$, or $n$ is odd};\\
  2,&\text{ if $n$ is positive and even.}
\end{cases}
\end{multline*}
It appears that
\begin{equation}\label{eqn:rt3}
  \sqrt3=1+\cfrac1{1+\cfrac1{2+\cfrac1{1+\cfrac1{2+\cfrac1{\ddots}}}}}.
\end{equation}
If this has any meaning though,
it should be that $\sqrt3$ is the \tech{limit},
in the sense of calculus, of the sequence
\begin{align*}
&1,&
&1+\frac11,&
&1+\cfrac1{1+\cfrac12},&
&1+\cfrac1{1+\cfrac1{2+\cfrac11}},&
&\dots
\end{align*}
We introduce some notation for the terms of this sequence.
Here square brackets do
\emph{not} denote the greatest-integer function:
\begin{align*}
	  [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}
Here we must have $a_n\neq0$ when $n>0$; 
we shall assume also $a_n>0$ when $n>0$.  
We can also use the notation in the infinite case.  
For example, from $\sqrt3$, 
we have obtained $[1;1,2,1,2,\dots]$, 
which we can write as
\begin{equation*}
  [1;\overline{1,2}].
\end{equation*}
We have not yet proved that this is the limit of the sequence
\begin{align*}
	&[1],&
	&[1;1],&
	&[1;1,2],&
	&[1;1,2,1],&
	&[1;1,2,1,2],&
	&\dots.
\end{align*}

\myweek

\myday{February 26, 2008 (Tuesday)}

\topic{Euclidean algorithm}

Obtaining the sequences $(a_n\colon n\in\upomega)$%
\index{$\upomega$}
and
$(\xi_n\colon n\in\upomega)$ from $x$ as above corresponds to applying the
\defn{Euclidean algorithm}.\label{EucAlg}  
With this algorithm, 
we find the greatest common divisor of $155$ and $42$ by computing
\begin{align*}
  155&=42\cdot3+29,\\ 
   42&=29\cdot1+13,\\
   29&=13\cdot2+3,\\
   13&=3\cdot4+1.
\end{align*}
Since $1\divides3$, we have $\gcd(155,42)=1$,
We are now interested in the sequence $(3,1,2,4,3)$ of multipliers,
which is a sequence of greatest integers in fractions,
obtained as follows.
\begin{align*}
  \left[\frac{155}{42}\right]&=3,\quad&  \frac{155}{42}-3&=\frac{29}{42},\\
  \left[\frac{42}{29}\right]&=1,&  \frac{42}{29}-1&=\frac{13}{29},\\
  \left[\frac{29}{13}\right]&=2,&  \frac{29}{13}-2&=\frac3{13},\\
  \left[\frac{13}3\right]&=4,& \frac{13}3-4&=\frac13,
\end{align*}
and finally $[3/1]=[3]=3$.
In short, the sequence $(3,1,2,4,3)$
is the sequence of $a_n$ as defined earlier,
when $x=155/42$.
Moreover,
\begin{equation*}
  \frac{155}{42}=3+\cfrac1{1+\cfrac1{2+\cfrac1{4+\cfrac1{3}}}}.
\end{equation*}
In the same way,
we can write every fraction as a (finite) \defn{continued fraction}{}
$[a_0;a_1,\dots,a_n]$, where the $a_k$ are integers, and all of them
are positive except perhaps $a_0$.  Such a continued fraction is
called \defn{simple}.  We shall work only with simple continued
fractions.  But the continued fraction obtained for
irrational $x$ does not terminate.

The $k$th \defn{convergent}{} of $[a_0;a_1,\dots]$ is
$[a_0;a_1,\dots,a_k]$.  For example, 
by a tedious computation to be made easier in a moment,
the convergents of
$[1;\overline{1,2}]$ are
\begin{equation*}
  1,\quad 2,\quad \frac53,\quad \frac74,\quad \frac{19}{11},\quad
  \frac{26}{15},\quad \frac{71}{41},\quad \frac{97}{56},\quad \dots 
\end{equation*}
How are these convergents as approximations of $\sqrt 3$?  
We check a few of them:\label{rt3} 
\begin{align*}
  \left(\frac53\right)^2      &=\frac{25}9,       &25-3\cdot9     &=-2,\\
  \left(\frac74\right)^2      &=\frac{49}{16},    &49-3\cdot16    &=1,\\
  \left(\frac{19}{11}\right)^2&=\frac{361}{121},  &361-3\cdot121  &=-2,\\
  \left(\frac{26}{15}\right)^2&=\frac{676}{225},  &676-3\cdot225  &=1,\\
  \left(\frac{71}{41}\right)^2&=\frac{5041}{1681},&5041-3\cdot1681&=-2.
\end{align*}
If the pattern of differences continues,
and the denominators of the convergents grow without bound,
then indeed the convergents converge to $\sqrt3$.

In general, we shall write
the $k$th convergent of $[a_0;a_1,\dots]$ as $p_k/q_k$.
However, this does not define $p_k$ and $q_k$ separately,
unless we require them to be positive and prime to one another.
We shall take a different route;
$p_k$ and $q_k$ will be prime to one another,
but not by definition.
Since we want $p_0/q_0=a_0$, we just define
\begin{align}\label{eqn:p_0}
  p_0&=a_0,&q_0&=1.
\end{align}
Since we want
$p_1/q_1=[a_0;a_1]$, and now
\begin{equation*}
  [a_0;a_1]=a_0+\frac1{a_1}=\frac{a_0a_1+1}{a_1}
=\frac{p_0a_1+1}{a_1},
\end{equation*}
we define
\begin{align}\label{eqn:p_1}
  p_1&=p_0a_1+1,  &q_1&=a_1.
\end{align}
We want $p_2/q_1=[a_0;a_1,a_2]$, and now
\begin{equation*}
[a_0;a_1,a_2]
=  a_0+\cfrac1{a_1+\cfrac1{a_2}}
=\frac{a_0a_1a_2+a_0+a_2}{a_1a_2+1}
=\frac{p_1a_2+p_0}{q_1a_2+q_0},
\end{equation*}
so we define
\begin{align}\label{eqn:p_2}
  p_2&=p_1a_2+p_0,&q_2&=q_1a_2+q_0.
\end{align}
Following the pattern of \eqref{eqn:p_2}, we define
\begin{equation}\label{eqn:pq}
  p_{k+2}=p_{k+1}a_{k+2}+p_k,\qquad q_{k+2}=q_{k+1}a_{k+2}+q_k;
\end{equation}
but now we have to check that this gives us what we want.

\begin{theorem}\label{thm:pq}
Under the definitions \eqref{eqn:p_0}, \eqref{eqn:p_1}, and \eqref{eqn:pq},
for all $k$ in $\upomega$,
\begin{equation}\label{eqn:convergent}
  \frac{p_k}{q_k}=[a_0;a_1,\dots,a_k].
\end{equation}
\end{theorem}

\begin{proof}
We use induction.
By design, the claim holds when $k$ is $0$, $1$, or $2$.  
Supposing, for some $j$ in $\upomega$,
the claim holds when $k=j+2$,
using the recursive definition \eqref{eqn:brackets},
we have
\begin{multline*}
[a_0;a_1,\dots,a_{j+3}]
=\left[a_0;a_1,\dots,a_{j+1},a_{j+2}+\frac1{a_{j+3}}\right]\\
=\frac{p_{j+1}\cdot
  \left(a_{j+2}+\displaystyle\frac1{a_{j+3}}\right)+p_j}
     {q_{j+1}\cdot\left(a_{j+2}+\displaystyle\frac1{a_{j+3}}\right)+q_j}\\
=
\frac{p_{j+1}a_{j+2}a_{j+3}+p_{j+1}+p_ja_{j+3}}
     {q_{j+1}a_{j+2}a_{j+3}+q_{j+1}+q_ja_{j+3}}\\
=
\frac{p_{j+2}a_{j+3}+p_{j+1}}{q_{j+2}a_{j+3}+q_{j+1}}
=\frac{p_{j+3}}{q_{j+3}}.
\end{multline*}
By induction, we have~\eqref{eqn:convergent} for all $k$.
\end{proof}

We now confirm the additional property that we wanted.

\begin{theorem}\label{thm:-1}
For all $k$ in $\upomega$,
  \begin{equation*}
    \frac{p_{k+1}}{q_{k+1}}-\frac{p_k}{q_k}=\frac{(-1)^k}{q_{k+1}q_k},
  \end{equation*}
equivalently,
\begin{equation*}
  p_{k+1}q_k-p_kq_{k+1}=(-1)^k.
\end{equation*}
\end{theorem}

\begin{proof}
Again we use induction.  From \eqref{eqn:p_0} and \eqref{eqn:p_1}, we have
  \begin{equation*}
    \frac{p_1}{q_1}-\frac{p_0}{q_0}=\frac1{a_1}=\frac{(-1)^0}{q_1q_0},
  \end{equation*}
so the claim holds when $k=0$.  Supposing it holds for some $k$, we have
\begin{multline*}
  p_{k+2}q_{k+1}-p_{k+1}q_{k+2}\\
  =(p_{k+1}a_{k+2}+p_k)q_{k+1}-p_{k+1}(q_{k+1}a_{k+2}+q_k)\\
  =p_kq_{k+1}-p_{k+1}q_k,
\end{multline*}
which is $-(-1)^k$, that is, $(-1)^{k+1}$.  Thus
the claim holds for all $k$.
\end{proof}

\begin{corollary}
The integers $p_k$ and $q_k$ are prime to one another,
the sequences $\{p_{2n}/q_{2n}\}$
$\{p_{2n+1}/q_{2n+1}\}$ are respectively
increasing and decreasing, and
  \begin{equation*}
\frac{p_0}{q_0}<\frac{p_2}{q_2}<\dotsb<\frac{p_3}{q_3}<\frac{p_1}{q_1}.
  \end{equation*}
The two sequences converge to the same limit.  If the convergents are
obtained as above from $x$, then their limit is $x$.
\end{corollary}

Now we are justified in writing~\eqref{eqn:rt3}.


\topic{Pell equation}

With these tools, we turn now to the \defn{Pell equation},
\begin{equation}\label{eqn:pell}
  x^2-dy^2=1.
\end{equation}
We first take care of some trivial cases:
\begin{compactenum}
  \item
If $d<-1$, then $(x,y)=(\pm1,0)$.
\item
If $d=-1$, then $(x,y)$ is $(\pm1,0)$ or $(0,\pm1)$.
\item
If $d=0$, then $x=\pm1$, while $y$ is anything.
\item
If $d$ is a positive square, as $a^2$, 
the the equation becomes
\begin{equation*}
  (x+ay)(x-ay)=1,
\end{equation*} 
so $x\pm ay$ are equal to one another and to $\pm1$, 
and therefore $y=0$ and $x=\pm1$.
\end{compactenum}
\conv{We assume $d$ is a positive non-square}\label{d-nsq}
for the rest of this lecture (and again on page \pageref{d-nsq-2}).  
Thus
\begin{equation*}
  d\in\{2,3,5,6,7,8,10,11,12,13,14,15,17,\dots\}.
\end{equation*}
Then~\eqref{eqn:pell} still has the solution $(\pm1,0)$; but perhaps
it has others too.  Indeed,
in case $d=3$, on page \pageref{rt3}
we found solutions $(49,16)$ and
$(676,225)$, with a possibility of
finding more if the pattern continued.

Suppose $(a,b)$ and $(s,t)$ are solutions to~\eqref{eqn:pell};
This means
\begin{align*}
  a^2-db^2&=1,&s^2-dt^2&=1.
\end{align*}
Multiplication gives
\begin{equation}\label{eqn:pell-identity}
  1=  (a^2-db^2)(s^2-dt^2)=(as\pm dbt)^2-d(at\pm bs)^2,
\end{equation}
and so each pair $(as\pm dbt,at\pm bs)$ is a solution.  

We can repeat this process as follows,
noting also
\begin{equation*}
  a^2-db^2=(a+b\sqrt d)(a-b\sqrt d).
\end{equation*}
If we define $(a_n,b_n)$ by
\begin{equation}\label{eqn:a_n,b_n}
  a_n+b_n\sqrt d=(a+b\sqrt d)^n,
\end{equation}
then also $a_n-b_n\sqrt d=(a-b\sqrt d)^n$, so
\begin{equation*}
  a_n{}^2-db_n{}^2
  =(a+b\sqrt d)^n(a-b\sqrt d)^n=(a^2-b^2d)^n=1,   
\end{equation*}
and $(a_n,b_n)$ is a solution to \eqref{eqn:pell}.  
If $a+b\sqrt d>1$, 
then these solutions $(a_n,b_n)$ must all be distinct.
We ask now whether there is even 
\emph{one} solution $(a,b)$ such that $a+b\sqrt d>1$. 

\begin{lemma}
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
  $\sqrt d$.
  When $n$ is odd, we have
  \begin{align*}
    0<\frac{p_n}{q_n}-\sqrt 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}+\sqrt d&<\frac{2p_n}{q_n};
  \end{align*}
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}

If $(a,b)$ solves~\eqref{eqn:pell}, and each of $a$ and $b$ is
positive, then let us refer to $(a,b)$ as a \defn{positive}{} solution.

\begin{lemma}\label{lem:pos-sol}
\eqref{eqn:pell} has a positive solution.  
\end{lemma}

\begin{proof}
  By the previous lemma, we may let $k$ be a positive number such
  that~\eqref{eqn:pell-k} has infinitely many solutions.  But 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} together with the congruences
  \begin{equation*}
    x\equiv a,\quad y\equiv b\pmod k
  \end{equation*}
have infinitely many solutions.  Let $(m,n)$ and $(s,t)$ be two such
solutions.  Then by the identity in~\eqref{eqn:pell-identity}, we have
\begin{equation*}
  k^2=(m^2-dn^2)(s^2-dt^2)=(ms-dnt)^2-d(mt-ns)^2.
\end{equation*}
But we have also
\begin{equation*}
  ms-dnt\equiv m^2-dn^2\equiv0,\quad mt-ns\equiv mn-nm\equiv0\pmod k.
\end{equation*}
So we can divide by $k^2$ to get
\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}

\begin{theorem}\label{thm:pell-min-sol}
If $(a,b)$ is the positive solution of~\eqref{eqn:pell} 
for which $x+y\sqrt d$ is minimized,
then the equation has just the solutions
$(\pm a_n,\pm b_n)$ given by \eqref{eqn:a_n,b_n},
where 
%$a_n+b_n\sqrt d=(a+b\sqrt d)^n$ and 
$n\in\upomega$.  
\end{theorem}

\begin{proof}
  Let $(a,b)$, which exists by Lemma~\ref{lem:pos-sol},
be as in the statement.  
Then $a+b\sqrt d>1$, so the powers of $a+b\sqrt d$ grow arbitrarily large.  
We know that all of the $(a_n,b_n)$ are solutions of~\eqref{eqn:pell}.  
Let $(s,t)$ be an arbitrary positive solution.  Then
  \begin{equation*}
    (a+b\sqrt d)^n\leq s+t\sqrt d<(a+b\sqrt d)^{n+1}
  \end{equation*}
for some non-negative $n$.  
Since $(a+b\sqrt d)(a-b\sqrt d)=1$, 
and $a+b\sqrt d$ is positive, so is $a-b\sqrt d$.  
Therefore, when we multiply by the $n$th power of this, we get
\begin{equation}\label{eqn:stab}
  1\leq(s+t\sqrt d)(a-b\sqrt d)^n<a+b\sqrt d.
\end{equation}
But we have
\begin{equation*}
  (s\pm t\sqrt d)(a\mp b\sqrt d)^n=\ell\pm m\sqrt d
\end{equation*}
for some integers $\ell$ and $m$.
This makes $(\ell,m)$ a solution of~\eqref{eqn:pell},
and from \eqref{eqn:stab} 
we now have
\begin{gather*}
(\ell+m\sqrt d)(\ell-m\sqrt d)\leq \ell+m\sqrt d<a+b\sqrt d,\\
0<\ell-m\sqrt d\leq 1\leq\ell+m\sqrt d,
\end{gather*}
so $m\geq0$,
and therefore $\ell>0$.
By minimality of $a+b\sqrt d$, 
we must have $\ell+m\sqrt d=1$, so $(s,t)=(a_n,b_n)$. 
\end{proof}

\myweek

\myday{March 4, 2008 (Tuesday)}

\topic{Quadratic fields}

Every field $L$ is a vector space
over its every subfield $F$,
and the dimension is denoted by
\begin{equation*}
  [L:F].
\end{equation*}%
\label{K}\index{$K$ (a quadratic field, usually $\Q(\sqrt d)$)}
A subfield $K$ of $\C$%
\label{C}\index{$\C$ (the field of complex numbers)}  
such that $[K:\Q]=2$ 
is called a \defn{quadratic field}.  Henceforth
\conv{let $K$ be a quadratic field.}
The letter stands for the German \emph{K\"orper} ``body,'' 
this being the name, in languages other than English and Russian,
for a field.
Thus Russian \ru{pole,}
but French \emph{corps}
and Turkish \emph{cisim.}

An integer that is indivisible by the square of any prime
is called \defn{\sqf}.
Thus $1$, $2$, and $3$ are \sqf,
but $0$, $4$, and $12$ are not.
We may recall that the M\"obius function of a \sqf{} positive integer $n$
is $-1$ raised to the power of the number of prime factors of $n$;
if $n$ is not \sqf, then $\upmu(n)=0$.

For any $\alpha$ in $\C$, we let
\begin{equation*}
  \Q(\alpha)
\end{equation*}
denote the smallest subfield of $\C$ that contains $\alpha$,
while
\begin{equation*}
  \Z[\alpha]
\end{equation*}\label{Za}
is the smallest sub-\emph{ring} of $\C$ that contains $\alpha$.
It is easy to see that this ring is 
$\{x+\alpha y\colon(x,y)\in\Z\times\Z\}$.
It is not so easy to say what $\Q(\alpha)$ is;
but we are interested only in the quadratice case.

\begin{theorem}
The quadratic fields
are just the fields $\Q(\sqrt d)$,\label{Q(rt d)}\index{$\Q(\sqrt d)$} 
where $d$ is a \sqf{} integer,
possibly negative, different from $1$.
\end{theorem}

\begin{proof}
Every $K$ as above must contain some irrational $x$.
Then $1$ and $x$ are linearly independent over $\Q$,
so $\{1,x\}$ must be a basis over $\Q$
of $K$ as a vector space.
In particular, $x^2$ is a rational linear combination of $1$ and $x$,
which means
\begin{equation}\label{eqn:bc}
  x^2+bx+c=0
\end{equation}
for some $b$ and $c$ in $\Q$.
Thus
\begin{equation*}
  x=\frac{-b\pm\oldsqrt{b^2-4c}}2.
\end{equation*}
We can write $b^2-4c$ as
$s^2d$, where $s\in\Q$ and $d$ is as described.
Then $\sqrt d\in K\setminus\Q$, 
so $\{1,\sqrt d\}$ is a basis of $K$.
This means, as a space, $K$ is
\begin{equation*}
\Q\oplus\Q\sqrt d.
\end{equation*}
Every subfield of $\C$ containing $\sqrt d$
must include this space.
This space must therefore be $\Q(\sqrt d)$.
It is an exercise to check that, conversely,
for any $d$ as described,
the two-dimensional space $\Q\oplus\Q\sqrt d$
is indeed the field $\Q(\sqrt d)$.
In particular, if $a,b\in\Q$, and $b\neq0$, then
\begin{equation*}
  \frac1{a+b\sqrt d}=\frac{a-b\sqrt d}{a^2-b^2d}= \frac
  a{a^2-b^2d}-\frac
  b{a^2-b^2d}\sqrt d.  
\end{equation*}
Thus non-zero elements of $\Q\oplus\Q\sqrt d$
have multiplicative inverses. 
\end{proof}

A rational number is an integer if and only if it satisfies an
equation
\begin{equation*}
  x+c=0,
\end{equation*}
where $c\in\Z$.\index{$\Z$ (the ring of rational integers)}  This is a
trivial observation, but it motivates the
following definition.
An element of $K$ is an \defn{integer}{} of $K$ 
if it is an integer in the old sense, 
or else it satisfies an equation \eqref{eqn:bc},
where now $b$ and $c$ are in $\Z$.  
Henceforth, integers in the old sense can be called
\defn{rational integer}{s.}  
More generally, the \defn{algebraic integer}s\label{ai}
are the complex numbers that are roots of equations
\begin{equation*}
  x^n+a_1x^{n-1}+\dotsb+a_{n-1}x+a_n=0,
\end{equation*}
where $a_i\in\Z$ and $n$ ranges over the positive rational integers;
but we shall not go beyond the quadratic case, $n=2$. 


\topic{Gaussian integers}

For our first specific example of a quadratic field,
we shall use the standard abbreviation
\begin{equation*}
  \mi=\sqrt{{-1}}.
\end{equation*}
The integers of $\Q(\mi)$ 
are called the \defn{Gaussian integer}{s.}%
\index{$\gi$ (the ring of Gaussian integers)}   

The following is a special case 
of what we shall prove as Theorem \ref{thm:roi}.

\begin{theorem}\label{thm:gi}
The Gaussian integers compose the ring $\gi$.
\end{theorem}

\begin{proof}
Let $\alpha$ be $m+n\mi$ in $\gi$.
Then $(\alpha-m)^2=(n\mi)^2=-n^2$, 
so $\alpha^2-2m\alpha+m^2+n^2=0$, 
and thus $\alpha$ is a Gaussian integer. 

Suppose conversely $\alpha$ is a Gaussian integer.  
By definition,
$\alpha^2+b\alpha+c=0$ for some $b$ and $c$ in $\Z$.
Hence
\begin{equation*}
  \alpha=\frac{-b\pm\oldsqrt{b^2-4c}}2.
\end{equation*}
Since $\alpha\in\Q(\mi)$,
the absolute value $\size{b^2-4c}$ must be a square in $\Z$.  
Say this square is $e^2$.  
Now $\alpha$ is one of
\begin{align*}
  &\frac{-b\pm e}2,&&\frac{-b\pm e\mi}2.
\end{align*}
Since $b^2-4c=\pm e^2$, we have
\begin{align*}
  b^2\mp e^2&\equiv 4c\equiv 0\pmod 4,&
b&\equiv e\pmod 2.
\end{align*}
If $b$ and $e$ are both even, 
then $\alpha$ is in $\Z$ or $\Z\oplus\Z\mi$;
if odd, then $4\ndivides b^2+e^2$, 
so it must be that $b^2-e^2=4c$, 
which means $b^2-4c=e^2$, 
so that $\alpha\in\Z$. 
\end{proof}

The \defn{norm}{} on $\Q(\mi)$ is the function given by%
\index{$\norm x$}
\begin{equation}\label{eqn:norm}
  \begin{aligned}
    \norm{a+b\mi}
&=a^2+b^2\\
&=\size{a+b\mi}^2.
  \end{aligned}
\end{equation}
The values are non-negative rational numbers, and
\begin{equation*}
  \norm{\alpha\beta}=\norm{\alpha}\norm{\beta}.
\end{equation*}
Since
\begin{equation*}
  \frac1{a+b\mi}=\frac{a-b\mi}{a^2+b^2}=\frac{a-b\mi}{\norm{a+b\mi}},
\end{equation*}
we have
  \begin{equation*}
  \frac1{a+b\mi}\in\gi\iff
  \norm{a+b\mi}=\pm1\iff \norm{a+b\mi}=1.  
  \end{equation*}
In short, $a+b\mi$ is a unit of $\gi$ if and only if $a^2+b^2=1$.
In particular, the unit Gaussian integers are $\pm1$ and $\pm\mi$.   


\myday{March 7, 2008 (Friday)}

\topic{Euclidean domains}
An \defn{integral domain}{} (\emph{taml\i k alan\i}), or simply a
\defn{domain}, is a sub-ring of a field.  For us, the
field will usually be $\C$.  
As an example, $\gi$ is an integral domain.  
A \tech{Euclidean domain}{} is a domain
in which the Euclidean algorithm works.  
This means two things:
\begin{compactenum}[1)]
\item  
we can perform division with remainder, 
where the remainder is ``smaller'' than the divisor; 
\item
a sequence of remainders of decreasing size must terminate.  
\end{compactenum}
Since decreasing sequences of natural numbers must terminate, 
we shall use natural numbers to measure size.  
Formally, a domain $R$ is a \defn{Euclidean domain}{} 
if there is a function $x\mapsto\edeg x$,%
\index{$\edeg x$}
the \defn{degree}, 
from $R\setminus\{0\}$ into $\upomega$%
\index{$\upomega$ (the set $\{x\in\Z\colon x\geq 0\}$)}
such that, for all $\alpha$ and $\beta$ in $R$,
if $\beta\neq0$, then the system
\begin{equation*}
  \alpha=\beta x+y\And \edeg y<\edeg{\beta}
\end{equation*}
is soluble in $R$.

Gaussian integers have a size, namely their absolute value, 
but this need not be a rational integer.  
Since the \emph{square} is one, 
we let $\edeg x$ be the norm $\norm x$ as in~\eqref{eqn:norm}.

\begin{theorem}\label{thm:Gauss}
  $\gi$, as equipped with the norm, is a Euclidean domain.
\end{theorem}

\begin{proof}
  Given $\alpha$ and $\beta$ in $\gi$, where $\beta\neq0$, we must
  solve
\begin{equation*}
  \alpha=\beta x+y\And \norm y<\norm{\beta}
\end{equation*}
The Gaussian-integral multiples of $\beta$ compose a square \defn{lattice}{}
(\emph{kafes}) in $\C$, as in Figure~\ref{fig:Gmult}.
\begin{figure}[ht]
  \centering
\psset{unit=3mm}
  \begin{pspicture}(-11.5,-4.5)(12.5,12.5)
%\psgrid
\psline{->}(-11.5,0)(12.5,0)
\psline{->}(0,-4.5)(0,12.5)
\psdots(-2.5,8.5)
\uput[d](-2.5,8.5){$\alpha$}
\pspolygon[linestyle=dotted](-3,4)(1,7)(-2,11)(-6,8)
    \psdots
                   (-9,12)
           (-10, 5)(-6, 8)(-2,11)
   (-11,-2)( -7, 1)(-3, 4)( 1, 7)(5,10)
           ( -4,-3)( 0, 0)( 4, 3)(8, 6)(12,9)
                   ( 3,-4)( 7,-1)(11,2)
\uput[r](4,3){$\beta$}
\uput[d](-3,4){$\beta\mi$}
\uput[u](-2,11){$\gamma$}
  \end{pspicture}
\caption{A lattice of Gaussian multiples}\label{fig:Gmult}
\end{figure}
Then $\alpha$ is in one of the squares whose vertices are among these
multiples.  
The closest vertex to $\alpha$
is some $\gamma$ such that
\begin{equation*}
  \size{\alpha-\gamma}\leq\frac{\sqrt 2}2\size{\beta},\qquad
\norm{\alpha-\gamma}\leq\frac12\norm{\beta}.
\end{equation*}
So our solution is $(\gamma/\beta,\alpha-\gamma)$.  
\end{proof}

Doing the proof more algebraically, we have $\alpha/\beta=r+s\mi$ for
some $r$ and $s$ in $\Q$.  There are $m$ and $n$ in $\Z$ such that
$\size{r-m},\size{s-n}\leq1/2$. Then
\begin{multline*}
  \norm{\alpha-\beta(m+n\mi)}
=\norm{\beta}\norm{\frac{\alpha}{\beta}-(m+n\mi)}\\
=\norm{\beta}\norm{r-m+(s-n)\mi}
\leq\frac12\norm{\beta}.
\end{multline*}

Now we can find \tech{greatest common divisor}s in $\gi$.  In any
domain, a \defn{greatest common divisor}{} of two elements $\alpha$
and $\beta$, not both $0$, is a common divisor that is divisible by
every other common divisor.  This greatest common divisor need not be
unique.  Two greatest common divisors divide each other and so are called
\defn{associate}{s.}  Conversely, the associate of a greatest common
divisor is a greatest common divisor.

\begin{problem}
  Find in $\gi$ a greatest common divisor of $7+6\mi$ and
  $-1+7\mi$.
\end{problem}

  \begin{solution}
Following the pattern of the Euclidean Algorithm as on page \pageref{EucAlg},
we compute first
\begin{multline*}
        \frac{7+6\mi}{-1+7\mi}
       =\frac{(7+6\mi)(-1-7\mi)}{50}
       =\frac{35-55\mi}{50}
=\frac{7-11\mi}{10}\\
=\frac{10-3-(10+1)\mi}{10}
       =1-\mi+\frac{-3-\mi}{10},  
\end{multline*}
and then
\begin{equation*}
  \frac{(-1+7\mi)(-3-\mi)}{10}=1-2\mi,
\end{equation*}
so that, finally
\begin{equation*}
\frac{-1+7\mi}{1-2\mi}
=\frac{10}{-3-\mi}=-3+\mi.
\end{equation*}
Thus, in sum,
\begin{align*}
 7+6\mi&=(-1+7\mi)(1-\mi)+1-2\mi,\\
-1+7\mi&=(1-2\mi)(-3+\mi).
\end{align*}
In particular, $1-2\mi$ is a greatest common divisor 
of $7+6\mi$ and $-1+7\mi$.  
The other greatest common divisors 
are obtained by multiplying by the units of $\gi$, 
namely $\pm1$ and $\pm\mi$.  
So they are $\pm(1-2\mi)$ and $\pm(2+\mi)$.
  \end{solution}

  \myweek
  
\myday{March 11, 2008 (Tuesday)}

\topic{Unique-factorization domains}

All Euclidean domains are \tech{principal-ideal domain}{s,} and all
principal-ideal domains are \defn{unique-factorization domain}{s.}
Therefore $\gi$ is a unique-factorization domain;
but we can also prove this directly, using that
\begin{equation*}
  \norm{\xi\eta}=\norm{\xi}\norm{\eta}.
\end{equation*}
First, an element of any domain, other than $0$ or a unit, is
\defn{irreducible}{} if its only divisors are itself and units.
Suppose $\alpha$ is a reducible Gaussian integer.  Then
\begin{equation*}
  \alpha=\beta\gamma
\end{equation*}
for some $\beta$ and $\gamma$, neither of which is a unit.  But then
$\norm{\beta}$ and $\norm{\gamma}$ are greater than $1$, so
\begin{equation*}
  1<\norm{\beta}<\norm{\alpha},\qquad
  1<\norm{\gamma}<\norm{\alpha}.
\end{equation*}
Since there is no infinite strictly decreasing sequence of natural
numbers, the process of factorizing the factors of $\alpha$ as
products of non-units must terminate.  Thus $\alpha$ can be written as
a product of irreducible factors.

The definition of unique-factorization domain requires that irreducible
factorizations must be unique.  This means, if
\begin{equation*}
  \alpha_0\alpha_1\dotsm\alpha_m=\beta_0\beta_1\dotsm\beta_n,
\end{equation*}
where each $\alpha_i$ and each $\beta_j$ are irreducible, then each
$\alpha_i$ must be an associate of some $\beta_j$.  To prove this for
$\gi$, it is enough to show that each irreducible Gaussian integer is
\tech{prime}.  In any domain, an element $\alpha$ (not $0$ or a unit)
is \defn{prime}, provided
\begin{equation*}
  \alpha\divides\beta\gamma\And\alpha\ndivides\beta\implies
  \alpha\divides\gamma.  
\end{equation*}
In $\gi$, suppose $\alpha$ is irreducible, and
$\alpha\divides\beta\gamma\And\alpha\ndivides\beta$.  Then the
greatest common divisors of $\alpha$ and $\beta$ are just the units.
By applying the Euclidean Algorithm,
we can solve the equation
\begin{equation*}
  \alpha\xi+\beta\eta=1
\end{equation*}
$\gi$.  But then
\begin{equation*}
  \alpha\gamma\xi+\beta\gamma\eta=\gamma,
\end{equation*}
and since $\alpha$ divides the summands on the left, it divides
$\gamma$. 

\topic{Gaussian primes}

We now ask:  What are the primes of $\gi$?  Suppose $\pi$%
\index{$\pi$ (an arbitrary prime of $\gi$)}
is one of
them.  Then $\pi$ is not a unit, so $\norm{\pi}$ has rational-prime
factors.  But
\begin{equation*}
  \pi\cc{\pi}=\norm{\pi}.
\end{equation*}
Therefore, since $\pi$ is prime, we have
\begin{equation*}
  \pi\divides p
\end{equation*}
for some rational-prime factor of $\norm{\pi}$.  If $q$ is another
rational prime, then $ap+bq=1$ for some rational integers $a$ and
$b$.  Since $\pi\ndivides 1$, it must be that $\pi\ndivides q$.  Thus
$p$ is unique.


\begin{theorem}\label{thm:G-primes}
  The Gaussian primes are just the associates of the following:
  \begin{compactenum}
    \item
$1+\mi$;
\item
the rational primes $p$, where $p\equiv3\pmod 4$;
\item
$\alpha$, where $\norm{\alpha}$ is a rational prime $p$ such that
  $p\equiv1\pmod 4$ (and two such non-associated $\alpha$ exist for
  every such $p$). 
  \end{compactenum}
\end{theorem}

\begin{proof}
We have just seen that every Gaussian prime $\pi$
divides some rational prime $p$.
Then
$\norm{\pi}$ divides $\norm p$, which is $p^2$;
so $\norm{\pi}$, which is $\pi\cc{\pi}$,
is either $p$ or $p^2$.
Also $\norm{\pi}$
is of the form $x^2+y^2$,
so it is congruent to $0$, $1$, or $2$,
\emph{modulo} $4$.

Suppose now $p\equiv3\pmod4$.
Then we must have
\begin{equation*}
  \pi\cc{\pi}=p^2.
\end{equation*}
But $\pi\cc{\pi}$ is a prime factorization, so it is unique as such.
Therefore $\pi$ and $\cc{\pi}$ are associates of $p$ and hence of each
other.  In short, $p$ is a Gaussian prime.

In case $p=2$, we note
\begin{equation*}
  2=(1+\mi)(1-\mi).
\end{equation*}
Also, $1\pm\mi$ must be irreducible, since $\norm{1\pm\mi}=2$ (so if
$1\pm\mi=\alpha\beta$, then $\alpha$ or $\beta$ must have norm $1$ and
so be a unit).  So we have the unique prime factorization of $2$.
Also $1+\mi$ and $1-\mi$ are associates.  Hence the only prime
divisors of $2$ are the four associates
\begin{equation*}
  1+\mi,\quad 1-\mi,\quad -1+\mi,\quad-1-\mi.
\end{equation*}

Finally, suppose $p\equiv1\pmod 4$.  Then $-1$ is a quadratic residue
\emph{modulo} $p$, so $-1\equiv x^2\pmod p$ for some $x$, that is,
$p\divides 1+x^2$, and therefore
\begin{equation*}
  p\divides(1+x\mi)(1-x\mi).
\end{equation*}
But $(1\pm x\mi)/p$ is \emph{not} a Gaussian integer.  Therefore $p$
must not be a Gaussian prime.  Consequently, if $\pi$ is a prime
factor of $p$, then $\norm{\pi}=p$, that is,
\begin{equation*}
  \pi\cc{\pi}=p.
\end{equation*}
This is a prime factorization.  Moreover, $\pi$ and $\cc{\pi}$ are not
associates.  Indeed, $\pi=x+y\mi$ for some rational integers $x$ and
$y$, so that
\begin{equation*}
  \frac{\pi}{\cc{\pi}}=\frac{(x+y\mi)^2}p=\frac{x^2-y^2+2xy\mi}p.
\end{equation*}
If this is a Gaussian integer, then $p\divides 2xy$, so $p\divides xy$
(since $p$ is odd), so $p<x^2+y^2=p$, which is absurd.
\end{proof}

If $n$ is a positive rational integer, then the Diophantine equation
\eqref{eqn:n} of Problem \ref{prob:n},
namely
  $x^2+y^2=n$,
is soluble if and only if the equation
\begin{equation}\label{eqn:norm=n}
  \norm{\xi}=n
\end{equation}
is soluble, where $\xi$ is a Gaussian integer.  
Moreover, there is a bijection $(x,y)\mapsto x+y\mi$ 
between the solution-sets.  
This gives us an alternative solution to Problem \ref{prob:n}:

\begin{corollary}
In case $n$ is a rational prime $p$, 
the equation~\eqref{eqn:n} has a solution if and only if 
$p=2$ or $p\equiv 1\pmod 4$.
\end{corollary}

We can also \emph{count} solutions.
Suppose $p\equiv1\pmod4$.
If $n=p$, then~\eqref{eqn:norm=n} has exactly 8 solutions: 
the associates of $\pi$ for some prime $\pi$, 
and the associates of $\cc{\pi}$.  
If $n=p^2$, the solutions are the
associates of $\pi^2$, of $\pi\cc{\pi}$, and of ${\cc{\pi}}^2$, so
there are 12 solutions.  
If $q$ is another prime,
but still $q\equiv1\pmod4$, and $n=pq$, 
then there are 16 solutions.
In this way we obtain the following;
details are an exercise.

\begin{theorem}\label{thm:count}
  The number of solutions of~\eqref{eqn:n} is $4(a-b)$, where
  \begin{equation*}
  \begin{aligned}
    a&=\size{\{x\in\upomega\colon x\divides n\And x\equiv 1\}}\\
    b&=\size{\{x\in\upomega\colon x\divides n\And x\equiv 3\}}
  \end{aligned}
\pmod4.
  \end{equation*}
\end{theorem}

\index{$\mpi$ (the circumference of the unit circle)}% 
\begin{theorem}\label{thm:pi}
Letting $\mpi$ be (as usual) the circumference of the unit circle,
we have
\begin{equation*}
\frac{\mpi}{4}=1-\frac13+\frac15-\frac17+\dotsb
\end{equation*}
\end{theorem}

\begin{proof}
  The area of a circle of radius $r$ is $\mpi r^2$.  Hence
  \begin{equation*}
    \mpi
    r^2\approx\size{\{\xi\in\gi\colon1\leq\size{\xi}\leq
    r\}}
=\sum_{n=1}^{r^2}\size{\{\xi\in\gi\colon\norm{\xi}=n\}}.
  \end{equation*}
(See Figure~\ref{fig:counting}.)
  \begin{figure}[ht]
    \centering\psset{unit=8mm}
    \begin{pspicture}(-6.1,-3.1)(6.1,3.1)
      \pscircle(0,0)3
%\psset{fillstyle=solid,fillcolor=black}
%\multirput*(-4,-4)(1,0)9{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-6,-3)(1,0){13}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-6,-2)(1,0){13}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-6,-1)(1,0){13}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-6, 0)(1,0){13}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-6, 1)(1,0){13}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-6, 2)(1,0){13}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-6, 3)(1,0){13}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
%\multirput*(-4, 4)(1,0)9{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
    \end{pspicture}
\caption{Estimating the area of a circle}\label{fig:counting}
  \end{figure}
By Theorem~\ref{thm:count}, to this number, each positive $4m+1$ contributes
$4$ for each of its multiples between $1$ and $r^2$, while each
positive $4m+3$ takes away $4$ for each such multiple.  Therefore
\begin{multline*}
\frac{\mpi r^2}4
\approx\sum_{n=0}^{\infty}\left(\left[\frac{r^2}{4n+1}\right]-
\left[\frac{r^2}{4n+3}\right]\right)\\
=r^2-\left[\frac{r^2}3\right]+
    \left[\frac{r^2}5\right]-\left[\frac{r^2}7\right]+\dotsb
\end{multline*}
Dividing by $r^2$ and taking the limit yields the claim.
(For details, see~\cite[pp.\ 32--9]{MR0046650}.)
\end{proof}


\topic{Arbitrary quadratic fields}

Recall
the Pell equation~\eqref{eqn:pell} on page \pageref{eqn:pell},
which we can factorize as
\begin{equation}\label{eqn:pell-again}
  1=(x+y\sqrt d)(x-\sqrt d).
\end{equation}
This suggests looking at $\Q(\sqrt d)$.  
We eliminated some trivial cases before,
and one of them was $d<0$.
Now we shall allow this,
but shall henceforth require
  \conv{that $d$ be a \sqf{} integer other than $1$.}\label{d}
\index{$d$ (a \sqf{} element of $\Z$, not $1$)}%
Let us also henceforth suppose
\conv{$K=\Q(\sqrt d)$.}\label{body}
On $K$ we define $\xi\mapsto\xi'$ by
\begin{equation}\label{eqn:prime}
  (a+b\sqrt d)'=a-b\sqrt d.
\end{equation}
When $d<0$, this is complex conjugation.
In any case, we define the 
\defn{trace}{}\index{$\tr x$} and 
\defn{norm}{}\index{$\norm x$} of $\alpha$ by
\begin{align}%\label{eqn:norm}
  \tr{\alpha}&=\alpha+\alpha',&
\norm{\alpha}&=\alpha\alpha'
\end{align}
respectively.
These are rational numbers.  Indeed, if $\alpha=a+b\sqrt d$, then
\begin{equation*}
  \tr{\alpha}=2a,\qquad\norm{\alpha}=a^2-b^2d.
\end{equation*}

\begin{theorem}\label{thm:int}
An element of $K$ is an integer
if and only if its norm and trace are rational integers.
\end{theorem}

\begin{proof}
Let $\alpha\in K$.
Since
\begin{equation*}
  (x-\alpha)(x-\alpha')
=x^2-(\alpha+\alpha')x+\alpha\alpha',
\end{equation*}
$\alpha$ is a zero of the polynomial
\begin{equation}\label{eqn:min-pol}
x^2-\tr{\alpha}x+\norm{\alpha}.
\end{equation}
Thus if the trace and norm of $\alpha$ are rational integers,
then $\alpha$ is an integer, by the definition on page \pageref{ai}.
Conversely,
if $\alpha$ is an integer,
then either $\alpha$ is a rational integer,
or else the polynomial in \eqref{eqn:min-pol} 
must be the \defn{minimal polynomial}{} 
of $\alpha$ over $\Q$, that is, 
the polynomial of least degree with rational coefficients, 
and leading coefficient $1$, of which $\alpha$ is a root.  
(This must exist, since the ring $\Q[x]$ of polynomials 
is a Euclidean domain with respect to polynomial degree.)  
In either case, the norm and trace of $\alpha$
must be rational integers.
\end{proof}

The set of integers of $K$ can be denoted by%
\index{$\roi$}
\begin{equation*}\label{roi}
  \roi.
\end{equation*}
As in case $d=-1$ with Theorem \ref{thm:gi},
so generally,
we want to show that $\roi$ is a sub-ring of $K$,
thus an integral domain.
This means showing $\roi$ contains $0$ and $1$
and is closed under addition, subtraction, and multiplication.
Obviously $\roi$ contains $0$ and $1$,
since it includes $\Q$.
If $\alpha$ satisfies \eqref{eqn:bc} on page \pageref{eqn:bc},
then $-\alpha$ satisfies
\begin{equation*}
  x^2-bx+c=0;
\end{equation*}
thus $\roi$ is closed under additive inversion.
It remains to show $\roi$ is closed under addition and multiplication.
For this, by Lemma \ref{thm:int},
assuming the norms and traces of $\alpha$ and $\beta$ are in $\Z$,
we need only show that so are the norms and traces of $\alpha+\beta$
and $\alpha\beta$.
Since $(\alpha+\beta)'=\alpha'+\beta'$ and $(\alpha\beta)'=\alpha'\beta'$,
we have
\begin{align*}
\tr{\alpha+\beta}&=\tr{\alpha}+\tr{\beta},&
\norm{\alpha\beta}&=\norm{\alpha}\norm{\beta}.  
\end{align*}
Since
  $(\alpha+\beta)(\alpha'+\beta')
=\alpha\alpha'+\alpha\beta'+\alpha'\beta+\beta\beta'$,
we have
\begin{equation*}
  \norm{\alpha+\beta}=\norm{\alpha}+\tr{\alpha\beta'}+\norm{\beta}.
\end{equation*}
Thus it is enough to show $\tr{\alpha\beta'}\in\Z$.
Letting
\begin{align*}
  \alpha&=a_0+a_1\sqrt d,&
  \beta&=b_0+b_1\sqrt d,
\end{align*}
so that
  $\alpha\beta'=a_0b_0-a_1b_1d-(a_0b_1-a_1b_0)\sqrt d$,
we are assuming $\Z$ contains all of
\begin{align*}
  &2a_0,&&2b_0,&&a_0{}^2-a_1{}^2d,&&b_0{}^2-b_1{}^2d,
\end{align*}
and we have to show $\Z$ also contains $a_0b_0-a_1b_1d$.
This is left as an exercise,
which can be solved independently 
or by Theorem \ref{thm:roi} below.


\myday{March 14, 2008 (Friday)}



As on page \pageref{Za},
\begin{equation*}
\Z[\sqrt d]=\Z\oplus\Z\sqrt d=\{x+y\sqrt d\colon(x,y)\in\Z\times\Z\}.
\end{equation*}
It follows now that 
$\Z[\sqrt d]\included\roi$.
The converse fails when $d\equiv1\pmod4$,
since $(1+\sqrt d)/2$ has the minimal polynomial
$x^2-x+(1-d)/4$.
In order to characterize $\roi$,
we define\index{$\omega$ (generator of $\roi$ over $\Z$)}
  \begin{equation}\label{omega}
    \omega=
    \begin{cases}
      \sqrt d,& \text{ if }d\equiv 2 \text{ or }3\pmod 4;\\
\displaystyle\frac{1+\sqrt d}2,& \text{ if }d\equiv1\pmod 4.
    \end{cases}
  \end{equation}
\conv{Henceforth $\omega$ shall always have this meaning.}
Note that, in any case of $d$,
we have $\Z[\sqrt d]\included\Z[\omega]$.

\begin{theorem}\label{thm:roi}
$\roi=\Z[\omega]$.
\end{theorem}

\begin{proof}
Let $\alpha$ be an element $a+b\sqrt 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 Lemma \ref{thm:int}.
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[\sqrt d]$, and so $\alpha\in\Z[\omega]$.
\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\Z[\omega]$.
\end{compactenum}
Suppose conversely $\alpha\in\Z[\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$.
\end{proof}

\topic{Quadratic forms}

Assuming $a,b,c\in\Q$, let
\begin{equation}\label{eqn:abc}
  f(x,y)=ax^2+bxy+cy^2;
\end{equation}
this is a \defn{binary quadratic form}.  We shall
investigate the rational-integral solutions of
\begin{equation*}
  f(x,y)=m,
\end{equation*}
where $m\in\Q$.  The Pell equation~\eqref{eqn:pell},
rewritten as \eqref{eqn:pell-again}, is a special case.  
Assuming $a\neq0$,
we can factorize $f$ over an appropriate quadratic field 
by completing the square:
\begin{align*}
  f(x,y)
&=a\Bigl(x^2+\frac ba\cdot xy+\frac{b^2}{4a^2}\cdot
  y^2\Bigr)-\Bigl(\frac{b^2}{4a}-c\Bigr)y^2 \\
&=a\Bigl(x+\frac b{2a}\cdot y\Bigr)^2-\Bigl(\frac{b^2}{4a}-c\Bigr)y^2 \\
&=\frac1a\Bigl(ax+\frac b{2}\cdot
  y\Bigr)^2-\frac1a\Bigl(\frac{b^2}{4}-ac\Bigr)y^2.
\end{align*}
Letting $\Disc=b^2-4ac$,\label{Disc} 
the \defn{discriminant}{} of $f$, we have
\begin{align*}
f(x,y)
&=\frac1a\biggl[\Bigl(ax+\frac b{2}\cdot
  y\Bigr)^2-\frac \Disc4\cdot y^2\biggr]\\
&=\frac1a\Bigl(ax+\frac b2\cdot y+\frac{\sqrt{\Disc}}2\cdot y\Bigr)
\Bigl(ax+\frac b2\cdot y-\frac{\sqrt{\Disc}}2\cdot y\Bigr)\\
&=\frac1a\Bigl(ax+\frac{b+\sqrt{\Disc}}2\cdot y\Bigr)
\Bigl(ax+\frac{b-\sqrt{\Disc}}2\cdot y\Bigr).
\end{align*}
Assuming $\sqrt{\Disc}$ is irrational,
we can write $\Disc$ as $s^2d$, where $s$ is a nonzero rational number,
while $d$ is a \sqf{} rational integer different from $1$,
as per the convention established on page \pageref{body}.
working in $K$, which is by our convention $\Q(\sqrt d)$,
and letting
\begin{equation*}
  \alpha=a,\qquad \beta=\frac{b+\sqrt{\Disc}}2=\frac{b+s\sqrt d}2,
\end{equation*}
we have
\begin{equation*}
  f(x,y)=\frac1a(\alpha x+\beta y)(\alpha'x+\beta'y)
  =\frac1a\norm{\alpha x+\beta y}.
\end{equation*}
Moreover, $\alpha$ and $\beta$ are linearly independent over $\Q$;
that is, the only rational solution to $\alpha x+\beta y=0$ is
$(0,0)$.  

For any $\alpha$ and $\beta$ in $K$, 
we may denote the set $\{\alpha x+\beta y:x,y\in\Z\}$ 
of all rational-integral linear combinations of $\alpha$ and $\beta$ 
by either of
\begin{align*}
  &\Z\alpha+\Z\beta,&&\latt.
\end{align*}\index{$\latt$}
If $\alpha$ and $\beta$ are linearly independent over $\Q$, then
$\latt$ is a \defn{lattice}{} in $K$,
to be denoted by $\mLambda$.
This means two things:
\begin{compactenum}
\item
$\mLambda$ is a \tech{free abelian subgroup}{} of $K$;
\item
the minimum number of generators of this group is the dimension $[K:\Q]$.  
\end{compactenum}
In short, \conv{$\mLambda$ is $\Z\alpha\oplus\Z\beta$.}\label{Lambda}

For example, by Theorem \ref{thm:roi}, 
as a group, $\roi$ is the lattice $\latt[1,\omega]$.
In general, if $\mLambda$ is a lattice in $K$, let%
\index{$\End$}\label{End}
\begin{equation*}
  \End=\{\xi\in\C\colon \xi\mLambda\included\mLambda\}.
\end{equation*}
This set is a sub-ring of $K$ and and can be understood as the ring of
\defn{endomorphism}{s} of the abelian group $\mLambda$.  That is, the
function $\xi\mapsto\alpha\xi$ is an endomorphism of $\mLambda$ if and
only if $\alpha\in\End$.

For example, if $\mLambda=\latt[1,\mi]$, then
$\End=\latt[1,\mi]$.  
But suppose $\mLambda=\latt[1,\tau]$,
where
\begin{equation}\label{eqn:tau-7}
\tau=\frac{-1+\sqrt{{-7}}}4.
\end{equation}
Then $(4\tau+1)^2=-7$, so $16\tau^2+8\tau+8=0$,
which means $2\tau^2+\tau+1=0$, that is, $2\tau^2=-\tau-1$,
and therefore
\begin{equation*}
  2\tau\mLambda=\latt[2\tau,-\tau-1]=\latt[2,\tau+1].
\end{equation*}
See Figure~\ref{fig:lat-end}.
In particular, $\latt[1,2\tau]\included\End$.
Conversely, if $x+y\tau\in\End$,
then $\mLambda$ contains $(x+y\tau)\tau$, but
\begin{equation*}
  (x+y\tau)\tau=x\tau+y\tau^2=x\tau+y\frac{-\tau-1}2
  =-\frac y2+\Bigl(x-\frac y2\Bigr)\tau,
\end{equation*}
So $y$ must be even.  Thus
$\End=\latt[1,2\tau]$.
\begin{figure}[ht]
\centering\psset{unit=11mm}
\begin{pspicture}(-4,-4)(4,3)
%\psgrid
\psline{->}(-4.5,0)(4.5,0)
\psline{->}(0,-3)(0,3)
\multirput*(0,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(1,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(2,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(3,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(4,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-1,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-2,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-3,0)(-0.25,0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
%
\multirput*(0,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(1,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(2,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(3,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-4,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-3,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-1,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-2,0)(0.25,-0.661){5}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\rput*(4,2.646){\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\rput*(-4,-2.646){\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\uput[ur](1,0){$1$}
\uput[dl](-0.25,0.661){$\tau$}
  \end{pspicture}

\begin{pspicture}(-4,-3)(4,3)
%\psgrid
\psline{->}(-4.5,0)(4.5,0)
\psline{->}(0,-3)(0,3)
\multirput*(0,0)(-0.5,1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(0.75,0.661)(-0.5,1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(2,0)(-0.5,1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(2.75,0.661)(-0.5,1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(4,0)(-0.5,1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-1.25,0.661)(-0.5,1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-2,0)(-0.5,1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-3.25,0.661)(-0.5,1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
%
\multirput*(0,0)(0.5,-1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(1.25,-0.661)(0.5,-1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(2,0)(0.5,-1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(3.25,-0.661)(0.5,-1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-4,0)(0.5,-1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-2.75,-0.661)(0.5,-1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-2,0)(0.5,-1.322){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-0.75,-0.661)(0.5,-1.322){2}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\uput[dr](2,0){$2$}
\uput[r](0.75,0.661){$\tau+1$}
  \end{pspicture}

  \begin{comment}
  \begin{pspicture}(-4,-3)(4,3)
%\psgrid
\psline{->}(-4,0)(4.5,0)
\psline{->}(0,-3)(0,3)
\psset{fillstyle=solid}
\multirput*(0,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(1,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(2,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(3,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(4,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-1,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-2,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-3,0)(-0.5,1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
%
\multirput*(0,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(1,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(2,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(3,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-3,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-4,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-1,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\multirput*(-2,0)(0.5,-1.323){3}{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\rput*(4,2.646){\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\rput*(-4,-2.646){\pscircle[fillstyle=solid,fillcolor=black]{0.05}}
\uput[ur](1,0){$1$}
\uput[dl](-0.50,1.323){$2\tau$}
  \end{pspicture}
\end{comment}
\caption[Lattice and isomorphic sublattice]%
{Lattice and isomorphic sublattice, $\tau$ as in \eqref{eqn:tau-7}}
\label{fig:lat-end}
\end{figure}

\myweek

\myday{March 18, 2008 (Tuesday)}

\topic{Lattices and elliptic curves}

To get a sense for where things may lead 
(not in this course, but see for example~\cite{MR890960}),
suppose $\mLambda$ is a lattice,
merely in the sense that $\alpha\neq0$ and $\beta/\alpha\not\in\R$;%
\index{$\R$ (the field of real numbers)}
the complex numbers $\alpha$ and $\beta$ need not be quadratic.
Geometrically, the quotient group $\C/\mLambda$
is the parallelogram 
%with vertices $0$, $\alpha$, $\beta$, and $\alpha+\beta$ as 
shown in Figure~\ref{fig:fund-paral},
\begin{figure}[ht]
\centering
\begin{pspicture}(-0.4,-0.2)(5.2,3.2)
%\psgrid
    \psline(0,0)(3,1)(4,3)(1,2)(0,0)
    \uput[l](0,0){$0$}
    \uput[r](4,3){$\alpha+\beta$}
    \uput[dr](3,1){$\alpha$}
    \uput[ul](1,2){$\beta$}
  \end{pspicture}
\caption{A fundamental parallelogram of a lattice}\label{fig:fund-paral}
\end{figure}
but opposite edges are identified;
thus the quotient is a \defn{torus}.  
The holomorphic function $\wp$
called the \defn{Weierstra\ss{} function} is given by
\begin{equation*}
  \wp(z)=\frac1{z^2}+
  \sum_{\zeta\in\mLambda\setminus\{0\}}\Bigl(\frac1{(z-\zeta)^2}
  -\frac1{\zeta^2}\Bigr)
\end{equation*}
and is \defn{doubly periodic}, with period $\mLambda$, meaning
\begin{equation*}
  \zeta\in\mLambda\iff\wp(z+\zeta)=\wp(z)\text{ for all }z.
\end{equation*}
Hence $\wp$ is well-defined as a function on the torus $\C/\mLambda$.
There are complex numbers $g_2$ and $g_3$, depending on $\mLambda$,
such that $(\wp(z),\wp'(z))$ solves the 
equation
\begin{equation*}
  y^2=4x^3-g_2x-g_3.
\end{equation*}
This equation defines an \defn{elliptic curve},
such as in Figure~\ref{fig:elliptic}.  
\begin{figure}[ht]
\centering
\begin{pspicture}(-3,-2.8)(3,2.8)
%\psgrid[subgriddiv=10]
\psset{linewidth=1.2pt,plotpoints=200}
\psplot{-2.103}{2.3}{x x x mul mul x 3 mul sub 3 add sqrt}
\psplot{-2.103}{2.3}{x x x mul mul x 3 mul sub 3 add sqrt neg}
\psline(-2.103,-0.1)(-2.103,0.1)
\psline(-3,-1)(3,-2)
\psline(-1.97,-2.8)(-1.97,2.8)
\psdots(-1.97,-1.17)(-1.97,1.17)(0.21,-1.53)(1.77,-1.78)
\uput[dl](-1.97,-1.17){$P$}
\uput[ul](-1.97,1.17){$-P$}
\uput[ul](0.21,-1.53){$Q$}
\uput[ur](1.77,-1.78){$R$}
  \end{pspicture}
\caption{An elliptic curve}\label{fig:elliptic}
\end{figure}
This curve is an abelian group by the rule that
$P+Q+R=0$ when the three points are collinear. 
Here $0$ is the point at infinity,
met by every vertical line.  
Then $(\wp,\wp')$ is an isomorphism from $\C/\mLambda$ 
to the elliptic curve.

An analytic endomorphism of $\C/\mLambda$ is a function 
$z\mapsto\gamma z$, where $\gamma\in\C$, 
such that $\gamma\mLambda\included\mLambda$.
The set of these $\alpha$ 
is what we are calling $\End$.  
Always $\Z\included\End$.  
You can show that $\Z=\End$ if and only if 
$\beta/\alpha$ is not quadratic.


\topic{Quadratic lattices}

We are interested in the quadratic case,
and henceforth we assume
\conv{$\alpha$ and $\beta$ are in $K$ for some $d$.}\label{ab}
Every element $\alpha x+\beta y$ of $\mLambda$ is the matrix product
\begin{equation*}
  \begin{pmatrix}
    x&y
  \end{pmatrix}
  \begin{pmatrix}
    \alpha\\\beta
  \end{pmatrix}.
\end{equation*}
Then $\latt[\gamma,\delta]\included\latt$ if and only if the equation
\begin{equation*}
  \begin{pmatrix}
    \gamma\\\delta
  \end{pmatrix}=
  \begin{pmatrix}
    x&y\\z&w
  \end{pmatrix}
  \begin{pmatrix}
    \alpha\\\beta
  \end{pmatrix}
\end{equation*}
is soluble in $\Z$.  
In particular, $\latt[\gamma,\delta]=\latt$ if and only if
\begin{equation*}
  \begin{pmatrix}
    \gamma\\\delta
  \end{pmatrix}=M
  \begin{pmatrix}
    \alpha\\\beta
  \end{pmatrix}
\end{equation*}
for some \emph{invertible} matrix $M$ over $\Z$: this means $\det
M=\pm1$.

Along with the sub-ring $\End$ of $K$, we have the sub-ring $\roi$.
What is the relation between the two rings?

\begin{lemma}\label{lem:end-in-roi}
  $\End\included\roi$.
\end{lemma}

\begin{proof}
  Suppose $\gamma\in\End$. Then there are $a$, $b$, $c$, and $d$ in
  $\Z$ such that
  \begin{gather*}
    \begin{pmatrix}
      a&b\\c&d
    \end{pmatrix}
    \begin{pmatrix}
      \alpha\\\beta
    \end{pmatrix}
=\gamma
    \begin{pmatrix}
      \alpha\\\beta
    \end{pmatrix}
=\begin{pmatrix}
  \gamma&0\\0&\gamma
\end{pmatrix}
    \begin{pmatrix}
      \alpha\\\beta
    \end{pmatrix},\\
    \begin{pmatrix}
      0\\0
    \end{pmatrix}
=\begin{pmatrix}
  \gamma-a&-b\\-c&\gamma-d    
    \end{pmatrix}
    \begin{pmatrix}
      \alpha\\\beta
    \end{pmatrix}.
  \end{gather*}
Hence the last square matrix is not invertible over any field, 
so its determinant is $0$.
In particular, $\gamma$ is a root of the equation
\begin{equation*}
0=  (x-a)(z-d)-bc=x^2-(a+d)x+ad-bc.
\end{equation*}
The coefficients belonging to $\Z$, 
we have $\gamma\in\roi$.
\end{proof}


\topic{Pell equation examples}

\begin{problem}\label{prob:14}
  Solve the Pell equation 
\begin{equation}\label{eqn:14}
x^2-14y^2=1.
\end{equation}
\end{problem}

\begin{solution}
We first find the continued fraction expansion
of $\sqrt{14}$ by our algorithm:
\begin{alignat*}3
&&  a_0&=3,&\quad\xi_0&=\sqrt{14}-3;\\
\frac1{\sqrt{14}-3}&=\frac{\sqrt{14}+3}5,\quad&\quad
a_1&=1,\quad&\quad\xi_1&=\frac{\sqrt{14}-2}5;\\ 
\frac 5{\sqrt{14}-2}&=\frac{\sqrt{14}+2}2,&\quad
a_2&=2,&\quad\xi_2&=\frac{\sqrt{14}-2}2;\\
\frac2{\sqrt{14}-2}&=\frac{\sqrt{14}+2}5,&\quad a_3&=1,&\quad\xi_3&=\frac{\sqrt{14}-3}5;\\
\frac5{\sqrt{14}-3}&=\sqrt{14}+3,&\quad a_4&=6,&\quad\xi_4&=\sqrt{14}-3=\xi_0;
\end{alignat*}
therefore
\begin{equation}\label{eqn:rt14}
  \sqrt{14}=[3;\overline{1,2,1,6}].
\end{equation}
For the convergents $p_n/q_n$, we have
\begin{equation*}
  \frac{p_0}{q_0}=\frac31,\qquad\frac{p_1}{q_1}=\frac41,\qquad
\frac{p_n}{q_n}=\frac{a_np_{n-1}+p_{n-2}}{a_nq_{n-1}+q_{n-2}}
\end{equation*}
by \eqref{eqn:pq},
so the list is
\begin{equation*}
  \frac31,\quad\frac41,
  \quad\frac{11}3,\quad\frac{15}4,\quad\frac{101}{27},\quad\dots  
\end{equation*}
We check for a solution to~\eqref{eqn:14}:
\begin{align*}
  3^2-14\cdot1^2&=-5,\\
4^2-14\cdot 1^2&=2,\\
11^2-14\cdot3^2&=121-126=-5,\\
15^2-14\cdot4^2&=225-(15-1)(15+1)=1.
\end{align*}
Then $15/4=[3;1,2,1]$, and $(15,4)$ solves~\eqref{eqn:14}.  
This is the positive solution $(a,b)$ for which $a+b\sqrt{14}$ is least: 
we shall be able to conclude this 
from Theorem \ref{thm:rt-d-periodic} on page \pageref{thm:rt-d-periodic}, 
but meanwhile one can verify the claim 
by trying all pairs $(a,b)$ such that $0<a<15$ and $0<b<4$.  
Then by Theorem \ref{thm:pell-min-sol} on page \pageref{thm:pell-min-sol},
every positive solution must be $(a_n,b_n)$, where
\begin{equation*}
a_n+b_n\sqrt{14}=(15+4\sqrt{14})^n.
\end{equation*} 
Finally, $(a_n,b_n)=(p_{4n+3},q_{4n+3})$.
\begin{comment}
  , and
  \begin{equation*}
    \frac{p_{4n+3}}{q_{4n+3}}=
    [3;\underbrace{\underbrace{1,2,1,6},\dots,\underbrace{1,2,1,6}}_n,1,2,1].
  \end{equation*}
\end{comment}
Indeed, if $(k,\ell)$ is a solution, then by the computation
\begin{equation*}
  (15+4\sqrt{14})(k+\ell\sqrt{14})=15k+56\ell+(4k+15\ell)\sqrt{14},
\end{equation*}
we have that $(15k+56\ell,4k+15\ell)$ is a solution.  But also,
writing $(p_{4n+3},q_{4n+3})$ as $(a,b)$, we have
\begin{multline*}
  \frac{p_{4n+7}}{q_{4n+7}}
=\Bigl[3;1,2,1,3+%\frac{p_{4n+3}}{q_{4n+3}}
\frac ab\Bigr]
=3+\cfrac1{1+\cfrac1{2+\cfrac1{1+\cfrac1{3+\cfrac ab}}}}\\
=3+\cfrac1{1+\cfrac1{2+\cfrac1{1+\cfrac b{a+3b}}}}
%=3+\cfrac1{1+\cfrac1{2+\cfrac1{\cfrac{a+4b}{a+3b}}}}
=3+\cfrac1{1+\cfrac1{2+\cfrac{a+3b}{a+4b}}}\\
%=3+\cfrac1{1+\cfrac1{\cfrac{3a+11b}{a+4b}}}
=3+\cfrac1{1+\cfrac{a+4b}{3a+11b}}
%=3+\cfrac1{\cfrac{4a+15b}{3a+11b}}
=3+\cfrac{3a+11b}{4a+15b}
=\frac{15a+56b}{4a+15b}.
\end{multline*}
By induction, our claim is proved.
\end{solution}

The expansion $[3;\overline{1,2,1,6}]$ of $\sqrt{14}$ has the period
$(1,2,1,6)$ of length $4$, which is even.  But
\begin{equation}\label{eqn:rt13}
  \sqrt{13}=[3;\overline{1,1,1,1,6}]
\end{equation}
with a period of odd length $5$.  The convergents $p_n/q_n$ of $\sqrt
d$ are alternately above and below $\sqrt d$,
this being irrational;
in particular, the convergents $p_{2n}/q_{2n}$ are below.  
Therefore $[3;1,1,1,1]$ cannot provide a solution to
$x^2-13y^2=1$.  But
\begin{equation*}
    [3;1,1,1,1,6,1,1,1,1]
\end{equation*}
will provide the fundamental solution,
which generates the others,
so that the solutions here will be $p_{10n+9}/q_{10n+9}$. 
See page \pageref{ch:april-18}.

\myweek

\myday{March 25, 2008 (Tuesday)}

\topic{Quadratic form example}
A problem on last night's examination was to find solutions to the
Diophantine equation 
\begin{equation}\label{eqn:232}
  2x^2-3y^2=2.
\end{equation}
Let us define
\begin{multline*}
f(x,y)
=  2x^2-3y^2
=2\left(x^2-\frac32y^2\right)\\
=2\left(x+\sqrt[\sum]\frac32\cdot y\right)
\left(x-\sqrt[\sum]\frac32\cdot y\right)\\
=\frac12(2x+\sqrt 6\cdot y)(2x-\sqrt 6\cdot y).
\end{multline*}
Working in $\Q(\sqrt 6)$, we have
\begin{equation*}
  f(x,y)=\frac12\norm{2x+\sqrt 6\cdot y}=\frac12\norm{\alpha x+\beta y},
\end{equation*}
where $\alpha=2$ and $\beta=\sqrt 6$.  We have a bijection
$(x,y)\mapsto\alpha x+\beta y$ between:
\begin{compactenum}
  \item
the solution-set of~\eqref{eqn:232};
\item
the set of $\xi$ in $\latt$ such that $\norm{\xi}=4$.
\end{compactenum}
In particular, $(5,4)$ is a solution of~\eqref{eqn:232}, and
$\norm{5\alpha+4\beta}=4$.  Then other solutions to $\norm{\xi}=4$
include $\epsilon\cdot(5\alpha+4\beta)$, provided:
\begin{compactenum}
  \item
$\norm{\epsilon}=1$;
\item
 $\epsilon\cdot(5\alpha+4\beta)\in\latt$,---and this is achieved if
 $\epsilon\latt\included\latt$, that is, $\epsilon\in\End[\latt]$. 
\end{compactenum}


\topic{Discriminants}

Let $f(x,y)=ax^2+bxy+cy^2$ for some $a$, $b$, and $c$ in $\Q$
as in~\eqref{eqn:abc},
so that the discriminant $\Disc$ of $f$ is $b^2-4ac$.
By the quadratic formula,
\begin{align*}
  f(x,y)&=a\Bigl(x-\frac{-b+\sqrt{\Disc}}{2a}y\Bigr)
  \Bigl(x-\frac{-b-\sqrt{\Disc}}{2a}y\Bigr)\\ 
  &=\frac1a\Bigl(ax+\frac{b-\sqrt{\Disc}}{2}y\Bigr)
  \Bigl(ax+\frac{b+\sqrt{\Disc}}{2}y\Bigr).
\end{align*}
As before, $\Disc=s^2d$
for some nonzero rational $s$
and some rational integer $d$ that is \sqf{} or zero.
Assuming as on page \pageref{d} that $d$ is \sqf, but not $1$,
or equivalently, $\sqrt{\Disc}\not\in\Q$,
we have $a\neq0$,
and again $f(x,y)=\norm{\alpha x+\beta y}/a$,
where
$\alpha=a$, $\beta=(b+\sqrt{\Disc})/2$,
and the norm is computed in $K$,
which is $\Q(\sqrt d)$ (again as on page \pageref{body}).
Since $\sqrt{\Disc}$ is irrational, we have
$\beta/\alpha\not\in\Q$,
that is, $\alpha$ and $\beta$ are linearly independent over $\Q$;
equivalently, $\{\alpha,\beta\}$ is a basis of $K$
as a vector space over $\Q$. 

Now suppose conversely $\alpha$ and $\beta$ are in $K$
and $f$ is given simply by
$f(x,y)=\norm{\alpha x+\beta y}$.
Then
\begin{align*}
  f(x,y)
  &=(\alpha x+\beta y)(\alpha'x+\beta'y)\\
  &=\alpha\alpha'x^2+(\alpha\beta'+\alpha'\beta)xy+\beta\beta'y^2  
\end{align*}
so that
\begin{equation}\label{eqn:D-as-square}
  \Disc
  =(\alpha\beta'+\alpha'\beta)^2-4\alpha\beta\alpha'\beta'
=(\alpha\beta'-\alpha'\beta)^2.
\end{equation}
We note then
\begin{equation}\label{eqn:D-as-det}
  \Disc=
\begin{vmatrix}
  \alpha&\alpha'\\\beta&\beta'
\end{vmatrix}^2.
\end{equation}
Alternatively,
\begin{gather*}
  f(x,y)
  =\norm{\alpha}x^2+\tr{\alpha\beta'}xy+\norm{\beta}y^2,\\
  \Disc=\tr{\alpha\beta'}^2-4\norm{\alpha\beta}.
\end{gather*}

\begin{lemma}\label{lem:D}
For some elements $\alpha$ and $\beta$ of $K$,
let $\Disc$ be the discriminant of $\norm{\alpha x+\beta y}$,
so that $\Disc=s^2d$ for some $s$ in $\Q$.
The following are equivalent:
  \begin{compactenum}
    \item\label{item:Dnot0}
$\Disc\neq0$;
\item\label{item:lin-ind}
$\alpha$ and $\beta$ are linearly independent over $\Q$;
\item\label{item:irrat}
$\sqrt{\Disc}$ is irrational.
  \end{compactenum}
\end{lemma}

\begin{proof}
  If $\alpha=0$, then $\Disc=0$ by \eqref{eqn:D-as-square},
  so~\eqref{item:Dnot0},~\eqref{item:lin-ind},
  and~\eqref{item:irrat} all fail.  Suppose $\alpha\neq0$.  Then we
  can write $\beta/\alpha$ as $r+t\sqrt d$ for some $r$ and $t$ in $\Q$.
  From~\eqref{eqn:D-as-square}, we have
  \begin{multline*}
    \Disc=\biggl(\alpha\alpha'\Bigl(\frac{\beta'}{\alpha'}
    -\frac{\beta}{\alpha}\Bigr)\biggr)^2 
=\norm{\alpha}^2\biggl(\Bigl(\frac{\beta}{\alpha}\Bigr)'
    -\Bigl(\frac{\beta}{\alpha}\Bigr)\biggr)^2\\
=\norm{\alpha}^2\cdot4t^2d
=(2t\norm{\alpha})^2\cdot d.
  \end{multline*}
Since $2t\norm{\alpha}\in\Q$, we have
\begin{equation*}
  \sqrt{\Disc}\in\Q\iff \Disc=0\iff t=0\iff\beta/\alpha\in\Q.
\end{equation*}
Thus,~\eqref{item:Dnot0},~\eqref{item:lin-ind},
  and~\eqref{item:irrat} are again equivalent.
\end{proof}

We have observed that two lattices $\latt$ and $\latt[\gamma,\delta]$ of
$K$ are the same lattice $\mLambda$ if and only if
\begin{equation*}
  \begin{pmatrix}
    \gamma\\\delta
  \end{pmatrix}=
  \begin{pmatrix}
    a&b\\c&d
  \end{pmatrix}
  \begin{pmatrix}
    \alpha\\\beta
  \end{pmatrix}
\end{equation*}
for some $a$, $b$, $c$, and $d$ in $\Z$ such that $ad-bc=\pm1$.  In
this case, 
\begin{equation*}
  \begin{pmatrix}
    \gamma&\gamma'\\\delta&\delta'
  \end{pmatrix}=
  \begin{pmatrix}
    a&b\\c&d
  \end{pmatrix}
  \begin{pmatrix}
    \alpha&\alpha'\\\beta&\beta'
  \end{pmatrix},
\end{equation*}
so that
\begin{equation*}
  \begin{vmatrix}
    \gamma&\gamma'\\\delta&\delta'
  \end{vmatrix}^2=
  \begin{vmatrix}
    \alpha&\alpha'\\\beta&\beta'
  \end{vmatrix}^2.
\end{equation*}
This number is the \defn{discriminant}{} of $\mLambda$, and we
write%
\index{$\disc{\mLambda}$, $\disc{\alpha,\beta}$}
\begin{equation}\label{eqn:disc}
  \disc{\mLambda}=\disc{\alpha,\beta}=  
\begin{vmatrix}
    \alpha&\alpha'\\\beta&\beta'
  \end{vmatrix}^2.
\end{equation}
This is the discriminant of the quadratic forms
$\norm{\alpha x+\beta y}$
and $\norm{\gamma x+\delta y}$,
by \eqref{eqn:D-as-det}.


\begin{lemma}\label{lem:2-gen}
  Suppose $\alpha,\beta\in K$.
  \begin{compactenum}
    \item\label{item:dab}
$\disc{\alpha,\beta}\in\Q$;
\item\label{item:abroi}
$\alpha,\beta\in\roi\implies\disc{\alpha,\beta}\in\Z$;
\item\label{item:d=0}
$\{\alpha,\beta\}$ is a basis for $K$ if and only if
  $\disc{\alpha,\beta}\neq0$. 
  \end{compactenum}
\end{lemma}

\begin{proof}
  We have~\eqref{item:dab} by what we have just noted,
  and~\eqref{item:d=0} by Lemma~\ref{lem:D}.
  As for~\eqref{item:abroi}, if $\alpha,\beta\in\roi$, then
  $\disc{\alpha,\beta}\in\roi\cap\Q$,
  which is $\Z$ by an exercise.
\end{proof}


\topic{Quadratic form example}

Suppose 
\begin{equation*}
f(x,y)=2x^2+6xy+3y^2.
\end{equation*}
Then $\Disc=36-24=12=2^2\cdot3$.\label{last-Disc}  
Also
\begin{align*}
  f(x,y)
&=2\Bigl(x^2+3xy+\frac32y^2\Bigr) \\
&=2\Bigl(x-\frac{-3+2\sqrt3}2y\Bigr)\Bigl(x-\frac{-3+2\sqrt 3}2y\Bigr)\\
&=\frac12\bigl(2x+(3+2\sqrt3)y\bigr)\bigl(2x+(3-2\sqrt3)y\bigr). 
\end{align*}
So we have a bijection $(x,y)\mapsto 2x+(3+2\sqrt3)y$ between the sets
\begin{gather*}
\{(x,y)\in\Z\times\Z\colon f(x,y)=m\},\\
\{\xi\in\latt[2,3+2\sqrt3]\colon\norm{\xi}=2m\},
\end{gather*}
where the norm is
computed in $\Q(\sqrt3)$.  We can write the form as a matrix product:
\begin{equation*}
  f(x,y)=
  \begin{pmatrix}
    x&y
  \end{pmatrix}
  \begin{pmatrix}
    2&3\\3&3
  \end{pmatrix}
  \begin{pmatrix}
    x\\y
  \end{pmatrix}.
\end{equation*}
Then making a change of variable, as by
\begin{equation*}
  \begin{pmatrix}
    x\\y
  \end{pmatrix}=
  \begin{pmatrix}
    a&b\\c&d
  \end{pmatrix}
  \begin{pmatrix}
    u\\v
  \end{pmatrix},
\end{equation*}
means forming a new product
\begin{equation*}
  \begin{pmatrix}
    u&v
  \end{pmatrix}
  \begin{pmatrix}
    a&c\\b&d
  \end{pmatrix}
  \begin{pmatrix}
    2&3\\3&3
  \end{pmatrix}
  \begin{pmatrix}
    a&b\\c&d
  \end{pmatrix}
  \begin{pmatrix}
    u\\v
  \end{pmatrix}.
\end{equation*}
Such a change may be useful particularly if what we want to understand
is the possible values of $f(x,y)$.


\topic{Lattices}

Again $d$ and $K$ are as on page \pageref{d},
and $\omega$, in \eqref{omega} on page \pageref{omega}.

\begin{lemma}\label{lem:lat-cond}
  Let $L$ be a subset of $K$.  Then $L$ is a lattice of $K$ if and
  only if:
  \begin{compactenum}
    \item\label{item:+}
$L$ is an additive subgroup of $K$ (that is, $K$ contains $0$ and is
      closed under addition and subtraction);
\item\label{item:span}
as a vector-space, $K$ is spanned by $L$ (over $\Q$);
\item\label{item:nL}
$nL\included\roi$ for some $n$ in $\Z\setminus\{0\}$.
  \end{compactenum}
\end{lemma}

\begin{proof}
Suppose $L$ is a lattice of $K$.
Then~\eqref{item:+} and~\eqref{item:span} hold by definition of lattice.
Also $L=\latt$ for some $\alpha$ and $\beta$ in $K$.
But $\roi$ is the lattice $\latt[1,\omega]$ by Theorem \ref{thm:roi}.
In particular, $(1,\omega)$ spans $K$.
So $\alpha=k+\ell\omega$ and $\beta=r+s\omega$
for some $k$, $\ell$, $r$, and $s$ in $\Q$.
Let $n$ be a common multiple of their denominators.
Then $n\alpha$ and $n\beta$ are in $\roi$, so \eqref{item:nL} holds.

Suppose conversely that~\eqref{item:+},~\eqref{item:span},
and~\eqref{item:nL} hold.
Then $L$ contains $\alpha$ and $\beta$ such that
$\{\alpha,\beta\}$ is a basis for $K$;
and there is $n$ in $\Z\setminus\{0\}$ such that, for every such basis,
$n\alpha$ and $n\beta$ are in $\roi$.
By Lemma~\ref{lem:2-gen}, this means $\disc{n\alpha,n\beta}\in\Z$.
Also $\disc{\alpha,\beta}\neq0$.
So we may suppose $\alpha$ and $\beta$ have been chosen from $L$
so as to minimize $\size{\disc{n\alpha,n\beta}}$,
which is $n^4\size{\disc{\alpha,\beta}}$.
We shall show $L=\latt$.
Suppose $\gamma\in L$.  Then $\gamma\in K$, so 
\begin{equation*}
  \gamma=\alpha r+\beta s
\end{equation*}
for some $r$ and $s$ in $\Q$.  We want to show $r$ and $s$ are in $\Z$.
Since
\begin{equation*}
  \gamma-\alpha[r]=\alpha(r-[r])+\beta s,
\end{equation*}
we compute
\begin{equation*}
\disc{\gamma-\alpha[r],\beta}=(r-[r])^2\disc{\alpha,\beta},
\end{equation*}
since
\begin{multline*}
  \begin{vmatrix}
\alpha(r-[r])+\beta s  &\alpha'(r-[r])+\beta' s\\
\beta&\beta'
\end{vmatrix}^2\\
=\begin{vmatrix}
\alpha(r-[r])&\alpha'(r-[r])\\
\beta&\beta'
\end{vmatrix}^2
=(r-[r])^2\begin{vmatrix}
\alpha&\alpha'\\
\beta&\beta'
\end{vmatrix}^2.
\end{multline*}
By minimality of $\size{\disc{\alpha,\beta}}$, we must have
$r-[r]=0$, so $r\in\Z$.  By symmetry, $s\in\Z$.
\end{proof}

\myday{March 28, 2008 (Friday)}

\topic{Orders and conductors}

The ring $\End$ is also called the \defn{order}{} of $\mLambda$
and denoted by%
\index{$\ord$}\label{ord}
\begin{equation*}
  \ord.
\end{equation*}
By Lemma~\ref{lem:end-in-roi} (page \pageref{lem:end-in-roi}),
we know that this is a sub-ring of $\roi$,
which is $\latt[1,\omega]$ by Theorem \ref{thm:roi} (page \pageref{thm:roi}).

\begin{lemma}
$\ord$ is also a lattice of $K$. 
\end{lemma}

\begin{proof}
  By Lemma~\ref{lem:lat-cond}, it is enough to show that $\ord$ spans $K$
  over $\Q$.  Write $\mLambda$ as $\latt$.  Let $\gamma\in K$.  Then
  \begin{equation*}
\gamma
    \begin{pmatrix}
      \alpha\\\beta
    \end{pmatrix}=
    \begin{pmatrix}
      r&s\\t&u
    \end{pmatrix}
    \begin{pmatrix}
      \alpha\\\beta
    \end{pmatrix}
  \end{equation*}
for some rational numbers $r$, $s$, $t$, and $u$.  Let $n$ be a common
multiple of their denominators.  Then
$n\gamma\mLambda\included\mLambda$, that is, $n\gamma\in\ord$.  But
$\gamma=(1/n)n\gamma$. 
\end{proof}

\begin{theorem}\label{thm:cond}
For some positive rational integer $c$,
\begin{equation}\label{eqn:c}
  \ord=\latt[1,c\omega].
\end{equation}
\end{theorem}

\begin{proof}
We know $1\in\ord$ and $\ord\included\latt[1,\omega]$.
Since $\ord$ is a lattice,
it must therefore have an irrational element $m+n\omega$,
where $m$ and $n$ are rational integers and $n\neq0$.
Then $n\omega\in\ord$.
Let $c$ be the least positive such $n$.
Then for \emph{any} such $n$ we have $\gcd(c,n)\omega\in\ord$,
and so $c\divides n$.
Now \eqref{eqn:c} follows.
\end{proof}

The number $c$ is the \defn{conductor}{} of $\ord$. 

\begin{theorem}\label{thm:homothety}
  $\ord[\gamma\mLambda]=\ord$ for all non-zero $\gamma$ in $K$.
\end{theorem}

\begin{proof}
  Since $\xi\mapsto\gamma\xi$ is a bijection from $K$ to itself,
  \begin{equation*}
    \xi\mLambda\included\mLambda\iff
    \xi\gamma\mLambda\included\gamma\mLambda.\qedhere
  \end{equation*}
\end{proof}

In looking for $\ord$, we may therefore assume that
\conv{$\mLambda$ is the lattice $\latt[1,\tau]$,}\label{tau}
where $\tau=\beta/\alpha$,
so that also
  \begin{equation*}
    a\tau^2+b\tau+c=0
  \end{equation*}
for some $a$, $b$, and $c$ in $\Z$, where $\gcd(a,b,c)=1$ and $a>0$.
Then
\begin{equation*}
  a\tau^2=-b\tau-c,
\end{equation*}
which shows $\latt[1,a\tau]\included\ord$.
That this inclusion is an equality can be seen first in some examples.
If $b=0$ and $c=1$, so $a\tau^2=-1$,
we may assume $\tau=\mi/\sqrt a$, as in Figure~\ref{fig:lat-end-1}.
\begin{figure}[ht]
  %\centering
  \psset{unit=7mm}
\begin{pspicture}(-2.5,-0.5)(2.5,2.5)
    \psline{->}(-2.5,0)(2.5,0)
    \psline{->}(0,-0.5)(0,2.5)
\psdots(-2,0)(0,0)(2,0)(-2,2)(0,2)(2,2)
\uput[ur](0,2){$\mi$}
\uput[dl](2,0){$1$}
  \end{pspicture}
\hfill
  \begin{pspicture}(-2.5,-0.5)(2.5,2.5)
    \psline{->}(-2.5,0)(2.5,0)
    \psline{->}(0,-0.5)(0,2.5)
\psdots(-2,0)(0,0)(2,0)(-2,1.414)(0,1.414)(2,1.414)
\uput[ur](0,1.414){$\mi/\sqrt 2$}
\uput[dl](2,0){$1$}
  \end{pspicture}
\hfill
  \begin{pspicture}(-2.5,-0.5)(2.5,2.5)
    \psline{->}(-2.5,0)(2.5,0)
    \psline{->}(0,-0.5)(0,2.5)
\psdots(-2,0)(0,0)(2,0)(-2,1.155)(0,1.155)(2,1.155)
\uput[ur](0,1.155){$\mi/\sqrt 3$}
\uput[dl](2,0){$1$}
  \end{pspicture}
\caption{Lattices $\latt[1,\mi/\sqrt a]$}\label{fig:lat-end-1}
\end{figure}
If $b=-1$ and $c=1$, so $a\tau^2=\tau-1$,
we may assume
$\tau=(1+\mi\oldsqrt{4a-1})/2a$,
and again $\size{\tau}=1/\sqrt a$,
as in Figure~\ref{fig:lat-end-2}.
\begin{figure}[ht]
%\centering
  \psset{unit=7mm}
\begin{pspicture}(-2.5,-0.5)(2.5,3)
%\psgrid
    \psline{->}(-2.5,0)(2.5,0)
    \psline{->}(0,-0.5)(0,2.5)
\psdots(-2,0)(0,0)(2,0)(-1,1.732)(1,1.732)
\uput[ur](1,1.732){$\displaystyle\frac{1+\mi\sqrt 3}2$}
\uput[dl](2,0){$1$}
  \end{pspicture}
\hfill
  \begin{pspicture}(-2.5,-0.5)(2.5,2.8)
%\psgrid
    \psline{->}(-2.5,0)(2.5,0)
    \psline{->}(0,-0.5)(0,2.5)
\psdots(-2,0)(0,0)(2,0)(-1.5,1.323)(0.5,1.323)
\uput[ur](0.5,1.323){$\displaystyle\frac{1+\mi\sqrt 7}4$}
\uput[dl](2,0){$1$}
  \end{pspicture}
\hfill
  \begin{pspicture}(-2.5,-0.5)(2.5,2.8)
%\psgrid
    \psline{->}(-2.5,0)(2.5,0)
    \psline{->}(0,-0.5)(0,2.5)
\psdots(-2,0)(0,0)(2,0)(-1.667,1.106)(0.333,1.106)
\uput[ur](0.333,1.106){$\displaystyle\frac{1+\sqrt{11}}6$}
\uput[dl](2,0){$1$}
  \end{pspicture}
\begin{comment}


  \begin{pspicture}(-2.5,-0.5)(2,2)
    \psdots(-2,0)(0,0)(2,0)(1,1.732)(-1,1.732)
\uput[d](-2,0){$-1$}
\uput[d](0,0){$0$}
\uput[d](2,0){$1$}
\uput[ur](1,1.732){$\tau$}
\uput[ul](-1,1.732){$\tau^2$}
\uput[d](0,1){$a=1$}
  \end{pspicture}
\hfill
  \begin{pspicture}(-2,-0.5)(2,1.5)
    \psdots(-2,0)(0,0)(2,0)(0.5,1.323)(-1.5,1.323)
\uput[d](-2,0){$-1$}
\uput[d](0,0){$0$}
\uput[d](2,0){$1$}
\uput[ur](0.5,1.323){$\tau$}
\uput[ul](-1.5,1.323){$2\tau^2$}
\uput[d](0,1){$a=2$}
  \end{pspicture}
\hfill
  \begin{pspicture}(-2,-0.5)(2.2,1.5)
    \psdots(-2,0)(0,0)(2,0)(0.333,1.106)(-1.666,1.106)
\uput[d](-2,0){$-1$}
\uput[d](0,0){$0$}
\uput[d](2,0){$1$}
\uput[ur](0.333,1.106){$\tau$}
\uput[ul](-1.666,1.106){$3\tau^2$}
\uput[d](0,1){$a=3$}
  \end{pspicture}


\end{comment}
\caption{Lattices
  $\latt[1,(1+\mi\protect\oldsqrt{4a-1})/2a]$}\label{fig:lat-end-2} 
\end{figure}

\begin{theorem}\label{thm:conductor}
$\ord=\latt[1,a\tau]$.
\end{theorem}

\begin{proof}
We have first
\begin{align*}
  %&\phantom{{}\iff{}}
  \theta\in\ord
&\iff\theta\latt[1,\tau]\included\latt[1,\tau]\\
  &\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}

\myweek

\myday{April 1, 2008 (Tuesday)}

What then is the conductor of $\ord$?  Since
\begin{equation*}
  \tau=\frac{-b\pm\oldsqrt{b^2-4ac}}{2a},
\end{equation*}
but $\tau\in K$, we have
\begin{equation}\label{eqn:s}
\oldsqrt{b^2-4ac}=s\sqrt d
\end{equation}
for some $s$ in $\Z$.
This gives us
\begin{align*}
  \ord&=\Bigl\langle1,\frac{-b\pm s\sqrt d}2\Bigl\rangle,&
  b^2&\equiv s^2d\pmod 4.
\end{align*}

\begin{theorem}
  The conductor of $\ord$ is
  \begin{itemize}
  \item
$s/2$, when $d\not\equiv1\pmod4$,
\item
$s$, when $d\equiv1\pmod4$,
  \end{itemize}
where $s$ is as in \eqref{eqn:s}.
\end{theorem}

\begin{proof}
If $d$ is congruent to $2$ or $3$, 
then (since squares are congruent to $0$ or $1$), 
we must have $s^2\equiv0$, so $s$ is even, and then $b$ is even,
so that
\begin{equation*}
  \ord=\Bigl\langle1,\frac s2\sqrt d\Bigr\rangle
=\Bigl\langle1,\frac s2\omega\Bigr\rangle.
\end{equation*}
If $d\equiv1$, then $s^2\equiv b^2$, so $b\pm s$ is even, and hence
\begin{equation*}
  \ord=\Bigl\langle1,\frac{-b\mp s\pm s\pm s\sqrt d}2\Bigr\rangle
%=\Bigl\langle1,\pm s\frac{1\pm\sqrt d}2\Bigr\rangle;
=\latt[1,s\omega].\qedhere
\end{equation*}
\end{proof}

To sum up the last four theorems:\label{summary}
\begin{compactitem}
  \item
For the lattice $\mLambda$ or $\latt$ of $K$,
for some conductor $c$, the endomorphism ring $\ord$
is $\latt[1,c\omega]$.
\item
We may replace $\mLambda$ with $\latt[1,\tau]$,
where $\tau=\beta/\alpha$.
\item
If $\tau$ solves $ax^2+bx+c=0$,
the coefficients having no common factor,
then $\ord$ is $\latt[1,a\tau]$.
\item
Moreover, $\ord$ is $\latt[1,s\upomega/2]$ or $\latt[1,s\upomega]$,
where $d$ is not or is congruent to $1$ \emph{modulo} $4$ respectively,
and $s^2d=b^2-4ac$.
\end{compactitem}
Conversely, we have the following.

\begin{theorem}\label{thm:all-cond}
  For every $d$,
for every positive rational integer $c$,
when $\tau=c\omega$, then $\ord=\mLambda$.
\end{theorem}

\begin{proof}
Let $\tau=c\omega$.
\begin{compactitem}
\item
If $d\not\equiv1\pmod4$, then $\tau^2-c^2d=0$.  
\item
If $d\equiv1\pmod4$, then $\tau^2-c\tau-c^2(d-1)/4=0$.\qedhere
\end{compactitem}
\end{proof}


\topic{Units}

If, for some $d$, 
we can bring a quadratic Diophantine equation into the form
\begin{equation}\label{eqn:n(xa+yb)=m}
 \norm{x\alpha+y\beta}=m, 
\end{equation}
then its solutions correspond to the solutions from $\mLambda$
of
\begin{equation*}
\norm{\xi}=m.  
\end{equation*}
From any of the latter solutions,
we obtain another by multiplying by a solution from $\ord$
of
\begin{equation*}
  \norm{\eta}=1.
\end{equation*}

\begin{lemma}
The units of $\ord$, which itself is $\latt[1,c\omega]$, 
are just those elements that solve $\norm{\xi}=\pm1$;
and these are the elements $x+c\omega y$ 
such that,
when $d\not\equiv1$ and $d\equiv1$ respectively $\pmod 4$,
\begin{gather}\label{eqn:units23}
x^2-d(cy)^2=\pm1,\\\label{eqn:units1}
\left(x+\frac{cy}2\right)^2-\frac d4(cy)^2=\pm1.  
\end{gather}
\end{lemma}

\begin{proof}
Since $\ord\included\roi$,
%(originally by Lemma~\ref{lem:end-in-roi}, page \pageref{lem:end-in-roi},
%and now Theorem \ref{thm:cond}, page \pageref{thm:cond}),
the norms of its elements are rational integers,
by Theorem \ref{thm:int} (page \pageref{thm:int}).
%$\norm{\alpha}\in\Z$ for all $\alpha$ in $\ord$.
Suppose $\alpha$ is a unit of $\ord$.  
Then $\alpha\neq0$ and $\alpha\inv\in\ord$.  
But $1=\norm1=\norm{\alpha\alpha\inv}=\norm{\alpha}\norm{\alpha\inv}$,
and since these factors are in $\Z$,
we have that $\norm{\alpha}$ is a unit in $\Z$,
that is, $\norm{\alpha}=\pm1$.

Suppose conversely $\alpha\in\ord$ and $\norm{\alpha}=\pm1$.
This means $\alpha\alpha'=\pm1$, so $\alpha\inv=\pm\alpha'$.
But $\ord$ is closed under $\xi\mapsto\xi'$,
since $\ord=\latt[1,c\omega]$,
and $\omega'$ is either $-\omega$ or $1-\omega$.
Therefore $\alpha\inv\in\ord$, so $\alpha$ is a unit of $\ord$.  
\end{proof}


\topic{Imaginary case}

The easier case to consider is $d<0$, when $\norm{\xi}=\size{\xi}^2$,
which is not negative,
so only the positive signs in \eqref{eqn:units23} and \eqref{eqn:units1}
need be considered.
In particular, all units of $\ord$ lie on the unit circle,
as in Figure~\ref{fig:units},
\begin{figure}[ht]
\centering
\begin{pspicture}(-2.8,-2.8)(2.8,2.8)
%\psgrid
    \pscircle(0,0)2
    \psdots[dotsize=2pt 3]
(2,0)(1,1.732)(0,2)(-1,1.732)(-2,0)(-1,-1.732)(0,-2)(1,-1.732)
\uput[dr](2,0){$1$}
\uput[ur](1,1.732){$\displaystyle\frac{1+\mi\sqrt 3}2$}
\uput[ur](0,2){$\mi$}
\uput[ul](-1,1.732){$\displaystyle\frac{-1+\mi\sqrt 3}2$}
\uput[ul](-2,0){$-1$}
\uput[dl](-1,-1.732){$\displaystyle\frac{-1-\mi\sqrt 3}2$}
\uput[dl](0,-2){$-\mi$}
\uput[dr](1,-1.732){$\displaystyle\frac{1-\mi\sqrt 3}2$}
\psline{->}(-2.8,0)(2.8,0)
\psline{->}(0,-2.8)(0,2.8)
  \end{pspicture}
\caption{Units in imaginary quadratic fields}\label{fig:units}
\end{figure}
which indeed shows all of the possibilities,
by the following.

\begin{theorem}\label{thm:units}
  When $d<0$, then the units of $\latt[1,c\omega]$ are:
  \begin{compactenum}
    \item
$\pm1$ and $\pm\omega$, when $c=1$ and $d=-1$;
\item
$\pm1$, $\pm\omega'$, and $\pm\omega$, when $c=1$ and $d=-3$;
\item
$\pm1$, in all other cases.
  \end{compactenum}
\end{theorem}

\begin{proof}
If $d\not\equiv1$, then~\eqref{eqn:units23} has the solutions
\begin{compactenum}
  \item
$(\pm1,0)$, if $c>1$ or $d<-1$;
\item
$(\pm1,0)$ and $(0,\pm1)$, if $c=1$ and $d=-1$.
\end{compactenum}
If $d\equiv1$, then either $d=-3$, or else $d\leq-7$.  In the latter
case, the only solutions to~\eqref{eqn:units1} are $(\pm1,0)$.  But if
$d=-3$, so that~\eqref{eqn:units1} becomes
\begin{equation*}
x^2+x\cdot cy+(cy)^2=1,
%\Bigl(x+\frac c2y\Bigr)^2+3\left(\frac c2y\right)^2=1,  
\end{equation*}
then the solutions are
\begin{compactenum}
  \item
$(\pm1,0)$, if $c>1$;
\item
$(\pm1,0)$, $(\pm1,\mp1)$, and $(0,\pm1)$, if $c=1$.\qedhere
\end{compactenum}
\end{proof}


\begin{problem}\label{prob:qDe1}
Solve the quadratic Diophantine equation
\begin{equation}\label{eqn:qDe1}
x^2+xy+y^2=3.
\end{equation}
\end{problem}

\begin{solution}
We complete the square.
Since
\begin{equation*}
  x^2+xy+y^2
=x^2+xy+\frac14y^2+\frac34y^2,  
\end{equation*}
we can rewrite \eqref{eqn:qDe1} as
\begin{equation}\label{eqn:qDe1-2}
  \left(x+\frac y2\right)^2+\frac34y^2=3.
\end{equation}
This defines the ellipse shown in Figure \ref{fig:qDe1-ell},
\begin{figure}
\centering
\begin{pspicture}(-4,-3)(4,3)
\parametricplot{0}{360}{1.732 t cos mul t sin sub t sin 2 mul}
\psline{->}(-4,0)(4,0)
\psline{->}(0,-3)(0,3)
\uput[d](1,-2){$(1,-2)$}
\uput[u](-1,2){$(-1,2)$}
\uput[dl](! 3 sqrt neg 0){($-\sqrt 3,0)$}
\uput[ur](! 3 sqrt 0){($\sqrt 3,0)$}
\psdots(1,-2)(-1,2)(! 3 sqrt neg 0)(! 3 sqrt 0)
\psset{linestyle=dashed}
\psline(-1,2)(1,-2)
\psset{linestyle=dotted}
\pspolygon(! 3 sqrt neg 1 sub  2)
          (! 3 sqrt     1 sub  2)
          (! 3 sqrt     1 add -2)
          (! 3 sqrt neg 1 add -2)
  \end{pspicture}
\caption{Ellipse $\frac13\left(x+\frac12y\right)^2+\frac14y^2=1$}
\label{fig:qDe1-ell}
\end{figure}
of which each of the lines $y=2x$ and $y=0$
is a \tech{diameter}{} (\gk{di'ametros}) 
that is \tech{conjugate}{} (\gk{suzug'hs}) to the other
in the sense of Apollonius (\cite[\textsc i.16, p.\ 64]{Apollonius-Heiberg}
or \cite{MR1660991}),
namely that each of the lines bisects the chords of the ellipse 
that are parallel to the other line.
The figure suggests where to look for the solutions to \eqref{eqn:qDe1};
they are
\begin{align*}
  &(\pm1,\pm1),&&(\mp1,\pm2),&&(\pm2,\mp1),
\end{align*}
as shown in Figure \ref{fig:qDe1-2}.
\begin{figure}
\centering
\begin{pspicture}(-3,-2.5)(3,2.5)
\parametricplot{0}{360}{1.732 t cos mul t sin sub t sin 2 mul}
\psdots
(-2,2)(-1, 2)(0, 2)
(-2,1)(-1, 1)(0, 1)(1, 1)
(-2,0)(-1, 0)(0, 0)(1, 0)(2, 0)
      (-1,-1)(0,-1)(1,-1)(2,-1)
             (0,-2)(1,-2)(2,-2)
\uput[ur](1,1){$(1,1)$}
\uput[u](-1,2){$(-1,2)$}
\uput[l](-2,1){$(-2,1)$}
\uput[dl](-1,-1){$(-1,-1)$}
\uput[d](1,-2){$(1,-2)$}
\uput[r](2,-1){$(2,-1)$}
  \end{pspicture}
\caption{Solutions of $x^2+xy+y^2=3$}\label{fig:qDe1-2}
\end{figure}

Alternatively,
instead of sketching an ellipse,
we may just observe that $(1,1)$ is a solution to our equation.
To find the others,
letting $d=-3$, we write \eqref{eqn:qDe1} as
\begin{equation*}
  \norm{x+\omega y}=3.
\end{equation*}
Letting $\mLambda=\latt[1,\omega]$, 
we have $\ord=\mLambda=\roi$, 
which by Theorem \ref{thm:units} 
has the six units $\pm1$, $\pm\omega$, and $\pm\omega'$, 
each having norm $1$.
Since $1+\omega$ is a solution of
\begin{equation*}
  \norm{\xi}=3
\end{equation*}
from $\mLambda$, so are $\pm(1+\omega)$, $\pm\omega(1+\omega)$, and
$\pm\omega'(1+\omega)$.  
Since $\omega^2-\omega+1=0$, and $\omega+\omega'=1$, these solutions
are 
\begin{align*}
 &\pm(1+\omega),&&\pm(2\omega-1),&&\pm(2-\omega)
\end{align*}
as in
Figure~\ref{fig:qDe1},
\begin{figure}
  \centering
  \begin{pspicture}(-3,-2.2)(3,2.2)
%\psgrid
    \pscircle(0,0){1.732}
\psdots
        (-1,1.732)( 0,1.732)(1,1.732)
(-1.5,0.866)(-0.5,0.866)(0.5,0.866)(1.5,0.866)
(-2,0)(-1,0)(0,0)(1,0)(2,0)
(-1.5,-0.866)(-0.5,-0.866)(0.5,-0.866)(1.5,-0.866)
(-1,-1.732)(0,-1.732)(1,-1.732)
%\uput[d](0,0){$0$}
%\uput[d](1,0){$1$}
%\uput[d](0.5,0.866){$\omega$}
\uput[r](1.5,0.866){$1+\omega$}
\uput[u](0,1.732){$-1+2\omega$}
\uput[l](-1.5,0.866){$-2+\omega$}
\uput[l](-1.5,-0.866){$-1-\omega$}
\uput[d](0,-1.732){$1-2\omega$}
\uput[r](1.5,-0.866){$2-\omega$}
  \end{pspicture}
\caption{Solutions of $\norm{\xi}=3$ from $\latt[1,\omega]$ in
  $\Q(\sqrt{{-3}})$}\label{fig:qDe1}  
\end{figure}
corresponding to the solutions to \eqref{eqn:qDe1}.
It is now easy to see from Figure \ref{fig:qDe1}
that there are no other solutions.
\end{solution}


\begin{problem}\label{prob:qDe2}
Solve
\begin{equation}\label{eqn:qDe2}
  4x^2+2xy+y^2=7.
\end{equation}
\end{problem}

\begin{solution}
We complete the square in $y$ now,
because it seems simpler, getting
\begin{equation}\label{eqn:qDe2-2}
  3x^2+(x+y)^2=7.
\end{equation}
This defines the ellipse shown in Figure \ref{fig:qDe2-ell},
\begin{figure}
\centering
\psset{unit=8mm}
\begin{pspicture}(-4,-4.2)(4,4.2)
    \parametricplot{0}{360}{7 3 div sqrt t cos mul 7 sqrt t sin mul 7 3 div
    sqrt t cos mul sub}
\psline{->}(0,-4.2)(0,4.2)
\psline{->}(-4,0)(4,0)
\uput[ur](! 0 7 sqrt){$(0,\sqrt 7)$}
\uput[dl](! 0 7 sqrt neg){$(0,-\sqrt 7)$}
\uput[r](! 7 3 div sqrt 7 3 div sqrt neg){$(\sqrt{\frac73},-\sqrt{\frac73})$}
\uput[l](! 7 3 div sqrt neg 7 3 div sqrt){$(-\sqrt{\frac73},\sqrt{\frac73})$}
\psline[linestyle=dashed]
(! 7 3 div sqrt neg 7 3 div sqrt)
(! 7 3 div sqrt 7 3 div sqrt neg)
\psdots
(! 7 3 div sqrt neg 7 3 div sqrt)
(! 7 3 div sqrt 7 3 div sqrt neg)
(! 0 7 sqrt)
(! 0 7 sqrt neg)
\psset{linestyle=dotted}
\pspolygon(! 7 3 div sqrt neg 7 3 div sqrt     7 sqrt add)
          (! 7 3 div sqrt     7 3 div sqrt neg 7 sqrt add)
          (! 7 3 div sqrt     7 3 div sqrt neg 7 sqrt sub)
          (! 7 3 div sqrt neg 7 3 div sqrt     7 sqrt sub)
  \end{pspicture}
\caption{Ellipse $\frac37x^2+\frac17(x+y)^2=1$}\label{fig:qDe2-ell}
\end{figure}
with conjugate diameters $x=0$ and $y=-x$.
We find the integer points as shown in Figure \ref{fig:qDe2-2}.
\begin{figure}
\centering
\psset{unit=8mm}
\begin{pspicture}(-2,-3.5)(2,3.5)
    \parametricplot{0}{360}{7 3 div sqrt t cos mul 7 sqrt t sin mul 7 3 div
    sqrt t cos mul sub}
\psdots
       (-1, 3)(0, 3)
 (-2,2)(-1, 2)(0, 2)(1, 2)
 (-2,1)(-1, 1)(0, 1)(1, 1)
 (-2,0)(-1, 0)(0, 0)(1, 0)(2, 0)
       (-1,-1)(0,-1)(1,-1)(2,-1)
       (-1,-2)(0,-2)(1,-2)(2,-2)
              (0,-3)(1,-3)
\uput[r](1,1){$(1,1)$}
\uput[ul](-1,3){$(-1,3)$}
\uput[l](-1,-1){$(-1,-1)$}
\uput[dr](1,-3){$(1,-3)$}
  \end{pspicture}
\caption{Solutions to $4x^2+2xy+1=7$}\label{fig:qDe2-2}
\end{figure}

Alternatively, one solution is $(1,1)$.  
From \eqref{eqn:qDe2-2}, we factorize:
\begin{multline}\label{eqn:factors}
3x^2+(x+y)^2
=(\sqrt 3x+\mi(x+y))(\sqrt 3x-\mi(x+y))\\
=((\sqrt3+\mi)x+\mi y)((\sqrt3-\mi)x-\mi y),  
\end{multline}
but this is not over a quadratic field, 
since a field that contains $\sqrt 3+\mi$ and $\mi$ 
contains also $\sqrt 3$, and
$[\Q(\sqrt3,\mi):\Q]=4$ as in Figure~\ref{fig:fields}.
\begin{figure}
\centering\begin{equation*}
  \xymatrix
{& \Q(\sqrt3,\mi) \\
\Q(\sqrt3) \ar@{-}[ur]^2 &&\Q(\mi) \ar@{-}[ul]_2\\
&\Q \ar@{-}[ul]^2 \ar@{-}[ur]_2}
\end{equation*}
\caption{Subfields of $\Q(\sqrt 3,\mi)$}\label{fig:fields}
\end{figure}
We can fix this problem by multiplying each factor
in~\eqref{eqn:factors} by the appropriate unit, such as $-\mi$ and $\mi$.
What amounts to the same thing is to perform the alternative factorization
\begin{multline*}
3x^2+(x+y)^2
=(x+y)^2+3x^2\\
=(x+y+x\sqrt{{-3}})(x+y-x\sqrt{{-3}}),
\end{multline*}
so that, letting $d=-3$, we can write \eqref{eqn:qDe2} as
\begin{equation*}
  \norm{y+2\omega x}=7.
\end{equation*}
Letting $\mLambda=\latt[1,2\omega]$,
we want to solve
\begin{equation}\label{eqn:qDe2-3}
  \norm{\xi}=7
\end{equation}
in $\mLambda$.  We know one solution, namely $1+2\omega$.
By Theorem \ref{thm:all-cond},
$\ord=\mLambda$.  
The only units of this are $\pm1$,
by Theorem \ref{thm:units}.
Hence we have the solutions $\pm(1+2\omega)$
of~\eqref{eqn:qDe2-3}.  To find any others, again we
can draw a picture, Figure~\ref{fig:qDe2}.
\begin{figure}[ht]
\centering
\begin{pspicture}(-3,-2.5)(3,2.5)
\pscircle(0,0){2.646}
\psset{dotsize=2pt 3}
    \psdots
%(-2,3.464)(-1,3.464)(0,3.464)(1,3.464)(2,3.464)
(-2,1.732)(-1,1.732)(0,1.732)(1,1.732)(2,1.732)
(-3,0)(-2,0)(-1,0)(0,0)(1,0)(2,0)(3,0)
(-2,-1.732)(-1,-1.732)(0,-1.732)(1,-1.732)(2,-1.732)
%(-2,-3.464)(-1,-3.464)(0,-3.464)(1,-3.464)(2,-3.464)
\psset{dotstyle=o}
\psdots
(-1.5,2.598)(-0.5,2.598)(0.5,2.598)(1.5,2.598)
(-2.5,0.866)(-1.5,0.866)(-0.5,0.866)(0.5,0.866)(1.5,0.866)(2.5,0.866)
(-2.5,-0.866)(-1.5,-0.866)(-0.5,-0.866)(0.5,-0.866)(1.5,-0.866)(2.5,-0.866)
(-1.5,-2.598)(-0.5,-2.598)(0.5,-2.598)(1.5,-2.598)
\uput[ur](2,1.732){$1+2\omega$}
\uput[ul](-2,1.732){$2\omega-3$}
\uput[dl](-2,-1.732){$-1-2\omega$}
\uput[dr](2,-1.732){$3-2\omega$}
  \end{pspicture}
\caption{Solutions of $\norm{\xi}=7$ from
  $\latt[1,2\omega]$ in $\Q(\sqrt{{-3}})$}\label{fig:qDe2} 
\end{figure}
So~\eqref{eqn:qDe2-3} has the solutions 
$\pm(1+2\omega)$ and $\pm(3-2\omega)$ in $\latt[1,2\omega]$,
but no others (though there are more solutions in $\latt[1,\omega]$).  
The solutions of~\eqref{eqn:qDe2} 
are therefore $(\pm1,\pm1)$ and $(\mp1,\pm3)$
(as we already saw in Figure \ref{fig:qDe2-2},
if we cared to draw it).
\end{solution}


In the same way, we can solve any quadratic Diophantine equation
\begin{equation*}
  ax^2+bxy+cy^2=m,
\end{equation*}
provided $b^2-4ac<0$.  For in this case, the equation defines an
ellipse, which is bounded, so that there are only finitely many
possible solutions to check.


\topic{Real case}

Now we move to the case where $d>0$, so $K\included\R$.  We have
\begin{equation*}
  \latt[1,c\sqrt d]\included\latt[1,c\omega]=\ord.
\end{equation*}
A unit of $\ord$ of the form $x+cy\sqrt d$ thus corresponds to a
solution of \eqref{eqn:units23}.
Since a Pell equation has infinitely many solutions 
by Theorem \ref{thm:pell-min-sol},
we conclude that $\ord$ has infinitely many units.  We want to find them.

Suppose $\epsilon$ is a unit of $\ord$.  Since there are infinitely
many units, there are units other than $\pm1$.  So we may assume
$\epsilon\neq\pm1$.  If $\epsilon<0$, then $-\epsilon$ is a unit
greater than $0$.  So we may assume $\epsilon>0$.  If $0<\epsilon<1$,
then $\epsilon\inv$ is a unit greater than $1$.  So we may assume
$\epsilon>1$.  Also $\epsilon<n$ for some $n$.  But
\begin{equation*}
  \epsilon^2-(\epsilon+\epsilon')\epsilon+\epsilon\epsilon'=0,
\end{equation*}
that is, $\epsilon^2-\tr{\epsilon}\epsilon+\norm{\epsilon}=0$.  Since
$\pm1=\norm{\epsilon}=\epsilon\epsilon'$, we have
$\size{\epsilon'}=\epsilon\inv$.  Hence
\begin{equation*}
 \size{\tr{\epsilon}}= \size{\epsilon+\epsilon'}\leq\epsilon+\epsilon\inv<n+1.
\end{equation*}
This shows that there are only finitely many possibilities for the
equation $x^2-\tr{\epsilon}x+\norm{\epsilon}=0$.  Hence there are only
finitely many units of $\ord$ between $1$ and $n$.  Therefore there is
a least such unit, the \defn{fundamental unit},% 
\index{$\funit$}\label{funit}
which we may denote by
\begin{equation*}
  \funit.
\end{equation*}
Then $(\funit{}^n:n\in\Z)$ is an increasing sequence,
\begin{align*}
  \displaystyle\lim_{n\to\infty}\funit{}^n&=\infty,&
\displaystyle\lim_{n\to-\infty}\funit{}^n&=0.
\end{align*}

\begin{theorem}\label{thm:unit}
When $d>0$, each unit of $\ord$ is $\pm\funit{}^n$ for some $n$ in $\Z$.  
If $\norm{\funit}=1$, then every unit has norm $1$.  
If $\norm{\funit}=-1$, then the units of norm $1$ are $\pm\funit{}^{2n}$.
\end{theorem}

\begin{proof}
We argue as in the proof of Theorem \ref{thm:pell-min-sol}
(page \pageref{thm:pell-min-sol}),
though more easily.
Suppose $\zeta$ is a positive unit of $\ord$.  Then
\begin{equation*}
  \funit{}^n\leq\zeta<\funit{}^{n+1}
\end{equation*}
for some $n$.  Hence $1\leq\funit{}^{-n}\zeta<\funit$.  But
$\funit{}^{-n}\zeta$ is a unit too.  By minimality of $\funit$, we
conclude that $\zeta=\funit{}^n$.
\end{proof}

How do we find $\funit$?

\begin{lemma}\label{lem:not5}
Assuming $d>0$, 
let $\epsilon$ be a unit $x+y\omega$ of $\roi$ such that $\epsilon>1$.  
Then both $x$ and $y$ are positive, 
or else $d=5$ and $\epsilon=\omega$.
\end{lemma}

\begin{proof}
  We have
  \begin{equation*}
  (\omega-\omega')y=\epsilon-\epsilon'\geq\epsilon-\size{\epsilon\inv}>0,
  \end{equation*}
and $\omega>\omega'$, so $y>0$.  Also
\begin{equation*}
1>\size{\epsilon'}=\size{x+y\omega'}; 
\end{equation*}
so since $\omega'<0$, and
hence $y\omega'<0$, we must have $x\geq0$, since $x\in\Z$.  If $x>0$,
we are done.  Suppose $x=0$.  Then
\begin{equation*}
  \pm1=\norm{y\omega}=
  \begin{cases}
    -dy^2,                  &\text{ if }d\not\equiv1\pmod 4;\\
\displaystyle\frac{1-d}4y^2,&\text{ if }d\equiv 1\pmod4.
  \end{cases}
\end{equation*}
The only way this can happen is if $d=5$ and $y=1$ (since $y>0$).
\end{proof}

\myday{April 4, 2008 (Friday)}

\topic{Golden ratio}

When $d=5$, then $\omega=\gr$, the so-called \defn{Golden Ratio}:%
\index{$\gr$ (the Golden Ratio)}
\begin{equation*}
  \gr=\frac{1+\sqrt 5}2.
\end{equation*}
This has an intimate connexion with the sequence $(\Fib n\colon n\in\upomega)$
of \defn{Fibonacci number}{s,}%
\index{$\Fib n$}
 given by 
\begin{equation*}
\Fib 0=0,\quad
\Fib 1=1,\quad
\Fib {n+2}=\Fib n+\Fib {n+1}.
\end{equation*}
We can continue the sequence backwards by writing the last rule as
\begin{equation*}
  \Fib{n-2}=\Fib n-\Fib {n-1}.
\end{equation*}
Then the bi-directional sequence is
\begin{equation*}
\dots13,\ -8,\ 5,\ -3,\ 2,\ -1,\ 1,\ 
0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13\dots 
\end{equation*}

\begin{theorem}\label{thm:Fib}
  The units of the ring of integers of $\Q(\sqrt 5)$
are $\pm\gr^n$; and
\begin{equation}\label{eqn:Fib}
  \gr^n=\Fib {n-1}+\Fib n\gr.
\end{equation}
\end{theorem}

\begin{proof}
Let $K=\Q(\sqrt 5)$.
  By Lemma~\ref{lem:not5}, $\gr$ is the least unit of $\roi$ that is
  greater than~$1$.  Then every unit is $\pm\gr^n$ for some $n$ in
  $\Z$, by Theorem~\ref{thm:unit}.
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}

\myweek

\myday{April 8, 2008 (Tuesday)}

\topic{Real example}

\begin{problem}\label{prob:qDe3}
  Solve the quadratic Diophantine equation
  \begin{equation}\label{eqn:qDe3}
    4x^2+2xy-y^2=4.
  \end{equation}
\end{problem}

\begin{solution}
Completing the square, 
we can rewrite the left member of the equation as either of
\begin{align}\label{eqn:lhs}
&\Bigl(2x+\frac12y\Bigr)^2-\frac54y^2,&
&(2x+y\gr)(2x+y\gr').  
\end{align}
Thus \eqref{eqn:qDe3} defines an hyperbola
with \tech{transverse}{} (\gk{plag'ia}) diameter $y=0$
and \tech{upright}{} (\gk{>orj'ia}) diameter $2x+\frac12y=0$,
each of the lines $2x+y\gr=0$ and $2x+y\gr'=0$ being an asymptote
(\gk{>as'umptotos}), as 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+\frac12y)^2-\frac54y^2=4$}\label{fig:hyperbola}
\end{figure}
We may note the indicated integer points;
but there may be infinitely many others,
and we need a system for finding them.

Letting $d=5$, we can write \eqref{eqn:qDe3} as
\begin{equation*}
\norm{2x+y\gr}=4.  
\end{equation*}
Letting $\mLambda=\latt[2,\gr]$, we have
$\ord=\End[{\latt[1,\gr/2]}]$ by Theorem~\ref{thm:homothety}.  
Since 
\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} that
$\ord=\latt[1,2\gr]$.  
Since $\norm{\gr}=-1$, 
the positive elements of $\ord$ of norm $1$ are 
the powers of the least power $\gr^{2n}$, where $n>0$,
that belongs to $\latt[1,2\gr]$.  
By Theorem~\ref{thm:Fib}, we have the following values.
\begin{equation*}
  \begin{array}{c||c|c|c}
n    &2&4&6\\\hline
\gr^n&1+\gr&2+3\gr&5+8\gr
  \end{array}
\end{equation*}
So 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 from $\mLambda$ of
\begin{equation}\label{eqn:nx=4}
  \norm{\xi}=4,
\end{equation}
then so is $\pm(5+8\gr)^n\gamma$.  
There is some $n$ in $\Z$ such that
\begin{equation*}
  (5+8\gr)^n<\size{\gamma}<(5+8\gr)^{n+1},
\end{equation*}
so that
\begin{equation*}
  1<(5+8\gr)^{-n}\size{\gamma}<5+8\gr.
\end{equation*}
Let $(5+8\gr)^{-n}\size{\gamma}=2k+\ell\gr$.  
Then $(k,\ell)$ lies between the lines
\begin{align*}
  2x+y\gr&=1,& 2x+y\gr&=5+8\gr.
\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}
These are parallel to one of the asymptotes of the hyperbola 
that we have discussed,
and $(k,\ell)$ lies on this hyperbola,
which, from the equation involving the second entry in \eqref{eqn:lhs},
meets the bounding line $2x+y\gr=1$ 
at this line's intersection with the line $2x+y\gr'=4$, 
parallel to the other asymptote.  
This means $(k,\ell)$ lies within the parallelogram
in the 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\}$.  
The analysis continues in the next lecture.
\end{solution}

\myday{April 11, 2008 (Friday)}

\topic{Example continued}

At the end of the solution of Problem \ref{prob:qDe3},
\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} are $\pm2\gr^{2k}$,
where $k\in\Z$.
%Since $\gr^2=1+\gr$ as in \eqref{eqn:gr^2=1+gr},
By Theorem \ref{thm:Fib},
 these solutions are
\begin{equation*}
\pm(2\Fib{2k-1}+2\Fib{2k}\gr).  
\end{equation*}
Every Fibonacci number appears among them.

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},
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 the single bi-directional sequence
listed in Table \ref{tab:gr}.
\begin{table}
  \centering
  \begin{equation*}
  \begin{array}{rll}
    2x+y\gr&\multicolumn2l{\qquad(x,y)}\\\hline
    \multicolumn3c{\dotfill}\\
 2\gr^{  -6 }&(13,-16)&(\Fib{-7},2\Fib{-6})\\
-2\gr^{-(-6)}&(-5,-16)&(-\Fib{-(-5)},-2\Fib{-(-6)})\\
-2\gr^{  -4 }&(-5,6)&(-\Fib{-5},-2\Fib{-4})\\
 2\gr^{-(-4)}&(2,6)&(\Fib{-(-3)},2\Fib{-(-4)})\\
 2\gr^{  -2 }&(2,-2)&(\Fib{-3},2\Fib{-2})\\
-2\gr^{-(-2)}&(-1,-2)&(-\Fib{-(-1)},-2\Fib{-(-2)})\\
-2\gr^   0  &(-1,0)&(-\Fib{-1},-2\Fib0)\\
 2\gr^{  -0 }&(1,0)&(\Fib{-1},2\Fib{-0})\\
 2\gr^   2  &(1,2)&(\Fib{1},2\Fib{2})\\
-2\gr^{  -2  }&(-2,2)&(-\Fib{-3},-2\Fib{-2})\\
-2\gr^   4  &(-2,-6)&(-\Fib{3},-2\Fib{4})\\
 2\gr^{  -4  }&(5,-6)&(\Fib{-5},2\Fib{-4})\\
 2\gr^   6  &(5,16)&(\Fib{5},2\Fib{6})\\
 \multicolumn3c{\dotfill}
  \end{array}
\end{equation*}
  \caption{Solutions of $4x^2+2xy-y^2=4$}
  \label{tab:gr}
\end{table}
In particular, the sequence is $(a_n\colon n\in\Z)$, where
\begin{equation*}
  a_n=
  \begin{cases}
  ( \Fib{-(4m+1)}, 2\Fib{- 4m   }),&\text{ if }n=4m,\\
  ( \Fib{  4m+1 }, 2\Fib{  4m+2 }),&\text{ if }n=4m+1,\\
  (-\Fib{-(4m+3)},-2\Fib{-(4m+2)}),&\text{ if }n=4m+2,\\
  (-\Fib{  4m+3 },-2\Fib{  4m+4 }),&\text{ if }n=4m+3.
  \end{cases}
\end{equation*}
Alternatively,
if $n=4m+2e+f$, where $e$ and $f$ are $0$ or $1$, then
\begin{equation*}
  a_n=((-1)^e\Fib{-(-1)^f(4m+2e+1)},(-1)^e2\Fib{-(-1)^f(4m+2e+2f)}).
\end{equation*}

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$.
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:nx=4} correspond to the matrices
\begin{equation*}
\pm2  \begin{pmatrix}
1&1\\1&2        
  \end{pmatrix}^{2n}.
\end{equation*}


\myweek

\myday{April 15, 2008 (Tuesday)}

\topic{Units from convergents}

By converting a quadratic Diophantine equation to the form 
\eqref{eqn:n(xa+yb)=m},
we can solve as in Problems~\ref{prob:qDe1},~\ref{prob:qDe2}, 
and~\ref{prob:qDe3}, provided we can find the units of $\roi$.  
The case where $d>0$ is the challenge.
We need to find the fundamental unit $\funit$, 
so that, by Theorem \ref{thm:unit}, 
every unit of $\roi$ is $\pm\funit{}^n$ for some $n$.

We have solved this problem when $d=5$,
since then $\funit=\gr$ by Theorem \ref{thm:Fib}.  

\begin{comment}
We have $\roi=\latt[1,\omega]$ by Theorem \ref{thm:roi}, and
\begin{equation*}
  \norm{x+y\omega}=
  \begin{cases}
    x^2-dy^2,&\text{ if }d\not\equiv1\pmod 4;\\
(x+y/2)^2-dy^2/4,&\text{ if }d\equiv1.
  \end{cases}
\end{equation*}
\end{comment}
We know by Lemma \ref{lem:not5} that $\funit=a+b\omega$ 
for some positive $a$ and $b$, unless $d=5$.  
\begin{compactitem}
  \item
If $d\not\equiv1\pmod4$, then $a+b\omega=a+b\sqrt d$.
\item
If $d\equiv1$, then $a+b\omega=\frac12(2a+b)+\frac12b\sqrt d$.
\end{compactitem}
For the moment writing $a+b\omega$ as $a'+b'\sqrt d$,
we shall show that $a'/b'$ is a convergent of $\sqrt d$.
However, the argument will depend on $a$ and $b$ separately
and thus on whether $d\equiv1\pmod 4$;
also on how big $d$ is.
In any case,
assuming $\sqrt d=[a_0;a_1,a_2,\dots]$, 
we let $p_n/q_n$ be the $n$th convergent, $[a_0;a_1,\dots,a_n]$.  

\begin{lemma}\label{lem:q_{n+1}}
If $a$ and $b$ are rational integers such that  
\begin{equation*}
  1\leq b<q_{n+1},
\end{equation*}
then
  \begin{equation*}
    \size{p_n-q_n\sqrt d}\leq\size{a-b\sqrt d}.
  \end{equation*}
\end{lemma}

\begin{proof}
By Theorem~\ref{thm:-1},
  \begin{equation*}
    (-1)^n=p_{n+1}q_n-p_nq_{n+1}=
    \begin{vmatrix}
      p_{n+1}&p_n\\ q_{n+1}&q_n
    \end{vmatrix},
  \end{equation*}
so the matrix is invertible,
and there are $s$ and $t$ in $\Z$ such that
\begin{equation*}
  \begin{pmatrix}
    a\\b
  \end{pmatrix}
=
\begin{pmatrix}
      p_{n+1}&p_n\\ q_{n+1}&q_n
\end{pmatrix}
\begin{pmatrix}
  s\\t
\end{pmatrix}
=
\begin{pmatrix}
  sp_{n+1}+tp_n\\sq_{n+1}+tq_n
\end{pmatrix}.
\end{equation*}
We compute $a=sp_{n+1}+tp_n$ and $b=sq_{n+1}+tq_n$, so
\begin{equation*}
  a-b\sqrt d
=s(p_{n+1}-q_{n+1}\sqrt d)
+t(p_n-q_n\sqrt d).
\end{equation*}
It is enough to show that the two terms here have the same sign
and $t\neq0$.
Since the factors $p_{n+1}-q_{n+1}\sqrt d$ and $p_n-q_n\sqrt d$
have opposite sign, it is enough to show
$st\leq0$ and $t\neq0$.
For the latter, we note
\begin{equation*}
  \begin{pmatrix}
    s\\t
  \end{pmatrix}
=(-1)^n
\begin{pmatrix}
      q_n&-p_n\\-q_{n+1}&p_{n+1}
\end{pmatrix}
\begin{pmatrix}
  a\\b
\end{pmatrix},
\end{equation*}
so
\begin{equation*}
  t=(-1)^n(-aq_{n+1}+bp_{n+1}).
\end{equation*}
Since $\gcd(p_{n+1},q_{n+1})=1$,
if $t=0$, so that $aq_{n+1}=bp_{n+1}$, then $q_{n+1}\divides b$, 
hence $q_{n+1}\leq b$, contrary to our assumption.

To show $st\leq0$, suppose $s\neq0$.  We have
\begin{equation*}
  b=sq_{n+1}+tq_n.
\end{equation*}
\begin{compactitem}
  \item
If $s<0$, then $t>0$, since $1\leq b$; 
\item
if $s>0$, then $t<0$, since $b<q_{n+1}$.\qedhere
\end{compactitem}
\end{proof}

The lemma uses only that $\sqrt d$ has convergents up to step $n+1$.
The following lemma requires that all convergents of $\sqrt d$ exist, 
that is, $\sqrt d$ must be irrational.

\begin{lemma}\label{lem:criterion}
If $a$ and $b$ are positive rational integers such that
  \begin{equation}\label{eqn:ab-d}
    \xsize{\frac ab-\sqrt d}<\frac1{2b^2},
  \end{equation}
then $a/b$ is a convergent of $\sqrt d$.
\end{lemma}

\begin{proof}
Since $(q_n\colon n\in\upomega)$ increases to $\infty$, 
we can find $n$ such that
  \begin{equation*}
    q_n\leq b<q_{n+1}.
  \end{equation*}
In this case,
by Lemma~\ref{lem:q_{n+1}} and \eqref{eqn:ab-d},
\begin{equation*}
  q_n\xsize{\frac{p_n}{q_n}-\sqrt d}
\leq b\xsize{\frac ab-\sqrt d}<\frac1{2b},
\end{equation*}
so that
\begin{equation*}
\xsize{\frac{p_n}{q_n}-\sqrt d}
<\frac1{2bq_n}.  
\end{equation*}
By the triangle inequality and this,
\begin{multline*}
  \frac1{bq_n}\size{aq_n-bp_n}
=\xsize{\frac ab-\frac{p_n}{q_n}}
\leq\xsize{\frac ab-\sqrt d}+\xsize{\sqrt d-\frac{p_n}{q_n}}\\
<\frac1{2b^2}+\frac1{2bq_n}
\leq\frac1{bq_n}.
\end{multline*}
Thus $\size{aq_n-bp_n}<1$, hence $aq_n=bp_n$ and $a/b=p_n/q_n$.
\end{proof}

\begin{theorem}\label{thm:units-from-convergents}
Assuming $d>0$, let $a+b\omega$ be a unit of
$\roi$ where $a$ and $b$ are positive. 
\begin{compactenum}
  \item\label{item:d=2,3}
If $d\not\equiv1\pmod 4$, then $a/b$ is a convergent of $\sqrt d$.
\item\label{item:d=1}
If $d\equiv1$,
then $(2a+b)/b$ is a convergent of $\sqrt d$,
provided $d$ is at least $21$.
\end{compactenum}
\end{theorem}

\begin{proof}
  \begin{asparaenum}
    \item
  Suppose first
  \begin{equation}\label{eqn:a^2-db^2=pm1}
    a^2-db^2=\pm1,
  \end{equation}
which is the case when $d\not\equiv1$.
  By Lemma~\ref{lem:criterion}, it is enough to show
  \begin{equation*}
    \xsize{\frac ab-\sqrt d}<\frac1{2b^2},
  \end{equation*}
that is,
\begin{equation*}
  \size{a-b\sqrt d}<\frac1{2b},
\end{equation*}
that is, 
multiplying by $a+b\sqrt d$ and using~\eqref{eqn:a^2-db^2=pm1},
\begin{equation}\label{eqn:1<a+b}
  1<\frac{a+b\sqrt d}{2b}=\frac12\Bigl(\frac ab+\sqrt d\Bigr).
\end{equation}
But we have, again from~\eqref{eqn:a^2-db^2=pm1},
and since $d\geq2$,
\begin{gather}\notag
  a^2-db^2\geq-1,\\\label{eqn:ab2}
\Bigl(\frac ab\Bigr)^2\geq d-\frac 1{b^2}\geq d-1,\\\notag
\frac ab\geq\oldsqrt{d-1},\\\label{eqn:12ab}
\frac12\Bigl(\frac ab+\sqrt d\Bigr)\geq \frac12(\oldsqrt{d-1}+\sqrt d)>1,
\end{gather}
which gives us \eqref{eqn:1<a+b}.
\item
In case $d\equiv1$, we try to proceed likewise.
Parallel to \eqref{eqn:a^2-db^2=pm1} we have
\begin{equation*}
  (2a+b)^2-db^2=\pm4,
\end{equation*}
so that, parallel to \eqref{eqn:ab2},
\begin{equation}\label{eqn:ineqn}
  \Bigl(\frac{2a+b}b\Bigr)^2\geq d-\frac4{b^2}\geq d-4.
\end{equation}
We should like to show, parallel to \eqref{eqn:12ab},
\begin{equation}\label{eqn:4<}
  \frac12\Bigl(\frac{2a+b}b+\sqrt d\Bigr)>4.
\end{equation}
It is enough if we can show
\begin{equation}\label{eqn:d-4}
  \frac12(\oldsqrt{d-4}+\sqrt d)>4.
\end{equation}
We have this if $d\geq21$.\qedhere
\end{asparaenum}
\end{proof}

It remains to consider the cases when $d$ is $17$ or $13$.  

\begin{lemma}
In Theorem \ref{thm:units-from-convergents},
$a$ is the nearest integer to $-b\omega'$.
\end{lemma}

\begin{proof}
Since $a+b\omega>2$ and
$1=(a+b\omega)\size{a+b\omega'}$,
we conclude
\begin{equation*}
  \size{a+b\omega'}<\frac12,
\end{equation*}
so $a$ is indeed the nearest integer to $-b\omega'$.
\end{proof}

\begin{theorem}\label{thm:17}
Theorem \ref{thm:units-from-convergents} holds also when $d=17$.
\end{theorem}

\begin{proof}
In this case $-\omega'\approx1.56$, 
to which $2$ is nearest.
Since $\norm{2+\omega}=2$, we must have $b>1$.  
In the proof of Theorem \ref{thm:units-from-convergents},
instead of~\eqref{eqn:ineqn} we have
\begin{equation*}
  \Bigl(\frac{2a+b}b\Bigr)^2\geq d-\frac4{b^2}\geq d-1.
\end{equation*}
It is now enough if
\begin{equation*}
  \frac12(\oldsqrt{d-1}+\sqrt d)>4;
\end{equation*}
and we have this.
\end{proof}

\begin{lemma}\label{lem:13}
If $d=13$, then the fundamental unit of $\roi$ is $1+\omega$,
and $(2+1)/1$ is the first convergent of $\sqrt{13}$.
\end{lemma}

\begin{proof}
We have $-\omega'\approx 1.3$, to which $1$ is the
nearest integer; and $1+\omega$ is indeed a unit (of norm $-1$) and is
the least possible unit greater than $1$, so it is the fundamental
unit of $\roi$.
\end{proof}


\myday{April 18, 2008 (Friday)}\label{ch:april-18}

\topic{The cases of 13 and 5}

The argument for Case~\eqref{item:d=1} 
of Theorem~\ref{thm:units-from-convergents} does not work when $d=13$,
because $13$ is too small.  
We cannot show~\eqref{eqn:4<} in this case, 
because we have not got \eqref{eqn:d-4}.
However, we have \eqref{eqn:rt13},
namely $\sqrt{13}=[3;1,1,1,1,6]$,
and from this we obtain the convergents listed in Table~\ref{tab:13}.
\begin{table}
\renewcommand{\arraystretch}{1.5}
\begin{equation*}
  \begin{array}{|c||*{5}{c|}}\hline
n&0&1&2&3&4\\\hline
    \displaystyle\frac{p_n}{q_n}%\text{ or }\frac{2a+b}b
\vphantom{\displaystyle\frac{\sqrt 1}{q\sqrt 1}}
& \displaystyle\frac 31&
    \displaystyle\frac41& \displaystyle\frac72&
    \displaystyle\frac{11}3& \displaystyle\frac{18}5\\\hline
p_n{}^2-13q_n{}^2
\vphantom{\sqrt 1}
& -4& 3& -3& 4& -1\\\hline\hline
\displaystyle\frac{2a+b}b
\vphantom{\displaystyle\frac{\sqrt 1}{q\sqrt 1}}
&\displaystyle\frac31&&
&\displaystyle\frac{11}3
&\displaystyle\frac{36}{10}
\\\hline 
\text{\parbox{15mm}{\centering$(1+\omega)^k$\\ or\\ $a+b\omega$}}
&1+\omega &&
&4+3\omega
&13+10\omega \\\hline
k&1&&&2&3\\\hline
  \end{array}
\end{equation*}

\begin{equation*}
\begin{array}{|c||*{5}{c|}}\hline
n&5&6&7&8&9\\\hline
\displaystyle\frac{p_n}{q_n}
\vphantom{\displaystyle\frac{\sqrt 1}{q\sqrt 1}}
&   \displaystyle\frac{119}{33}& \displaystyle\frac{137}{38}&
    \displaystyle\frac{256}{71}& \displaystyle\frac{393}{109}&
    \displaystyle\frac{649}{180}\\\hline
p_n{}^2-13q_n{}^2
\vphantom{\sqrt 1}
& 4& -3& 3& -4& 1\\\hline\hline
\displaystyle\frac{2a+b}b
\vphantom{\displaystyle\frac{\sqrt 1}{q\sqrt 1}}
&\displaystyle\frac{119}{33}&&
&\displaystyle\frac{393}{109}
&\displaystyle\frac{1298}{360}\\\hline 
\text{\parbox{15mm}{\centering$(1+\omega)^k$\\ or\\ $a+b\omega$}}
&43+33\omega&&
&142+109\omega 
&\text{\parbox{15mm}{$469+$\\\mbox{}\hfill$360\omega$}}  \\\hline
k&4&&&5&6\\\hline
  \end{array}
\end{equation*}

\caption{Convergents and units when $d=13$}\label{tab:13}
\end{table}
To complete the table,
noting that, 
by Lemma \ref{lem:13},
the positive units of $\roi$ (when $d=13$) are the powers of
$1+\omega$, we have
\begin{align*}
  \omega&=\frac{1+\sqrt{13}}2,&
\Bigl(\omega-\frac12\Bigr)^2&=\frac{13}4,&
\omega^2&=3+\omega,
\end{align*}
so that
\begin{multline*}
    (x+y\omega)(1+\omega)
=x+(x+y)\omega+y\omega^2\\
=x+(x+y)\omega+y(3+\omega)
=x+3y+(x+2y)\omega.
  \end{multline*}
  This gives the rest of Table~\ref{tab:13}.
We show now that the pattern of the table continues.

\begin{theorem}\label{thm:13}
  Assuming $d=13$, let
$p_k/q_k$ be the $k$th convergent of $\sqrt d$, and let
  \begin{equation*}
    a_{\ell}+b_{\ell}\omega=(1+\omega)^{\ell}.
  \end{equation*}
Then
\begin{equation*}
  \frac{2a_{3m+i}+b_{3m+i}}{b_{3m+i}}=
    \begin{cases}
      p_{5m}/q_{5m},&\text{ if }i=1;\\
      p_{5m+3}/q_{5m+3},&\text{ if }i=2;\\
      p_{5m+4}/q_{5m+4},&\text{ if }i=3.
    \end{cases}
\end{equation*}
\end{theorem}

\begin{proof}
We shall use the method of Problem~\ref{prob:14} on page \pageref{prob:14}.
From Table \ref{tab:13},
our claim holds when $m=0$.  
Writing $p/q$ for $p_k/q_k$ and $p'/q'$ for $p_{k+5}/q_{k+5}$, 
we have
\begin{multline*}
    \frac{p'}{q'}
=\Bigl[3;1,1,1,1,3+\frac pq\Bigr]
=\Bigl[3;1,1,1,1+\frac q{p+3q}\Bigr]\\
=\Bigl[3;1,1,1+\frac{p+3q}{p+4q}\Bigr]
=\Bigl[3;1,1+\frac{p+4q}{2p+7q}\Bigr]\\
=\Bigl[3;1+\frac{2p+7q}{3p+11q}\Bigr]
=3+\frac{3p+11q}{5p+18q}
=\frac{18p+65q}{5p+18q}.
\end{multline*}
Writing $a+b\omega$ for $a_{\ell}+b_{\ell}\omega$, and $a'+b'\omega$
for $a_{\ell+3}+b_{\ell+3}\omega$, we have
\begin{multline*}
  a'+b'\omega
=(a+b\omega)(13+10\omega)\\
=13a+(10a+13b)\omega+10b(3+\omega)\\
=13a+30b+(10a+23b)\omega.
\end{multline*}
Therefore, if, as an inductive hypothesis,
we have
\begin{equation*}
  \frac{2a+b}b=\frac pq,
\end{equation*}
so that
\begin{equation*}
\frac ab=\frac{p-q}{2q},
\end{equation*}
then
\begin{multline*}
  \frac{2a'+b'}{b'}
=\frac{26a+60b+10a+23b}{10a+23b}
=\frac{36a+83b}{10a+23b}\\
=\frac{36(p-q)+83\cdot2q}{10(p-q)+23\cdot2q}
%=\frac{36p-36q+166q}{10p-10q+46q}
=\frac{36p+130q}{10p+36q}
=\frac{18p+65q}{5p+18q}
=\frac{p'}{q'}.
\end{multline*}
Therefore the claim holds for all $m$.
\end{proof}

We know now that, when $d>5$,
if $s+t\sqrt d$ is a unit of $\roi$ with positive coefficients,
then $s/t$ is a convergent of $\sqrt d$.
By the last theorem, not every convergent arises in this way when $d=13$.
It does when $d=5$,
by Theorem \ref{thm:Fib} and the next theorem;
but then not every unit gives rise to a convergent.

\begin{theorem}\label{thm:5}
  The $n$th convergent of $\sqrt 5$ is
  \begin{equation*}
    \frac{2\Fib{3n+2}+\Fib{3n+3}}{\Fib{3n+3}}.
  \end{equation*}
\end{theorem}

\begin{proof}
This can be left as an exercise.
Since $(\sqrt5-2)\inv=\sqrt5+2$, we have
\begin{equation*}
  \sqrt5=[2;\overline4],
\end{equation*}
and so
\begin{equation*}
  \frac{p_{k+1}}{q_{k+1}}=2+\cfrac1{2+\cfrac{p_k}{q_k}}
=\frac{2p_k+5q_k}{p_k+2q_k}.
\end{equation*}
Since
\begin{equation*}
  \frac{2\Fib2+\Fib3}{\Fib3}=\frac{2+2}2=2=\frac{p_0}{q_0},
\end{equation*}
our claim holds when $n=0$.
If it holds when $n=k$ for some $k$, then
\begin{multline*}
  \frac{p_{k+1}}{q_{k+1}}
=\frac{2(2\Fib{3k+2}+\Fib{3k+3})+5\Fib{3k+3}}
{2\Fib{3k+2}+\Fib{3k+3}+2\Fib{3k+3}}\\
=\frac{4\Fib{3k+2}+7\Fib{3k+3}}{2\Fib{3k+2}+3\Fib{3k+3}}
=\frac{4\Fib{3k+4}+3\Fib{3k+3}}{2\Fib{3k+4}+\Fib{3k+3}}\\
=\frac{\Fib{3k+4}+3\Fib{3k+5}}{\Fib{3k+4}+\Fib{3k+5}}
=\frac{\Fib{3k+6}+2\Fib{3k+5}}{\Fib{3k+6}},
\end{multline*}
so the claim holds when $n=k+1$.
\end{proof}

\myweek

\myday{April 22, 2008 (Tuesday)}

\topic{Continued fractions}

We can give alternative proofs of Theorems~\ref{thm:13} and~\ref{thm:5}, 
avoiding the computations, 
by developing more of the theory of continued fractions.
We assume now simply that
\conv{$d$ is a positive non-square,}\label{d-nsq-2}
as on page \pageref{d-nsq}.
We let $\sqrt d$ be the $x$
in~\eqref{eqn:a_0} and~\eqref{eqn:a_n},
which define $a_n$ and $\xi_n$ in terms of $x$,
and we let $p_n$ and $q_n$ be as defined by \eqref{eqn:p_0},
\eqref{eqn:p_1}, and \eqref{eqn:pq},
so that, in particular,
$p_n/q_n$ is the convergent $[a_0;a_1,\dots,a_n]$,
by Theorem \ref{thm:pq}.

In case $d\in\{3,14,13\}$, 
as in \eqref{eqn:rt3}, \eqref{eqn:rt14}, and \eqref{eqn:rt13}
on pages \pageref{eqn:rt3}, \pageref{eqn:rt14}, and \pageref{eqn:rt13},
we have seen
  \begin{equation}\label{eqn:rt-d-periodic}
    \sqrt d=[a_0;\overline{a_1,\dots,a_n}]
  \end{equation}
for some $n$.
Now we shall show this generally,
and, moreover, 
that $(a,b)$ is a positive solution to the Pell equation~\eqref{eqn:pell}
if and only if $(a,b)=(p_{n-1},q_{n-1})$
for some \emph{even} $n$ such that $\sqrt
d=[a_0;\overline{a_1,\dots,a_n}]$. 
We already know part of this, implicitly, as follows.

\begin{theorem}\label{thm:every-pos}
Every positive solution of~\eqref{eqn:pell}
is $(p_n,q_n)$ for some $n$.
\end{theorem}

\begin{proof}
Suppose $(a,b)$ is such a solution.
Note that $a$ and $b$ must be prime to one another.
We have $a/b=p_n/q_n$ from the proof of part \eqref{item:d=2,3} of
Theorem~\ref{thm:units-from-convergents},
since this proof requires only that $\sqrt d$ be irrational.
The equation of $(a,b)$ and $(p_n,q_n)$ follows,
since $p_n$ and $q_n$ too are prime to one another, by Theorem~\ref{thm:-1}. 
\end{proof}

The computation of the continued-fraction expansions of particular $\sqrt d$
(as in the examples mentioned above) suggests the following.

\begin{lemma}\label{lem:st}
There are sequences of rational integers $s_n$ and $t_n$ such that
  \begin{equation}\label{eqn:xi}
    \xi_n=\frac{\sqrt d-t_n}{s_n}.
  \end{equation}
\end{lemma}

\begin{proof}
It is easy to establish that there are such rational \emph{numbers} 
$s_n$ and $t_n$.  
Indeed, this claim holds when $n=0$, since $\xi_0=\sqrt d-a_0$.  
Suppose for some $k$ the claim holds when $n=k$.  Then
  \begin{multline*}
    \xi_{k+1}
=\frac1{\xi_k}-a_{k+1}
=\frac{s_k}{\sqrt d-t_k}-a_{k+1}\\
=\frac{\sqrt
      d+t_k}{\Bigl(\displaystyle\frac{d-t_k{}^2}{s_k}\Bigr)}-a_{k+1}
=\frac{\sqrt d-
      \Bigl(a_{k+1}\displaystyle\frac{d-t_k{}^2}{s_k}-t_k\Bigr)}
       {\displaystyle\frac{d-t_k{}^2}{s_k}}.
     \end{multline*}
Thus the claim holds when $n=k+1$.
In particular,
\begin{align}\label{eqn:st}
  s_{k+1}&=\frac{d-t_k{}^2}{s_k},&
t_{k+1}&=a_{k+1}s_{k+1}-t_k.
\end{align}
We now show that $s_n$ and $t_n$ are integers.
We have $s_0=1$ and $t_0=a_0$.
Then $s_1=d-a_0{}^2$, an integer.  
Suppose $s_k$, $t_k$, and $s_{k+1}$ are integers.  
Immediately $t_{k+1}$ is one too.  Also,
\begin{gather*}
  s_{k+1}\divides d-t_k{}^2,\\
d-t_{k+1}{}^2\equiv d-t_k{}^2\equiv0\pmod{s_{k+1}},
\end{gather*}
and therefore $s_{k+2}$ is an integer.
\end{proof}

The following needs only that $\sqrt d$ is irrational,
so that the infinite expansion
$[a_0;a_1,\dots]$ exists.

\begin{lemma}\label{lem:x}
For all $n$,
\begin{equation*}
\sqrt d=[a_0;a_1,\dots,a_{n-1},a_n+\xi_n].
\end{equation*}
\end{lemma}

\begin{proof}
The claim is trivially true when $n=0$.
Also, since $a_{k+1}+\xi_{k+1}=\xi_k{}\inv$ by~\eqref{eqn:a_n},
by~\eqref{eqn:brackets} we have
\begin{equation*}
    [a_0;a_1,\dots,a_k,a_{k+1}+\xi_{k+1}]
=[a_0;a_1,\dots,a_{k-1},a_k+\xi_k].\qedhere  
\end{equation*}
\end{proof}

\begin{theorem}\label{thm:s}
If $s_{n+1}$ is as in Lemma~\ref{lem:st}, 
then
  \begin{equation*}
    p_n{}^2-dq_n{}^2=(-1)^{n+1}s_{n+1}.
  \end{equation*}
\end{theorem}

\begin{proof}
In case $n=0$, we have
  \begin{equation*}
    p_0{}^2-dq_0{}^2=a_0{}^2-d=-s_1
  \end{equation*}
as in the proof of Lemma~\ref{lem:st}.
By~\eqref{eqn:pq}, when $k\geq1$, we have
\begin{equation*}
  \frac{p_{k+1}}{q_{k+1}}=\frac{p_ka_{k+1}+p_{k-1}}{q_ka_{k+1}+q_{k-1}}.
\end{equation*}
From this,
by Lemma~\ref{lem:x} we obtain
\begin{equation*}
  \sqrt d=
\frac{p_k(a_{k+1}+\xi_{k+1})+p_{k-1}}{q_k(a_{k+1}+\xi_{k+1})+q_{k-1}}  
\end{equation*}
or rather
\begin{equation*}
(q_ka_{k+1}+q_{k-1})\sqrt d+q_k\xi_{k+1}\sqrt d
=p_ka_{k+1}+p_{k-1}+p_k\xi_{k+1}.
\end{equation*}
By \eqref{eqn:xi} this gives
\begin{multline*}
s_{k+1}(q_ka_{k+1}+q_{k-1})\sqrt d+q_k(\sqrt d-t_{k+1})\sqrt d\\
=s_{k+1}(p_ka_{k+1}+p_{k-1})+p_k(\sqrt d-t_{k+1})
\end{multline*}
and therefore
\begin{multline*}
\bigl(s_{k+1}(q_ka_{k+1}+q_{k-1})-q_kt_{k+1}\bigr)\sqrt d +q_kd\\
=\bigl(s_{k+1}(p_ka_{k+1}+p_{k-1})-p_kt_{k+1}\bigr)+p_k\sqrt d.  
\end{multline*}
Since only $\sqrt d$ is irrational here, we obtain
\begin{equation*}
\left\{
  \begin{aligned}
p_k&=    s_{k+1}(q_ka_{k+1}+q_{k-1})-q_kt_{k+1},\\
q_kd&= s_{k+1}(p_ka_{k+1}+p_{k-1})-p_kt_{k+1}.
  \end{aligned}
\right.
\end{equation*}
Multiplying by $p_k$ and $q_k$ respectively, then subtracting, yields
\begin{equation*}
  p_k{}^2-dq_k{}^2=s_{k+1}(p_kq_{k-1}-q_kp_{k-1})=(-1)^{k+1}s_{k+1}
\end{equation*}
by Theorem~\ref{thm:-1}.
\end{proof}

\begin{corollary}
  $s_n>0$.
\end{corollary}

\begin{proof}
By Theorem~\ref{thm:-1} and its corollary,
\begin{align*}
  (-1)^{n+1}=1
\iff\frac{p_n}{q_n}>\sqrt d
&\iff p_n-q_n\sqrt d>0\\
&\iff p_n{}^2-dq_n{}^2>0.\qedhere
\end{align*}
\end{proof}

\begin{lemma}\label{lem:frac-lin}
$[a_0;a_1,\dots,a_n]$ determines $a_n$.
\end{lemma}

\begin{proof}
The claim is easy when $0\leq n\leq1$.
In the other cases,
by Theorem~\ref{thm:pq},
\begin{equation*}
\frac{p_{m+2}}{q_{m+2}}
=\frac{p_{m+1}a_{m+2}+p_m}{q_{m+1}a_{m+2}+q_m},  
\end{equation*}
and now we can solve for $a_{m+2}$.
Indeed we obtain
\begin{equation*}
a_{m+2}(p_{m+2}q_{m+1}-p_{m+1}q_{m+2})=p_{m+2}q_m+p_mq_{m+2},  
\end{equation*}
which yields $a_{m+2}$
since $p_{m+2}/q_{m+2}\neq p_{m+1}/q_{m+1}$
by Theorem~\ref{thm:-1}.
\end{proof}


\begin{theorem}\label{thm:rt-d-periodic}
\eqref{eqn:rt-d-periodic} holds
for some $n$.  If $m$ is the least such $n$, then the positive
solutions of the Pell equation~\eqref{eqn:pell} are precisely
$(p_{km-1},q_{km-1})$, where $k>0$ and $km$ is even.
\end{theorem}

\begin{proof}
The Pell equation has a positive solution by Lemma~\ref{lem:pos-sol}.  
This solution is $(p_{n-1},q_{n-1})$ for some $n$, 
by Theorem~\ref{thm:every-pos}.  
Since $s_n>0$ by the corollary of Theorem \ref{thm:s},
the theorem itself yields that $s_n=1$ and $n$ is even.  
Then $\xi_{n}=\sqrt d-t_{n}$ by Lemma~\ref{lem:st}, 
and $t_{n}$ is unique such that $0<\sqrt d-t_{n}<1$.  
But $0<\sqrt d-a_0<1$, so $t_n=a_0$, and $\xi_{n}=\xi_0$.  
Therefore $a_{n+1}=a_1$, and $\xi_{n+1}=\xi_1$, and so forth, 
so~\eqref{eqn:rt-d-periodic} holds.  
If $m$ is the least such $n$,  then, for any such $n$, 
we must have $m\divides n$.

Conversely, suppose $\sqrt d=[a_0;\overline{a_1,\dots,a_m}]$.  Then
\begin{align*}
  \sqrt d
&=[a_0;a_1,\dots,a_{km-1},a_{km},\overline{a_1,\dots,a_m}]\\
&=[a_0;a_1,\dots,a_{km-1},a_{km}-a_0+a_0,\overline{a_1,\dots,a_m}]\\
&=[a_0;a_1,\dots,a_{km-1},a_{km}-a_0+\sqrt d].\\
\intertext{But also}
\sqrt d&=[a_0;a_1,\dots,a_{km-1},a_{km}+\xi_{km}],
\end{align*}
 by
Lemma~\ref{lem:x}; hence, by Lemma~\ref{lem:frac-lin}, $\xi_{km}=\sqrt
d-a_0$.  In particular, $s_{km}=1$,  so $(p_{km-1},q_{km-1})$
solves~\eqref{eqn:pell} by Theorem~\ref{thm:s}, as long as $km$ is even.
\end{proof}

\begin{porism}
  If~\eqref{eqn:rt-d-periodic} holds, then $\xi_{n+k}=\xi_k$ for all $k$.
\end{porism}

\begin{proof}
  Under the assumption, $p_{n-1}{}^2-dq_{n-1}{}^2=(-1)^n$, so $s_n=1$,
  and $\xi_n=\xi_0$.  Hence the claim.
\end{proof}

Some of the computations in Theorems~\ref{thm:13} and~\ref{thm:5} are
special cases of the following.

\begin{theorem}
  If $\sqrt d=[a_0;\overline{a_1,\dots,a_n}]$, then
    \begin{equation*}
      p_{k+n}+q_{k+n}\sqrt d=(p_{n-1}+q_{n-1}\sqrt d)(p_k+q_k\sqrt d),
    \end{equation*}
equivalently,
\begin{equation*}
  \begin{pmatrix}
    p_{k+n}\\q_{k+n}
  \end{pmatrix}=
  \begin{pmatrix}
    p_{n-1}&dq_{n-1}\\q_{n-1}&p_{n-1}
  \end{pmatrix}
  \begin{pmatrix}
    p_k\\q_k
  \end{pmatrix}.
\end{equation*}
\end{theorem}

\begin{proof}
As in the proof of Theorem \ref{thm:rt-d-periodic},
we have
\begin{multline}\label{eqn:dd}
    \sqrt d
=[a_0;a_1,\dots,a_{n-1},a_n-a_0+a_0,\overline{a_1,\dots,a_n}]\\
=[a_0;a_1,\dots,a_{n-1},a_n-a_0+\sqrt d].  
\end{multline}
By Theorem~\ref{thm:pq} then,
\begin{multline}\label{eqn:rt-d-frac}
\sqrt d
=\frac{(a_n-a_0+\sqrt d)p_{n-1}+p_{n-2}}{(a_n-a_0+\sqrt d)q_{n-1}+q_{n-2}}\\
=\frac{p_{n-1}\sqrt d+(a_n-a_0)p_{n-1}+p_{n-2}}
      {q_{n-1}\sqrt d+(a_n-a_0)q_{n-1}+q_{n-2}}.
\end{multline}
Here, if $n=1$, then $p_{n-2}=1$ and $q_{n-2}=0$.
Since $\sqrt d$ is irrational,
\begin{equation}\label{eqn:dqp}
\left\{
\begin{aligned}
  dq_{n-1}&=(a_n-a_0)p_{n-1}+p_{n-2},\\
p_{n-1}&=(a_n-a_0)q_{n-1}+q_{n-2}.
\end{aligned}
\right.  
\end{equation}
Putting these values into \eqref{eqn:rt-d-frac}
and using \eqref{eqn:dd} again, we have
\begin{equation*}
  [a_0;a_1,\dots,a_{n-1},a_n-a_0+\sqrt d]
  =\frac{p_{n-1}\sqrt d+dq_{n-1}}{q_{n-1}\sqrt d+p_{n-1}}.
\end{equation*}
Moreover, the same is true if we put $p_k/q_k$ in place of $\sqrt d$,
leaving $d$ itself unchanged since it comes from \eqref{eqn:dqp}.
Thus
\begin{equation*}
  \frac{p_{k+n}}{q_{k+n}}=
  \Bigl[a_0;a_1,\dots,a_{n-1},a_n-a_0+\frac{p_k}{q_k}\Bigr] 
=\frac{p_{n-1}p_k+dq_{n-1}q_k}{q_{n-1}p_k+p_{n-1}q_k}.
\end{equation*}
We are done, once we establish that the last fraction is in lowest terms.  
We write it as $a/b$ in the same terms.
By Theorem~\ref{thm:rt-d-periodic} (strictly speaking, the proof),
\begin{equation*}
  p_{n-1}{}^2-dq_{n-1}{}^2=(-1)^n.
\end{equation*}
Using this, we compute
\begin{gather*}
  q_{n-1}a-p_{n-1}b=-(-1)^nq_k,\\
p_{n-1}a-dq_{n-1}b=(-1)^np_k.
\end{gather*}
Since $\gcd(p_k,q_k)=1$, we must have $\gcd(a,b)=1$.
\end{proof}

As a refinement of Theorem~\ref{thm:rt-d-periodic}, we have
the following.

\begin{theorem}\label{thm:ultimate}
For some $n$, 
  \begin{equation*}
    \sqrt d=[a_0;\overline{a_1,\dots,a_{n-1},2a_0}],
  \end{equation*}
where, when $0<k<n$,
\begin{equation}\label{eqn:a_k}
a_k=a_{n-k}
\end{equation}
\end{theorem}

\begin{proof}
By Theorem~\ref{thm:rt-d-periodic}, \eqref{eqn:rt-d-periodic} holds.
We shall show first
\begin{equation}\label{eqn:xi_k}
  \xi_k=\frac1{-\xi_{n-(k+1)}{}'}
\end{equation}
whenever $0\leq k<n$.
By \eqref{eqn:st} in the proof of Lemma~\ref{lem:st},
\begin{equation*}
  \frac1{\xi_k}=\frac{s_k}{\sqrt d-t_k}=\frac{\sqrt d+t_k}{s_{k+1}}.
\end{equation*}
Now using also Lemma~\ref{lem:x}, as well as~\eqref{eqn:pq} and
Theorem~\ref{thm:pq}, we have
\begin{multline*}
  \qquad s_{k+1}\cdot\frac1{\xi_k}\\
=\sqrt d+t_k
=\Bigl[a_0+t_k;a_1,\dots,a_k,\frac1{\xi_k}\Bigr]
=\frac{p_k\cdot\displaystyle\frac1{\xi_k}+p_{k-1}}
      {q_k\cdot\displaystyle\frac1{\xi_k}+q_{k-1}},
\end{multline*}
from which we obtain
\begin{gather*}
s_{k+1}q_k\cdot\Bigl(\frac1{\xi_k}\Bigr)^2
+(s_{k+1}q_{k-1}-p_k)\cdot\frac1{\xi_k}-p_{k-1}=0. 
\end{gather*}
Let us write this as $f(\xi_k{}\inv)=0$.
The coefficients of $f$ being rational,
also $1/\xi_k{}'$ is a zero of $f$.
Moreover,
\begin{gather*}
  f(-1)=s_{k+1}(q_k-q_{k-1})+p_k-p_{k-1}>0,\\
f(0)=-p_{k-1}<0,
\end{gather*}
so $f$ has a root between $-1$ and $0$.  
That root must be $1/\xi_k{}'$, since $1/\xi_k>0$.  Thus
\begin{equation*}
  0<\frac1{-\xi_k{}'}<1.
\end{equation*}
We also have
\begin{equation*}
  0<\xi_k<1.
\end{equation*}
We can now establish~\eqref{eqn:xi_k} by induction.
By the porism to Theorem~\ref{thm:rt-d-periodic}, 
and because
\begin{equation}\label{eqn:xi_0}
  \xi_0=\sqrt d-a_0,
\end{equation}
we obtain
\begin{equation*}
  \frac1{\xi_{n-1}}=a_n+\xi_n=\xi_0+a_n=\sqrt d-a_0+a_n
\end{equation*}
and therefore
\begin{equation*}
  \frac1{-\xi_{n-1}{}'}=\sqrt d+a_0-a_n.
\end{equation*}
Comparing with \eqref{eqn:xi_0},
noting that both values are between $0$ and $1$,
we obtain
\begin{align*}
\xi_0&=\frac1{-\xi_{n-1}{}'},& a_n&=2a_0.  
\end{align*}
In particular, we have~\eqref{eqn:xi_k} when $k=0$.  Suppose we have
it when $k=j$, where $j+1<n$.  Then
\begin{multline*}
  \xi_{j+1}+a_{j+1}
  =\frac1{\xi_j}
  =-\xi_{n-(j+1)}{}'
  =-\Bigl(\frac1{\xi_{n-(j+2)}}-a_{n-(j+1)}\Bigr)'\\
  =-\frac1{\xi_{n-(j+2)}{}'}+a_{n-(j+1)}.
\end{multline*}
As before, we must have~\eqref{eqn:xi_k} when $k=j+1$.  
By induction, we have it for all $k$ such that $0\leq k<n$, 
and incidentally we have~\eqref{eqn:a_k} when $0<k<n$.
\end{proof}

\myweek

\myday{April 29, 2008 (Tuesday)}

\topic{Norm of a lattice} 

From Theorem \ref{thm:Gauss} (page \pageref{thm:Gauss}) 
and Exercise \ref{ex:Eisenstein} (page \pageref{ex:Eisenstein}),
we know $\roi$ is a Euclidean domain when $d\in\{-1,-3\}$.  
However, when $d=-5$, then
\begin{equation}\label{eqn:3215}
  3\cdot2=(1+\sqrt{{-5}})(1-\sqrt{{-5}}),
\end{equation}
although each factor is irreducible. 
To prove the irreducibility, suppose for example
\begin{equation*}
  1+\sqrt{{-5}}=\alpha\beta.
\end{equation*}
Then
$\norm{\alpha}\norm{\beta}=\norm{\alpha\beta}=\norm{1+\sqrt{{-5}}}=6$.
But no element of $\roi$ has norm $2$, since the equation
\begin{equation*}
  x^2+5y^2=2
\end{equation*}
is insoluble.  Hence one of $\norm{\alpha}$ and $\norm{\beta}$ is $1$,
so $\alpha$ or $\beta$ is a unit.  Thus there can be irreducibles that
are not prime.

To avoid such problems, instead of working with the \emph{numbers} in
a quadratic field, we shall work with ``ideal numbers,'' 
or what we now call simply \tech{ideal}{s.}  
Recall that an ideal of a commutative ring
$R$ is an additive subgroup of $R$ that is closed under multiplication
by elements of $R$.  In other words, it is an $R$-submodule of $R$.
(The definition of $R$-module is the same as the definition of a real
vector-space, with $\R$ replaced by $R$.) 

We shall generalize this definition slightly so that every lattice
$\mLambda$ of the quadratic field $K$ will be an ideal of $\ord$, even if
$\mLambda\nincluded\ord$.  Let $\ord[]$ be an \defn{order}{} of $K$,
that is, a sub-ring of $\roi$ that spans $K$ as a vector-space over
$\Q$.  Then $\ord[]$ is a lattice $\mLambda$ by
Lemma~\ref{lem:lat-cond} (page \pageref{lem:lat-cond}), 
and $\ord=\ord[]$ by Exercise \ref{ex:ord=lat} (page \pageref{ex:ord=lat}).
An additive subgroup $G$ of
$K$ is an \defn{ideal}{} of $\ord[]$ if it is closed under multiplication
by elements of $\ord[]$, \emph{and} $\alpha G\included\ord[]$ for some
non-zero $\alpha$ in $K$; we also require $G\neq\{0\}$.

\begin{theorem}
  Ideals of $\ord[]$ are lattices of $K$.
\end{theorem}

\begin{proof}
Let $L$ be an ideal of $\ord[]$.  We have $\ord[]=\latt[1,c\omega]$ for
some positive rational integer $c$ by
Theorem~\ref{thm:cond} (page \pageref{thm:cond}). 
Now use Lemma~\ref{lem:lat-cond}.  There,~\eqref{item:+} is
immediate.  For~\eqref{item:span}, note that $L$ contains some
non-zero $\alpha$, hence also $\alpha c\omega$.  But
$\{\alpha,\alpha c\omega\}$ is a basis of $K$ over $\Q$.
For~\eqref{item:nL}, we have $\beta L\included\ord[]$ for some
non-zero $\beta$.  Multiplying $\beta$ by some positive rational
integer, we may assume $\beta\in\ord[]$.  Then $\beta'\in\ord[]$, so
$\norm{\beta}L=\beta'\beta L\included\beta'\ord[]\included\ord[]$.
\end{proof}

So ideals are nothing new for us.  Instead of saying that $\mLambda$ is
an ideal of $\ord$, we may say that $\mLambda$ \defn{belong}{s to} $\ord$.

Given an order, 
we aim to develop something like unique factorization 
for the lattices belonging to it.  
To do this, we define a \defn{norm}{} for lattices.

In the original sense of norm, 
in any quadratic field $K$, 
if $n\in\Z$, then $\norm n=n^2$.
We want this to be the norm of the smallest ideal of $\roi$ that contains $n$.
This ideal is $n\roi$ or $\latt[n,n\omega]$, 
and the quotient group $\roi/n\roi$ or $\latt[1,\omega]/\latt[n,n\omega]$ 
has size $n^2$.  
Indeed, every coset of $\latt[n,n\omega]$ is $a+b\omega+\latt[n,n\omega]$ 
for some $a$ and $b$ in $\Z$, but
\begin{multline*}
a+b\omega+\latt[n,n\omega]=s+t\omega+\latt[n,n\omega]\\
\iff a\equiv s\And b\equiv t\bmod n,
\end{multline*}
so there are just $n^2$ distinct cosets.  
Generalizing this idea, we define
\begin{equation*}
  \norm{\mLambda}=\size{\ord/\mLambda}=(\ord:\mLambda),
\end{equation*}
assuming $\mLambda\included\ord$; 
in this case, $\mLambda$ is an \defn{integral}{} lattice.

Suppose $\mLambda$ and $\mMu$ are arbitrary lattices of $K$, and
$\mLambda\included\mMu$.  What is $(\mMu:\mLambda)$?  We can write
$\mMu$ as $\latt$; then
\begin{equation*}
  \mLambda=\latt[e\alpha+f\beta,g\alpha+h\beta].
\end{equation*}
By the Euclidean algorithm, we can eliminate $\beta$ from one
generator.  Indeed, suppose $\gcd(f,h)=a$, so that
$fx+hy=a$
for some $x$ and $y$ in $\Z$.  Then
\begin{gather*}
  \begin{vmatrix}
    h/a&-f/a\\x&y
  \end{vmatrix}=1,\\
  \begin{pmatrix}
    h/a&-f/a\\x&y
  \end{pmatrix}
  \begin{pmatrix}
    e\alpha+f\beta\\g\alpha+h\beta
  \end{pmatrix}=
  \begin{pmatrix}
    (he-fg)\alpha/a\\(ex+gy)\alpha+a\beta
  \end{pmatrix}.
\end{gather*}
Thus
\begin{equation}\label{eqn:mLambda}
  \mLambda=\latt[b\alpha,c\alpha+a\beta],
\end{equation}
where $b=(he-fg)/a$ and $c=ex+gy$.  In particular,
\begin{equation}\label{eqn:ab=efgh}
  \size{ab}=
\Bigl\lvert\det
  \begin{pmatrix}
    e&f\\g&h
  \end{pmatrix}
\Bigr\rvert.
\end{equation}
We may then assume that $b>0$ and $0\leq c<b$,
while~\eqref{eqn:mLambda} and~\eqref{eqn:ab=efgh} continue to hold.  Then
the cosets of $\mLambda$ in $\mMu$ are in one-to-one correspondence
with the pairs $(i,j)$ such that $0\leq i<a$ and $0\leq j<b$.  That
is, every element of $\mMu$ is congruent \emph{modulo} $\mLambda$ to
some unique $j\alpha+i\beta$, where $0\leq i<a$ and $0\leq j<b$.  Thus
\begin{equation*}
  (\mMu:\mLambda)=ab=\Bigl\lvert\det
  \begin{pmatrix}
    e&f\\g&h
  \end{pmatrix}
\Bigr\rvert
=\oldsqrt{
  \begin{vmatrix}
    e&f\\g&h
  \end{vmatrix}^2}.
\end{equation*}
For example, if $\mMu=\latt[1,\mi]$ and $\mLambda=\latt[3,1+2\mi]$,
then $(\mMu:\mLambda)=\size{\mMu/\mLambda}=6$;
equivalently, every element of $\mMu$
is congruent \emph{modulo} $\mLambda$ to one of the six elements
lying within the parallelogram depicted in Figure~\ref{fig:ML}.
\begin{figure}[ht]
\centering
\begin{pspicture}(-0.5,-0.5)(4.5,2.5)
\multirput*(0,0)(1,0)5{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}    
\multirput*(0,1)(1,0)5{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}    
\multirput*(0,2)(1,0)5{\pscircle[fillstyle=solid,fillcolor=black]{0.05}}    
\pspolygon[linestyle=dotted](-0.3,-0.2)(2.7,-0.2)(3.7,1.8)(0.7,1.8)
%\psline(-0.25,-0.5)(1.25,2.5)
%\psline(2.75,-0.5)(4.25,2.5)
%\psline(-0.5,0)(4.5,0)
%\psline(-0.5,2)(4.5,2)
\uput[ur](1,0){$1$}
\uput[l](0,1){$\mi$}
\uput[ur](0,0){$0$}
\uput[dr](3,0){$3$}
\uput[u](1,2){$1+2\mi$}
  \end{pspicture}
\caption{Lattices $\latt[1,\mi]$ and $\latt[3,1+2\mi]$}\label{fig:ML}
\end{figure}
In the general situation,
recalling the discriminant of a lattice as defined in \eqref{eqn:disc}
on page \pageref{eqn:disc}, we have
\begin{equation*}
(\mMu:\mLambda)^2=
  \begin{vmatrix}
    e&f\\g&h
  \end{vmatrix}^2=
\frac
{\displaystyle\begin{vmatrix}
    e&f\\g&h
  \end{vmatrix}^2
  \begin{vmatrix}
    \alpha&\alpha'\\\beta&\beta'
  \end{vmatrix}^2}
{\begin{vmatrix}
    \alpha&\alpha'\\\beta&\beta'
  \end{vmatrix}^2}=\frac{\disc{\mLambda}}{\disc{\mMu}}.
\end{equation*}
We can use this to define the norm in general:
\begin{equation*}
  \norm{\mLambda}=\sqrt[\frac11]{\frac{\disc{\mLambda}}{\disc{\ord}}}.
\end{equation*}\label{last-disc}
This is always positive, unlike the norm of some numbers when $d>0$.
But suppose $\alpha\in K$, and let $\ord[]$ be an order of $K$.  Then
$\alpha\ord[]$ is a lattice belonging to $\ord[]$; and since
$\ord[]=\latt[1,c\omega]$ for some positive rational integer $c$, we
have
\begin{equation*}
  \norm{\alpha\ord[]}=\sqrt[\frac11]
  {\frac
    {\begin{vmatrix}
      \alpha&\alpha'\\\alpha c\omega&\alpha'c\omega'
     \end{vmatrix}^2}
    {\begin{vmatrix}
      1&1\\c\omega&c\omega'
     \end{vmatrix}^2}}
=\oldsqrt{(\alpha\alpha')^2}=\size{\norm{\alpha}}.
\end{equation*}

\myday{May 2, 2008 (Friday)}

\topic{Products of lattices}

The product of lattices $\mLambda$ and $\mMu$ of $K$
is the smallest subgroup of $K$ that includes the set
$\{xy:x\in\mLambda\And y\in\mMu\}$.  
If $\mLambda=\latt$ and $\mMu=\latt[\gamma,\delta]$, then
\begin{equation*}
  \mLambda\mMu=\latt[\alpha\gamma,\alpha\delta,\beta\gamma,\beta\delta].
\end{equation*}
Then $\mLambda\mMu$ is a lattice by Lemma~\ref{lem:lat-cond}, 
since $\roi$ includes $m\mLambda$ and $n\mMu$,
and therefore $nm\mLambda\mMu$, for some $m$ and $n$,
and $\mLambda\mMu$ spans $K$ 
since $\mLambda\mMu$ contains $\alpha\gamma$ and $\beta\gamma$, which span.

\begin{lemma}\label{lem:mult}
  Multiplication of lattices is commutative and associative, and
  \begin{equation*}
    \ord\cdot\mLambda=\mLambda.
  \end{equation*}
\end{lemma}

\begin{proof}
  The first part follows from the same properties of multiplication of
  numbers.  For the second part, $\mLambda\included\ord\cdot\mLambda$ since
  $1\in\ord$, and $\ord\cdot\mLambda\included\mLambda$ by definition of
  $\ord$. 
\end{proof}

\begin{lemma}\label{lem:LL'}
For all lattices $\mLambda$ belonging to an order $\ord[]$,
\begin{equation*}
  \mLambda\mLambda'=\norm{\mLambda}\cdot\ord[].
\end{equation*}
\end{lemma}

\begin{proof}
  Suppose first $\mLambda=\latt[1,\tau]$, where
  \begin{align*}
    A\tau^2+B\tau+C&=0,& \gcd(A,B,C)&=1,& A&>0.
  \end{align*}
  Then
  \begin{align*}
  \frac BA&=-(\tau+\tau'),&\frac CA&=\tau\tau',& \ord&=\latt[1,A\tau].  
  \end{align*}
Hence
\begin{multline*}
  \latt[1,\tau]\latt[1,\tau']
=\latt[1,\tau',\tau,\tau\tau']
=\Bigl\langle\frac AA,\tau,\frac BA,\frac CA\Bigr\rangle\\
=\Bigl\langle\frac1A,\tau\Bigr\rangle
=\frac1A\latt[1,A\tau]
=\frac1A\cdot\ord.
\end{multline*}
But
\begin{equation*}
  \norm{\latt[1,\tau]}=\sqrt[\frac11]\frac
{
  \begin{vmatrix}
    1&1\\\tau&\tau'
  \end{vmatrix}^2}
{
  \begin{vmatrix}
    1&1\\A\tau&A\tau'
  \end{vmatrix}^2}
=\frac1A.
\end{equation*}
We can write an arbitrary lattice as $\latt[\alpha,\alpha\tau]$.  
Then
\begin{multline*}
\latt[\alpha,\alpha\tau]\latt[\alpha',\alpha'\tau']
=\alpha\latt[1,\tau]\alpha'\latt[1,\tau']
=\alpha\alpha'\norm{\latt[1,\tau]}\ord\\
=\norm{\latt[\alpha,\alpha\tau]}\ord,
\end{multline*}
where $\mLambda$ can be understood indifferently as $\latt[1,\tau]$ or
$\latt[\alpha,\alpha\tau]$, by Theorem~\ref{thm:homothety}.
\end{proof}

\begin{theorem}\label{thm:group}
The lattices belonging to an order $\ord[]$ compose an abelian group
under multiplication; the identity is $\ord[]$ itself, and inversion
given by
\begin{equation*}
  \mLambda\inv=\frac1{\norm{\mLambda}}\mLambda'.
\end{equation*}
\end{theorem}

\begin{proof}
By Lemmas~\ref{lem:mult} and~\ref{lem:LL'}, 
it remains to show that the set of lattices belonging to $\ord[]$ 
is actually closed under multiplication.  We compute
\begin{multline}\label{eqn:LMO}
    \norm{\mLambda}\norm{\mMu}\cdot\ord[]
=\norm{\mLambda}\cdot\ord[]\cdot\norm{\mMu}\cdot\ord[]\\
=\mLambda\mLambda'\mMu\mMu'
=(\mLambda\mMu)(\mLambda\mMu)'
=\norm{\mLambda\mMu}\cdot\ord[\mLambda\mMu].    
\end{multline}
Since $\ord[]=\latt[1,c\omega]$ and $\ord[\mLambda\mMu]=\latt[1,e\omega]$ 
for some positive rational integers $c$ and $e$,
using the new expressions in \eqref{eqn:LMO} gives us
\begin{align*}
  \norm{\mLambda}\norm{\mMu}&=\norm{\mLambda\mMu},&
  \norm{\mLambda}\norm{\mMu}c\omega&=\norm{\mLambda\mMu}e\omega,
\end{align*}
and therefore $c=e$, so $\ord[\mLambda\mMu]=\ord[]$.
\end{proof}

\begin{porism}
  If $\mLambda$ and $\mMu$ belong to the same order, then
  \begin{equation*}
    \norm{\mLambda\mMu}=\norm{\mLambda}\norm{\mMu}.
  \end{equation*}
\end{porism}

\myweek

\myday{May 6, 2008 (Tuesday)}

\topic{Arithmetic of lattices}

In addition to multiplying, we can add lattices:
\begin{equation*}
  \mLambda+\mMu=\{\xi+\eta\colon \xi\in\mLambda\And\eta\in\mMu\}.
\end{equation*}
Proving the following is Exercise \ref{ex:addition}.

\begin{lemma}\label{lem:addition}
  Let $\mLambda$ and $\mMu$ be lattices of $K$.
  \begin{compactenum}
\item
    $\mLambda+\mMu$ is a lattice, and
    \begin{equation*}
      \latt+\latt[\gamma,\delta]=\latt[\alpha,\beta,\gamma,\delta].
    \end{equation*}
\item
Addition of lattices is commutative and associative.
\item
Multiplication of lattices distributes over addition.
\item
If $\mLambda$ and $\mMu$ belong to $\ord[]$, then
$\ord[]\included\ord[\mLambda+\mMu]$. 
\item\label{item:LMK}
If $\mLambda$ and $\mMu$ belong to $\roi$, then
$\ord[\mLambda+\mMu]=\roi$. 
  \end{compactenum}
\end{lemma}

Although $\mLambda$ and $\mMu$ belong to the same order $\ord[]$,
possibly $\mLambda+\mMu$ does not belong to $\ord[]$.  For example,
$\latt[n,1+\omega]$ and $\latt[1,n\omega]$ both belong to
$\latt[1,n\omega]$ (Exercise \ref{ex:n11n}), but
\begin{equation*}
  \latt[n,1+\omega]+\latt[1,n\omega]
=  \latt[n,1+\omega,1,n\omega]
=\latt[1,\omega].
\end{equation*}

We aim to show that the integral lattices belonging to $\ord[]$ have
unique prime factorizations.  What does this mean?  The integral
lattices have norms that are positive rational integers, since in this
case $\norm{\mLambda}=(\ord[]:\mLambda)$.  Also,
\begin{equation*}
  \norm{\mLambda}=1\iff\mLambda=\ord[]
\end{equation*}
(again assuming $\mLambda\included\ord[]$).  By the porism to
Theorem~\ref{thm:group}, no non-trivial factorization can go on
forever.  That is, we obtain
\begin{equation}\label{eqn:LP}
  \mLambda=P_1P_2\dotsm P_n,
\end{equation}
where each $P_i$ is an integral lattice of norm greater than $1$, with
no factors other than itself and $\ord[]$.  In a word, each $P_i$ is
\defn{irreducible}. 

For example, if $\norm{P}$ is a rational prime $p$, then $P$ is
irreducible, since $p$ is irreducible:
\begin{align*}
  P=\mLambda_0\mLambda_1
&\implies p=\norm{P}=\norm{\mLambda_0}\norm{\mLambda_1}\\
&\implies\norm{\mLambda_i}=1\text{ for some }i\\
&\implies\mLambda_i=\ord[]\And\mLambda_{1-i}=P\text{ for some }i.
\end{align*}

We want (if possible) to establish uniqueness of the factorization
in~\eqref{eqn:LP}.  For this, we use the notion of a \defn{prime}{}
lattice.  Working with the integral lattices of some order $\ord[]$,
we define \defn{divisibility}{} by
\begin{equation*}
  \mLambda\divides\mMu\iff \mLambda A=\mMu\text{ for some }A.
\end{equation*}

\begin{theorem}\label{thm:division}
  For all integral lattices $\mLambda$ and $\mMu$ of an order
  $\ord[]$,
  \begin{equation*}
    \mLambda\divides\mMu\iff\mMu\included\mLambda.
  \end{equation*}
\end{theorem}

\begin{proof}
  If $\mLambda A=\mMu$, where $A\included\ord[]$, then $\mMu=\mLambda
  A\included\mLambda\ord[]=\mLambda$.   Conversely, suppose
  $\mMu\included\mLambda$.  Then
  \begin{equation*}
    \mLambda\cdot\frac1{\norm{\mLambda}}\mLambda'\mMu=\ord[]\mMu=\mMu,\qquad
\frac1{\norm{\mLambda}}\mLambda'\mMu\included
\frac1{\norm{\mLambda}}\mLambda'\mLambda=\ord[],
  \end{equation*}
so $(1/\norm{\mLambda})\mLambda'\mMu$ is integral, and hence
$\mLambda\divides\mMu$. 
\end{proof}

Having division, we may have \tech{greatest common divisor}{s:}  An
integral lattice $\mPi$ is a \defn{greatest common divisor}{} of
$\mLambda$ and $\mMu$, provided
\begin{gather*}
\mPi\divides\mLambda\And\mPi\divides\mMu,\\
\mSigma\divides\mLambda\And\mSigma\divides\mMu\implies
\mSigma\divides\mPi.
\end{gather*}
But what \emph{is} $\mPi$ here?  We have 
\begin{gather*}
\mLambda,\mMu\included\mLambda+\mMu;\\
\mLambda,\mMu\included\mSigma\implies\mLambda+\mMu\included\mSigma.
\end{gather*}
Since $\mLambda+\mMu\included\ord[]$,
we can apply Theorem~\ref{thm:division}, \emph{provided}
$\mLambda+\mMu$ also belongs to $\ord[]$.  
We have this in case $\ord[]$ is $\ord$,
by Lemma~\ref{lem:addition}~\eqref{item:LMK}:

\begin{lemma}\label{lem:gcd}
The sum of integral lattices of $\roi$
is their greatest common divisor.
\end{lemma}

An integral lattice $P$ is \defn{prime}{} if
\begin{equation*}
  P\divides\mLambda\mMu\And P\ndivides\mLambda\implies P\divides\mMu,
\end{equation*}
equivalently,
\begin{equation*}
  \mLambda\mMu\included P\And \mLambda\nincluded
  P\implies\mMu\included P.
\end{equation*}

\begin{lemma}\label{lem:irred-prime}
  Irreducible integral lattices of $\roi$ are prime.
\end{lemma}

\begin{proof}
Suppose $\mPi$ is irreducible, and $\mLambda\mMu\included \mPi$, 
but $\mLambda\nincluded \mPi$.  
Sincet $\mPi+\mLambda\divides\mPi$ by Lemma~\ref{lem:gcd},
and $\mPi$ is irreducible, 
$\mPi+\mLambda$ is either $\mPi$ or $\ord[]$.  
But $\mPi\ndivides\mLambda$, so $\mPi+\mLambda=\ord[]$.  Hence
  \begin{equation*}
    \mMu=\ord[]\mMu=(\mPi+\mLambda)\mMu=\mPi\mMu+\mLambda\mMu.
  \end{equation*}
%We cannot conclude immediately that $\mPi\divides\mMu$.
But $\mLambda\mMu=\mPi\mSigma$ for some integral $\mSigma$ since
$\mPi\divides\mLambda\mMu$.  Hence
\begin{equation*}
  \mMu=\mPi\mMu+\mPi\mSigma=\mPi(\mMu+\mSigma).
\end{equation*}
By Lemma~\ref{lem:addition}~\eqref{item:LMK}, we have $\mPi\divides\mMu$.
\end{proof}

\begin{theorem}\label{thm:upf}
The integral lattices of $\roi$ admit unique prime factorizations.  
\end{theorem}

\begin{proof}
The proof is as for the Fundamental Theorem of Arithmetic.
  Suppose $P_1P_2\dotsm P_m$ and $Q_1Q_2\dotsm Q_m$ are two
  irreducible factorizations of the same lattice $\mLambda$.  Then
  $P_1\divides\mLambda$, so $P_1\divides Q_i$ for some $i$ by
  Lemma~\ref{lem:irred-prime}.  We may assume $i=1$.  Then $P_1=Q_1$,
  since $P_1\neq\roi$ and $Q_1$ is irreducible.  We now have
  \begin{gather*}
    P_1P_2\dotsm P_m=P_1Q_2\dotsm Q_n,\\
%    P_1{}'P_1P_2\dotsm P_m=P_1{}'P_1Q_2\dotsm Q_n,\\
%\norm{P_1}P_2\dotsm P_m=\norm{P_1}Q_2\dotsm Q_n,\\
P_2\dotsm P_m=Q_2\dotsm Q_n
  \end{gather*}
since we are in a group.
Continuing, we get that $m=n$ and we may assume $P_i=Q_i$.
\end{proof}

\myday{May 9, 2008 (Friday)}

\topic{Prime factorizations}

We want to \emph{find} prime factorizations.  
For example, letting $d=-5$ and $\ord[]=\roi$,
so that this is $\latt[1,\omega]$,
from~\eqref{eqn:3215}
we have,
as an equation of products of integral lattices of $\ord[]$,
\begin{equation}\label{eqn:321o}
  (3\ord[])(2\ord[])=((1+\omega)\ord[])((1-{\omega})\ord[]).
\end{equation}
Since
\begin{equation*}
  (1\pm\omega)\ord[]
=\latt[1\pm\omega,\omega\pm\omega^2]
=\latt[1\pm\omega,\omega\mp5]
=\latt[1\pm\omega,6],
\end{equation*}
we can write \eqref{eqn:321o} as
\begin{equation*}
  \latt[3,3\omega]\latt[2,2\omega]
=\latt[6,1+\omega]\latt[6,1-\omega].
\end{equation*}
By Theorem \ref{thm:upf},
the factors here cannot be prime.  
What then are the prime factors of, for example, 
$2\ord[]$, which is $\latt[2,2\omega]$?  
We have $\norm{2\ord[]}=\norm 2\norm{\ord[]}=4$, 
so we should look for factors of norm $2$.  
Two possibilities are $\latt[2,\omega]$ and $\latt[1,2\omega]$.  
But
\begin{align*}
  \latt[2,\omega]&=2\xlat[1,\frac12\omega],&4\left(\frac12\omega\right)^2+5&=0, 
\end{align*}
and therefore, by Theorems \ref{thm:homothety} and \ref{thm:conductor}
(page \pageref{thm:homothety}),
\begin{equation*}
  \ord[{\latt[2,\omega]}]=
\xlat[1,4\cdot\frac12\omega]=\latt[1,2\omega],
\end{equation*}
which is not $\ord[]$.
In particular, $\latt[2,\omega]$ does not belong to $\ord[]$.  
Similarly, $\latt[1,2\omega]$ does not, but belongs to itself.  

A third option for a prime factor of
$\latt[2,2\omega]$ is $\latt[2,1+\omega]$.
(See Figure~\ref{fig:2-wrong}.) 
\begin{figure}
\psset{unit=8mm,dotsize=4pt 2,linestyle=dotted}
%\mbox{}\hfill
  \begin{pspicture}(-1,-0.5)(2,5)
\pspolygon(0,0)(2,0)(2,2.236)(0,2.236)
    \psdots(0,0)(2,0)(0,2.236)(2,2.236)(0,4.472)(2,4.472)
    \psdots[dotstyle=o](1,0)(1,2.236)(1,4.472)
\uput[dl](0,0){$0$}
\uput[dr](1,0){$1$}
\uput[ul](0,2.236){$\sqrt{{-5}}$}
  \end{pspicture}
\hfill
  \begin{pspicture}(-0.5,-0.5)(2,5)
\pspolygon(0,0)(1,0)(1,4.472)(0,4.472)
    \psdots(0,0)(2,0)(0,4.472)(2,4.472)(1,0)(1,4.472)
    \psdots[dotstyle=o](0,2.236)(2,2.236)(1,2.236)
\uput[dl](0,0){$0$}
\uput[dr](1,0){$1$}
\uput[ul](0,2.236){$\sqrt{{-5}}$}
  \end{pspicture}
\hfill\mbox{}
\begin{pspicture}(-0.5,-0.5)(3.1,5)
\pspolygon(0,0)(2,0)(3,2.236)(1,2.236)
    \psdots(0,0)(2,0)(0,4.472)(2,4.472)(1,2.236)(3,2.236)
    \psdots[dotstyle=o](0,2.236)(2,2.236)(1,0)(1,4.472)(3,0)(3,4.472)
\uput[dl](0,0){$0$}
\uput[dr](1,0){$1$}
\uput[ul](0,2.236){$\sqrt{{-5}}$}
  \end{pspicture}
%\hfill\mbox{}
  \caption{Index-$2$ sublattices of
  $\latt[1,\sqrt{{-5}}]$}\label{fig:2-wrong} 
\end{figure}
This works: if $\alpha=(1+\omega)/2$, then
\begin{align*}
  (2\alpha-1)^2&=-5,&
4\alpha^2-4\alpha+6=0,
\end{align*}
so $2\alpha^2-2\alpha+3=0$, and $\latt[2,1+\omega]$ belongs to $\ord[]$.  
Moreover $\latt[2,1+\omega]'=\latt[2,1+\omega]$, so by Lemma~\ref{lem:LL'},
\begin{equation*}
  \latt[2,1+\omega]^2=2\ord[].
\end{equation*}

Now let $d$ be arbitrary, $\ord[]=\roi$, 
and $P$ be a prime lattice of $\ord[]$.  
There is a non-zero element $\alpha$ of $P$.  
Then $\alpha'\in\ord[]$, so $P$ contains $\alpha\alpha'$, a
rational integer.  Since $P$ is prime, the least positive rational
integer that it contains must be prime.  Suppose this is $p$.  then
\begin{equation*}
  P\divides p\ord[].
\end{equation*}
Conversely, suppose $p$ is a rational prime, and $P$ is a prime factor
of $p\ord[]$.  Then
\begin{equation*}
  \norm{P}\divides p^2.
\end{equation*}
\begin{itemize}
\item 
If $\norm P=p^2$, this means $P$ is just $p\ord[]$.  
\item
If $\norm P=p$, then $PP'=p\ord[]$, but possibly $P=P'$.
\end{itemize}
So there are three possibilities.
\begin{enumerate}
\item 
If $p\ord[]$ is itself prime, then $p$ is \defn{inert}{} in $\ord[]$;
\item
If $p\ord[]=PP'$, where $P\neq P'$, then $p$ \defn{split}{s} in $\ord[]$;
\item
If $p\ord[]=P^2$, then $p$ \defnplain{ramifies}{}\index{ramify} in $\ord[]$.
\end{enumerate}

\myweek

\myday{May 20, 2008 (Tuesday)}

\topic{Primes}

To compute which of the three possibilities actually happens, it is
convenient to let\index{$\mDelta$}
\begin{equation*}
  \mDelta=\Delta(\ord[])=
  \begin{vmatrix}
    1&1\\
\omega&\omega'
  \end{vmatrix}^2=
\begin{cases}
  d,&\text{ if }d\equiv1\pmod 4;\\
4d,&\text{ if }d\not\equiv1.
\end{cases}
\end{equation*}

\begin{theorem}
  \mbox{}
  \begin{compactenum}
    \item\label{item:inert}
If $p\ndivides\mDelta$, and $\mDelta\equiv x^2\pmod{4p}$ has no
solution, then $p$ is inert in $\ord[]$.
\item\label{item:splits}
If $p\ndivides\mDelta$, and $\mDelta\equiv s^2\pmod{4p}$, then $p$
splits in $\ord[]$, and 
\begin{equation*}
p\ord[]=\Bigl\langle p,\frac{s+\sqrt{\mDelta}}2\Bigr\rangle
\Bigl\langle p,\frac{s-\sqrt{\mDelta}}2\Bigr\rangle.
\end{equation*}
\item\label{item:ramifies}
If $p\divides\mDelta$, then $p$ ramifies in $\ord[]$, and
\begin{equation*}
  p\ord[]=
  \begin{cases}
    \Bigl\langle
    p,\displaystyle\frac{\mDelta+\sqrt{\mDelta}}2\Bigr\rangle^2,&\text{
    if $p$ is odd;}\\
\latt[2,\sqrt d]^2,&\text{ if }p=2\And d\equiv 2;\\
\latt[2,1+\sqrt d]^2,&\text{ if }p=2\And d\equiv 3.
  \end{cases}
\end{equation*}
  \end{compactenum}
\end{theorem}

\begin{proof}\sloppy
  Suppose $p$ is not inert in $\ord[]$.  Then $p\ord[]$ has a proper
  prime factor $P$, of norm $p$, so that
  \begin{equation*}
    (\ord[]:P)=p.
  \end{equation*}
So there are just $p$ distinct congruence-classes \emph{modulo} $P$.
Moreover, they are represented by the elements of
$\{0,1,\dots,p-1\}$.  Indeed, if $0\leq i\leq j<p$, and $i\equiv
j\pmod P$, then $P\divides (j-i)\ord[]$, so $\norm
P\divides\norm{(j-i)\ord[]}$, that is,
\begin{equation*}
  p\divides(j-i)^2,
\end{equation*}
so $i=j$.  Therefore, in particular, there is a rational integer $r$
such that $0\leq r<p$ and
\begin{gather*}
  \frac{\mDelta+\sqrt{\mDelta}}2\equiv r\pmod P,\\
2r-\mDelta-\sqrt{\mDelta}\equiv0\pmod{2P},\\
2P\divides(2r-\mDelta-\sqrt{\mDelta})\ord[],\\
\norm{2P}\divides\norm{(2r-\mDelta-\sqrt{\mDelta})\ord[]},\\
4p\divides(2r-\mDelta)^2-\mDelta,\\
\mDelta\equiv(2r-\mDelta)^2\pmod{4p}.
\end{gather*}
This proves~\eqref{item:inert}.

Now suppose $\mDelta\equiv s^2\pmod{4p}$, and let
\begin{equation*}
  P=\Bigl\langle p,\frac{s+\sqrt{\mDelta}}2\Bigr\rangle.
\end{equation*}
To compute $\ord[P]$ by means of Theorem~\ref{thm:conductor}, we have
\begin{align*}
  \alpha=\frac{s+\sqrt{\mDelta}}{2p}
&\implies 2p\alpha-s=\sqrt{\mDelta}\\
&\implies 4p^2\alpha^2-4ps\alpha+s^2-\mDelta=0\\
&\implies p\alpha^2-s\alpha+\frac{s^2-\mDelta}{4p}=0.
\end{align*}
If $p\ndivides\mDelta$, then $p\ndivides s$, and we can conclude
\begin{equation*}
  \ord[P]=\Bigl\langle 1,\frac{s+\sqrt{\mDelta}}2\Bigr\rangle=\ord[].
\end{equation*}
So $P$ belongs to $\ord[]$; and it has norm $p$, so $p\ord[]=PP'$ by
Lemma~\ref{lem:LL'}.  Finally, $P\neq P'$, since $P+P'$ contains $s$,
but $P$ does not.  Thus~\eqref{item:splits}.

Finally, to prove~\eqref{item:ramifies}, since each of the given
lattices is its own conjugate, it is enough to show that the lattices
belong to $\ord[]$.  For example, in case $p$ is odd, assuming
$p\divides\mDelta$, we have
\begin{align*}
  \alpha=\frac{\mDelta+\sqrt{\mDelta}}{2p}
&\implies 2p\alpha-\mDelta=\sqrt{\mDelta}\\
&\implies 4p^2\alpha^2-4p\mDelta \alpha+\mDelta^2-\mDelta=0\\
&\implies p\alpha^2-\mDelta \alpha+\frac{\mDelta^2-\mDelta}{4p}=0.
\end{align*}
We always have $\mDelta\equiv0$ or $1 \pmod4$, so
$4\divides\mDelta^2-\mDelta$; hence $4p\divides\mDelta^2-\mDelta$.
But $\mDelta^2-\mDelta=\mDelta(\mDelta-1)$, and $p\ndivides\mDelta-1$, but
also $p^2\ndivides\mDelta$, since $d$
is \sqf.  Therefore $\latt[p,(\mDelta+\sqrt{\mDelta})/2]$ does
belong to $\ord[]$.  The remaining cases are easier.
\end{proof}

For example, if $d=21$, then $\mDelta=21$, and the primes ramifying in
$\ord[]$ are just $3$ and $7$.

\appendix

\chapter{Exercises}

\section{February 26, 2008}


  \begin{xca}
    Let $S$ be the set of Pythagorean triples $(a,b,c)$ such
    that
$\gcd(a,b,c)=1$;
$a$, $b$, and $c$ are positive; and
$a<b$.
Order $S$ by the rule
\begin{equation*}
  (a,b,c)<(d,e,f)\iff(a+b<d+e)\lor(a+b=d+e\land b<e).
\end{equation*}
Find the first few elements of $S$ with respect to this ordering. 
  \end{xca}

  \begin{xca}
Solve $x^2+4y^2=z^2$.
  \end{xca}

  \begin{xca}
    Solve $x^4+y^2=z^2$.
  \end{xca}

  \begin{xca}
    \begin{enumerate}
      \item
Show that $f(x,y)=0$ is soluble if and only if $f(3x+2y,4x+3y)=0$ is
soluble.
\item
Find necessary and sufficient conditions on $a$, $b$, $c$, and $d$
such that an arbitrary Diophantine equation $f(x,y)=0$ is soluble if
and only if $f(ax+by,cx+dy)=0$ is soluble.
    \end{enumerate}
  \end{xca}

  \begin{xca}
\begin{enumerate}
\item
    Find the expansion of $\sqrt d$ as a continued fraction for
    various $d$, including $7$. 
\item
Solve the Pell equation $x^2-dy^2=1$ for these $d$.
\end{enumerate}
  \end{xca}

  \begin{xca}
    \begin{enumerate}
      \item
        Show $[a_0;a_1,\dots,a_k,a_{k+1},\dots,a_n]=$
        \begin{equation*}
          [a_0;a_1,\dots,a_k,[a_{k+1},\dots,a_n]].
        \end{equation*}
\item
Show $  [a_0;a_1,\dots,a_k,a_{k+1},\dots]=$
\begin{equation*}
 [a_0;a_1,\dots,a_k,[a_{k+1},\dots]].  
\end{equation*}
\item
Compute $[\overline{2;1}]$ (which is $[2;1,\overline{2,1}]$) in terms
of radicals. 
\item
Show that $[a_0;a_1,\dots,a_k,\overline{a_{k+1},\dots,a_n}]$ is always
the root of a quadratic polynomial.
    \end{enumerate}
  \end{xca}

  \section{March 11, 2008}

  
  \begin{xca}
If $d$ is a positive non-square rational integer, prove $\sqrt d$ is
irrational.  
  \end{xca}

  \begin{xca}
    Find a greatest common divisor $\alpha$ of the Gaussian integers
    $27+55\mi$ and $20+18\mi$, and solve
    \begin{equation*}
    (27+55\mi)\xi+(20+18\mi)\eta=\alpha.
    \end{equation*}
  \end{xca}

  \begin{xca}
    Find all solutions of the Diophantine equation
    \begin{equation*}
     x^2+y^2=1170.
    \end{equation*}
  \end{xca}

  \begin{xca}
    Assuming $n$ is positive, prove that the number
    of solutions of the Diophantine equation 
    \begin{equation*}
    x^2+y^2=n
    \end{equation*}
is 4 times the
    excess of the number of positive factors of $n$ that are congruent
    to $1$ \emph{modulo} $4$ over the number that are congruent to $3$
    \emph{modulo} $4$.
  \end{xca}

  \begin{xca}
    \begin{enumerate}
      \item
    Characterize (by describing their prime factorizations) those
    Gaussian integers $\alpha$ such that $\size{\alpha}^2$ is square
    as a rational integer.
\item
Use this characterization to solve the Diophantine equation 
\begin{equation*}
x^2+y^2=z^2.
\end{equation*}
    \end{enumerate}
  \end{xca}

  \begin{xca}\label{ex:Eisenstein}
    The polynomial $x^2+x+1$ has two conjugate roots.  Let~$\omega$ be
    the root with positive imaginary part.
    \begin{enumerate}
      \item
Write $\omega$ in radicals.
\item
Sketch $\Z[\omega]$ as a subset of the complex plane.
\item
Letting $\norm z=\size z^2$, show that $\norm{\alpha}\in\N$ when
$\alpha\in\Z[\omega]$. 
\item
Express $\norm{x+\omega y}$ in terms of $x$ and $y$.
\item
Show that $\Z[\omega]$ with $z\mapsto\norm z$ is a Euclidean domain.
    \end{enumerate}
(The elements of $\Z[\omega]$ are the \defn{Eisenstein integer}{s.})
  \end{xca}

  \section{April 3, 2008}

  \begin{xca}
    Verify that the integers of a quadratic field do compose a ring.
  \end{xca}

  \begin{xca}
    Suppose $\tau=(15+3\sqrt{17})/4$.  Find $A$, $B$, and $C$ in $\Z$
    such that $A\tau^2+B\tau+C=0$ and $\gcd(A,B,C)=1$.
  \end{xca}

  \begin{xca}
    Suppose $A\tau^2+B\tau+C=0$ for some $A$, $B$, and $C$ in $\Z$,
    where $A>0$ and $\gcd(A,B,C)=1$.
    \begin{enumerate}
      \item\label{item:ABCa}
Show $\latt[1,A\bar\tau]\latt[1,\tau]=\latt[1,\tau]$.
\item\label{item:ABCb}
Show $\latt[A,A\bar\tau]\latt[1,\tau]=\latt[1,A\bar\tau]$.
\item
Using~\eqref{item:ABCa} and~\eqref{item:ABCb}, show
$\ord=\latt[1,A\bar\tau]$, where $\mLambda=\latt[1,\tau]$. 
    \end{enumerate}
  \end{xca}

  \begin{xca}
    Let $\mLambda$ be the lattice
    \begin{equation*}
    \Bigl\langle\frac{3+5\sqrt 6}2,\frac{6+\sqrt 6}3\Bigr\rangle
    \end{equation*}
    of $\Q(\sqrt 6)$.  Find $\ord$. 
  \end{xca}

  \begin{xca}
    Suppose $\tau\in\C\setminus\Q$.  Show that the following are equivalent:
    \begin{enumerate}
\renewcommand{\theenumi}{\roman{enumi}}
      \item
$A\tau^2+B\tau+C=0$ for some $A$, $B$, and $C$ in $\Z$;
\item
$\alpha\latt[1,\tau]\included\latt[1,\tau]$ for some $\alpha$ in $\C\setminus\Z$.
    \end{enumerate}
  \end{xca}

  \begin{xca}
    Let $f(x,y)$ be the quadratic form
    \begin{equation*}
      60x^2+224xy-735y^2.
    \end{equation*}
    \begin{enumerate}
      \item
Find the discriminant of $f$ in the form $n\sqrt d$, where $n$ and $d$
are rational integers, and $d$ is \sqf.
\item
Find all solutions from $\Z$ of $f(x,y)=1$.
\item
Find all solutions from $\Z$ of $f(x,y)=6$.
    \end{enumerate}
  \end{xca}

  \begin{xca}
    For every lattice $\mLambda$ of a quadratic field $K$, show that
    the units of $\ord$ are just the units of $\roi$ that are in
    $\ord$.  
  \end{xca}

  \section{April 10, 2008}

  
These exercises involve quadratic Diophantine equations.

\begin{xca}
  Solve
  \begin{equation*}
    2x^2+2xy+y^2=25.
  \end{equation*}
\end{xca}

\begin{xca}
  Solve
  \begin{equation*}
    9x^2+6xy+2y^2=17.
  \end{equation*}
\end{xca}

\begin{xca}
  Solve (if you can!)
  \begin{equation*}
    121x^2+304xy+191y^2=37.
  \end{equation*}
(If nothing else works, try letting $3x+4y=u$ and $4x+5y=v$.)
\end{xca}

  \begin{xca}
    Solve
    \begin{equation*}
      4x^2+2xy-y^2=44.
    \end{equation*}
  \end{xca}

  \begin{xca}
    Concerning
    \begin{equation*}
      8x^2+4xy-y^2=m:
    \end{equation*}
    \begin{enumerate}
      \item
solve when $m=8$;
\item
solve when $m=44$;
\item
find all $m$ for which the equation is soluble, where $0<m<44$.
    \end{enumerate}
  \end{xca}

  \section{May 18, 2008}

  \begin{xca}
    Prove that the $n$th convergent of $\sqrt 5$ is
    \begin{equation*}
      \frac{2\Fib{3n+2}+\Fib{3n+3}}{\Fib{3n+3}}.
    \end{equation*}
  \end{xca}

  \begin{xca}\label{ex:ord=lat}
    Verify that an order $\ord[]$ of $K$ is in particular a lattice
    $\mLambda$ such that $\ord=\ord[]$.
  \end{xca}

  \begin{xca}\label{ex:addition}
      Let $\mLambda$ and $\mMu$ be lattices of $K$.  Prove the
      following [which is Lemma \ref{lem:addition}].
  \begin{enumerate}
\item
    $\mLambda+\mMu$ is a lattice, and
    \begin{equation*}
      \latt+\latt[\gamma,\delta]=\latt[\alpha,\beta,\gamma,\delta].
    \end{equation*}
\item
Addition of lattices is commutative and associative.
\item
Multiplication of lattices distributes over addition.
\item
If $\mLambda$ and $\mMu$ belong to $\ord[]$, then
$\ord[]\included\ord[\mLambda+\mMu]$. 
\item
If $\mLambda$ and $\mMu$ belong to $\roi$, then
$\ord[\mLambda+\mMu]=\roi$. 
  \end{enumerate}
  \end{xca}

  \begin{xca}\label{ex:n11n}
Show that $\latt[n,1+\omega]$ and $\latt[1,n\omega]$ both belong to
$\latt[1,n\omega]$ .
  \end{xca}

  \chapter{Examinations}

  \section{March 24, 2008 (Monday)}

  \begin{instructions}
    Take at most 90 minutes to write reasonably legible solutions on
    the blank sheets provided.
    You may want to do scratch-work first, on sheets that you will
    keep.  But the sheets that you turn in should show sufficient work to
    justify your answers.
    You may keep this problem-sheet for future study.  \emph{Kolay gelsin.} 
  \end{instructions}

  \begin{prob}
This problem involves the Gaussian integers.  Let $\alpha=40+5\mi$ and
$\beta=39\mi$.  
    \begin{enumerate}
      \item\label{item:40a}
Find a greatest common divisor of $\alpha$ and $\beta$.
\item
If $\gamma$ is your answer to \eqref{item:40a}, solve
\begin{equation*}
  (40+5\mi)\cdot\xi+39\mi\cdot\eta=\gamma.
\end{equation*}
    \end{enumerate}
  \end{prob}

\begin{sol}
\begin{asparaenum}
\item
    Apply the Euclidean algorithm:
    \begin{gather*}
\frac{\alpha}{\beta}=\frac{40+5\mi}{39\mi}
=\frac{5-40\mi}{39}=-\mi+\frac{5-\mi}{39},\\
40+5\mi=(39\mi)(-\mi)+1+5\mi;\\
\frac{39\mi}{1+5\mi}=\frac{195+39\mi}{26}
=7+\mi+\frac{1+\mi}2,\\
39\mi=(1+5\mi)(7+\mi)-2+3\mi;\\
\frac{1+5\mi}{-2+3\mi}=\frac{(1+5\mi)(-2-3\mi)}{13}=1-\mi;
\end{gather*}
thus $-2+3\mi$ is a greatest common divisor of $\alpha$ and $\beta$.
\item
By the computations above,
\begin{gather*}
  \alpha=\beta\cdot(-\mi)+1+5\mi,\\
1+5\mi=\alpha+\beta\cdot\mi;\\
\beta=(\alpha+\beta\cdot\mi)(7+\mi)-2+3\mi,\\
-2+3\mi=\alpha\cdot(-7-\mi)+\beta\cdot(2-7\mi).
\end{gather*}
\end{asparaenum}
\end{sol}

  \begin{remark}
    In (i), each step of the computation should lower the norm of the
    remainder.  Indeed, $\norm{39\mi}>\norm{1+5\mi}>\norm{-2+3\mi}$.
    But the way to achieve this is not unique.  For example, from the third
    line, the computation could have been
    \begin{gather*}
\frac{39\mi}{1+5\mi}=\frac{195+39\mi}{26}
=8+\mi+\frac{-1+\mi}2,\\
39\mi=(1+5\mi)(8+\mi)-3-2\mi;\\
\frac{1+5\mi}{-3-2\mi}=\frac{(1+5\mi)(-3+2\mi)}{13}=-1-\mi.
\end{gather*}
So $-3-2\mi$ could also be found as a greatest common divisor of
$\alpha$ and $\beta$.  (Also $2-3\mi$ and $3+2\mi$ are $\gcd$'s.)

In an alternative approach to (i), one might observe that
\begin{gather*}
  \alpha=5\cdot(8+\mi)=(2+\mi)(2-\mi)(8+\mi),\\
\norm{\alpha}=5^2\cdot65=5^3\cdot13;\\
\beta=3\cdot13\mi,\\
\norm{\beta}=3^2\cdot13^2.
\end{gather*}
The factors $2\pm\mi$ of $\alpha$ are prime, and their norm is
$5$, and $5\ndivides\norm{\beta}$. Also, $3$ is prime, and
$3\ndivides\norm{\alpha}$.  One can therefore take $\gamma$ as a
$\gcd$ of $8+\mi$ and $13\mi$.  To find this, one could apply the
Euclidean algorithm to the latter pair. 

Instead of applying the Algorithm here, 
one may note that,
since $\gcd(\norm{\alpha},\norm{\beta})=13$, we must
have $\norm{\gamma}\divides13$.  Since $13$ has the prime
factorization $(3+2\mi)(3-2\mi)$, each factor having norm $13$, one
could test whether one of these 
factors divides $\alpha$ and $\beta$: if one does, then it is
$\gamma$; if neither does, then $\alpha$ and $\beta$ are co-prime.

The alternative approaches are not much help in solving (ii).
However, once one \emph{does} have an answer to (ii), 
it is easy to check.
  \end{remark}

  \begin{prob}
This problem involves the Diophantine equation
\begin{equation}\label{eqn:D}
  2x^2-3y^2=2.
\end{equation}
    \begin{enumerate}
      \item
Express $\oldsqrt{3/2}$ as a continued fraction.
\item
  Find a positive solution to~\eqref{eqn:D}.
\item
Find a solution $(a,b)$ to~\eqref{eqn:D} in which each of $a$ and $b$
has two digits (in the usual decimal notation).
\item
Find a solution $(a,b)$ to~\eqref{eqn:D} in which each of $a$ and $b$
has three digits.
\end{enumerate}
  \end{prob}

  \begin{sol}
    \begin{asparaenum}
      \item
Let $x=\oldsqrt{3/2}=\sqrt 6/2$.  Applying our algorithm to $x$, we
have
\begin{align*}
&&  a_0&=1,&\xi_0&=\frac{\sqrt 6}2-1=\frac{\sqrt 6-2}2;\\
\frac2{\sqrt 6-2}&=\sqrt 6+2,& a_1&=4,&\xi_2&=\sqrt 6-2;\\
\frac1{\sqrt 6-2}&=\frac{\sqrt 6+2}2,&a_2&=2,&\xi_2&=\frac{\sqrt
  6-2}2=\xi_0; 
\end{align*}
therefore $\oldsqrt{3/2}=[1;\overline{4,2}]$.
\item
The equation \eqref{eqn:D} can be written as $x^2-(3/2)y^2=1$.  Assuming it is
like a Pell equation,
we expect solutions to ($*$) to come from convergents of $x$.  These
are:
\begin{equation*}
  \frac11,\quad\frac54,\quad\frac{11}9,\quad
  \frac{49}{40},\quad\frac{109}{89},\quad\frac{485}{396},\quad\dots
\end{equation*}
In particular, we expect the solutions to come from $[1;4]$,
$[1;4,2,4]$, $[1;4,2,4,2]$, and so on.  Indeed, $(5,4)$ is a solution.
\item
Also $(49,40)$.
\item
Also $(485,396)$.
\end{asparaenum}
\end{sol}

  \begin{remark}
    Since we have not \emph{yet} proved that our procedure for solving
    a Pell equation works in general, and since \eqref{eqn:D} is not literally
    a Pell equation anyway, one should check one's answers to (ii),
    (iii), and (iv) here.
  \end{remark}

  \begin{prob}
    In class we found the bijection
    \begin{equation*}
      t\longmapsto\Bigl(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2}\Bigr)
    \end{equation*}
between $\Q$ and the set of rational solutions (other than $(-1,0)$)
to the equation
\begin{equation*}
  x^2+y^2=1.
\end{equation*}
\begin{enumerate}
  \item
Find all rational solutions to the equation
\begin{equation*}
  x^2+3y^2=1.
\end{equation*}
\item
Find $\alpha$ in $\Q(\mi)$ such that $\norm{\alpha}=1$, but $\alpha$ is
not a Gaussian integer.
\item
Find $\beta$ in $\Q(\sqrt{{-3}})$ such that $\norm{\beta}=1$, but
$\beta$ is not an integer (that is, not an Eisenstein integer).
\end{enumerate}
  \end{prob}

  \begin{sol}
    \begin{asparaenum}
      \item
The solutions are
$\Bigl(\displaystyle\frac{1-3t^2}{1+3t^2},\frac{2t}{1+3t^2}\Bigr)$,
where $t\in\Q$; and $(-1,0)$. 
\item
Letting $t=2$ in the given formula yields
$(-3+4\mi)/5$, not a Gaussian integer.
\item
Letting $t=2$ in (i) yields $(-11+4\mi\sqrt3)/{13}$,
which is not in $\Z[(1+\mi\sqrt 3)/2]$.
    \end{asparaenum}
  \end{sol}

  \begin{remark}
    One may solve (i) just by thinking about why the given point is on
    the circle.  Alternatively, one may just use the same method
    for deriving it: find the other intersection, besides $(-1,0)$ of
    the line $y=tx+t$ and the ellipse $x^2+3y^2=1$.
  \end{remark}

  \begin{prob}    
    \begin{enumerate}
      \item
Find all distinct solutions (from $\Z$) of the Diophantine equation
\begin{equation*}
  x^2+y^2=221.
\end{equation*}
\item
Find a factorization of $27-57{}\mi$ as a product of Gaussian primes.
    \end{enumerate}
  \end{prob}

  \begin{sol}
    \begin{asparaenum}
      \item
$221=13\cdot17$.  In the Gaussian integers, $\norm{\xi}=13$ is solved
	by $3\pm2\mi$ and their associates; $\norm{\eta}=17$, by
	$4\pm\mi$ and their associates.  We have
	\begin{gather*}
	  (3\pm2\mi)(4\pm\mi)=10\pm11\mi,\qquad
	  (3\pm2\mi)(4\mp\mi)=14\pm5\mi.
	\end{gather*}
Hence the 16 desired solutions are
\begin{multline*}
  (10,\pm11),(-10,\mp11),(\mp11,10),(\pm11,-10),\\
  (14,\pm5),(-14,\mp5),(\mp5,14),(\pm5,-14).
\end{multline*}
\item
$27-57\mi=3\cdot(9-19\mi)$, where $3$ is prime; and
\begin{equation*}
\norm{9-19\mi}=81+361=442=2\cdot221.  
\end{equation*}
But $2$ has associated prime
  factors $1\pm\mi$, and
  \begin{multline*}
    \frac{9-19\mi}{1+\mi}=\frac{(9-19\mi)(1-\mi)}2=-5-14\mi\\
=-\mi\cdot(14-5\mi)=-\mi\cdot(3-2\mi)(4+\mi)
  \end{multline*}
by (i).  Since $(1+\mi)\cdot(-\mi)=1-\mi$, we conclude
\begin{equation*}
  27-57\mi=3\cdot(1-\mi)(3-2\mi)(4+\mi).
\end{equation*}
    \end{asparaenum}
  \end{sol}

  \section{May 26 (Monday)}

  
  \begin{instructions}
Solve {four} of these five problems in 90 minutes.  \emph{\.Iyi
  \c cal\i\c smalar.} 
  \end{instructions}

  \begin{prob}
Assuming $a>0$, prove
\begin{equation*}
\oldsqrt{a^2+1}=[a;\overline{2a}].
\end{equation*}
  \end{prob}

  \begin{sol}
    By the algorithm for finding continued fractions, when
    $x=\oldsqrt{a^2+1}$, we have first $a_0=a$, and then
    \begin{align*}
\xi_0&=\oldsqrt{a^2+1}-a,&
      \frac1{\xi_0}&=\frac{\oldsqrt{a^2+1}+a}{a^2+1+a^2}=\oldsqrt{a^2+1}+a,
    \end{align*}
    so $a_1=2a$ and $\xi_1=\oldsqrt{a^2+1}-a=\xi_0$.  Therefore
$x=[a;\overline{2a}]$. 
  \end{sol}

  \begin{remark}
    Alternatively, one may let
    \begin{multline*}
      x=[a;\overline{2a}]=[a;a+a,\overline{2a}]=[a;a+[a,\overline{2a}]]\\
=[a;a+x]=a+\frac1{a+x}=\frac{a^2+ax+1}{a+x}, 
    \end{multline*}
    so that $ax+x^2=a^2+ax+1$ and therefore $x^2=a^2+1$.  Since $a>0$, we
have $[a;\overline{2a}]>0$ and therefore
$[a;\overline{2a}]=x=\oldsqrt{a^2+1}$. 
  \end{remark}

  \begin{prob}
    Let $K=\Q(\sqrt 5)$ and $\mLambda=\latt[1,\sqrt 5]$.
    \begin{enumerate}
      \item
Find the order $\ord$ (that is, $\{\xi\in
K\colon\xi\mLambda\included\mLambda\}$). 
\item
Find the elements of $\ord$ having norm $1$.
    \end{enumerate}
  \end{prob}
  
  \begin{sol}
    \begin{asparaenum}
      \item
Since $\sqrt 5$ is a root of $x^2-5$, whose leading coefficient is $1$,
we can conclude $\ord=\latt[1,\sqrt 5]=\mLambda$.
\item
We know that the units of $\roi$ (when $K=\Q(\sqrt 5)$) are
$\pm\gr^n$.  Of these, those that are greater than $1$ form the list
\begin{equation*}
  \gr,1+\gr,1+2\gr,2+3\gr,3+5\gr,5+8\gr,\dots
\end{equation*}
(and in general $\gr^n=\Fib{n-1}+\Fib n\gr$).  But since $2\gr=1+\sqrt
5$, we have $\ord=\latt[1,2\gr]$; also, $\norm{\gr}=-1$.  The first
power of $\gr$ greater than $1$ that belongs to $\ord$ and has norm $1$
is therefore $\gr^6$.  Hence the elements of $\ord$ of norm $1$ are
$\pm\gr^{6n}$, where $n\in\Z$.
    \end{asparaenum}
  \end{sol}

  \begin{prob}
    Solve in $\Z$:
    \begin{equation*}
    x^2+2xy+4y^2=19.
    \end{equation*}
  \end{prob}

  \begin{sol}
We want to solve    
    \begin{equation*}
    19=x^2+2xy+4y^2=(x+y)^2+3y^2.
    \end{equation*}
Hence $y^2\leq19/3<9$, so $\size y<3$.  When $y=\pm2$, the equation
becomes $(x\pm2)^2=7$, which has no solution.  When $y=\pm1$, we get
$(x\pm 1)^2=16$, so $(x\pm1)\in\{4,-4\}$.  When $y=0$, there is no
solution.  So the solutions of the original equation are $(3,1)$,
$(-5,1)$, $(5,-1)$, $(-3,-1)$. 
  \end{sol}

  \begin{remark}
    Solving an equation means not only finding solutions, but showing
    that there are no other solutions.  This is done here by noting
    that there are only 5 possibilities for~$y$.  Alternatively, one
    may rewrite the equation as
    \begin{equation*}
19=(x+y+y\sqrt{{-3}})(x+y-y\sqrt{{-3}})=\norm{x+2\omega y},
    \end{equation*}
where we work in $\Q(\sqrt{{-3}})$.  Since $(x,y)$ is a solution if
and only if $(\size x,\size y)$ is a solution, we can obtain all
solutions from Figure~\ref{fig:1}.
\begin{figure}[ht]\center
  \begin{pspicture}(-5,-0.5)(5,4.4)
%\psgrid
\psarc(0,0){4.359}{-5}{185}
\psset{dotsize=2pt 3}
    \psdots
(0,0)(1,0)(2,0)(3,0)(4,0)(5,0)
(0,1.732)(1,1.732)(2,1.732)(3,1.732)(4,1.732)
(0,3.464)(1,3.464)(2,3.464)(3,3.464)%(4,3.464)
(-1,0)(-2,0)(-3,0)(-4,0)(-5,0)
(-1,1.732)(-2,1.732)(-3,1.732)(-4,1.732)
(-1,3.464)(-2,3.464)(-3,3.464)%(-4,3.464)
\psset{dotstyle=o}
\psdots
(0.5,4.330)(1.5,4.330)(2.5,4.330)%(3.5,4.330)
(0.5,2.598)(1.5,2.598)(2.5,2.598)(3.5,2.598)
(0.5,0.866)(1.5,0.866)(2.5,0.866)(3.5,0.866)(4.5,0.866) 
(-0.5,4.330)(-1.5,4.330)(-2.5,4.330)%(-3.5,4.330)
(-0.5,2.598)(-1.5,2.598)(-2.5,2.598)(-3.5,2.598)
(-0.5,0.866)(-1.5,0.866)(-2.5,0.866)(-3.5,0.866)(-4.5,0.866) 
\uput[ur](1,1.732){$2\omega$}
\uput[ur](4,1.732){$3+2\omega$}
\uput[ul](-4,1.732){$-5+2\omega$}
\uput[d](0,0){$0$}
\uput[d](1,0){$1$}
  \end{pspicture}
\caption{Solutions of $\norm{\xi}=19$ from
  $\latt[1,2\omega]$ in $\Q(\sqrt{{-3}})$}\label{fig:1} 
\end{figure}
  \end{remark}

  \begin{prob}
    \begin{enumerate}
      \item
    Prove that, for each $n$ in $\Z$, there are $a_n$ and $b_n$ in
    $\Z$ such that 
    \begin{equation*}
      a_n+b_n\sqrt{21}=2\Bigl(\frac{5+\sqrt{21}}2\Bigr)^n.
    \end{equation*}
\item
Find a quadratic form $f(x,y)$ and a rational integer $m$ such that
each $(\pm a_n,\pm b_n)$ is a solution of
\begin{equation}\label{eqn:f}
  f(x,y)=m.
\end{equation}
\item
Prove that each solution of~\eqref{eqn:f} is  $(\pm a_n,\pm b_n)$ for
some $n$.
    \end{enumerate}
  \end{prob}

  \begin{sol}
    \begin{asparaenum}
      \item
In $\Q(\sqrt{21})$, we have $(5+\sqrt{21})/2=2+\omega$,
and
 $\norm{(5+\sqrt{21})/2}=1$.  Hence $(5+\sqrt{21})/2$ is a unit of
  $\roi$, so its powers are also units of $\roi$.  Let
$\alpha\in\roi$.  Since
\begin{equation*}
\roi=\latt[1,\omega]=\xlat[1,\frac{1+\sqrt{21}}2],
\end{equation*}
we have $2\alpha\in\latt[2,1+\sqrt{21}]\included\latt[1,\sqrt{21}]$.  This
proves 
\begin{equation*}
a_n+b_n\sqrt{21}=2\Bigl(\frac{5+\sqrt{21}}2\Bigr)^n\in\latt[1,\sqrt{21}], 
\end{equation*}
so
$a_n,b_n\in\Z$. 
\item
Since $\norm{a_n+b_n\sqrt{21}}=4$, the pairs $(\pm a_n,\pm b_n)$ are
solutions of $x^2-21y^2=4$.
\item
Suppose $(a,b)$ is an arbitrary solution of $x^2-21y^2=4$.  Then
$a\equiv b\pmod 2$, so $2\divides a-b$.  Hence
\begin{multline*}
  \frac{a+b\sqrt{21}}2
  =\frac{a-b+b+b\sqrt{21}}2\\
  =\frac{a-b}2+b\frac{1+\sqrt{21}}2
 =\frac{a-b}2+b\omega
\in\latt[1,\omega],
\end{multline*}
so $(a+b\sqrt{21})/2$ is an element of $\roi$ of norm $1$.  But there
is $\epsilon$ or $r+s\omega$ in $\roi$ of norm $1$ such that $r,s>0$
and every element of $\roi$ of norm $1$ is $\pm\epsilon^n$ for some
$n$.  But $(5+\sqrt{21})/2=2+\omega$ and has norm $1$, so it must be
$\epsilon$.  Hence $(a,b)=(\pm a_n,\pm b_n)$ for some $n$.
    \end{asparaenum}
  \end{sol}

  \begin{remark}
    The pair $(a_n/2,b_n/2)$ solves the Pell equation $x^2-21y^2=1$,
    but its entries need not belong to $\Z$.  For example,
    $(a_1/2,b_1/2)=(5/2,1/2)$. 
  \end{remark}

  \begin{prob}    
    \begin{enumerate}
      \item
Find a quadratic field $K$, a lattice $\latt$ or $\mLambda$ of $K$, and
$m$ in $\Z$ for which the function
\begin{equation*}
  (x,y)\mapsto x\alpha+y\beta
\end{equation*}
is a bijection between the solution-set (in $\Z\times\Z$) of 
\begin{equation}\label{eqn:2}
  2x^2-3y^2=2
\end{equation}
and the solution-set in $\mLambda$ of
  $\norm{\xi}=m$.
\item\label{item:Pi}
Describe a parallelogram $\mPi$ in the plane $\R^2$ such that,
for every solution $(a,b)$ of~\eqref{eqn:2}, there is a solution
$(c,d)$ in $\mPi$ such that
\begin{equation}\label{eqn:frac}
  \frac{a\alpha+b\beta}{c\alpha+d\beta}\in\ord.
\end{equation}
\item
Find $\mPi$ as in~\eqref{item:Pi} with the additional
condition that, if $(a,b)$ and $(c,d)$ are distinct solutions
to~\eqref{eqn:2} in $\mPi$, then~\eqref{eqn:frac} fails.
    \end{enumerate}
  \end{prob}

  \begin{sol}
    \begin{asparaenum}
      \item
We have
$2=2x^2-3y^2\iff 4=4x^2-6y^2=\norm{2x+y\sqrt 6}$ in $\Q(\sqrt 6)$.
So let
\begin{equation*}
  K=\Q(\sqrt 6),\quad \alpha=2,\quad \beta=\sqrt 6,\quad m=4.
\end{equation*}
\item\label{item:b}
We want the elements of $\ord$ of norm $1$.  But
$(1/2)\mLambda=\latt[1,\sqrt 6/2]$, and $\sqrt6/2$ is a root of
$2x^2-3$.  Hence
\begin{equation*}
\ord=\latt[1,2\sqrt6/2]=\latt[1,\sqrt6]=\latt[1,\omega]=\roi.  
\end{equation*}
We obtain the units of $\roi$ from the continued-fraction expansion
of $\sqrt 6$:
\begin{align*}
  x&=\sqrt 6,& a_0&=2,& \xi_0&=\sqrt6-2;\\
\frac1{\xi_0}&=\frac{\sqrt6+2}2,&a_1&=2,&\xi_1&=\frac{\sqrt6-2}2;\\
\frac1{\xi_1}&=\sqrt6+2,&a_2&=4,&\xi_2&=\sqrt6-2=\xi_0;
\end{align*}
so $\sqrt6=[2;\overline{2,4}]$.  Since $[2;2]=5/2$, and
$\norm{5+2\omega}=1$, we can conclude that the elements of $\roi$ of
norm $1$ are $\pm(5+2\omega)^n$.  Therefore the desired parallelogram
$\mPi$ can be bounded by the straight lines given by
\begin{equation*}
  2x+y\sqrt6=1;\qquad2x+y\sqrt6=5+2\sqrt6.
\end{equation*}
Also, we are looking for points on the hyperbola
\begin{equation*}
  4=4x^2-6y^2=(2x+y\sqrt6)(2x-y\sqrt6),
\end{equation*}
one of whose asymptotes, given by
\begin{equation*}
  2x-y\sqrt6=0,
\end{equation*}
forms a third side of $\mPi$; the fourth side is given by
\begin{equation*}
  2x-y\sqrt6=4,
\end{equation*}
since this line meets the hyperbola where $2x+y\sqrt6=1$ does. 
\item\label{item:c}
Same as \eqref{item:b}.
    \end{asparaenum}
  \end{sol}

  \begin{remark}
    The point in~\eqref{item:b} is that, if $\gamma$ is from
    $\mLambda$ and solves $\norm{\xi}=4$, then the same is true of
    $\delta$ or $2a+b\omega$, where $\delta=
    \pm(5+2\omega)^n\gamma$; and we should be able to pick the sign and
    $n$ so that $(a,b)\in\mPi$.  But we can
    pick $n$ so that
    \begin{equation*}
      1\leq\size{\delta}<\size{5+2\omega}<10.
    \end{equation*}
We also have $4=\delta\delta'$, so
\begin{equation*}
  \size{\delta'}=\frac4{\delta}\leq4.
\end{equation*}
Since
\begin{equation*}
  \delta=\frac{\delta+\delta'}2+\frac{\delta-\delta'}{2\omega}\omega.
\end{equation*}
we conclude
\begin{equation*}
  \size a=\xsize{\frac{\delta+\delta'}4}<4, \quad \size
  b=\xsize{\frac{\delta-\delta'}{2\omega}}<4.
\end{equation*}
Thus, in~\eqref{item:b}, $\mPi$ can be the square with vertices
$(\pm4,4)$ and $(\pm4,-4)$.  But this isn't good enough
for~\eqref{item:c}. 
  \end{remark}

\section{June 2, 2008 (Monday)}


\begin{prob}
  Suppose $\sqrt 2=[a_0;a_1,a_2,\dots]$, and as usual let
  $p_n/q_n=[a_0;a_1,\dots,a_n]$.  Find rational integers $a$, $b$,
  $k$, and $\ell$ such that
  \begin{equation*}
    p_n+q_n\sqrt 2=(a+b\sqrt 2)(k+\ell\sqrt 2)^n
  \end{equation*}
for all positive rational integers $n$.
\end{prob}

\begin{sol}
  First compute the expansion of $\sqrt 2$:
  \begin{align*}
                 &           & a_0&=1,&\xi_0&=\sqrt 2-1;\\
\frac1{\sqrt 2-1}&=\sqrt 2+1,& a_1&=2,&\xi_1&=\sqrt 2-1=\xi_0.
  \end{align*}
So $\sqrt 2=[1,\overline2]$.  In particular, the period has length
$1$, so 
\begin{equation*}
p_{n+1}+q_{n+1}\sqrt 2=(p_n+q_n\sqrt 2)(p_0+q_0\sqrt 2).
\end{equation*}
Since $p_0/q_0=1/1$, we conclude
\begin{equation*}
    p_n+q_n\sqrt 2=(1+\sqrt 2)(1+\sqrt 2)^n.
\end{equation*}
(This is justified by Theorem 20 of the notes.  Alternatively, one may
note that
\begin{equation*}
  \frac{p_{n+1}}{q_{n+1}}
=\Bigl[1,1+\frac{p_n}{q_n}\Bigr]
=1+\frac{q_n}{p_n+q_n}
=\frac{p_n+2q_n}{p_n+q_n},
\end{equation*}
and both fractions are irreducible,
so $(p_n+q_n\sqrt 2)(1+\sqrt 2)=p_n+2q_n+(p_n+q_n)\sqrt
2=p_{n+1}+q_{n+1}\sqrt 2$.)
\end{sol}

\begin{prob}
Here $\mLambda$ and $\mMu$ are lattices in some quadratic field.
\begin{enumerate}
\item
  Find $\size{\mLambda/\mMu}$, that is, $(\mLambda:\mMu)$, when
  \begin{enumerate}
    \item
$\mLambda=\latt$, $\mMu=\latt[2\alpha,3\beta]$;
\item
$\mLambda=\latt$, $\mMu=\latt[2\alpha,\alpha+3\beta]$.
  \end{enumerate}
\item
Assuming $\mMu\included\mLambda$, find a number $n$ such that
$n\mLambda\included\mMu$. 
\end{enumerate}
\end{prob}

\begin{sol}
  \begin{asparaenum}
    \item
      \begin{inparaenum}
	\item
$6$.\qquad\qquad
\item
$6$.
\end{inparaenum}
\item
Let
$n=(\mLambda:\mMu)$.  Indeed, we can write $\mLambda$ as $\latt$, and
then $\mMu=\latt[c\alpha,f\alpha+e\beta]$ for some positive rational
integers $c$, $e$, and $f$.  Then $(\mLambda:\mMu)=ce$, and
$ce\mLambda=\latt[ce\alpha,ce\beta]\included\mMu$ since
$ce\beta=c(f\alpha+e\beta)-f(c\alpha)$.
  \end{asparaenum}
\end{sol}

\begin{prob}
  In some quadratic field, find a lattice $\mLambda$ such that
  $\norm{\mLambda}=1$, but $\mLambda\neq\ord$.
\end{prob}

\begin{sol}
  One strategy is to find a lattice $\latt$ whose norm is $k^2$ for
  some $k$; then $\mLambda$ can be $\latt[\alpha/k,\beta/k]$.  Assuming
  the quadratic field $K$ is $\Q(\sqrt d)$, where $d\equiv 2$ or $3\pmod
  4$, we can try letting $\latt=\latt[k^2,\ell+\sqrt d]$, where $\ell$
  will be chosen so that the order is $\latt[1,\sqrt d]$, that is,
  $\roi$.  To compute this order, we have
  \begin{align*}
    x=\frac{\ell+\sqrt d}{k^2}
&\implies k^2x-\ell=\sqrt d\\
&\implies k^4x^2-2k^2\ell x+\ell^2-d=0\\
&\implies k^2x^2-2\ell x+\frac{\ell^2-d}{k^2}=0.
  \end{align*}
It is enough now if $\gcd(k,2\ell)=1$, while $k^2\divides{\ell^2-d}$.
We can achieve this by letting $k=3$, $\ell=5$, and $d=-2$.  So
\begin{equation*}
\mLambda=\Bigl\langle3,\frac{5+\sqrt{{-2}}}3\Bigr\rangle
\end{equation*}
is one possibility.
\end{sol}

\begin{prob}
  Letting $K=\Q(\sqrt5)$ and $\ord[]=\roi$, for each $p$ in
  $\{2,3,5,7,11\}$, find the prime factorization of $p\ord[]$ in $\ord[]$.
\end{prob}

\begin{sol}
In the notation of our last theorem, $\mDelta=d=5$.  Then $5$
ramifies in $\ord[]$, and
\begin{equation*}
  5\ord[]=\Bigl\langle5,\frac{5+\sqrt 5}2\Bigr\rangle^2.
\end{equation*}
Now we check solubility of $5\equiv x^2\pmod{4p}$ for the remaining
$p$.  There is no solution when $p\in\{2,3,7\}$.  Indeed, when $p=2$,
just check the possibilities: $(\pm1)^2\equiv1$; $(\pm2)^2\equiv4$;
$(\pm3)^2\equiv1$; $4^2\equiv0$.  In the other cases, we can show
$5\equiv x^2\pmod p$ is insoluble by Legendre symbols and quadratic
reciprocity: $(5/3)=(2/3)=-1$; 
$(5/7)=(7/5)=(2/5)=-1$.  So $2$, $3$, and $7$ are inert in $\ord[]$.

Finally, $(5/11)=(11/5)=(1/5)=1$, and indeed $5\equiv7^2\pmod{44}$.
Then
\begin{equation*}
  11\ord[]=\Bigl\langle11,\frac{7+\sqrt 5}2\Bigr\rangle
\Bigl\langle11,\frac{7-\sqrt 5}2\Bigr\rangle.
\end{equation*}
\end{sol}

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

\begin{thebibliography}{10}

\bibitem{MR0476613}
William~W. Adams and Larry~Joel Goldstein.
\newblock {\em Introduction to number theory}.
\newblock Prentice-Hall, Englewood Cliffs, N.J., 1976.

\bibitem{Apollonius-Heiberg}
{Apollonius of Perga}.
\newblock {\em Apollonii {P}ergaei Qvae {G}raece Exstant Cvm Commentariis
  Antiqvis}, volume~I.
\newblock Teubner, 1974.
\newblock Edited with Latin interpretation by I. L. Heiberg. First published
  1891.

\bibitem{MR1660991}
{Apollonius of Perga}.
\newblock {\em Conics. {B}ooks {I}--{III}}.
\newblock Green Lion Press, Santa Fe, NM, revised edition, 1998.
\newblock Translated and with a note and an appendix by R. Catesby Taliaferro,
  with a preface by Dana Densmore and William H. Donahue, an introduction by
  Harvey Flaumenhaft, and diagrams by Donahue, edited by Densmore.

\bibitem{Burton}
David~M. Burton.
\newblock {\em Elementary Number Theory}.
\newblock McGraw-Hill, Boston, sixth edition, 2007.

\bibitem{MR2135478}
Graham Everest and Thomas Ward.
\newblock {\em An introduction to number theory}, volume 232 of {\em Graduate
  Texts in Mathematics}.
\newblock Springer-Verlag London, London, 2005.

\bibitem{MR568909}
G.~H. Hardy and E.~M. Wright.
\newblock {\em An Introduction to the Theory of Numbers}.
\newblock Clarendon Press, Oxford, fifth edition, 1979.
\newblock First edition 1938. Reprinted 1990.

\bibitem{MR0046650}
D.~Hilbert and S.~Cohn-Vossen.
\newblock {\em Geometry and the imagination}.
\newblock Chelsea Publishing, New York, 1952.
\newblock Translated by P. Nem\'enyi.

\bibitem{MR0092794}
Edmund Landau.
\newblock {\em Elementary Number Theory}.
\newblock Chelsea Publishing, New York, 1958.
\newblock Originally part of \emph{Vorlesungen {\"u}ber Zahlentheorie}
  (Leipzig, 1927). Translated by J. E. Goodman.

\bibitem{MR890960}
Serge Lang.
\newblock {\em Elliptic functions}, volume 112 of {\em Graduate Texts in
  Mathematics}.
\newblock Springer-Verlag, New York, second edition, 1987.
\newblock With an appendix by J. Tate.

\bibitem{MR0210649}
James~E. Shockley.
\newblock {\em Introduction to number theory}.
\newblock Holt Rinehart and Winston, New York, 1967.

\end{thebibliography}


\sloppy%\printindex
\begin{theindex}

  \item $K$ (a quadratic field, usually $\Q(\sqrt d)$), 33
  \item $\C$ (the field of complex numbers), 33
  \item $\End$, 51
  \item $\Fib n$, 83
  \item $\Q$ (the field of rational numbers), 20
  \item $\Q(\sqrt d)$, 34
  \item $\R$ (the field of real numbers), 54
  \item $\Z$ (the ring of rational integers), 35
  \item $\disc{\mLambda}$, $\disc{\alpha,\beta}$, 64
  \item $\edeg x$, 37
  \item $\funit$, 81
  \item $\gi$ (the ring of Gaussian integers), 35
  \item $\gr$ (the Golden Ratio), 83
  \item $\latt$, 51
  \item $\mDelta$, 127
  \item $\mi$ (not the variable $i$, but $\sqrt{{-1}}$), 15
  \item $\mpi$ (the circumference of the unit circle), 44
  \item $\norm x$, 36, 45
  \item $\omega$ (generator of $\roi$ over $\Z$), 48
  \item $\ord$, 68
  \item $\pi$ (an arbitrary prime of $\gi$), 41
  \item $\roi$, 46
  \item $\tr x$, 45
  \item $\upomega$, 24
  \item $\upomega$ (the set $\{x\in\Z\colon x\geq 0\}$), 37
  \item $d$ (a \sqf{} element of $\Z$, not $1$), 45

  \indexspace

  \item algebraic integer, 35
  \item associate, 39

  \indexspace

  \item belong, 113
  \item binary quadratic form, 49

  \indexspace

  \item conductor, 69
  \item conjugate, 75
  \item continued fraction, 20, 21, 25
  \item convergent, 25

  \indexspace

  \item degree, 37
  \item diameter, 75
  \item Diophantine equation, 11
  \item discriminant, 50, 64
  \item divisibility, 121
  \item domain, 37
  \item doubly periodic, 54

  \indexspace

  \item Eisenstein integer, 132
  \item elliptic curve, 55
  \item endomorphism, 51
  \item Euclidean algorithm, 24
  \item Euclidean domain, 37

  \indexspace

  \item Fibonacci number, 83
  \item free abelian subgroup, 51
  \item fundamental unit, 81

  \indexspace

  \item Gaussian integer, 35
  \item Golden Ratio, 83
  \item greatest common divisor, 39, 122

  \indexspace

  \item ideal, 112, 113
  \item inert, 126
  \item infinite descent, 14
  \item integer, 35
  \item integral, 114
  \item integral domain, 37
  \item irreducible, 40, 121

  \indexspace

  \item lattice, 38, 51
  \item limit, 22

  \indexspace

  \item minimal polynomial, 46

  \indexspace

  \item norm, 36, 45, 113

  \indexspace

  \item order, 68, 113

  \indexspace

  \item Pell equation, 29
  \item positive, 31
  \item prime, 41, 121, 122
  \item primitive solution, 12
  \item principal-ideal domain, 40
  \item Pythagorean triple, 13

  \indexspace

  \item quadratic extension, 11
  \item quadratic field, 33

  \indexspace

  \item ramify, 126
  \item rational integer, 35
  \item rational point, 19

  \indexspace

  \item simple, 25
  \item split, 126
  \item square-free, 33

  \indexspace

  \item torus, 54
  \item trace, 45
  \item transverse, 85

  \indexspace

  \item unique-factorization domain, 40
  \item upright, 85

  \indexspace

  \item Weierstra\ss {} function, 54

\end{theindex}


\end{document}