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 = {p1, p2, … , pn} is equal to the set Q = {q1, q2, …, qr}
- From the first equation n = p1p2p3…pn , we see that p1 | n. But this also implies that p1 | q1q2…qr.
- Note that the property p = qk holds (see here), in this case, we have p1 = qi. Thus division of p1 on p1p2p3…pn, and division of qi on q1, q2, …, qr, we thus obtain:
\begin{equation} p_2p_3...p_n = q_1q_2...q_{i-1}q_{i+1}....q_r \end{equation}
- Since p2 | p2p3…pn clearly, then it follows that p2 | q1, q2, …, qi-1qi+1qr
- We can thus apply the property that p2 = qj for some j in the set {1, 2, …, i-1, i+1, …, n}. Thus, both sides of the equation are divisible by qj, 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.