%\documentclass[a4paper,twoside,draft,12pt]{article}
\documentclass[a4paper,reqno,12pt,draft]{amsart}
\usepackage[headings]{fullpage}
%\usepackage{multicol}
\usepackage{upgreek}

%\usepackage[fulloldstyle]{fourier}
\title{Elementary Number Theory II, examination III solutions}
%\author{David Pierce}
\date{May 26, 2008}
\usepackage{verbatim}  % allows a comment environment:
%\begin{comment}
\address{Mathematics Dept\\
Middle East Technical University\\
Ankara 06531, Turkey}

\email{dpierce@metu.edu.tr}
\urladdr{http://www.math.metu.edu.tr/~dpierce/}
%\end{comment}

\usepackage{amsmath,amsthm,amssymb}
\usepackage{url}
\usepackage{textcomp}  % supposedly useful with \oldstylenums
\usepackage{hfoldsty} % this didn't work until I added missing
		      % brackets to some of the files.

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

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

\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{\included}{\subseteq}      % [the name suggests the meaning here]

\newcommand{\stnd}[1]{\mathbb{#1}}
\newcommand{\Z}{\stnd{Z}}         % integers
\newcommand{\R}{\stnd{R}}         % reals
\newcommand{\Q}{\stnd{Q}}         % rationals

\newcommand{\mi}{\mathrm i}
%\newcommand{\gr}{\upphi}  % golden ratio
\newcommand{\mLambda}{\mathit{\Lambda}}
\newcommand{\mPi}{\mathit{\Pi}}
\newcommand{\mMu}{M}
\newcommand{\mDelta}{\mathit{\Delta}}

\newcommand{\norm}[1]{\operatorname{N}(#1)}

\newcommand{\size}[1]{\lvert#1\rvert}


\let\oldsqrt\sqrt
\renewcommand{\sqrt}[2][1]{\oldsqrt{\vphantom{#1}}#2}
%\newcommand{\rft}{\sqrt{14}}
%\newcommand{\rtt}{\sqrt{13}}

\newcommand{\lat}[1][\alpha,\beta]{\langle#1\rangle} % lattice
\newcommand{\ord}[1][\mLambda]{\mathfrak O_{#1}}
\newcommand{\roi}{\ord[K]}

\newcommand{\divides}{\mathrel{|}}

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

\theoremstyle{definition}
\newtheorem{problem}{Problem}

\theoremstyle{remark}

\newtheorem*{instructions}{Instructions}

\newtheorem*{solution}{Solution}

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

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


\begin{document}
  \maketitle\thispagestyle{empty}

\begin{problem}
  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{problem}

\begin{solution}
  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{solution}
\vfill
\begin{problem}
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=\lat$, $\mMu=\lat[2\alpha,3\beta]$;
\item
$\mLambda=\lat$, $\mMu=\lat[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{problem}

\begin{solution}
\mbox{}
  \begin{enumerate}
    \item
\mbox{}
      \begin{enumerate}
	\item
$6$
\item
$6$
      \end{enumerate}
\item
Let
$n=(\mLambda:\mMu)$.  Indeed, we can write $\mLambda$ as $\lat$, and
then $\mMu=\lat[c\alpha,f\alpha+e\beta]$ for some positive rational
integers $c$, $e$, and $f$.  Then $(\mLambda:\mMu)=ce$, and
$ce\mLambda=\lat[ce\alpha,ce\beta]\included\mMu$ since
$ce\beta=c(f\alpha+e\beta)-f(c\alpha)$. 
  \end{enumerate}
\end{solution}
\vfill
\newpage
\begin{problem}
  In some quadratic field, find a lattice $\mLambda$ such that
  $\norm{\mLambda}=1$, but $\mLambda\neq\ord$.
\end{problem}

\begin{solution}
  One strategy is to find a lattice $\lat$ whose norm is $k^2$ for
  some $k$; then $\mLambda$ can be $\lat[\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 $\lat=\lat[k^2,\ell+\sqrt d]$, where $\ell$
  will be chosen so that the order is $\lat[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{solution}
\vfill
\begin{problem}
  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{problem}

\begin{solution}
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{solution}
\vfill
\end{document}