Proof of uniqueness of prime factorization by induction with Euclid's Lemma

Question

The uniqueness of the prime factorization is proved here on Wikipedia. I am wondering whether the initial trick could be extended to a full proof without using contradiction as it's done there. So, let $n$ have two prime factorizations: $$n=p_{1}*p_{2}*\dots*p_{j}=q_{1}*q_{2}*\dots*q_{k}$$ The trick is that $p_{1}$ divides $q_{1}*q_{2}*\dots*q_{k}$, so by Euclid's lemma it must divide some $q_{i}$. Without loss of generality, let $p_{1}$ divide $q_{1}$. Since they are both prime, they must be equal. So we have already shown, that both factorizations must have one common factor. But the proof then is completed through some contradiction argument. Couldn't you instead complete this to establish equality of all factors? So, let $P$ be the set containing $p_{1}, p_{2}, \dots, p_{j}$ and $Q$ the set containing $q_{1}, q_{2}, \dots, q_{k}$. $\forall i, p_{i}$ divides $q_{1}*q_2*\dots *q_k$, so by Euclid's lemma it must divide and therefore be equal to one of the $q_i$s. So $P \subset Q$ and the other way around $Q \subset P$, hence $P=Q$, so uniqueness of prime factors up to ordering. Or am I mistaken?

Answer 1

Your argument using set inclusion almost works - but it does not deal with multiple factors of the same prime.

You can avoid proof-by-contradiction with induction on the number of prime factors. Then Euclid's argument settles both the base case (one prime factor) and the inductive step (cancel one prime factor).

A nice way to combine proof-by-contradiction with induction is to use the well ordering equivalent. The smallest failure of unique factorization can't exist because you can cancel one prime to find a smaller failure.