\documentclass[12pt,twoside]{article}
\usepackage{light}

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

\begin{document}
\lecture{Number Theory, II.}{September 23, 2004}

\section{Die Hard}

\textbox{
\begin{list}{}{\itemsep=0in \leftmargin=0.25in \rightmargin=0.25in}

\item[\textbf{Simon:}] On the fountain, there should be 2 jugs, do you
see them?  A 5-gallon and a 3-gallon.  Fill one of the jugs with
exactly 4 gallons of water and place it on the scale and the timer
will stop.  You must be precise; one ounce more or less will result in
detonation.  If you're still alive in 5 minutes, we'll speak.

\item[\textbf{Bruce:}] Wait, wait a second. I don't get it. Do you get it?

\item[\textbf{Samuel:}] No.

\item[\textbf{Bruce:}] Get the jugs. Obviously, we can't fill the 3-gallon jug
with 4 gallons of water.

\item[\textbf{Samuel:}] Obviously.

\item[\textbf{Bruce:}] All right. I know, here we go. We fill the 3-gallon jug
exactly to the top, right?

\item[\textbf{Samuel:}] Uh-huh.

\item[\textbf{Bruce:}] Okay, now we pour this 3 gallons into the 5-gallon jug,
giving us exactly 3 gallons in the 5-gallon jug, right?

\item[\textbf{Samuel:}] Right, then what?

\item[\textbf{Bruce:}] All right. We take the 3-gallon jug and fill it a third
of the way...

\item[\textbf{Samuel:}] No!  He said, ``Be precise.''  Exactly 4
gallons.

\item[\textbf{Bruce:}] Shit.  Every cop within 50 miles is running his ass off
and I'm out here playing kids games in the park.

\item[\textbf{Samuel:}] Hey, you want to focus on the problem at hand?

\end{list}
}

This is from the movie \textit{Die Hard 3: With a Vengance}.  Bruce
Willis and Samuel L. Jackson are cops trying to disarm Simon's
diabolical bomb.  In the nick of time, they find a solution.  On the
surface, \textit{Die Hard 3} is just a B-grade action movie; however,
I think the inner message of the film is that everyone should learn at
least a little number theory.

\subsection{Death by Induction}

Apparently, \textit{Die Hard 4: Die Hardest} is planned for release in
2005.  In this new film, Bruce just happens to stumble into another
terrorist plot while on vacation.  But the villian is even more
devious this time: Bruce is given a 3-gallon jug and a 6-gallon jug
and must measure out exactly 4 gallons.  Some scratchwork suggests
that the task is impossible.  But surely we'd all rest easier if we
could mathematically prove that there can be no \textit{Die Hard 5}.

Let's try an inductive proof that Bruce can not produce exactly 4
gallons of water using 3 and 6-gallon jugs.  The first difficulty is
that induction always proves that some statement holds for all values
of a natural variable $n$, but no such natural variable appears in the
problem statement.

In general, however, in problems where we want to show that some
condition always holds, a good choice is to let $n$ be a number of
steps or operations.  In this case, we can let $n$ be the number of
times water is poured.  Then we can try to prove that for all $n \geq
0$, neither jug contains exactly 4 gallons of water after $n$ steps.
At least we've now recast the problem in a form that makes induction
applicable.  Let's see how the argument works out.

\begin{theorem}
Bruce dies.
\end{theorem}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition, ``Neither
jug contains 4 gallons after $n$ steps.''  In the base case, $P(0)$ is
true because both jugs are initially empty.  Now we assume that $P(n)$
is true in order to prove $P(n+1)$; that is, we assume that neither
jug contains 4 gallons after $n$ steps and prove that neither jug
contains 4 gallons after $n + 1$ steps.  Umm...
\end{proof}

We're stuck!  The proof can not be completed.  The fact that neither
jug contains 4 gallons of water after $n$ steps is not sufficient to
prove that neither jug can contain 4 gallons after $n + 1$ steps.  For
example, after $n$ steps each jug might hold 2 gallons of water.  But
then combining their contents in the 6-gallon jug would produce 4
gallons.  In logical terms, we can't hope to \textit{prove} that
$P(n)$ implies $P(n+1)$, because that's not even true: $P(n)$ does
\textit{not} imply $P(n+1)$!

Our first recourse when the inductive step falls apart is to
strengthen the induction hypothesis.  For example, further scratchwork
suggests that the number of gallons in each jug is always a multiple
of 3.  So we might try again with the induction hypothesis, ``After
$n$ steps, both jugs contains a multiple of 3 gallons.''  In fact,
this approach goes through.  But we're going to use some number theory
to knock off all these water jug problems.  For example, what if we
want to get 3 gallons using a 17-gallon jug and a 19-gallon jug?  Or 1
gallon with 777 and 1001-gallon jugs?

