\section{Divisibility}

We'll be examining integer properties in these notes, so we'll adopt the
convention that variables range over integers.

The nature of number theory emerges as soon as we consider the
\term{divides} relation
\[
a \term{ divides } b \qiff ak = b \text{ for some } k.
\]
The notation, $a \divides b$, is an abbreviation for ``$a$ divides $b$.''
If $a \divides b$, then we also say that $b$ is a \term{multiple} of $a$.
As we've seen, a consequence of this definition is that every number
divides zero.

This seems simple enough, but let's play with this definition.  The
Pythagoreans, an ancient sect of mathematical mystics, said that a
number is \term{perfect} if it equals the sum of its positive
integral divisors, excluding itself.  For example, $6 = 1 + 2 + 3$
and $28 = 1 + 2 + 4 + 7 + 14$ are perfect numbers.  On the other hand,
10 is not perfect because $1 + 2 + 5 = 8$, and 12 is not perfect
because $1 + 2 + 3 + 4 + 6 = 16$.  Euclid characterized all the
\textit{even} perfect numbers around 300 BC.  But is there an
\textit{odd} perfect number?  More than two thousand years later, we
still don't know!  All numbers up to about $10^{300}$ have been ruled
out, but no one has proved that there isn't an odd perfect number
waiting just over the horizon.

So a half-page into number theory, we've strayed past the outer limits of
human knowledge!  This is pretty typical; number theory is full of
questions that are easy to pose, but incredibly difficult to answer.
Interestingly, computer scientists have found ways to turn these
difficulties to their advantage.  Every time you buy a book from Amazon,
check your grades on WebSIS, or use a PayPal account, you are relying on
number theoretic algorithms.

\textit{DON'T PANIC}--- we're going to stick to some relatively benign
parts of number theory.  We won't put any of these super-hard unsolved
problems on exams!

\subsection{Facts About Divisibility}

The lemma below states some basic facts about divisibility that are
\textit{not} difficult to prove:

\begin{lemma}
\label{lem:div}
The following statements about divisibility hold.
%
\begin{enumerate}
\item If $a \divides b$, then $a \divides bc$ for all $c$.
\item If $a \divides b$ and $b \divides c$, then $a \divides c$.
\item If $a \divides b$ and $a \divides c$, then $a \divides sb + tc$ for all $s$ and $t$.
\item For all $c \neq 0$, $a \divides b$ if and only if $ca \divides cb$.
\end{enumerate}
\end{lemma}

\begin{proof}
We'll prove only part 2.; the other proofs are similar.

Proof of 2.:  Since $a \divides b$, there exists an integer $k_1$ such
that $a k_1 = b$.  Since $b \divides 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 \divides c$.

\iffalse
Proof of (4): We must show that $a \divides b$ implies $ca \divides cb$ and
vice-versa.
%
\begin{itemize}
\item First, suppose $a \divides b$.  This means $a k = b$ for some $k$.
Multiplying both sides by $c$ gives $c a k = c b$ for some $k$.  This
implies $ca \divides cb$.
\item Now, suppose $ca \divides cb$.  Then $c a k = c b$ for some $k$.
We can divide both sides by $c$ since $c$ is nonzero, so $a k = b$ for
some $k$.  This means $a \divides b$.
\end{itemize}
\fi
\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}.  For example, 2, 3, 5, 7, 11, and 13 are all prime,
but 4, 6, 8, and 9 are composite.  The number 1 is considered neither
prime nor composite.  This is just a matter of definition, but
reflects the fact that 1 does not behave like a prime in many
contexts, such as the Fundamental Theorem of Arithmetic, which we'll
come to shortly.

