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.

  • 1
    $\begingroup$ If $p$ is any number (prime or composite), then no. For instance, $6 | 2 \cdot 3$, but $6 \not| 2$ or $6 \not| 3$ $\endgroup$ – NasuSama Jan 14 '14 at 19:51
  • 1
    $\begingroup$ If $ab=pq$ and assume that $a=pq_1 + r_1$ and $b=pq_2 + r_2$ with $r_1 \neq 0$ and $r_2 \neq 0$ (these are the translation of $p$ does not divide $a$ nor $b$). Now, multiplying $a$ and $b$ we get : $ab = p[pq_1q_2 + q_2r_1 + q_1r_2] + r_1r_2$; but $r_1r_2 \neq 0$, contradicting the fact that $p$ divides $ab$. Is it right ? $\endgroup$ – Mauro ALLEGRANZA Jan 14 '14 at 19:58
  • 1
    $\begingroup$ @MauroALLEGRANZA You would probably be better off asking a new question for something like this; in answer, however, the constraint you need on $r_1$ and $r_2$ is actually $0<r_i<p$ in order to assert non-divisibility by $p$, and this constraint is not sustained in the product $r_1 r_2$. I do remember seeing a similar proof along these lines, though; I think it involved assuming $p$ was minimal. $\endgroup$ – Dustan Levenstein Jan 14 '14 at 20:02
  • 1
    $\begingroup$ You have $r_1 r_2< p^2$ and $r_1 r_2 = px$, which implies in particular that $x<p$. If $p$ is a minimal counterexample, then for a prime factor $q \mid x$, you can divide $q$ out of either $r_1$ or $r_2$, and repeat until $x=1$. This gives a factorization $p = r_1 r_2$, which contradicts $p$ being prime (or rather, irreducible, as it is defined when you get into generalizations in abstract algebra). $\endgroup$ – Dustan Levenstein Jan 14 '14 at 20:20
  • 1
    $\begingroup$ @Dustan Levenstein - You are right; I neglected the fact that $p$ must be prime. If $p$ is a prime factor of $ab$, then $p$ is in the set of prime factors of $ab$. But this set is the union of the set of prime factors of $a$ with the set of prime factors of $b$. So, $p$ must divide $a$ or $p$ must divide $b$. $\endgroup$ – Mauro ALLEGRANZA Jan 19 '14 at 16:26

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.


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 gap in Disq. Arith. But even more than a couple centuries later rigor still suffers. Indeed, Harold Davenport wrote that some British schoolbooks deemed uniqueness a "law of thought".

  • $\begingroup$ You are so detailed this time, I wish you could be always. $\endgroup$ – jitender Mar 5 '18 at 10:29

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.

  • $\begingroup$ Sorry if it was unclear. What I meant it to say was that if $p$ can divide $ab$ then if you prime factorize $ab$ then one of prime factors of $ab$ must cancel with $p$. I don't know how to describe this perfectly but I'm trying to describe it as you would do it on paper. $\endgroup$ – Jeel Shah Jan 14 '14 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.