Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
If $p$ is any number (prime or composite), then no. For instance, $6 | 2 \cdot 3$, but $6 \not| 2$ or $6 \not| 3$ – NasuSama Jan 14 '14 at 19:51
is $p$ a prime ? if not how about $60|6 \times 10$ ? – LeGrandDODOM Jan 14 '14 at 19:52
Indeed, as NasuSama pointed it's not always true. In fact it is characterization of primes numbers. – leo Jan 14 '14 at 19:53
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 ? – Mauro ALLEGRANZA Jan 14 '14 at 19:58
@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. – Dustan Levenstein Jan 14 '14 at 20:02
up vote 5 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer
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. – Jeel Shah Jan 14 '14 at 19:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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