I am trying to prove that every natural number >1 has exactly one way of factorization by prime numbers.
I read the wikipedia page but it is not so clear to me (they use strong induction).
is there any other way to prove it ? maybe not by induction?
thanks
Best Answer
The following is a proof that uses the Well-ordering Principle of the natural numbers.
Proposition: If $a$ is an integer greater than $1$, then $a$ has a unique representation as a product of prime number (up to reordering).
Proof: We prove two lemmas.
Lemma 1: We first prove that all integers greater than $1$ can be written as a product of primes.
Proof: Suppose for the sake of contradiction that there exist some integer $b>1$ that does have a prime factorization. By the Well-ordering Principle, there is a smallest such $b$. Then, $b$ cannot be prime (otherwise it would have a trivial prime factorization), so $b$ is composite. Since $b$ is composite, it can be written as the product of two numbers smaller than it, $b = c,d$ where $1 < c,d, < b$. Then, since $b$ was the first such number without a prime factorization, $c$ and $d$ must both have prime factorizations. But then, $b$ does have a prime factorization, the product of the prime factorizations of $c$ and $d$. This is a contradiction, so the assumption that there exists any number $b>1$ such that $b$ does not have a prime factorization is false.
Lemma 2: We prove that the prime factorization of any number is unique up to reordering.
Proof: Suppose for the sake of contradiction that there exists some number $b>1$ that has two different prime factor representations, say $b = p_1 p_2 ... p_n = q_1 q_2 ... q_m$. Note that the $p_i$'s and $q_j$'s do not have to be unique (so we do not have to introduce exponents). By the Well-ordering prinicple, there is a smallest such $b$. Then, $p_1 \mid a = q_1 q_2 ... q_m$. Then, since $p_1$ is prime, the lemma above tell us that $p_i \mid q_k$ for some $1 \leq k \leq m$. WLOG lets say $k=1$. That is, $p_1 \mid q_1$, so $p_1 * z = q_1$ for some integer $z$. But $p_1$ and $q_1$ are both prime, so $z$ must be $1$, thus $p_1 = q_1$. So, we can cancel $p_1$ and $q_1$ from our equation above for $b$ to get $p_2...p_n = q_2...q_m$. But then, $p_2...p_n = q_2...q_m = s < b$, and we had that $b$ was the smallest number that did have two different representations, so $s$ has a unique representation, so $m = n$, and thus $p_2...p_n$ and $q_2...q_m$ are the same up to reordering. However, we also showed that $p_1 = q_1$, so in fact the two representations we had for $b$ were the same as well. This contradicts the assumption that there existed such a $b$, thus that assumption was false, and there does not exist such a $b$ with multiple prime factor representations.
Together, these two lemmas show that any integer greater than $1$ has a prime factor representation, and that the prime factor representation of any number is unique. It does not use induction, though it does require the Well-ordering principle which is very similar to induction. I hope this proof helps! Please comment any mistakes are suggestions.