The Unique Prime Factorization Theorem

We will now look at a very important theorem which says that any integer $n > 1$ can be written uniquely as a product of primes $p_1, p_2, ..., p_k$:

(1)

\begin{align} \quad n = p_1p_2...p_k \end{align}

Theorem 1 (The Unique Prime Factorization Theorem): If $n \in \mathbb{Z}$ and $n > 1$ then $n$ can be written as a product of primes uniquely apart from the ordering of the primes in the product.

If $n \in \mathbb{Z}$ and $n < -1$ then $n$ can also be written as a product of primes multiplied by $-1$.

• Proof: We first show that if $n \in \mathbb{Z}$ and $n > 1$ then $n$ can be written as a product of primes. We saw on the Prime and Composite Numbers page that if every $n \in \mathbb{Z}$ and $n > 1$ is divisible by a prime number. Let $p_1$ be this prime number. Then for some $n_2 \in \{1, 2, ... \}$ we have that:

(2)

\begin{align} \quad n = p_1n_1 \end{align}

• If $n_1 = 1$ then $n = p_1$ and we're done. If $n_1$ is prime then let $p_2 = n_1$ and so $n = p_1p_2$ and we're done. If $n_1$ is composite then $n_1 > 1$ and so once again, $n_1$ is divisible by a prime, say $p_2$, where $n_1 = p_2n_2$. Therefore:

(3)

\begin{align} \quad n = p_1p_2n_2 \end{align}

• If $n_2 = 1$ then $n = p_1p_2$ and we're done. If $n_2$ is prime then let $p_3 = n_2$ and so $n = p_1p_2p_3$ and we're done. If $n_2$ is composite then $n_2 > 1$ and again, $n_2$ is divisible by a prime, say $p_3$, where $n_2 = p_3n_3$.

• Note that $n_1 > n_2 > ... \geq 1$. This sequence of integers is bounded below by $1$ and hence must terminate at some point. Therefore, for some $k \in \{ 1, 2, ... \}$ we have that:

(4)

\begin{align} \quad n = p_1p_2...p_k \end{align}

• Therefore $n$ can be written as a product of primes. We will now show that this factorization is unique. Suppose that $n = p_1p_2...p_k$ and $n = q_1q_2...q_r$ so that then:

(5)

\begin{align} \quad p_1p_2...p_k = q_1q_2...q_r \end{align}

• Since $p_1 \mid n$ we must have $p_1 \mid q_1q_2...q_r$. Therefore $p_1 = q_i$ for some $i \in \{1, 2, ... r \}$. Without loss of generality, assume that $p_1 = q_1$. Therefore:

(6)

\begin{align} \quad p_2p_3...p_k = q_2q_3...q_r \end{align}

• Since $p_2 \mid n$ we must also have $p_2 \mid q_2q_3...q_r$. Therefore $p_2 = q_i$ for some $i \in \{2, 3, ... r \}$. Without loss of generality, assume that $p_2 = q_2$. Therefore:

(7)

\begin{align} \quad p_3p_4...p_k = q_3q_4...q_r \end{align}

• We continue in this process. We note that we won't run out of primes $p$ before primes $q$, otherwise this implies a prime $q$ is equal to $1$. Furthermore, we won't run out of primes $q$ before primes $p$, otherwise this implies a prime $p$ is equal to $1$. Therefore $k =r$ and we eventually get:

(8)

\begin{align} \quad p_k = q_r \end{align}

• Therefore the prime factorization $n = p_1p_2...p_k$ is unique. $\blacksquare$