%\documentclass[a4paper,twoside,draft,12pt]{article}
\documentclass[a4paper,reqno,12pt,draft]{amsart}
\usepackage[headings]{fullpage}
%\usepackage{multicol}
\usepackage{upgreek}
\usepackage{paralist}
%\usepackage[fulloldstyle]{fourier}
\title{Elementary Number Theory II, final examination solutions}
%\author{David Pierce}
\date{June 2, 2008; revised, \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.

\usepackage{pstricks}

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

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

\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{\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]}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\leq}{\leqslant}

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

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

\newtheorem*{instructions}{Instructions}

\newtheorem*{solution}{Solution}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}
%\newenvironment{solution}%
%{\begin{proof}[Solution.]}%
%{\end{proof}}

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


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

  \begin{problem}
    Find the positive rational-integer solutions to $x^2-22y^2=3$.
  \end{problem}

  \begin{solution}
    First find the expansion of $\sqrt{22}$:
    \begin{align*}
                   &                     &a_0&=4;&\xi_0&=\sqrt{22}-4;\\
\frac1{\sqrt{22}-4}&=\frac{\sqrt{22}+4}6,&a_1&=1,&\xi_1&=\frac{\sqrt{22}-2}6;\\
\frac6{\sqrt{22}-2}&=\frac{\sqrt{22}+2}3,&a_2&=2,&\xi_2&=\frac{\sqrt{22}-4}3;\\
\frac3{\sqrt{22}-4}&=\frac{\sqrt{22}+4}2,&a_3&=4,&\xi_3&=\frac{\sqrt{22}-4}2;\\
\frac2{\sqrt{22}-4}&=\frac{\sqrt{22}+4}3,&a_4&=2,&\xi_4&=\frac{\sqrt{22}-2}3;\\
\frac3{\sqrt{22}-2}&=\frac{\sqrt{22}+2}6,&a_5&=1,&\xi_5&=\frac{\sqrt{22}-4}6;\\
\frac6{\sqrt{22}-4}&=\sqrt{22}+4,        &a_6&=8,&\xi_6&=\xi_0.
    \end{align*}
So $\sqrt{22}=[4;\overline{1,2,4,2,1,8}]$.
If $3$ is the denominator of $\xi_{n+1}$, then
\begin{equation*}
  p_n{}^2-22q_n{}^2=(-1)^{n+1}3.
\end{equation*}
Hence the positive solutions of $x^2-22y^2=3$ that come from
convergents are $(p_{6k+1},q_{6k+1})$ and $(p_{6k+3},q_{6k+3})$.  To
verify that these are all of the (positive) solutions, we assume that
$(a,b)$ is a solution and show
\begin{equation*}
  \Bigl\lvert\frac ab-\sqrt{22}\Bigr\rvert<\frac1{2b^2},
\end{equation*}
that is,
\begin{equation*}
  \size{a-b\sqrt{22}}<\frac1{2b},
\end{equation*}
that is,
\begin{equation*}
  3<\frac{a+b\sqrt{22}}{2b}=\frac12\Bigl(\frac ab+\sqrt{22}\Bigr).
\end{equation*}
Since $a/b>\sqrt{22}>3$, we do have this.  To be more explicit about
the solutions, we compute the first convergents:
\begin{equation*}
  \frac41,\quad\frac51,\quad\frac{14}3,\quad\frac{61}{13},\quad\frac{136}{29},
  \quad\frac{197}{42}. 
\end{equation*}
So $(5,1)$ and $(61,13)$ are solutions; the others are $(a,b)$, where
\begin{equation*}
  a+b\sqrt{22}=(5+\sqrt{22})(197+42\sqrt{22})^k\text{ or }
                   (61+13\sqrt{22})(197+42\sqrt{22})^k.
\end{equation*}
  \end{solution}

  \begin{remark}
    In an alternative approach, we can rewrite the equation to be
    solved as
    \begin{equation*}
      \norm{x+y\sqrt{22}}=3,
    \end{equation*}
where the norm is taken in $\Q(\sqrt{22})$.  Let $K$ be this field,
and $\omega=\sqrt{22}$.
We want to solve $\norm{\xi}=3$, where $\xi\in\lat[1,\omega]$, which
is $\roi$.  We first
find the fundamental unit $\epsilon$ of $\roi$.  Then there
will be a certain finite set of solutions $\alpha$ of $\norm{\xi}=3$ such
that every solution is uniquely of the form $\pm\alpha\cdot\epsilon^n$.

From the work in the solution above, $\epsilon=197+42\sqrt{22}$.  (We
have $\norm{197+42\sqrt{22}}=1$ and not $-1$ because the period of
$\sqrt{22}$ has even length.  It
would take a while to find $\epsilon$ by testing all $a+b\sqrt{22}$ such
that $a$ is the closest integer to $b\sqrt{22}$; however one student did
try this approach.)

Now the $\alpha$ will satisfy $1\leq\xi<\epsilon$.
One of these $\alpha$, namely $5+\sqrt{22}$, can be
found by trial; but perhaps not the other one, $61+13\sqrt{22}$.
Finding it from the convergents of $\sqrt{22}$ seems most efficient.
Alternatively, one might find it within the appropriate parallelogram,
by the method worked out in class (and in the notes).  We are looking
for integers $x$ and $y$ such that
\begin{equation*}
  x^2-22y^2=3,\qquad 1\leq x+y\sqrt{22}<197+42\sqrt{22}.