\subsection{A General Theorem}

Suppose that we have jugs with capacities $a$ and $b$.  Let's carry
out a few arbitrary operations and see what happens.  The state of the
system at each step is described below with a pair of numbers $(x,
y)$, where $x$ is the amount of water in the jug with capacity $a$ and
$y$ is the amount in the jug with capacity $b$.
%
\begin{align*}
(0,0)
& \rightarrow (a,0) & \text{fill first jug} \\
& \rightarrow (a-b,b) & \text{fill second jug from first} \\
& \rightarrow (a-b, 0) & \text{empty second jug} \\
& \rightarrow (a-2b, b) & \text{fill second jug from first} \\
& \rightarrow (a-2b, 0) & \text{empty second jug} \\
& \rightarrow (0, a-2b) & \text{empty first jug into second} \\
& \rightarrow (a, a-2b) & \text{fill first jug} \\
& \rightarrow (2a-3b, b) & \text{fill second jug from first}
\end{align*}
%
Of course, we're making some assumptions about the relative capacities
of the two jugs here.  But another point leaps out: at every step,
the amount of water in each jug is of the form
%
\[
s \cdot a + t \cdot b
\]
%
for some integers $s$ and $t$.  An expression of this form is called a
\term{linear combination} of $a$ and $b$.  Furthermore, at least one
of the jugs is empty or full at all times.  This sounds like an
assertion that we might be able to prove by induction!

\begin{lemma}
\label{lem:waterjugs}
Suppose that we have water jugs with capacities $a$ and $b$.  Then the
amount of water in each jug is always a linear combination of $a$
and $b$ and at least one jug is either empty or full.
\end{lemma}

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that after $n$ steps,
the amount of water in each jug is a linear combination of $a$ and $b$
and at least one jug is either empty or full.  For the base case,
$P(0)$ is true, because both jugs are empty, and $0 \cdot a + 0 \cdot
b = 0$.  Now we assume that $P(n)$ is true and prove the claim for
$P(n+1)$.  There are two cases:

\begin{itemize}

\item If we fill a jug from the fountain or empty a jug into the
fountain, then that jug is empty or full.  The amount in the other jug
remains a linear combination of $a$ and $b$.  So $P(n+1)$ holds.

\item Otherwise, we pour water from one jug to another until one is
empty or the other is full.  By the assumption $P(n)$, the amount in
each jug is a linear combination of $a$ and $b$ before we begin
pouring:
%
\begin{align*}
j_1 & = s_1 \cdot a + t_1 \cdot b \\
j_2 & = s_2 \cdot a + t_2 \cdot b
\end{align*}
%
After pouring, one jug is either empty (contains 0 gallons) or full
(contains $a$ or $b$ gallons).  Thus, the other jug contains either
$j_1 + j_2$ gallons, $j_1 + j_2 - a$, or $j_1 + j_2 - b$ gallons, all
of which are linear combinations of $a$ and $b$.
\end{itemize}

Thus, $P(n+1)$ holds in both cases, and the claim follows by the
principle of induction.
\end{proof}

\begin{corollary}
Bruce dies.
\end{corollary}

\begin{proof}
Since Bruce has water jugs with capacities 3 and 6, the amount in each
jug is always of the form $3s + 6t$.  This is always a multiple of 3,
so he can not measure out 4 gallons.
\end{proof}

So Bruce is toast.  But Lemma~\ref{lem:waterjugs} isn't a very
satisfying answer to the general water jug problem.  Can we get 3
gallons with 17 and 19 gallon jugs or not?  Part of the difficulty is
that linear combinations are not so easy to reason about.  (Is 3 a
linear combination of 17 and 19?)  Fortunately, linear combinations
are closely related to a more familiar concept.

