Unique Factorization

# Theorem 1: Any positive integer can be expressed as a product of primes. The set of primes which expresses this integer as a product is unique.

It turns out that all numbers can be expressed as a unique product of prime numbers. Note that we will consider a product of prime numbers as "not unique" if the only difference between the product of prime numbers for two integers is their order. For example $3 \cdot 7 \cdot 7 = 147$ and $7 \cdot 3 \cdot 7 = 147$. But 147 cannot be expressed in any other way. The only difference between the first and second products for 147 are the order of the set {3, 7, 7}, which we define still as unique since by the commutative property of multiplication.

**Proof:**We know that any integer n ≥ 1 can be written as a product of primes. We thus need to show that the product of primes is unique, that is:

\begin{align} n = p_1p_2p_3...p_n \quad n = q_1q_2...q_r \end{align}

- Where the set P = {p
_{1}, p_{2}, … , p_{n}} is equal to the set Q = {q_{1}, q_{2}, …, q_{r}}

- From the first equation n = p
_{1}p_{2}p_{3}…p_{n}, we see that p_{1}| n. But this also implies that p_{1}| q_{1}q_{2}…q_{r}.

- Note that the property p = q
_{k}holds (see here), in this case, we have p_{1}= q_{i}. Thus division of p_{1}on p_{1}p_{2}p_{3}…p_{n}, and division of q_{i}on q_{1}, q_{2}, …, q_{r}, we thus obtain:

\begin{equation} p_2p_3...p_n = q_1q_2...q_{i-1}q_{i+1}....q_r \end{equation}

- Since p
_{2}| p_{2}p_{3}…p_{n}clearly, then it follows that p_{2}| q_{1}, q_{2}, …, q_{i-1}q_{i+1}q_{r}

- We can thus apply the property that p
_{2}= q_{j}for some j in the set {1, 2, …, i-1, i+1, …, n}. Thus, both sides of the equation are divisible by q_{j}, and the process can continue indefinitely. Thus, we have for every p in set P, there is an equivalent q in set Q.

- Also, we will not run out of q's before p's, as then we would have a product of primes that is equal to 1, and all primes ≥ 2. Thus, the prime product is unique for the integer n.