Is my intuition of "If $p \mid ab$ then $p \mid a$ or $p \mid b$" correct?

Solution 1:

Your intuition is correct. However, this part:

The prime factors of $ab$ can be thought of as the union of the sets of primes factors of $a$ and $b$.

is (part of) the content of the fundamental theorem of arithmetic. The statement that $p \mid ab$ implies $p \mid a$ or $p \mid b$ is typically used as a lemma in proving the fundamental theorem of arithmetic, and therefore it is circular to use the latter to prove the former.

Solution 2:

Let $\cal P(n) =$ the set of prime factors of $n$. You sketched the following argument: $ $ for a prime $\,p$

$$p\mid ab\!\iff\! p\in\color{#c00}{\cal P(ab) = \cal P(a)\cup \cal P(b)}\!\iff\! p\in\cal P(a)\ \ {\rm or}\ \ p\in \cal P(b)\!\iff\! p\mid a\ \ {\rm or}\ \ p\mid b$$

But you did not provide any proof of the $\rm\color{#c00}{red}$ theorem. In fact the converse is also true, the Prime Divisor Property implies the $\rm\color{#c00}{red}$ theorem. A proof of their equivalence, or an implication between them, does not constitute a proof of either of them.

Probably you have some prior intuition that the $\rm\color{#c00}{red}$ theorem is true from theorems you have learned about the uniqueness of prime factorization of integers (which, combined with the (trivial) existence of prime factorizations, constitues the Fundamental Theorem of Arithmetic). If so, then it is essential to explicitly mention how the $\rm\color{#c00}{red}$ theorem is a logical consequence of these prior-proved results, so that you can convince the reader that the proof that you have in mind is rigorous.

Such rigor is especially necessary for results like this because we have such strong empirical (vs. logical) intuition about the integers that many people think that results like uniqueness of prime factorization is "obvious," with no rigorous proof required. Without any explicit justification offered in a proof, there is no way for the reader to judge its correctness. It leaves doubts: did the author think that it is "obvious", or did they have in mind one of many common erroneous proofs?

For many centuries no one noticed that uniqueness of prime factorizations required proof. Apparently either no one conceived of the possibility of nonuniqueness (or those who did thought that the proof was "obvious"). This was not corrected until $1801$, when Gauss plugged this gaping logical hole in his book Disq. Arith., remarking before his proof that "It is clear from elementary considerations that any composite number can be resolved into prime factors, but it is often wrongly taken for granted that this cannot be done in several different ways". But even more than a couple centuries later rigor was still lacking in some textbooks. Indeed, Harold Davenport wrote that some British schoolbooks deemed uniqueness of prime factorizations to be a "law of thought".