The *Fundamental Theorem of Arithmetic* states that *every
natural number greater than 1 can be factored into
prime numbers in exactly one way* (the order of the
factors doesn't matter). For example, the only way that 4 can be
factored into primes is as 2 × 2. This is an important result
in number theory.

Start by assuming the opposite of what we want to prove; i.e., assume
that there is at least one natural number with two distinct factors.
The set of such numbers must contain a smallest element; call it
`m`. Since `m` is the smallest natural number with
this property, every natural number smaller than `m` has
the unique factorization property, while `m` itself has at
least two different factorizations. We can express these factorizations as:

Where all of the `p`'s and `q`'s represent some prime
number or another.

To start the proof, we'll show that each of the `p`'s must be
entirely different from each of the `q`'s. For example, if the
prime 5 appears in the first batch, it can't appear in the second batch.
If the two batches did have a common prime, we could arrange the notation
so that the common prime would be the first one in the batch, thus
`p`_{1} = `q`_{1}. In this case, we
would find that ^{m}/_{p1}
has two different prime factorizations, namely
`p`_{2}`p`_{3}...`p`_{r} and `q`_{2}`q`_{3}...`q`_{s}. However, this is impossible, because `m` was the
smallest number with more than one factoring, and ^{m}/_{p1} is smaller than `m`.

We have shown that all of the `p`'s are different from all of
the `q`'s. In particular, we know that `p`_{1}
is not equal to `q`_{1}. Assume that `p`_{1}
is the smaller of the two. We can assume this because the notation is
symmetric between the two batches of primes. If this weren't the case
we could just interchange the `p`'s and `q`'s and get
the same result anyway.

Now look at:

Obviously, `n` is smaller than `m`. In the first form, the factor (`q`_{1} - `p`_{1}) may or may not be a prime, but `p`_{1} will not be one of these factors.
If `p`_{1} were a factor of (`q`_{1} - `p`_{1}), then `p`_{1} would be a divisor of (`q`_{1} - `p`_{1}).
However, look at `m` - `p`_{1}`q`_{2}`q`_{3}...`q`_{s}. Both `m` and the other part both contain `p`_{1} as a factor, so
`p`_{1} is a factor of the entire expression.
Therefore, `n` has two different prime factorizations.
However, since `n` is smaller than `m`, this contradicts
our deduction that `m` was the smallest number with more than one
prime factorization. Therefore, our assumption must be false, and all
natural numbers have only one prime factorization.