Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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 have the following assertion in my notes from last year that I'm trying hard to digest, but I think it isn't true:

If $p$ is prime $\Leftrightarrow$ if $p | ab$ then either $p | a$ or $p | b$ or both.

A valid proof must prove both directions, so:

  1. if $p$ is prime, let $a_p$ be the prime factorisation of $a$ and likewise $b_p$ be the prime factorisation of $b$. By the fundamental theorem of arithmetic, if $p|ab$ then $p|a$ or $p|b$ or both.
  2. However, assuming $p|ab$ and that $p|a$ or $p|b$ or both, I can find a case that doesn't work. Let $p=4$, $a=7$, $b=8$. Then $4|56$ does imply $4|8$ ($p|b$) but $4$ is not prime.

Am I missing something? The rest of my notes use this result quite a lot (albeit mostly from the point of view of $p$ prime which is clearly true). Unfortunately I'm not sure I'll be happy to progress unless I'm happy this statement is true...

share|cite|improve this question
up vote 7 down vote accepted

What you are missing is the following: The criterion "$p|ab$ implies that $p|a$ or $p|b$" has to hold for all natural numbers $a$ and $b$ for $p$ to be prime.

For instance, $p=4$ is not prime, because $4|36$ but not $4|6$.

share|cite|improve this answer
Aaaaah. That fixes it. So simple. Thank you. – user892 Oct 2 '10 at 15:49

You could also take a look at this previous question.

share|cite|improve this answer
That's interesting, thanks! – user892 Oct 3 '10 at 21:02

Your Answer


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