We’ve already proved the existence of a prime factorization. So, now, we only have to prove uniqueness. As in the proof of existence, we work by contradiction using the Axiom 1.3. So suppose Theorem 1.8 is not true. Then there is a positive integer \(n\) with two distinct prime factorizations. So, by Axiom 1.3, we can find a smallest such positive integer \(n\).

It’s easy to see that \([]\) is the only prime factorization of \(1\). (The point is that, \(x,y {\gt} 1\Rightarrow xy {\gt} 1\).) So \(n {\gt} 1\), and \(n\) has two distinct prime factorizations \(p = [p_1,\ldots , p_r]\) and \(q = [q_1,\ldots , q_s]\), and, by switching \(p\) and \(q\) if necessary, we can assume \(p_1 \le q_1\).

First assume \(p_1 = q_1\). Then \(a := p_2\cdots p_r = q_2\cdots q_s {\lt} n\). So, by the minimality of \(n\), \(a\) has a unique prime factorization. Therefore, \([p_2,\ldots , p_r] = [q_2,\ldots , q_s]\). But then, obviously, \([p_1,\ldots , p_r] = [q_1,\ldots , q_s]\) as \(p_1 = q_1\), and this contradicts the assumption that \(p\) and \(q\) were two distinct prime factorizations of \(n\).

Therefore, we must have \(p_1 {\lt} q_1\). So set \(m: = (q_1 - p_1) q_2 \cdots q_s\). Then \(1 \le m {\lt} n\). By the minimality of \(n\), \(m\) has a unique prime factorization. My strategy is to get a contradiction by showing that, in fact, \(m\) has two distinct prime factorizations.

First, let \(u = [u_1,\ldots , u_t]\) be a (possibly empty) prime factorization of \(q_1 - p_1\). If \(p_1 = u_i\) for some \(i\), then \(p_1 | (q_1 - p_1)\) and, since \(q_1 = p_1 + (q_1 - p_1)\), this implies that \(p_1 | q_1\). But as \(1 {\lt} p_1 {\lt} q_1\) and \(q_1\) is prime, this is impossible. So, we see that \(p_1\) cannot be equal to any of the \(u_i\). And \(p_1\) is not equal to any of the \(q_i\) either as \(p_1 {\lt} q_1 \leq q_i\) for all \(i\). So, by sorting the list \([u_1,\ldots , u_t, q_2, \ldots , q_s]\), we get a prime factorization of \(m\) in which \(p_1\) does not appear.

On the other hand, we have

So, as \(\ell := p_2\ldots p_r - q_2\ldots q_s \in \mathbb {P}\), we can factor \(\ell \) into primes and this gives rise to a prime factorization of \(m\) containing \(p_1\). Therefore, \(m\) has two distinct prime factorizations, one not containing \(p_1\) and one containing \(p_1\). As \(m {\lt} n\), this contradicts the minimality of \(n\) and prove the theorem.