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

%\usepackage[fulloldstyle]{fourier}
\title{Elementary Number Theory II, examination I solutions}
\author{David Pierce}
\date{\today}
\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{\stnd}[1]{\mathbb{#1}}
\newcommand{\Z}{\stnd{Z}}         % integers
\newcommand{\Q}{\stnd{Q}}         % rationals

\newcommand{\mi}{\mathrm i}

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

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

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

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

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

\newtheorem{solution}{Solution}

\theoremstyle{remark}

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

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

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


\begin{document}
  \maketitle\thispagestyle{empty}
  \begin{solution}
\begin{enumerate}
\item
    Apply the Euclidean algorithm:
    \begin{align*}
\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{13+13\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,
&1+5\mi&=(-2+3\mi)(1-\mi).
    \end{align*}
Therefore $-2+3\mi$ is a greatest common divisor of $\alpha$ and $\beta$.
\item
By the computations above,
\begin{align*}
  \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{align*}
\end{enumerate}
  \end{solution}

  \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 second
    line, the computation could have been
    \begin{align*}
\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,
&1+5\mi&=(-3-2\mi)(-1-\mi).
    \end{align*}
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{align*}
  \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{align*}
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. 
Alternatively, 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.
However, these alternative approaches are not much help in solving
(ii).

Once one \emph{does} have an answer to (ii), it is easy to check.
  \end{remark}

  \begin{solution}
    \begin{enumerate}
      \item
Let $x=\oldsqrt{3/2}=\sqrt 6/2$.  Applying our algorithm to $x$, we
have
\begin{align*}
&&  a_0&=[x]=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 ($*$) 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{enumerate}
  \end{solution}

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

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

  \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{solution}
    \begin{enumerate}
      \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{gather*}
  (10,\pm11),(-10,\mp11),(\mp11,10),(\pm11,-10),
  (14,\pm5),(-14,\mp5),(\mp5,14),(\pm5,-14).
\end{gather*}
\item
$27-57\mi=3\cdot(9-19\mi)$, where $3$ is prime; and
$\norm{9-19\mi}=81+361=442=2\cdot221$.  But $2$ has associated prime
  factors $1\pm\mi$, and
  \begin{equation*}
    \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{equation*}
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{enumerate}
  \end{solution}
\end{document}

