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

\usepackage{amsmath}
\usepackage{amsfonts} % to get \mathbb letters
\usepackage{hyperref}
\usepackage[textheight=10in]{geometry}

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

\newenvironment{solution}
{\textbf{Solution: }}
{}

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

\begin{document}
\maketitle

\begin{enumerate}

\item Silverman, Exercise 9.1. 

\item Silverman, Exercise 9.2. 

Hint for part (b). When (if ever) is an element $a \in \ZZ_p$ its own
multiplicative inverse? When it's not, what is going on?

\item{Quadratic equations}

Let $p$ be a prime. We know that the linear congruence
%
\begin{equation*}
ax + b \equiv 0 \mod p
\end{equation*}
%
has a unique solution when $a \not\equiv 0$. Now let's think about the
\emph{quadratic} equation
%
\begin{equation}\label{eq:quadratic}
ax^2 + bx + c \equiv 0 \mod p
\end{equation}
%
for \emph{odd} primes $p$.
\begin{enumerate}
\item Show that the usual quadratic formula finds the roots of
  Equation~\ref{eq:quadratic} when the discriminant $\Delta = b^2 - 4ac$ has
    a square root in $\ZZ_p$.

Note: You don't have to \emph{derive} the quadratic formula. You just
have to show that it produces the roots.

\item Show that each element of $\ZZ_p^*$ has either two square roots
  or none.%
\footnote{$\ZZ_p^*$ is the set of \emph{nonzero} elements of $\ZZ_p$.}

\begin{solution}
Here's the idea.
If an element of $\ZZ_p$ has one square root then finding
a second one is easy, since $(-x)^2 =
x^2$. I just need to make sure those are different. Then I need to
make sure there are no others. That's not true when the modulus is 8,
so to prove it here I know I'll have to use the 
the fact that $p$ is prime.

Suppose $a \in \ZZ_p^*$ has a square root $x$. Then $x^2 \equiv (-x)^2
\equiv a \mod p$ so $-x$ is also a square root of $a$. Since $x
\not\equiv -x \mod p$ I have two square roots.

Let $y$ be a square root of $a \mod p$. I need to show that $y \equiv
\pm x \mod p$. That's easy:
%
\begin{equation*}
x^2 \equiv y^2 \mod p
\end{equation*}
%
implies
%
\begin{equation*}
p | y^2 - x^2 = (y-x)(y+x).
\end{equation*}
%
I know that when a prime divides a product it divides one of the
factors, so $p$ divides $y-x$ or $y+x$. That means $y \equiv -x \mod
p$ or $y \equiv x \mod p$.

\end{solution}
\end{enumerate}

\item Use Fermat's Little Theorem to show that
\begin{equation*}
a^{(p-1)/2} \equiv \pm 1 \mod p .
\end{equation*}

\begin{solution}
This is easy. Fermat's Little Theorem tells me that
%
\begin{equation*}
(a^{(p-1)/2})^2 = a^{p-1} \equiv 1 \mod p .
\end{equation*}
%
Since I just finished proving that 1 has only two square roots, $\pm
1$, $a^{(p-1)/2}$ must be one of them.

Several of you got the logic backwards here. Please read carefully.

\end{solution}
\item Who has a square root?

Investigate the set $S_p$ of elements of $\ZZ_p^*$ that have square roots. 

It's very hard to detect a pattern that tells you when a
  particular element has a square root. Finding that pattern is one of the
  goals of this course. But there are several parts of the pattern
  that we can begin to see now.

\begin{enumerate}
\item Start with some calculations: Find $S_p$ for $p
  = 5, 7, 11, 13$ and maybe some larger values -- perhaps $29$ and
  $31$. Consider doing this collaboratively -- parcel out some larger
  primes among the class and pool your results.
As you do the work you should stumble on arithmetic shortcuts
  that will in fact help you understand what's happening.

\item How many elements are there in $S_p$? (Make a conjecture. Prove it
  if you can.)

\item A previous problem in this homework leads to a conjecture
  relating $S_p$ to the computation $a^{(p-1)/2}$. Find that
  conjecture and prove it if you can.

\item 
 Clearly $1 \in S_p$ since $\pm 1$ are its square
  roots.%
\footnote{Remember that in $\ZZ_p$, $-1$ is $p-1$.}
Can you guess/conjecture of the form

\begin{quotation}
$-1$ has a square root $\mod p$ if and only if $p$ \ldots
\end{quotation}

\end{enumerate}
\item More proofs of Fermat's Little Theorem.
The Wikipedia article at
\url{http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem} 
offers several proofs of Fermat's Little Theorem. I recommend two of
these: 
\textbf{Proof by counting necklaces} and
\textbf{Proof using the binomial theorem}.
Read and understand them. To convince yourself and me that you do
really understand, find the step in each proof where you use the
hypothesis \emph{$p$ is prime} and find an example to show how that
step fails when the hypothesis is false.
\end{enumerate}


\end{document}
