%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Math 458 hw4
\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amsfonts} % to get \mathbb letters
\usepackage{hyperref}

\newcommand{\ZZ}{\mathbb{Z}}

\title{Number Theory, hw4}
\date{ \today }
\author{Ethan\ D.\ Bolker}

\begin{document}
\maketitle

Note: If the Brown freshmen for whom Silverman wrote this book can do
the problems then UMass math majors surely can. Prove me right.

\begin{enumerate}

\item Silverman, Exercise 10.1. 

\item Silverman, Exercise 10.2. 

\item Silverman, Exercise 10.3. 

\item Read and understand the proof of the Chinese Remainder Theorem
  at
\url{http://crypto.stanford.edu/pbc/notes/numbertheory/crt.xhtml}. (It 
uses the knowledge we have about which numbers have multiplicative
inverses in $\ZZ_n$. I like it better than the one in Silverman.)

Use the algorithm from that proof to answer Silverman 11.5. 

Doing it by hand will be good practice using the Euclidean algorithm
to find multiplicative inverses but you might be better off working
with an online number theory calculator. You might want to explore
\url{http://www.math.uconn.edu/~kconrad/math3240f09/calc.html}. Look
around for other tools (online calculators or downloadable
applications). Let me know if you find anything useful.

\item Consider the following statements about an odd prime $p$:

\begin{itemize}
\item $p \equiv 1 \mod 4$.

\item $p$ is a sum of two integer squares.

\item $-1$ has a square root in $\ZZ_p$.

\end{itemize}

These are in fact equivalent. Any one of them implies the other
two. Proving that was one of Fermat's major accomplishments.
Here's your assignment now:

\begin{enumerate}
\item Verify the equivalence for all the odd primes less than 100.

\item Prove as many of the six possible implications as you can. (Some
  are really easy. Some are really hard.)
\end{enumerate}

\item Approximating $\sqrt{2}$.

The Diophantine equation
%
\begin{equation*}
x^2 - 2y^2 = 0.
\end{equation*}
%
has no solutions. If it did, then 
$x/y$ would be a rational number whose square was
2. That's impossible. 

But we can get close. For example, 
%
\begin{equation*}
7^2 - 2 \times 5^2 = -1
\end{equation*}
%
so
%
\begin{equation*}
\biggl( \frac{7}{5} \biggr)^2 = 
2 - \frac{1}{5^{2}} \quad .
\end{equation*}

Your job: find enough solutions to the Diophantine equation
\begin{equation*}
x^2 - 2y^2 == \pm 1
\end{equation*}
%
to guess (and prove) a pattern that produces infinitely many
solutions. Then find one big enough to produce a rational number whose
square is between 1.999999999 and 2.000000001.

Hint to get you  started. There are several solutions \emph{smaller
  than} (7,5).
\end{enumerate}


\end{document}
