\section{The Fundamental Theorem of Arithmetic}

We now have almost enough tools 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 \cdots \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 you were in a 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, \dots
\]
%
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 couple of preliminary facts.

\floatingtextbox{
\textboxtitle{The Prime Number Theorem}

Let $\pi(x)$ denote the number of primes less than or equal to $x$.
For example, $\pi(10) = 4$ because 2, 3, 5, and 7 are the primes less
than or equal to 10.  Primes are very irregularly distributed, so the
growth of $\pi$ is similarly erratic.  However, the Prime Number
Theorem gives an approximate answer:
%
\[
\lim_{x\to\infty} \frac{\pi(x)}{x/\ln x} = 1
\]
%
Thus, primes gradually taper off.  As a rule of thumb, about 1 integer
out of every $\ln x$ in the vicinity of $x$ is a prime.

% The accent on Vallee screwed up the hyphens in the entire pdf file!!!

The Prime Number Theorem was conjectured by Legendre in 1798 and
proved a century later by de la Vallee Poussin and Hadamard in
1896.  However, after his death, a notebook of Gauss was found to
contain the same conjecture, which he apparently made in 1791 at age
15.  (You sort of have to feel sorry for all the otherwise ``great''
mathematicans who had the misfortune of being contemporaries of
Gauss.)

In late 2004 a billboard appeared in various locations around the
country:
%
{\Large
\[
\left\{
\begin{array}{c}
\text{first 10-digit prime found} \\
\text{in consecutive digits of $e$}
\end{array}
\right\}\textbf{. com}
\]
}
%
Substituting the correct number for the expression in curly-braces
produced the URL for a Google employment page.  The idea was that
Google was interested in hiring the sort of people that could and
would solve such a problem.

How hard is this problem?  Would you have to look through thousands or
millions or billions of digits of $e$ to find a 10-digit prime?  The
rule of thumb derived from the Prime Number Theorem says that among
10-digit numbers, about 1 in
%
\[
\ln 10^{10} \approx 23
\]
%
is prime.  This suggests that the problem isn't really so hard!  Sure
enough, the first 10-digit prime in consecutive digits of $e$ appears
quite early:
%
\begin{align*}
e = & 2.718281828459045235360287471352662497757247093699959574966 \\
    & 96762772407663035354759457138217852516642\textcolor{blue}{\mathbf{7427466391}}9320030 \\
    & 599218174135966290435729003342952605956307381323286279434\dots
\end{align*}
}

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

\begin{proof}
The greatest common divisor of $a$ and $p$ must be either 1 or $p$,
since these are the only positive 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 \divides b$ by part (4) of Lemma~\ref{lem:gcd}.
\end{proof}

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

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

Now we're ready to prove the Fundamental Theorem of Arithmetic.

\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 \cdots \leq p_j)
\end{eqnarray*}
\end{theorem}

\begin{proof}
We proved earlier using the well-ordering principle that every positive
integer can be expressed as a product of primes.  So we just have to prove
this expression is unique.  We will use the well-ordering principle to
prove this too.

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

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 \divides n$ and so $p_1 \divides 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}

\endinput