\end{equation*}
The two inequalities determine two sides of the parallelogram, given
by $1=x+y\sqrt{22}$ and $x+y\sqrt{22}=197+42\sqrt{22}$.
The original equation defines a hyperbola with asymptotes given together by
$x^2-22y^2=0$, or individually by $x\pm y\sqrt{22}=0$; the equation
$x-y\sqrt{22}=0$ defines a third side of the parallelogram.  Using
$1=x+y\sqrt{22}$ in the equation of the hyperbola gives the fourth
side, $x-y\sqrt{22}=3$.  Written in slope-intercept form, the sides
are:
\begin{align*}
  y&=\frac x{\sqrt{22}}& 
y&=-\frac x{\sqrt{22}}+\frac{197+42\sqrt{22}}{\sqrt{22}},\\
y&=\frac x{\sqrt{22}}-\frac3{\sqrt{22}},&
y&=-\frac x{\sqrt{22}}+\frac1{\sqrt{22}}.
\end{align*}
The vertices then are:
\begin{equation*}
  \Bigl(\frac{197+42\sqrt{22}}2,
  \frac{197+42\sqrt{22}}{2\sqrt{22}}\Bigr),\
\Bigl(\frac12,\frac1{2\sqrt{22}}\Bigr),\
  \Bigl(100+21\sqrt{22},
  \frac{97+21\sqrt{22}}{\sqrt{22}}\Bigr),\
\Bigl(2,\frac{-1}{\sqrt{22}}\Bigr).
\end{equation*}
These are approximately $(197,42.0)$, $(0.5,0.1)$, $(198.5,41.7)$,
$(2,-0.2)$.  In particular, the parallelogram contains at least 41
integer points, rather a lot to find and test by hand.
\begin{center}
  \begin{pspicture}(0.04,-0.016)(15.88,3.36)
\psset{unit=0.8mm}
    \pspolygon(0.5,0.1)(197,42)(198.5,41.7)(2,-0.2)
%\multirput*(0,0)(1,0){7}
%   {\pscircle[fillstyle=solid,fillcolor=black]{0.05}} 
\psdots(5,1)(61,13)
\uput[u](5,1){$(5,1)$}
\uput[u](61,13){$(61,13)$}
  \end{pspicture}
\end{center}
  \end{remark}

  \begin{problem}
    The curve $E$ defined by the cubic equation
    \begin{equation*}
      y^2=x^3-2
    \end{equation*}
has the rational point $(3,5)$.  This problem is about obtaining other
rational points.
\begin{inparaenum}
  \item
Find an equation for the tangent line to $E$ at $(3,5)$.  (You may use
implicit differentiation.)
\item
This tangent line meets $E$ twice at $(3,5)$.  Find the third point of
intersection.  (You may use that the sum of the roots of
$x^3-Ax^2+Bx-C$ is $A$.)
\item
Now generalize:  Suppose $(a,b)$ is on $E$, and let $\lambda$ be the
slope of the tangent line to $E$ at $(a,b)$.  Find $\lambda$ (assuming
$b\neq0$). 
\item
Derive the conclusion that this tangent line meets $E$ also at
\begin{equation*}
  \Bigl(\frac{a^4+16a}{4b^2},\frac{-a^6+40a^3+32}{8b^3}\Bigr).
\end{equation*}
\end{inparaenum}
  \end{problem}

  \begin{solution}
%\mbox{}
    \begin{enumerate}
      \item\label{item:a}
$2yy'=3x^2$, $y'=3x^2/2y=27/10$; the tangent line is given by
	\begin{equation*}
	  y=\frac{27}{10}(x-3)+5=\frac{27}{10}x-\frac{31}{10}.
	\end{equation*}
\item
Substitute:
\begin{gather*}
  \Bigl(\frac{27}{10}x-\frac{31}{10}\Bigr)^2=x^3-2,\\
0=x^3-ax^2+bx-c,
\end{gather*}
where $a=(27/10)^2$; we compute
\begin{gather*}
  \Bigl(\frac{27}{10}\Bigr)^2-2\cdot
  3=\frac{729}{100}-6=\frac{129}{100};\\
\frac{27}{10}\cdot\frac{129}{100}-\frac{31}{10}
  =\frac{3483}{1000}-\frac{31}{10}= 
  \frac{383}{1000}; 
\end{gather*}
the point is
\begin{equation*}
\Bigl(\displaystyle\frac{129}{100},\frac{383}{1000}\Bigr).
\end{equation*}
\item
As in~\eqref{item:a}, $\lambda=3a^2/2b$.
\item
The tangent line is $y=\lambda(x-a)+b$, so $(\lambda
x-a\lambda+b)^2=x^3-2$, the sum of the roots is $\lambda^2$, the third
root is $\lambda^2-2a$, that is,
\begin{equation*}
  \frac{9a^4}{4b^2}-2a=\frac{9a^4-8a(a^3-2)}{4b^2}=\frac{a^4+16a}{4b^2}.
\end{equation*}
For the corresponding $y$-coordinate, use the tangent line:
\begin{align*}
  \frac{3a^2}{2b}\Bigl(\frac{a^4+16a}{4b^2}-a\Bigr)+b
&=\frac{3a^6+48a^3}{8b^3}-\frac{3a^3}{2b}+b\\
&=\frac{3a^6+48a^3-12a^3b^2+8b^4}{8b^3}\\
&=\frac{3a^6+48a^3-12a^3(a^3-2)+8(a^3-2)^2}{8b^3}\\
&=\frac{3a^6+48a^3-12a^6+24a^3+8a^6-32a^2+32}{8b^3}\\
&=\frac{-a^6+40a^3+32}{8b^3}.
\end{align*}
    \end{enumerate}
  \end{solution}

  \begin{remark}
    Problem 1, and much of our class, concerned integer points on a
    curve defined by a quadratic equation.  For `most' curves given by
    equations of higher degree, there are only finitely many integer
    points; but for cubic equations, there may be infinitely many
    \emph{rational} points, as Problem 2 suggests.
  \end{remark}

%\layout
\end{document}

