\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

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

%  Custom macros.

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}
%\newcommand{\size}[1]{\left|#1\right|}
\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
%\newcommand{\ok}{\marginpar{ok?}}
\newcommand{\rem}{\textup{ rem }}
\newcommand{\term}[1]{\textit{\textbf{#1}}}
%\newtheorem*{conjecture*}{Conjecture}

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

\begin{document}
\lecturenotes{9}{Number Theory}

\term{Number theory} is the study of the integers.  This ancient field
is distinguished by many problems that are easy to state, but
incredibly hard to solve.  Here are some examples:

\begin{description}

\item[Fermat's Last Theorem] Do there exist positive integers $x$,
$y$, and $z$ such that

\begin{eqnarray*}
x^n + y^n & = & z^n
\end{eqnarray*}

for some integer $n > 2$?  In a book he was reading around 1630,
Fermat claimed to have a proof, but not enough space in the margin to
write it down.  Wiles finally solved the problem in 1994, after seven
years of working in secrecy and isolation in his attic.

\item[Prime Number Theorem] Let $\pi(x)$ denote the number of primes
less than or equal to $x$.  Primes are very irregularly distributed,
so this is a complicated function.  However, the Prime Number Theorem
states that $\pi(x) \sim x / \ln x$.  The theorem was conjectured by
Legendre in 1798 and proved by de la Vall\'{e}e Poussin in 1896.
However, after his death, a notebook of Gauss was found to contain the
conjecture, which he apparently made in 1791 at age 14.

\item[Goldbach Conjecture] Is every even integer greater than or equal
to 4 the sum of two primes?  For example, $4 = 2 + 2$, $6 = 3 + 3$, $8
= 3 + 5$, etc.  The conjecture holds for all numbers up to $10^{16}$.
In 1939 Schnirelman proved that every even number can be written as
the sum of not more than 300,000 primes, which was a start.  Today, we
know that every even number is the sum of at most 6 primes.

\item[Twin Prime Conjecture] Are there infinitely many primes $p$ such
that $p + 2$ is also a prime? In 1966 Chen showed that there are
infinitely many primes $p$ such that $p + 2$ is the product of at most
two primes.  So the conjecture is known to be {\em almost} true!

\item[Odd Perfect Numbers] A number is \term{perfect} if it is equal to
the sum of its positive divisors other than itself.  For example, $6 =
1 + 2 + 3$ and $28 = 1 + 2 + 4 + 7 + 14$.  Euclid characterized all
the even perfect numbers around 300 BC.  But is there an odd perfect
number?  More than two thousand years later, we still don't know.  All
numbers up to about $10^{300}$ have been checked.

\item[Primality Testing] Is there an efficient way to determine
whether $n$ is prime?  An amazing simple, yet efficient method was
finally discovered in 2002 by Agrawal, Kayal, and Saxena.  Their paper
began with a quote from Gauss emphasizing the importance and antiquity
of the problem even in his time--- two centuries ago.

\item[Factoring] Given the product of two large primes $n = pq$, is
there an efficient way to recover the primes $p$ and $q$?  The best
known algorithm is the ``number field seive'', which runs in time
proportional to:

\[
e^{1.9(\ln n)^{1/3} (\ln\ln n)^{2/3}}
\]

This is infeasible when $n$ has a couple hundred digits or more.
\end{description}

In the 1930's, the mathematician Hardy said of his beloved number
theory:

\begin{quotation}
[Number theorists] may be justified in rejoicing that there is one
science, at any rate, and that their own, whose very remoteness from
ordinary human activities should keep it gentle and clean.
\end{quotation}

What most concerned Hardy was that number theory not be used in
warfare; he was a pacifist.  However, some of the simple, yet
difficult problems of number theory (such as factoring) have proved to
be an excellent foundation for computer-based cryptography.  Today,
numerous public-key cryptosystems, digital signature schemes,
cryptographic hash functions, and digital cash systems have
underpinnings in number theory.  Every time you purchase a book from
Amazon, check your grades on WebSIS, or use a Paypal account, you are
relying on number-theoretic algorithms.

Several topics in these notes came up earlier in the course.  We
restate them here for completeness.  Every variable in these notes
denotes an integer, unless otherwise specified.

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

\section{Divisibility}
\label{sec:div}

We say that \term{$a$ divides $b$} if there is an integer $k$ such
that $ak = b$.  This is denoted $a \mid b$.  For example, $7 \mid 63$,
because $7 \cdot 9 = 63$.  A consequence of this definition is that
every number divides zero.  If $a$ divides $b$, then $b$ is a
\term{multiple} of $a$.  For example, 63 is a multiple of 7.  The
lemma below states some simple facts about divisibility.

\begin{lemma}
\label{lem:div}
The following statements about divisibility hold.

\begin{enumerate}

\item If $a \mid b$, then $a \mid bc$ for all $c$.

\item If $a \mid b$ and $b \mid c$, then $a \mid c$.

\item If $a \mid b$ and $a \mid c$, then $a \mid sb + tc$ for all $s$ and $t$.

\item For all $c \neq 0$, $a \mid b$ if and only if $ca \mid cb$.
\end{enumerate}
\end{lemma}

\begin{proof}
We'll only prove part (2); the other proofs are similar.  Since $a
\mid b$, there exists an integer $k_1$ such that $a k_1 = b$.  Since
$b \mid c$, there exists an integer $k_2$ such that $b k_2 = c$.
Substituting $a k_1$ for $b$ in the second equation gives $a k_1 k_2 =
c$, which implies that $a \mid c$.
\end{proof}

A number $p > 1$ with no positive divisors other than 1 and itself is
called a \term{prime}.  Every other number greater than 1 is called
\term{composite}.  The number 1 is neither prime nor composite.  This
is just a matter of definition, but reflects the fact that 1 does not
behave like a prime in some important contexts, such as the Fundamental
Theorem of Arithmetic.

\subsection{The Division Algorithm}

As you learned in elementary school, if one number does not evenly
divide another, then there is a ``remainder'' left over.  More
precisely, if you divide $b$ by $a$, then you get a quotient $q$ and
a remainder $r$.  This basic fact is the subject of a useful theorem:

\begin{theorem}[Division Algorithm]
Let $a$ and $b$ be integers such that $a > 0$.  Then there exist
integers $q$ and $r$ such that $b = qa + r$ and $0 \leq r < a$.
\end{theorem}

\begin{proof}
First, we show that the equation holds for {\em some} $r \geq 0$.  If
$b$ is positive, then the equation holds when $q = 0$ and $r = b$.  If
$b$ is not positive, then the equation holds when $q = b$ and $r = b(1
- a) \geq 0$.

By the least number principle, there must exist a {\em smallest} $r
\geq 0$ such that the equation holds.  Furthermore, $r$ must be less
than $a$; otherwise, $b = (q + 1) a + (r - a)$ would be another
solution with a smaller nonnegative remainder, contradicting the
choice of $r$.
\end{proof}

This theorem is traditionally called the ``division algorithm'', even
though it is a statement, not a procedure.  As an example, suppose
that $a = 10$ and $b = 2716$.  Then the quotient is $q = 271$ and the
remainder is $r = 6$, since $2716 = 271 \cdot 10 + 6$.  The remainder
$r$ is often denoted $b \term{\rem} a$.  For example, $32 \rem 5$ is
the remainder when 32 is divided by 5, which is 2.

{\em Warning:} Some people use ``mod'' in place of ``rem''.  This is
unfortunate, because ``mod'' has been used by mathematicians for
centuries in a confusingly similar context, and we shall do so here as
well.  Until all those people are, shall we say, liquidated, you'll
have to cope with the confusion.

\subsection{The Greatest Common Divisor}
\label{subsec:gcd}

The \term{greatest common divisor} of $a$ and $b$ is exactly what
you'd guess: the largest number that is a divisor of both $a$ and $b$.
It is denoted $\gcd(a, b)$.  For example, $\gcd(18, 24) = 6$.

Some junior high math teacher may, for some unexplained reason, have made
you compute greatest common divisors.  It turns out that the greatest
common divisor actually is an exceptionally useful tool for reasoning
about the integers.  The $\gcd(a, b)$ is a crucial piece of information
about the relationship between the numbers $a$ and $b$.

The theorem below describes an alternative characterization of the
greatest common divisor in terms of linear combinations, which is
particularly useful in proofs.  A \term{linear combination} of $a$ and
$b$ is an expression of the form $s a + t b$.  For example, $3 \cdot a
+ (-7) \cdot b$ is one possible linear combination of $a$ and $b$.

\begin{theorem}
\label{th:gcd}
The greatest common divisor of $a$ and $b$ is equal to the smallest
positive linear combination of $a$ and $b$.
\end{theorem}

For example, the greatest common divisor of 52 and 44 is 4.  Sure
enough, 4 is a linear combination of 52 and 44:
\[
6 \cdot 52 + (-7) \cdot 44  =  4
\]

And no linear combination of 52 and 44 is equal to a smaller positive
integer.  In Section~\ref{sec:pulverizer}, we'll describe an efficient
procedure for finding such linear combinations.

\begin{proof}
Let $m$ be the smallest positive integer that can be expressed as an
linear combination of $a$ and $b$; in particular, suppose $m = sa +
tb$.  We first show that $m$ is a common divisor of $a$ and $b$.  By
the division algorithm, there exist integers $q$ and $r$ such that
\[
a  =  q \cdot m + r
\]

where $0 \leq r < m$.  Rearranging terms and using the relation $m =
sa + tb$ gives:
\beqn
r & = & a - q \cdot m \\
  & = & a - q \cdot (sa + tb) \\
  & = & (1 - qs) \cdot a + (-qt) \cdot b
\eeqn

 We've now written $r$ as a linear combination of $a$ and $b$.
However, since $m$ was defined to be the smallest positive linear
combination of $a$ and $b$ and $r < m$, it follows that $r$ is not
positive; that is, the remainder $r$ is zero.  So $m$ is a divisor of
$a$.  By a symmetric argument, $m$ is a divisor of $b$, and so $m$ is
a common divisor of $a$ and $b$.

All that remains is to show that $m$ is the {\em greatest} common
divisor of $a$ and $b$.  By definition, $\gcd(a, b)$ divides both $a$
and $b$.  Thus, $\gcd(a, b)$ divides $sa + tb = m$ by part (3) of
Lemma~\ref{lem:div}.  This implies that $\gcd(a, b) \leq m$.  Of
course, the common divisor $m$ can not be strictly greater than the
greatest common divisor.  Therefore, $m$ must be equal to the greatest
common divisor of $a$ and $b$.
\end{proof}

Let's use this alternative characterization of the greatest common
divisor to prove some properties.

\begin{lemma} The following statements about the greatest common divisor hold:
\label{lem:gcd}

\begin{enumerate}
\item Every common divisor of $a$ and $b$ divides $\gcd(a, b)$.

\item $\gcd(k a, k b) = k \cdot \gcd(a, b)$ for all $k > 0$.

\item If $\gcd(a, b) = 1$ and $\gcd(a, c) = 1$, then $\gcd(a, bc) =
1$.

\item if $a \mid b c$ and $\gcd(a, b) = 1$, then $a \mid c$.

\end{enumerate}
\end{lemma}

\begin{proof}
We prove only parts (3) and (4).  For part (3), the assumptions
together with Theorem~\ref{th:gcd} imply that there exist integers
$s$, $t$, $u$, and $v$ such that:
\beqn
s a + t b & = & 1 \\
u a + v c & = & 1
\eeqn

Multiplying these two equations gives:
\[
(s a + t b)(u a + v c) = 1
\]

The left side can be rewritten as $a (a s u + b t u + c s v) + b c (t
v)$.  This is a linear combination of $a$ and $b c$ that is equal to
1, so $\gcd(a, bc) = 1$ by Thereom~\ref{th:gcd}.

For part (4), observe that $a \mid ac$ trivially and $a \mid bc$ by
assumption.  Therefore, $a$ divides every linear combination of $ac$
and $bc$ by part (3) of Lemma~\ref{lem:div}.  Theorem~\ref{th:gcd}
says that $\gcd(ac, bc)$ is equal to one such linear combination.
Therefore, $a$ divides $\gcd(ac, bc) = c \cdot \gcd(a, b) = c$.  The
first equality uses part (2) of this lemma, and the second uses the
assumption that $\gcd(a, b) = 1$.
\end{proof}

\subsection{The Fundamental Theorem of Arithemtic}

The Fundamental Theorem of Arithmetic states that every positive
integer can be written in a unique way as a product of primes.  There
is a certain wonder in this statement, even if you've known it since
the crib.  Primes show up erratically in the sequence of integers.  In
fact, their distribution seems almost random:

\[
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, \ldots
\]

Basic questions about this sequence have stumped humanity for
centuries.  And yet, somehow, every natural number can be built up
from primes in {\em exactly one way}.  The proof relies on a
preliminary lemma:

\begin{lemma}
\label{lem:prime-divides}
If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.
\end{lemma}

\begin{proof}
The greatest common divisor of $a$ and $p$ must be either 1 or $p$,
since these are the only divisors of $p$.  If $\gcd(a, p) = p$, then
the claim holds, because $a$ is a multiple of $p$.  Otherwise,
$\gcd(a, p) = 1$ and so $p \mid b$ by part (4) of Lemma~\ref{lem:gcd}.
\end{proof}

According to this lemma, if you know that $19 \mid 403 \cdot 629$,
then you know that 19 divides either 403 or 629--- even though you
might not know which!  We can generalize this with a routine induction
argument:

\begin{lemma}
\label{lem:prime-divides-ind}
Let $p$ be a prime.  If $p \mid a_1 a_2 \ldots a_n$, then $p$ divides
some $a_i$.
\end{lemma}

Now we can prove the Fundamental Theorem of Arithmetic.

\begin{theorem}
Every positive integer $n$ can be written in a unique way as a product
of primes:
\begin{eqnarray*}
n & = & p_1 \cdot p_2 \cdots p_j
\hspace{1in}
(p_1 \leq p_2 \leq \ldots \leq p_j)
\end{eqnarray*}
\end{theorem}

We're relying on a standard convention here: the product of an empty set
of numbers is defined to be 1, much as the sum of an empty set of
numbers is defined to be 0.  Without this convention, the theorem
would be false for $n = 1$.

\begin{proof}
We must prove two things: (1) every positive integer can be expressed
as a product of primes and (2) this expression is unique.

First, we use strong induction to prove that every positive integer
$n$ is a product of primes.  As a base case, $n = 1$ is the product of
the empty set of primes.  For the inductive step, suppose that every
$k < n$ is a product of primes.  We must show that $n$ is also a
product of primes.  If $n$ is itself prime, then this is true
trivially.  Otherwise, $n = a b$ for some $a, b < n$.  By the
induction assumption, $a$ and $b$ are both products of primes.
Therefore, $a \cdot b = n$ is also a product of primes.  Thus, the
claim is proved by induction.

Second, we use the least-number principle to prove that every positive
integer can be written as a product of primes in a unique way.  The
proof is by contradiction: Assume, contrary to the claim, that there
exist positive integers that can be written as products of primes in
more than one way.  By the least-number principle, one of these
integers is the \emph{smallest} to have this property. Call this
integer $n$, and let

\begin{eqnarray*}
n & = & p_1 \cdot p_2 \cdots p_j \\
  & = & q_1 \cdot q_2 \cdots q_k
\end{eqnarray*}

be two of the (possibly many) ways to write it as a product of primes.
Then $p_1 \mid n$ and so $p_1 \mid q_1 q_2 \cdots q_k$.
Lemma~\ref{lem:prime-divides-ind} implies that $p_1$ divides one of
the primes $q_i$.  But since $q_i$ is a prime, it must be that $p_1 =
q_i$.  Deleting $p_1$ from the first product and $q_i$ from the
second, we find that $n / p_1$ is a positive integer \emph{smaller}
than $n$ that can be written as a product of primes in two distinct
ways.  But this contradicts the selection of $n$ as the smallest
positive integer with this property.
\end{proof}

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

\section{Congruence}
\label{sec:congruence}

On page 1 of his masterpiece on number theory, {\em Disquisitiones
Arithmeticae}, Gauss introduced the notion of ``congruence''.  Now,
Gauss managed to cough up a half-decent idea every now and then, so
let's take a look at this one.  Gauss said that \term{$a$ is congruent
to $b$ modulo $c$} if $c \mid (a - b)$.  This is denoted $a \equiv b
\pmod{c}$.  For example:
\[
29 \equiv 15 \pmod{7}  \quad\text{ because }  7 \mid (29 - 15).
\]

Intuitively, the $\equiv$ symbol is sort of like an $=$ sign, and the
$\pmod{7}$ describes the specific sense in which 29 is equal-ish to
15.  Thus, even though $\pmod{7}$ appears on the right side, it is in
no sense more strongly associated with the 15 than the 29.  Don't
confuse rem and mod.

\subsection{How rem and mod are Related}

Let's look more closely at the notions of congruence and remainders,
because they are pretty important and closely related.  Suppose that
we fix a modulus $c$.  Then the relation ``is congruent modulo $c$''
is an equivalence relation on the set of integers.  For example, if we
choose the modulus $c = 3$, then we get an equivalence relation with
three equivalence classes:

\[
\begin{array}{c}
\left\{ \ldots,\ -6,\ -3,\ 0,\ 3,\ 6,\ \ldots \right \} \\
\left\{ \ldots,\ -5,\ -2,\ 1,\ 4,\ 7,\ \ldots \right \} \\
\left\{ \ldots,\ -4,\ -1,\ 2,\ 5,\ 8,\ \ldots \right \}
\end{array}
\]

Two numbers are congruent mod 3 if and only if they are in
the same equivalence class.  For example, $-5 \equiv 7 \pmod{3}$
because $-5$ and 7 are in the same equivalence class.  However, $6
\not\equiv 7 \pmod{3}$, because they are in different classes, as you
can see in the table above.

Thinking in terms of equivalence classes also gives some insight into
the $\rem$ operator.  Suppose we underline the smallest nonnegative
number in each equivalence class:

\[
\begin{array}{c}
\left\{ \ldots,\ -6,\ -3,\ \underline{0},\ 3,\ 6,\ \ldots \right \} \\
\left\{ \ldots,\ -5,\ -2,\ \underline{1},\ 4,\ 7,\ \ldots \right \} \\
\left\{ \ldots,\ -4,\ -1,\ \underline{2},\ 5,\ 8,\ \ldots \right \}
\end{array}
\]

 Now $n \rem 3$ is the underlined number in $n$'s equivalence
class.  For example, $8 \rem 3 = 2$, since 2 is the underlined number
in 8's equivalence class.  In effect, rem maps each number to a
``representative'' of its equivalence class.

This suggests another way of thinking about congruences: two numbers
are in the same equivalence class if and only if they have the same
representative; that is:

\[
a \equiv b \pmod{c} \quad \text{ iff } \quad (a \rem c) = (b \rem c)
\]

For example, 19 and 32 are congruent modulo 13, because both
leave a remainder of 6 when divided by 13.

Mathematics done with congruences instead of traditional equations is
usually called ``modular arithmetic''.  If anything, the importance of
modular arithmetic has grown since the time of Gauss.  For him,
congruences were a reasoning tool.  These days, computer hardware
works with fixed-sized chunks of data, so the arbitrarily large
integers that can come up in ordinary arithmetic are problematic.  A
standard solution is to build computers that, at a low level, do
modular arithmetic instead.  For example, a computer with 64-bit
internal registers typically does integer arithmetic modulo $2^{64}$.
An instruction to add the contents of registers $A$ and $B$ actually
computes $(A + B) \rem 2^{64}$.

\subsection{Facts about rem and mod}

Many familiar rules remain valid when one works modulo an integer $n
\geq 1$.  For example, we can add a constant to both sides of a
congruence:

\[
a \equiv b \pmod{n}
\hspace{0.5in} \text{implies} \hspace{0.5in}
a + c \equiv b + c \pmod{n}
\]

Whenever you are unsure about a relationship involving congruences or
remainders, go back to the definitions.  For example, $a \equiv b
\pmod{n}$ means that $n \mid (a - b)$.  We can rewrite this as $n \mid
((a + c) - (b + c))$, which means that $a + c \equiv b + c \pmod{n}$
as we claimed above.

There is one glaring difference between traditional arithmetic and
modular arithmetic.  You can cancel multiplicative terms on opposite
sides of an ordinary equation:

\[
a \not\!c = b \not\!c
\quad \text{implies} \quad
a = b \quad \text{(provided $c \neq 0$)}
\]

However, you can not always cancel such multiplicative terms in a
congruence.  Here is an example where a true statement becomes a false
statement after cancelling:

\[
2\ \cdot \not\!3 \equiv 4\ \cdot \not\!3 \pmod{6} \quad \leftarrow \text{This is an error!}
\]

We'll return to the issue of cancellation in the next two sections.
In the meanwhile, let's get more practice with rem and mod by proving
some basic facts:

\begin{lemma}
\label{lem:mod}
The following assertions hold for all $n \geq 1$:

\begin{enumerate}
\item If $a \equiv b \pmod{n}$, then $ac \equiv bc \pmod{n}$.
\item $(a \rem n) \equiv a \pmod{n}$
\item $(a_1 \rem n) \cdot (a_2 \rem n) \cdots (a_k \rem n) \equiv a_1 \cdot a_2 \cdots a_k \pmod{n}$
\item $\gcd(a, b) = \gcd(b, a \rem b)$
\end{enumerate}
\end{lemma}

The first statement can be interpreted in two ways.  More obviously,
multiplying both sides of a valid congruence by a constant $c$ gives a
new, valid congruence.  More subtly, if we replace term $a$ in a
product with a congruent term $b$, then the new product is congruent to
the old one.

\begin{proof}
We prove each part separately.

\begin{enumerate}

\item The condition $a \equiv b \pmod{n}$ is equivalent to the
assertion $n \mid (a - b)$.  Therefore, $n \mid (a - b)c$ by part 1 of
Theorem~\ref{lem:div}, and so $n \mid (ac - bc)$.  This is equivalent
to $ac \equiv bc \pmod{n}$.

\item Recall that $a \rem n$ is equal to $a - qn$ for some integer
$q$.  We can reason as follows:

\[
\begin{array}{ll}
            & n \mid qn \\
\Rightarrow & n \mid a - (a - qn) \\
\Rightarrow & n \mid a - (a \rem n)
\end{array}
\]

The last statement is equivalent to $(a \rem n) \equiv a \pmod{n}$.

\item We can transform the right side to the left side by applying
parts (1) and (2) of this lemma to each variable $a_i$ in turn:
\beqn
(a_1 \rem n) \cdot (a_2 \rem n) \cdots (a_k \rem n)
    & \equiv & a_1 \cdot (a_2 \rem n) \cdots (a_k \rem n) \pmod{n} \\
    & \equiv & a_1 \cdot a_2 \cdots (a_k \rem n) \pmod{n} \\
    & \ldots & \\
    & \equiv & a_1 \cdot a_2 \cdots a_k \pmod{n}
\eeqn

A routine induction formalizes this argument.


\item Recall that $a \rem b = a - q b$ for some quotient $q$.  Thus,
$a \rem b$ is a linear combination of $a$ and $b$.  By part (3) of
Lemma~\ref{lem:div}, any number that divides both $a$ and $b$ also
divides $a \rem b$.  Therefore, every common divisor of $a$ and $b$ is
also a common divisor of $b$ and $a \rem b$.  Similarly, $a$ is a
linear combination of $b$ and $a \rem b$, and so any number that
divides both $b$ and $a \rem b$ also divides $a$.  Therefore, every
common divisor of $b$ and $a \rem b$ is also a common divisor of $a$
and $b$.  Thus, in particular, $\gcd(a, b) = \gcd(b, a \rem b)$ as
claimed.

\end{enumerate}
\end{proof}

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

\section{Arithmetic Modulo a Prime}
\label{sec:prime}

The real numbers have a nice quality that the integers lack.  Namely,
every nonzero real number $r$ has a \term{multiplicative inverse}
$r^{-1}$ such that $r \cdot r^{-1} = 1$.  For example, the
multiplicative inverse of $-3$ is $-\frac{1}{3}$.  Multiplicative
inverses provide a basis for division: $a / b$ can be defined as $a
\cdot b^{-1}$.  In contrast, most integers do not have multiplicative
inverses within the set of integers.  For example, no integer can be
multiplied by 5 to give 1.  As a result, if we want to divide
integers, we are forced to muck about with remainders.

Remarkably, this defect of the integers vanishes {\em when we work
modulo a prime number $p$}.  In this setting, most integers do have
multiplicative inverses!  For example, if we are working modulo 11,
then the multiplicative inverse of 5 is 9, because:

\[
5 \cdot 9 \equiv 1 \pmod{11}
\]

The only exceptions are multiples of the modulus $p$, which lack
inverses in much the same way as 0 lacks an inverse in the real
numbers.  The following lemma makes this observation precise.

\begin{lemma}
\label{lem:inverse-prime}
Let $p$ be a prime.  If $k$ is not a multiple of $p$, then there
exists an integer $k^{-1}$ such that:

\[
k \cdot k^{-1} \equiv 1 \pmod{p}
\]
\end{lemma}

\begin{proof}
The greatest common divisor of $p$ and $k$ must be 1, since 1 and $p$
are the only divisors of $p$ and $p$ is not a divisor of $k$ by
assumption.  Therefore, there are integers $s$ and $t$ such that $s k
+ t p = 1$.  This means that $p \mid s k - 1$ and so $s \cdot k \equiv
1 \pmod{p}$.  Now define $k^{-1}$ to be $s$.
\end{proof}

(Every number congruent to $k^{-1}$ is also a multiplicative inverse
of $k$.)

The existence of multiplicative inverses has several nice
consequences.  First, we are free to cancel multiplicative terms that
appear on both sides of a congruence, just like we can with ordinary
equations:

\begin{corollary}
\label{cor:cancellation-prime}
Suppose $p$ is a prime and $k$ is not a multiple of $p$.  If

\[
a k \equiv b k \pmod{p}
\]

then

\[
a \equiv b \pmod{p}
\]
\end{corollary}

This holds because we can multiply both sides of the first congruence
by $k^{-1}$ and simplify to obtain the second.  Beyond this, many
theorems that hold for the real numbers (from linear algebra, say)
have direct analogues that hold for the integers modulo a prime.

\subsection{Fermat's Theorem}

We can now prove a classic result known as Fermat's Theorem, which is
much easier than his famous Last Theorem--- and also more useful.  We
need one preliminary lemma that sheds light on how arithmetic modulo a
prime works in general.

\begin{lemma}
\label{lem:permutes-prime}
Suppose $p$ is a prime and $k$ is not a multiple of $p$.  Then the
sequence:

\[
(0 \cdot k) \rem p,\quad
(1 \cdot k) \rem p,\quad
(2 \cdot k) \rem p,\quad
\quad \ldots,\quad
\bigl( (p-1) \cdot k \bigr) \rem p
\]

is a permutation of the sequence:

\[
0,\quad 1,\quad 2,\quad \ldots,\quad (p - 1)
\]

This remains true if the first term is deleted from each sequence.
\end{lemma}

\begin{proof}
The first sequence contains $p$ numbers.  And no two numbers in the
first sequence are the same, since $a k \rem p = b k \rem p$ implies
$a k \equiv b k \pmod{p}$ and so $a \equiv b \pmod{p}$.  This implies
that $a = b$, because $a$ and $b$ are both between 0 and $p - 1$.
Furthermore, the numbers in the first sequence must be in the range 0
to $p - 1$, by the definition of rem.  Therefore, the first sequence
must contain all of the numbers from 0 to $p - 1$ in some order.  The
claim remains true if the first terms are deleted, because both
sequences begin with 0.
\end{proof}

For example, suppose $p = 5$ and $k = 3$.  Then the sequence:

\[
\underbrace{(0 \cdot 3) \rem 5}_{=0},\quad
\underbrace{(1 \cdot 3) \rem 5}_{=3},\quad
\underbrace{(2 \cdot 3) \rem 5}_{=1},\quad
\underbrace{(3 \cdot 3) \rem 5}_{=4},\quad
\underbrace{(4 \cdot 3) \rem 5}_{=2}
\]

is a permutation of 0, 1, 2, 3, 4 and the last four terms are a
permutation of 1, 2, 3, 4.

\begin{theorem}[Fermat's Theorem]
Suppose $p$ is a prime and $k$ is not a multiple of $p$.  Then:

\begin{eqnarray*}
k^{p-1} \equiv 1 \pmod{p}
\end{eqnarray*}
\end{theorem}

\begin{proof}
\begin{eqnarray*}
1 \cdot 2 \cdot 3 \cdots (p-1)
	& \equiv & (k \rem p) \cdot (2k \rem p) \cdot (3k \rem p) \cdots ((p-1) k \rem p) \pmod{p} \\
	& \equiv & k \cdot 2k \cdot 3k \cdots (p-1) k \pmod{p} \\
	& \equiv & (p-1)! \cdot k^{p-1} \pmod{p} \\
\end{eqnarray*}

The expressions on the first line are actually equal, by
Lemma~\ref{lem:permutes-prime}, so they are certainly congruent modulo
$p$.  The second step uses part (3) of Lemma~\ref{lem:mod}.  In the
third step, we rearrange terms in the product.

Now $(p - 1)!$ can not be a multiple of $p$, since $p$ is a prime and
does not divide any of 1, 2, \ldots, $(p-1)$.  Therefore, we can
cancel $(p - 1)!$ from the first expression and the last by
Corollary~\ref{cor:cancellation-prime}, which proves the claim.
\end{proof}

\subsection{Finding Inverses with Fermat's Theorem}

Fermat's Theorem suggests an efficient procedure for finding the
multiplicative inverse of a number modulo a large prime.  Suppose that
$p$ is a prime and $k$ is not a multiple of $p$.  Then, by Fermat's
Theorem, we know that:

\begin{eqnarray*}
k^{p-2} \cdot k \equiv 1 \pmod{p}
\end{eqnarray*}

Therefore, $k^{p-2}$ must be a multiplicative inverse of $k$.  For
example, suppose that we want the multiplicative inverse of 6 modulo
17.  Then we need to compute $6^{15} \rem 17$, which we can do by the
now-familiar trick of successive squaring.  All the congruences below
hold modulo 17.

\begin{eqnarray*}
6^2
        & \equiv & 36 \\
	& \equiv & 2 \\
6^4
	& \equiv & (6^2)^2 \\
	& \equiv & 2^2 \\
	& \equiv & 4 \\
6^8
	& \equiv & (6^4)^2 \\
	& \equiv & 4^2 \\
	& \equiv & 16 \\
6^{15}
	& \equiv & 6^8 \cdot 6^4 \cdot 6^2 \cdot 6 \\
	& \equiv & 16 \cdot 4 \cdot 2 \cdot 6 \\
	& \equiv & 3
\end{eqnarray*}

Therefore, $6^{15} \rem 17 = 3$.  Sure enough, 3 is the multiplicative
inverse of 6 modulo 17, since:

\begin{eqnarray*}
3 \cdot 6 & \equiv 1 \pmod{17}
\end{eqnarray*}

In general, if we were working modulo a prime $p$, finding a
multiplicative inverse by trying every value between 1 and $p - 1$
would require about $p$ operations.  However, the approach above
requires only about $\log p$ operations, which is far better when $p$
is large.  We'll see another way to find inverses in
Section~\ref{sec:pulverizer}.

\section{Arithmetic with an Arbitrary Modulus}

Arithmetic modulo an arbitrary positive integer is only a little more
painful than working modulo a prime, in the same sense that a doctor
says ``This is only going to hurt a little'' before he jams a big
needle in your arm.

\subsection{Relative Primality and Phi}

First, we need a new definition.  Integers $a$ and $b$ are
\term{relatively prime} if $\gcd(a, b) = 1$.  For example, 8 and 15
are relatively prime, since $\gcd(8, 15) = 1$.  Note that every
integer is relatively prime to a genuine prime number $p$, except for
multiples of $p$.

We'll also need a certain function that is defined using relative
primality.  Let $n$ be a positive integer.  Then $\phi(n)$ denotes the
number of integers in $\set{1, 2, \ldots, n - 1}$ that are relatively
prime to $n$.  For example, $\phi(7) = 6$, since 1, 2, 3, 4, 5, and 6
are all relatively prime to 7.  Similarly, $\phi(12) = 4$, since only
1, 5, 7, and 11 are relatively prime to 12.  If you know the prime
factorization of $n$, then computing $\phi(n)$ is a piece of cake,
thanks to the following theorem.

\begin{theorem}
\label{th:phi}
The function $\phi$ obeys the following relationships:

\begin{enumerate}
\item If $a$ and $b$ are relatively prime, then $\phi(ab) = \phi(a)\phi(b)$.
\item If $p$ is a prime, then $\phi(p^k) = p^k - p^{k-1}$ for $k \geq 1$.
\end{enumerate}
\end{theorem}

For example, here's how we might use Theorem~\ref{th:phi} to compute
$\phi(300)$:
\beqn
\phi(300)
    & = & \phi(2^2 \cdot 3 \cdot 5^2) \\
    & = & \phi(2^2) \cdot \phi(3) \cdot \phi(5^2) \\
    & = & (2^2 - 2^1) (3^1 - 3^0) (5^2 - 5^1) \\
    & = & 80
\eeqn

We factor 300 in the first step, use part (1) of Theorem~\ref{th:phi}
twice in the second step, use part (2) in the third step, and then
simplify.

\subsection{Generalizing to an Arbitrary Modulus}

Let's generalize what we know about arithmetic modulo a prime.  Now,
instead of working modulo a prime $p$, we'll work modulo an arbitrary
positive integer $n$.  The basic theme is that arithmetic modulo $n$
may be complicated, but the integers {\em relatively prime} to $n$
remain fairly well-behaved.  For example, if $k$ is relatively prime
to $n$, then $k$ has a multiplicative inverse modulo $n$:

\begin{lemma}
\label{lem:inverse-arb}
Let $n$ be a positive integer.  If $k$ is relatively prime to $n$,
then there exists an integer $k^{-1}$ such that:

\[
k \cdot k^{-1} \equiv 1 \pmod{n}
\]
\end{lemma}

\begin{proof}
There exist integers $s$ and $t$ such that $s k + t n = \gcd(k, n) =
1$ by Theorem~\ref{th:gcd}.  Rearranging terms gives $tn = 1 - sk$,
which implies that $n \mid 1 - sk$ and $sk \equiv 1 \pmod{n}$.  Define
$k^{-1}$ to be $s$.
\end{proof}

As a consequence of this lemma, we can cancel a multiplicative term
from both sides of a congruence if that term is relatively prime to
the modulus:

\begin{corollary}
\label{cor:cancellation-arb}
Suppose $n$ is a positive integer and $k$ is relatively prime to $n$.
If

\[
a k \equiv b k \pmod{n}
\]

then

\[
a \equiv b \pmod{n}
\]
\end{corollary}

This holds because we can multiply both sides of the first congruence
by $k^{-1}$ and simplify to obtain the second.

\subsection{Euler's Theorem}

Now we're going to prove Euler's Theorem, a generalization of Fermat's
Theorem.  A clever application of Euler's Theorem opened the way to
public-key cryptography, which makes secure web transactions possible
today.  The proof is much like the proof of Fermat's Theorem, except
that we focus on integers relatively prime to the modulus.  Let's
start with a lemma.

\begin{lemma}
\label{lem:permutes-arb}
Suppose $n$ is a positive integer and $k$ is relatively prime to $n$.
Let $k_1, \ldots, k_r$ denote all the integers relatively prime to $n$
in the range $0 \leq k_i < n$.  Then the sequence:

\[
(k_1 \cdot k) \rem n,\quad
(k_2 \cdot k) \rem n,\quad
(k_3 \cdot k) \rem n,\quad
\quad \ldots,\quad
(k_r \cdot k) \rem n
\]

is a permutation of the sequence:

\[
k_1,\quad k_2,\quad \ldots,\quad k_r
\]
\end{lemma}

\begin{proof}
We will show that the numbers in the first sequence are all distinct
and all appear in the second sequence.  Since the two sequences have
the same length, the first must be a permutation of the second.

First, we show that the numbers in the first sequence are all
distinct.  Suppose $k_i k \rem n = k_j k \rem n$.  This is equivalent
to $k_i k \equiv k_j k \pmod{n}$, which implies $k_i \equiv k_j
\pmod{n}$ by Corollary~\ref{cor:cancellation-arb}.  This, in turn,
means that $k_i = k_j$ since both are between 1 and $n-1$.  Thus, a
term in the first sequence is only equal to itself.

Next, we show that each number in the first sequence appears in the
second.  By assumption, $\gcd(k_i, n) = 1$ and $\gcd(k, n) = 1$, which
means that $\gcd(k_i k, n) = \gcd(k_i k \rem n, n) = 1$ by part (3) of
Lemma~\ref{lem:gcd} and part (4) of Lemma~\ref{lem:mod}.  Therefore,
$k_i k \rem n$ is relatively prime to $n$ and is in the range from 0
to $n - 1$ by the definition of rem.  The second sequence is defined
to consist of all such integers.
\end{proof}

We can now prove Euler's Theorem:

\begin{theorem}[Euler's Theorem]
Suppose $n$ is a positive integer and $k$ is relatively prime to $n$.
Then:

\begin{eqnarray*}
k^{\phi(n)} \equiv 1 \pmod{n}
\end{eqnarray*}
\end{theorem}

\begin{proof}
Let $k_1, \ldots, k_r$ denote all integers relatively prime to $n$
such that $0 \leq k_i < n$.  Then $r = \phi(n)$, by the definition of
the function $\phi$.  Now we can reason as follows:
\begin{eqnarray*}
k_1 \cdot k_2 \cdot k_3 \cdots k_r
& \equiv & 
\bigl( (k_1 \cdot k) \rem n \bigr) \cdot 
\bigl( (k_2 \cdot k) \rem n \bigr) \cdot 
\bigl( (k_3 \cdot k) \rem n \bigr) \cdots 
\bigl( (k_r \cdot k) \rem n \bigr) \pmod{n} 
\\
& \equiv & 
(k_1 \cdot k) \cdot 
(k_2 \cdot k) \cdot 
(k_3 \cdot k) \cdots 
(k_r \cdot k) \pmod{n} 
\\
& \equiv & 
(k_1 \cdot k_2 \cdot k_3 \cdots k_r) \cdot k^r \pmod{p}
\end{eqnarray*}
The expressions on the first line are actually equal, by
Lemma~\ref{lem:permutes-arb}; therefore, they are also congruent.
The second step uses part 3 of Theorem~\ref{lem:mod}.  In the third
step, we rearrange terms in the product.

Part (3) of Lemma~\ref{lem:gcd} implies that $k_1 \cdot k_2 \cdot k_3
\cdots k_r$ is prime relative to $n$.  Therefore, we can cancel this product
from the first expression and the last by
Corollary~\ref{cor:cancellation-arb}.  This proves the claim.
\end{proof}

We can find multiplicative inverses using Euler's theorem as we did
with Fermat's theorm: if $k$ is relatively prime to $n$, then
$k^{\phi(n) - 1}$ is a multiplicative inverse of $k$ modulo $n$.
However, this approach requires computing $\phi(n)$.  Our best method
for doing so requires factoring $n$, which can be quite difficult in
general.  Fortunately, there is a tool that finds multiplicative
inverses and solves many other number-theoretic problems as well.

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

\section{The Pulverizer}
\label{sec:pulverizer}

Way back in Section~\ref{subsec:gcd}, we proved that there exist
integers $s$ and $t$ such that:
\[
\gcd(a, b)  =  s a + t b
\]

Unfortunately, the proof was nonconstructive; that is, it suggested no
way to actually find $s$ and $t$.  That job is tackled by a
mathematical tool that dates to sixth-century India, where it was
called {\em kuttak}, which means ``The Pulverizer''.  Today, the
Pulverizer is more commonly known as ``the extended Euclidean GCD
algorithm'', but that's lame.  We're sticking with ``Pulverizer''.

Euclid's algorithm for finding the greatest common divisor of two
numbers relies on repeated application of the equation:
\[
\gcd(a, b) = \gcd(b, a \rem b)
\]
which is part~(4) of Lemma~\ref{lem:mod}.  For example, we can compute
the greatest common divisor of 259 and 70 as follows:

\[
\begin{array}{rclcl}
\gcd(259, 70)
    & = & \gcd(70, 49) & \quad & \text{since $259 \rem 70 = 49$}\\
    & = & \gcd(49, 21) && \text{since $70 \rem 49 = 21$} \\
    & = & \gcd(21, 7) && \text{since $49 \rem 21 = 7$} \\
    & = & \gcd(7, 0) && \text{since $21 \rem 7 = 0$} \\
    & = & 7
\end{array}
\]

The Pulverizer goes through the same steps, but requires some extra
bookkeeping along the way.  As we compute $\gcd(a, b)$, we keep track
of how to write each of the remainders (49, 21, and 7, in the example)
as a linear combination of $a$ and $b$.  This is worthwhile, because
our objective is to write the last nonzero remainder (which is the
gcd) as such a linear combination.

The Pulverizer is probably best explained with an example.  For
example, here is how we find a linear combination of $a = 259$ and $b
= 70$ that is equal to $\gcd(a, b) = 7$:

\[
\begin{array}{ccccrcl}
x & \quad & y & \quad & (x \rem y) & = & x - q \cdot y \\ \hline
259 && 70 && 49 & = &   259 - 3 \cdot 70 \\
70 && 49 && 21  & = &   70 - 1 \cdot 49 \\
&&&&            & = &   70 - 1 \cdot (259 - 3 \cdot 70) \\
&&&&            & = &   -1 \cdot 259 + 4 \cdot 70 \\
49 && 21 && 7   & = &   49 - 2 \cdot 21 \\
&&&&            & = &   (259 - 3 \cdot 70) -
                                2 \cdot (-1 \cdot 259 + 4 \cdot 70) \\
&&&&            & = &   \fbox{$3 \cdot 259 - 11 \cdot 70$} \\
21 && 7 && 0
\end{array}
\]

Then again, maybe the Pulverizer is best explained with an example
{\em followed by some clarifying comments}.  We begin by initializing
two variables, $x = a$ and $y = b$.  In the first two columns above,
we carry out Euclid's algorithm.  At each step, we compute $x \rem y$,
which can be written in the form $x - q \cdot y$.  (Remember that the
Division Algorithm says $x = q \cdot y + r$, where $r$ is the
remainder.  We get $r = x - q \cdot y$ by rearranging terms.)  Then we
replace $x$ and $y$ in this equation with equivalent linear
combinations of $a$ and $b$, which we already computed.  After
simplifying, we are left with a linear combination of $a$ and $b$ that
is equal to the remainder as desired.  The final solution is boxed in
the example above.

The Pulverizer quickly solves many problems involving congruences.
For example, suppose that we want to find a multiplicative inverse of
$k$ modulo $n$, assuming such an inverse exists.  First, we use the
Pulverizer to find integers $s$ and $t$ such that:
\[
s k + t n =  1
\]

If this equation holds, then we know that:

\[
s k \equiv 1 \pmod{n}
\]

Therefore, $s$ is the multiplicative inverse of $k$.  Problem pulverized!

\end{document}
