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

\renewcommand{\coursecopyrightnames}{Eric~Lehman}
%\renewcommand{\coursecopyrightyear}{2003}

\newcommand{\rem}{\text{ rem }}

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

{\em 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 $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.  (Now 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 known to be {\em almost} true!

\item[Odd Perfect Numbers] A number is {\em 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
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 {\em number field seive}, which runs in time:

\[
O(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}

\noindent 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 all have
underpinnings in number theory.

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

\section{Review}

Let's begin with a review of some definitions and facts.  All
variables in this lecture represent integers.

\subsection{Divisibility}

We say that {\em $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.  A number $p > 1$ with no positive divisors
other than 1 and itself is called a {\em prime}.  Every other number
greater than 1 is called {\em composite}.  The number 1 is neither
prime nor composite.

\subsection{The Division Algorithm}

You learned the following fact in elementary school: if you divide $b$
by $a$, then you get a quotient $q$ and remainder $r$.

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

For some reason, this theorem is usually called the {\em division
algorithm}.  It can be proved from the least-number principle.  As an
example, suppose that $a = 10$ and $b = 2716$.  Then the quotient is
$q = 271$ and the remainder $r = 6$, since $2716 = 271 \cdot 10 + 6$.

The remainder $r$ in the theorem is often denoted $b \rem a$.  For
example, $2716 \rem 10 = 6$.  This notation is used extensively in the
pages ahead.

\subsection{The Congruence Relation}

We say that {\em $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} \quad 7 \mid (29 - 15)
\]

\subsubsection{Other Perspectives on Congruence}

Let's look more closely at the notion of congruence, because it is
pretty important.  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}
\]

\noindent Two numbers are congruent mod 3 if and only if they are in
the same equivalence class.  For example, $-5 \equiv 4 \pmod{3}$
because $-5$ and 4 are in the same equivalence class.  However, $0
\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.  Let's 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}
\]

\noindent 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.  Or, in mathspeak:

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

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

\subsection{Proving Stuff Involving rem and mod}

Many familiar rules remain valid when one works modulo an integer $n
\geq 1$.  For example, the distributive law still holds:

\begin{eqnarray*}
a(b + c) \equiv ab + ac \pmod{n}
\end{eqnarray*}

Whenever you are unsure about a step involving congruences or
remainders, go back to the definition.  For example, the distributive
law is equivalent to the assertion that $n \mid (a(b + c) - (ab +
ac))$.  This is true, because the right side is zero, and every
integer divides zero.

To get more practice with rem and mod, let's establish some simple
facts that we'll need later anyway.

\begin{claim}
\label{cl:misc}
The following assertions hold for $n \geq 1$ and all integer values of
the other variables:

\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}$
\end{enumerate}
\end{claim}

The first part of this claim is particularly important.  It says that
if we replace any term $a$ in a product with a congruent term $b$,
then the new product is congruent to the old one.  We'll use this fact
a lot!  One important caution, though: the converse of part 1 does not
always hold; that is, $ac \equiv bc \pmod{n}$ does not imply that $a
\equiv b \pmod{n}$.  For example, $2 \cdot 3 \equiv 4 \cdot 3
\pmod{6}$, but $2 \not\equiv 4 \pmod{6}$.


\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)$.  This implies that $n \mid (a - b)c$ and
thus $n \mid (ac - bc)$.  This is equivalent to $ac \equiv bc
\pmod{n}$.

\item The remainder $a \rem n$ is equal to $a - qn$ for some integer
$q$.  However, for every integer $q$, $n \mid ((a - qn) - a)$, so $(a
\rem n) \equiv a \pmod{n}$.

\item We can transform the right side to the left side by applying
parts 1 and 2 for each variable $a_i$ in turn.  Thus, the assertion
follows by a routine induction argument.

\end{enumerate}
\end{proof}

\subsection{A Little Lemma}

The following lemma enabled us to prove the Fundamental Theorem of
Arithmetic.

\begin{lemma}
\label{lem:little}
Let $p$ be a prime.  If $p \mid ab$, then $p \mid a$ or $p \mid b$.
\end{lemma}

Using induction, we obtained a generalization:

