Unique factorization

In mathematics, the unique factorization theorem, also known as the fundamental theorem of arithmetic states that every positive whole number can be expressed as a product of prime numbers in essentially only one way. It reveals that one may consider the prime numbers as "atoms" from which all other whole numbers can be assembled through multiplication. Unique factorization is the foundation for most of the structure of whole numbers as described by elementary number theory. The formulation of many results would either be nonsensical, or at least more complicated, if unique factorization did not hold. For instance, the assumption that many electronic financial transactions are secure is based on the belief that the product of two very large prime numbers is difficult to factor. If several other prime factorizations were possible, perhaps some having small prime factors, finding a factorization might be much easier and such security methods would be ineffective.

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.