>>11742584To prove uniqueness I will first prove a lemma.
Lemma: if p is an irreducible natural number, then p|ab => p|a or p|b.
Proof: Assume p|ab and that p doesn't divide a. It's enough to show that p|b.
Let I be the set of numbers of the form an + pm, for integers n,m. It can be shown that the smallest positive element of I is 1.
So we have an + pm = 1 for some n,m.
Multiply both sides of the equation by b to get
abn + pmb = b.
Since p|abn and p|pmb, that means p|b, so we're done.
Proof of uniqueness: Let p_1... p_n = q_1...q_m, where q_i, p_i are irreducible natural numbers greater than 1. Then p_1| (q_1)(q_2...q_n), so by lemma either p_1 | q_1 or p_1|(q_2...q_n). Continuing in a similar fashion we find that there is some i such that p_1 | q_i.
We might reorder the factors to make p_1|q_1. But then, since q_1 is irreducible, either p_1=1 or q_1. We've assumed that p_1>1 so p_1=q_1. We can divide both sides by p_1 to reduce the number of factors (because ab=0 => a=0 or b=0).
Cancelling out terms like that we continue until there are no terms left. We see that we are forced to have n=m and q_i = p_i (after reordering). Hence prime factorizations are unique.
