Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

up vote 6 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|improve this answer
Aaaaah. That fixes it. So simple. Thank you. –  Rhino Oct 2 '10 at 15:49

You could also take a look at this previous question.

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

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.