\subsection{The Greatest Common Divisor}
\label{sec: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$.

Probably some junior high math teacher made you compute greatest
common divisors for no apparent reason until you were blue in the
face.  But, amazingly, the greatest common divisor actually turns out
to be quite useful for reasoning about the integers.  Specifically,
the quantity $\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
often easier to work with in proofs.

\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.

\begin{proof}
Let $m$ be the smallest positive linear combination of $a$ and $b$.
We'll prove that $m = \gcd(a, b)$ by showing both $\gcd(a, b) \leq m$
and $m \leq \gcd(a, b)$.

First, we show that $\gcd(a, b) \leq m$.  By the definition of common
divisor, $\gcd(a, b) \mid a$ and $\gcd(a, b) \mid b$.  Therefore, for
every pair of integers $s$ and $t$:
%
\[
\gcd(a, b) \mid s a + t b
\]
%
Thus, in particular, $\gcd(a, b)$ divides $m$, and so $\gcd(a, b) \leq
m$.

Now we show that $m \leq \gcd(a, b)$.  We do this by showing that $m
\mid a$.  A symmetric argument shows that $m \mid b$, which means that
$m$ is a common divisor of $a$ and $b$.  Thus, $m$ must be less than
or equal to the \textit{greatest} common divisor of $a$ and $b$.

All that remains is to show that $m \mid a$.  By the division
algorithm, there exists a quotient $q$ and remainder $r$ such that:
%
\[
a = q \cdot m + r \hspace{1in} \text{(where $0 \leq r < m$)}
\]
%
Now $m = s a + t b$ for some integers $s$ and $t$.  Subtituting in for
$m$ and rearranging terms gives:
%
\begin{align*}
a & = q \cdot (s a + t b) + r \\
r & = (1 - qs) a + (-qt) b
\end{align*}
%
We've just expressed $r$ is as a linear combination of $a$ and $b$.
However, $m$ is the \textit{smallest} positive linear combination and
$0 \leq r < m$.  The only possibility is that the remainder $r$ is not
positive; that is, $r = 0$.  This implies $m \mid a$.
\end{proof}

\iffalse
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:
%
\begin{align*}
r & = a - q \cdot m \\
  & = a - q \cdot (sa + tb) \\
  & = (1 - qs) \cdot a + (-qt) \cdot b
\end{align*}
%
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$.  This implies that
$\gcd(a, b) \leq m$.  By definition, the common divisor $m$ can not be
strictly greater than the \textit{greatest} common divisor.
Therefore, $m$ must be equal to the greatest common divisor of $a$ and
$b$.
\fi

The proof notes that every linear combination of $a$ and $b$ is a
multiple of $\gcd(a, b)$.  In the reverse direction, since $\gcd(a,
b)$ is a linear combination of $a$ and $b$, every multiple of $\gcd(a,
b)$ is as well.  This establishes a corollary:

\begin{corollary}
\label{cor:lin-comb}
Every linear combination of $a$ and $b$ is a multiple of $\gcd(a, b)$
and vice versa.
\end{corollary}

Now we can restate the water jugs lemma in terms of the greatest
common divisor:

\begin{corollary}
\label{cor:waterjugs}
Suppose that we have water jugs with capacities $a$ and $b$.  Then the
amount of water in each jug is always a multiple of $\gcd(a, b)$ and
at least one jug is either empty or full.
\end{corollary}

Of course, now it would help to know a thing or two about the greatest
common divisor.

\subsection{Properties of the Greatest Common Divisor}

prove some properties
of the greatest common divisor.

\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$.

\item $\gcd(a, b) = \gcd(a \rem b, b)$.

\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:
%
\begin{align*}
s a + t b & = 1 \\
u a + v c & = 1
\end{align*}

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 Theorem~\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$.  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}

Part (5) of this lemma is useful for quickly computing the greatest
common divisor of two numbers.  For example, we could compute the
greatest common divisor of 1001 and 777 like this:
%
\begin{align*}
\gcd(1001, 777)
  & = \gcd(\underbrace{1001 \rem 777}_{= 224}, 777) \\
  & = \gcd(\underbrace{777 \rem 224}_{= 105}, 224) \\
  & = \gcd(\underbrace{224 \rem 105}_{= 14}, 105) \\
  & = \gcd(\underbrace{105 \rem 14}_{= 7}, 14) \\
  & = \gcd(14, 7) \\
  & = 7
\end{align*}
%
(This is called \term{Euclid's algorithm}.)  This calculation,
together with Corollary~\ref{cor:waterjugs}, implies that there is no
way to measure out 1 gallon of water using jugs with capacities 777
and 1001; we can only obtains multiples of 7 gallons.  On the other
hand, we might be able to get 3 gallons using jugs with capacities 17
and 19, since $\gcd(17, 19) = 1$ and 3 is a multiple of 1.  We leave
the question of whether or not this is really possible to you!

\section{The Fundamental Theorem of Arithemtic}

We're now almost ready to prove something that you probably already
know.

\begin{theorem}[Fundamental Theorem of Arithmetic]
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}

Notice that the theorem would be false if 1 were considered a prime;
for example, $15$ could be written as $3 \cdot 5$ or $1 \cdot 3 \cdot
5$ or $1^2 \cdot 3 \cdot 5$.  Also, we're relying on a standard
convention: 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$.

There is a certain wonder in the Fundamental Theorem, 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 we know that every natural number can be built up
from primes in {\em exactly one way}.  These quirky numbers are the
building blocks for the integers.  The Fundamental Theorem is not hard
to prove, but we'll need a fact that we just assumed earlier.

\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}

A routine induction argument extends this statement to the fact we
assumed last time:

\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're ready to prove the Fundamental Theorem of Arithemtic.

\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 well-ordering 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 well-ordering principle, there is
a smallest integer with this property.  Call this integer $n$, and let
%
\begin{align*}
n & = p_1 \cdot p_2 \cdots p_j \\
  & = q_1 \cdot q_2 \cdots q_k
