## Proof of the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states the following:

Every integer greater than 1 can be represented uniquely as the product of prime numbers.

Another way to put this is that every integer has a unique factorization.  For example, 60 factors into $2^2 \cdot 3 \cdot 5$, and there is only one way to do this factorization using prime numbers.  (Rearranging the order of the numbers doesn’t count as a different factorization.)

In this post we’ll prove the Fundamental Theorem of Arithmetic.  There are two parts: (1) Proving that every integer greater than 1 can be represented as the product of prime numbers (i.e., existence), and (2) Proving that this representation is unique (i.e., uniqueness).

Reminder: A prime number is a positive integer that is divisible by exactly two positive integers: itself and 1.

First, Existence.  Suppose, by way of contradiction, that there is some positive integer that cannot be represented as the product of primes.  Then there is a smallest such number N.  If N cannot be represented as a product of primes then N cannot itself be prime.  Thus there exist two positive integers a and b, with $1 < a \leq b < N$, such that $N = ab$.  Since a and b are both positive integers smaller than N they must each be the product of primes, where $a = p_1 p_2 \cdots p_m$, $b = q_1 q_2 \cdots q_n$, and $p_i$ and $q_j$ are primes for each i and j.  But then $N = p_1 p_2 \cdots p_m q_1 q_2 \cdots q_n$ and thus also is the product of primes.

Second, Uniqueness.  For this we need a lemma that isn’t hard to prove:

Lemma: If a prime p divides an integer $ab$, then divides a or p divides b.

Now, let N be a positive integer.  Suppose there exist two ways to represent N as the product of primes,

$N = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$,

where $p_i$ and $q_j$ are primes for each i and j.  Assume, without loss of generality, that these representations are ordered, so that $p_i \leq p_{i+1}$ and $q_i \leq q_{i+1}$ for all i for which these inequalities are defined.

Suppose $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_m$ and $n > m$.  Then  $N = p_1 p_2 \cdots p_m < q_1 q_2 \cdots q_n = N$, a contradiction.  Similarly, if  $p_1 p_2 \cdots p_n = q_1 q_2 \cdots q_n$ and $m > n$, we have a contradiction.

Now, let i be the first index for which $p_i \neq q_i$.  If i exists then $i \leq \min\{m,n\}$, by the argument in the previous paragraph.  We can assume, without loss of generality, that $p_i < q_i$.  We have that $p_1 p_2 \cdots p_{i-1} = q_1 q_2 \cdots q_{i-1}$.  Since $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$, we also have $p_i \cdots p_m = q_i \cdots q_n$.  By the lemma, $p_i$ divides $q_j$ for some j, $i \leq j \leq n$.  But each of the $q_j$ values is prime and so is only divisible by 1 and itself.  Since $p_i < q_i \leq q_j$, we have a contradiction.

Thus there is no index i for which $p_i \neq q_i$.  Our argument two paragraphs above shows that we can’t have this and $m < n$ or $m > n$.  Thus $m = n$, and so the two representations, $p_1 p_2 \cdots p_m$ and $q_1 q_2 \cdots q_n$, are identical.