# Is it true that for any natural number $p$, if $p$ divides $ab$, then it divides either $a$ or $b$?

I need someone to check my answer.

True or False ?

For any natural numbers $p$, if $p$ divides the product $a.b$ of two natural numbers $a$,$b$ in $\mathbb{N}$, then either $p$ divides $a$ or $b$.

My answer: True - since Lemma 2.6(Euclid). Let $a$ and $b$ be integers and $p$ be a prime number. If $p\mid ab$, then either $p \mid a$ or $p \mid b$.

• You are missing the role played by primes here. Check for e.g. $4 \mid (6\cdot 10)$. – Macavity Sep 14 '13 at 4:24

Your answer is incorrect. Your "Lemma 2.6" only holds under the hypothesis that $p$ is prime, but the statement you want to prove true or false has $p$ being any natural number.

Hint: $4 = 2 \times 2$

Hint 2: $4 \mid 2 \times 2$ but $4 \nmid 2$

• Thanks Clive N. Can you give a counterexample to support my answer(False) . – Emmanuel Mani Sep 14 '13 at 4:39
• Yes, see the hints. – Clive Newstead Sep 14 '13 at 14:00

HINT:

1- If $p$ is a prime number and $m$ is an integer that is not divisble by $p$, i.e. $p \not\mid m$, then $(p,m)=1$.

2- Suppose that $p \mid ab$ and $p \not\mid b$, then what can you conclude about $(p,b)$? How can you apply Euclid's theorem to this? Can you conclude $p \mid a$ from that?

EDIT:

If $p$ is NOT prime, then the theorem does NOT hold. For example if $p=ab$ is a composite number where $a,b>1$ then $p|ab$ but $p \not\mid a$ and $p \not\mid b$ because $a<p$ and $b<p$.