\end{align*}
%
be two of the (possibly many) ways to write $n$ 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 also be written as a product of primes in two
distinct ways.  But this contradicts the definition of $n$ as the
smallest such positive integer.
\end{proof}

\floatingtextbox{
\centerline{\textbf{{\Large The Riemann Hypothesis}}}
\bigskip

Turing's last project before he disappeared from public view in 1939
involved the construction of an elaborate mechanical device to test a
mathematical conjecture called the Riemann Hypothesis.  This
conjecture first appeared in a sketchy paper by Berhard Riemann in
1859 and is now the most famous unsolved problem in mathematics.  The
formula for the sum of an infinite geometric series says:
\[
1 + x + x^2 + x^3 + \ldots = \frac{1}{1-x}
\]
Substituting $x = 2s$, $x = 3s$, $x = 5s$, and so on for each prime
number gives a sequence of equations:
%
\begin{align*}
1 + \frac{1}{2^s} + \frac{1}{2^{2s}} + \frac{1}{2^{3s}} + \ldots
    & = \frac{1}{1 - 1 / 2^s} \\
1 + \frac{1}{3^s} + \frac{1}{3^{2s}} + \frac{1}{3^{3s}} + \ldots
    & = \frac{1}{1 - 1 / 3^s} \\
1 + \frac{1}{5^s} + \frac{1}{5^{2s}} + \frac{1}{5^{3s}} + \ldots
    & = \frac{1}{1 - 1 / 5^s} \\
    & \text{etc.}
\end{align*}
%
Multiplying together all the left sides and all the right sides gives:
%
\[
\sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \in \text{primes}} \left(\frac{1}{1 - 1 / p^s}\right)
\]
%
The sum on the left is obtained by multiplying out all the infinite
series and applying the Fundamental Theorem of Arithmetic.  For
example, the term $1 / 300^s$ in the sum is obtained by multiplying $1
/ 2^{2s}$ from the first equation by $1 / 3^s$ in the second and $1 /
5^{2s}$ in the third.  Riemann noted that every prime appears in the
expression on the right.  So he proposed to learn about the primes by
studying the equivalent, but simpler expression on the left.  In
particular, he regarded $s$ as a complex number and the left side as a
function, $\zeta(s)$.  Riemann found that the distribution of primes
is related to values of $s$ for which $\zeta(s) = 0$, which led to his
famous conjecture:

\begin{theorem*}
Every nontrivial zero of the zeta function $\zeta(s)$ lies on the line
$s = 1/2 + c i$ in the complex plane.
\end{theorem*}

A proof of the Riemann Hypothesis would immediately imply, among other
things, a strong form of the Prime Number Theorem--- and earn the
prover a \$1 million prize!}


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

\section{Arithmetic with an Arbitrary Modulus}

Turing's code did not work as he hoped.  However, his essential
idea--- using number theory as the basis for cryptography--- succeeded
spectacularly in the decades after his death.

In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed a
highly secure cryptosystem (called \textbf{RSA}) based on number
theory.  Despite decades of attack, no significant weakness has been
found.  Moreover, RSA has a major advantage over traditional codes:
the sender and receiver of an encrypted message need not meet
beforehand to agree on a secret key.  Rather, the receiver has both a
\term{secret key}, which she guards closely, and a \term{public key},
which she distributes as widely as possible.  To send her a message,
one encrypts using her widely-distributed public key.  Then she
decrypts the message using her closely-held private key.  The use of
such a \term{public key cryptography} system allows you and Amazon,
for example, to engage in a secure transaction without meeting up
beforehand in a dark alley to exchange a key.

Interestingly, RSA does not operate modulo a prime, as Turing's scheme
may have, but rather modulo the product of \textit{two} large primes.
Thus, we'll need to know a bit about how arithmetic works modulo a
composite number in order to understand RSA.  Arithmetic modulo an
arbitrary positive integer is really 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}

This is not a terribly difficult theorem, but we'll hold off on the
proof for a few weeks.  In the meanwhile, here's an example of how we
might use Theorem~\ref{th:phi} to compute $\phi(300)$:
%
\begin{align*}
\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
\end{align*}
%
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}

RSA essentially relies on Euler's Theorem, a generalization of
Fermat's Theorem to an arbitrary modulus.  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 that $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}.  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*}
\lefteqn{k_1 \cdot k_2 \cdot k_3 \cdots k_r} \hspace{0.25in} \\
& \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 first two expressions are actually equal by
Lemma~\ref{lem:permutes-arb}; therefore, they are certainly congruent
modulo $n$.  The second step uses a property of mod and rem that we
proved earlier.  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 theorem: 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.
You'll see this--- and RSA--- in recitation.
\end{document}
