Unique factorization

also known as the "Fundamental Theorem of Arithmetic"

Proof

Every integer $N>1$ can be written in a unique way as a product of prime factors, up to reordering. To see why this is true, assume that $N$ can be written as a product of prime factors in two ways

$N=p_{1}p_{2}\cdots p_{m}=q_{1}q_{2}\cdots q_{n}$

We may now use a technique known as mathematical induction to show that the two prime decompositions are really the same.

Consider the prime factor $p_{1}$. We know that

$p_{1}\mid q_{1}q_{2}\cdots q_{n}.$

Using the second definition of prime numbers, it follows that $p_{1}$ divides one of the q-factors, say $q_{i}$. Using the first definition, $p_{1}$ is in fact equal to $q_{i}$

Now, if we set $N_{1}=N/p_{1}$, we may write

$N_{1}=p_{2}p_{3}\cdots p_{m}$

and

$N_{1}=q_{1}q_{2}\cdots q_{i-1}q_{i+1}\cdots q_{n}$

In other words, $N_{1}$ is the product of all the $q$'s except $q_{i}$.

Continuing in this way, we obtain a sequence of numbers $N=N_{0}>N_{1}>N_{2}>\cdots >N_{n}=1$ where each $N_{\alpha }$ is obtained by dividing $N_{\alpha -1}$ by a prime factor. In particular, we see that $m=n$ and that there is some permutation ("rearrangement") σ of the indices $1,2,\ldots n$ such that $p_{i}=q_{\sigma (i)}$. Said differently, the two factorizations of N must be the same up to a possible rearrangement of terms.