\begin{lemma}
\label{lem:little-ind}
Let $p$ be a prime.  If $p \mid a_1 a_2 \ldots a_n$, then $p \mid a_i$
for some $i \in \{1, 2, \ldots, n\}$.
\end{lemma}

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

\section{Life Modulo a Prime}

In these notes, we'll focus on how arithmetic works modulo a prime
number.  One reason for doing so is the odd fact that {\em the
integers modulo a prime behave a lot like the real numbers}.  This is
hard to believe!  After all, the real numbers are infinite and
continuous, whereas there are only $p$ really ``different'' integers
modulo a prime $p$.  The path to this remarkable conclusion begins
with an innocuous lemma:

\begin{lemma}
Suppose $p$ is a prime and $k$ is not a multiple of $p$.  Then
for distinct $m_1, m_2 \in \{0, 1, \ldots, p-1 \}$:

\begin{eqnarray*}
m_1 k \not\equiv m_2 k \pmod{p}
\end{eqnarray*}
\end{lemma}

\begin{proof}
The proof is by contradiction.  Suppose $m_1 k \equiv m_2 k \pmod{p}$.
Then $p \mid (m_1 k - m_2 k)$, by the definition of congruence.
Rewriting the right side gives $p \mid k (m_1 - m_2)$.  By
Lemma~\ref{lem:little}, either $p \mid k$ or $p \mid (m_1 - m_2)$.
The former is ruled out by assumption, and the latter is impossible
because $m_1 - m_2$ lies strictly between $-1 \cdot p$ and $1 \cdot p$
and is not equal to $0 \cdot p = 0$.  This is a contradiction.
\end{proof}

Note that we could rewrite the assertion $m_1 k \not\equiv m_2 k
\pmod{p}$ in the lemma as $m_1 k \rem p \neq m_2 k \rem p$.  This is
the form we'll need in a moment.

\begin{corollary}
\label{cor:permutes}
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
(p-1) \cdot k \rem p
\]

is a permutation of:

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

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

\begin{proof}
The first sequence contains $p$ numbers that are distinct (by the
preceding lemma) and in the range $0$ to $p - 1$ (by the definition of
rem).  Therefore, the first sequence must contain {\em 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.

Every nonzero real number $r$ has a {\em multiplicative inverse}
$r^{-1}$ such that $r \cdot r^{-1} = 1$.  For example, the
multiplicative inverse of $-3$ is $-\frac{1}{3}$.  Division can
actually defined in terms of multiplication and multiplicative
inverses; $a / b$ is defined to be $a \cdot b^{-1}$.  On the other
hand, most integers do not have multiplicative inverses in the
integers.  Therefore, the integers are not closed under division.
This is a crucial difference between the real numbers and the
integers.

However, the corollary below shows that the integers {\em do} have
essentially unique multiplicative inverses when we work modulo a
prime.  This means that we can actually define division over the
integers, provided we work modulo a prime!

\begin{corollary}
\label{cor:inverses}
Suppose $p$ is a prime and $k$ is not a multiple of $p$.  Then there
exists a unique $k^{-1} \in \{1, 2, \ldots, p - 1\}$ such that $k^{-1}
\cdot k \equiv 1 \pmod{p}$.
\end{corollary}

\begin{proof}
The preceding corollary implies that there exists a unique $m \in \{
1, 2, \ldots, p-1 \}$ such that $m k \rem{p} = 1$ or, equivalently,
$mk \equiv 1 \pmod{p}$.  Let $k^{-1}$ be this value $m$.
\end{proof}

\section{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 much more useful.

\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
Corollary~\ref{cor:permutes}; therefore, they are also congruent.  The
second step uses part 3 of Claim~\ref{cl:misc}.  In the third step, we
rearrange terms in the product.

Now $p$ can not divide $(p-1)!$, because $p$ is a prime and does not
divide any of 1, 2, \ldots, $(p-1)$.  Therefore, $(p-1)!$ has a
multiplicative inverse, by Corollary~\ref{cor:inverses}.  Multiplying
the first expression and the last by this inverse of $(p-1)!$ 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} \rem p$ must be the multiplicative inverse of $k$.
Now 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
are 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*}

More generally, if we were working modulo a prime $p$, then finding a
multiplicative inverse by trying every value between 1 and $p$ would
require $O(p)$ operations.  However, the approach above requires only
$O(\log p)$ operations.

\end{document}
