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

Question

I'm studying number theory and I was given this Theorem to look at:

If $p \mid ab$ then $p \mid a$ or $p \mid b$

I had the following intuition for the problem or a proof of sorts if you will.

Intuitive Proof. We take the assumption that $p$ can in fact divide $ab$. Then, this implies that $p$ is divided out by one of prime factors of $ab$. The prime factors of $ab$ can be thought of as the union of the sets of primes factors of $a$ and $b$. This would mean that $p$ is in the set of prime factors of $a$ or $b$. More concretely:

Let $S$ be the set of primes factors of $ab$ which we defined to be the union of the sets of the prime factors of $a$ and $b$. For example:

Let $A$ be the set of primes factors of $a$ and let $B$ be the set of prime factors of $b$. Then $S=A \cup B$

Now, if $p \mid ab$ then $p$ must belong to $S$ ($p \in S$) this, therefore, implies that $p \in A$ or $p \in B$.

So, that's my "intuitive proof". Does it make sense?

All feedback is much appreciated.

Thanks a bunch!

EDIT: $p$ is prime.

Answer 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.

Answer 2

You might find this page extremely relevant: Euclid's Lemma

Your statement this implies that p is divided out by one of prime factors of ab is unclear or even erroneous: you are saying that if $n$ is a prime factor of $ab$, then $n|p$ for some $n$.

Otherwise, your intuition looks good. Dustan made a pertinent comment about circularity.

Answer 3

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".