\floatingtextbox{

\textboxtitle{Famous Problems in Number Theory}

\begin{description}

\item[Fermat's Last Theorem] Do there exist positive integers $x$,
$y$, and $z$ such that
%
\[
x^n + y^n = z^n
\]
%
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.
write it down.  Wiles finally gave a proof of the theorem
in 1994, after seven
years of working in secrecy and isolation in his attic.
His proof did not fit in any margin.

\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[Primality Testing] Is there an efficient way to determine whether
$n$ is prime?  A naive search for factors of $n$ takes a number of steps
exponential in $\log n$, which is the size of $n$ in bits.  All known
procedures for prime checking blew up like this on various inputs.
Finally in 2002, an amazingly simple, new method was discovered by
Agrawal, Kayal, and Saxena, which showed that prime testing only required
a polynomial number of steps.  Their paper began with a quote from Gauss
emphasizing the importance and antiquity of the problem even in his
time--- two centuries ago.  So prime testing is definitely not in the
category of infeasible problems requiring an exponentially growing number
of steps in bad cases.

\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 sieve'', which runs in time
proportional to:
%
\[
e^{1.9(\ln n)^{1/3} (\ln\ln n)^{2/3}}
\]
%
This is infeasible when $n$ has 300 digits or more.
\end{description}
}

\subsection{When Divisibility Goes Bad}

As you learned in elementary school, if one number does \textit{not}
evenly divide another, then there is a ``remainder'' left over.  More
precisely, if you divide $n$ by $d$, then you get a quotient $q$ and a
remainder $r$:

\begin{theorem}[Division Theorem]
Let $n$ and $d$ be integers such that $d > 0$.  Then there exists a
unique pair of integers $q$ and $r$ such that $n = qd + r$ and $0 \leq
r < d$.\footnote{This theorem is often called the ``Division Algorithm,'' even
though it is not an algorithm in the modern sense.}
\end{theorem}

As an example, suppose that $n = 2716$ and $d = 10$.  Then the
quotient is $q = 271$ and the remainder is $r = 6$, since $2716 = 271
\cdot 10 + 6$.

The remainder $r$ in the Division Theorem is denoted $\rem{n}{d}$.  In
other words, $\rem{n}{d}$ is the remainder when $n$ is divided by $d$.
For example, $\rem{32}{5}$ is the remainder when 32 is divided by 5, which
is 2.  Similarly, $\rem{-11}{7} = 3$, since $-11 = (-2) \cdot 7 + 3$.
There is a remainder operator built into many programming languages.  For
example, the expression ``32 \% 5'' evaluates to 2 in Java, C, and C++.
However, all these languages treat negative numbers strangely.

We'll take this familiar Division Theorem for granted without proof, but 
there is an important feature that you should notice.  The theorem asserts 
that the quotient $q$ and remainder $r$ \textit{exist} and also that these
values are \textit{unique}.  Thus, the Division Theorem is one example
of an ``existence and uniqueness'' theorem; there are many others.
Not surprisingly, the proof of such a theorem always has two parts:
%
\begin{itemize}
\item A proof that something exists, such as the quotient $q$ and
remainder $r$.
\item A proof that nothing else fits the bill; that is, there is no
other quotient $q'$ and remainder $r'$.
\end{itemize}
%
%We'll prove a famous ``existence and uniqueness'' theorem in this way
%shortly.

\TBA{put in 'example' environment...}

\subsection{Die Hard}

We've previously looked at the Die Hard water jug problem with jugs of
sizes 3 and 5, and 3 and 9.  It would be nice if we could solve all these
silly water jug questions at once.  In particular, how can one form $g$
gallons using jugs with capacities $a$ and $b$?  Here's where number
theory comes in handy.

\subsubsection{Finding an Invariant Property}

Suppose that we have water jugs with capacities $a$ and $b$.  The state of
the system 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$.  Let's carry out sample operations and see
what happens, assuming the $b$-jug is big enough:
%
\begin{align*}
(0,0)
& \rightarrow (a,0) & \text{fill first jug} \\
& \rightarrow (0,a) & \text{pour first into second} \\
& \rightarrow (a, a) & \text{fill first jug} \\
& \rightarrow (2a-b, b) & \text{pour first into second (assuming $2a \geq b$)} \\
& \rightarrow (2a-b, 0) & \text{empty second jug} \\
& \rightarrow (0, 2a-b) & \text{pour first into second} \\
& \rightarrow (a, 2a-b) & \text{fill first} \\
& \rightarrow (3a-2b, b) & \text{pour first into second (assuming $3a \geq 2b$)}
\end{align*}
%
What leaps out is that at every step, the amount of water in each jug is
of the form
%
\begin{equation}\label{satb}
s \cdot a + t \cdot b
\end{equation}
%
for some integers $s$ and $t$.  An expression of the form~\eqref{satb} is
called an \term{integer linear combination} of $a$ and $b$, but in these
notes we'll just call it a \term{linear combination}, since we're only
talking integers.  So we're suggesting:
\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$.
\end{lemma}

Lemma~\ref{lem:waterjugs} is easy to prove by induction on the number of
pourings.

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

\noindent \textit{Base case.}  $P(0)$ is true, because both jugs are
initially empty, and $0 \cdot a + 0 \cdot b = 0$.

\noindent \textit{Inductive step.}  Now we must show that $P(n)$
implies $P(n+1)$ for $n \geq 0$.  So assume that after $n$ steps the
amount of water in each jug is a linear combination of $a$ and $b$.
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 our assumption, 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}
%
The claim follows by the principle of induction.
\end{proof}

This theorem has an important corollary, which we will also
prove in class.

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

\begin{proof}
In Die Hard 6, Bruce has water jugs with capacities 3 and 6 and must
form 4 gallons of water.  However, the amount in each jug is always of
the form $3s + 6t$ by Lemma~\ref{lem:waterjugs}.  This is always a
multiple of 3 by part (3) of Lemma~\ref{lem:div}, so he can not
measure out 4 gallons.
\end{proof}

But Lemma~\ref{lem:waterjugs} isn't very satisfying.  We've just managed
to recast a pretty understandable question about water jugs into a
complicated question about linear combinations.  This might not seem like
progress.  Fortunately, linear combinations are closely related to
something more familiar and that will help us solve the water jug problem.

\endinput