If $p$ is a prime and $p|ab$, then $p|a$ or $p|b$.

Question

I'm just starting to write proof and I was asked to prove the above statement. I came up with the following proof by contrapositive:

Assume $p$ does not divide $a$ or $p$ does not divide $b$, then $p$ does not divide $ab$.

Let $a=pk$ & $b=pm$ for some integers $k$ and $m$.

So, $ab=(pk)(pm)$, then $ab=p(km)$. This is a contradiction.

I'm not sure if that is correct proof. Any help is appreciated. Thank you.

Answer 1

The proof is not valid.

First, let's review the contrapositive statement:

Assume $p$ does not divide $a \color{red}{\text{ and }} p$ does not divide $b$, then $p$ does not divide $ab$.

In the very next line, we have assumed that $p$ doesn't divide $a$, hence we can't write $a=pk$.

One possible way to solve the problem is by prime factorization of $a$ and $b$.

Answer 2

This is Euclid's lemma.

You could, as one approach, use the fundamental theorem of arithmetic (FTA), to write $a$ and $b$ uniquely as products of powers of primes. Then note that if $p$ isn't in one prime factorization it would have to be in the other (or else it won't be a factor of the product).

Or i found the following proof on Wikipedia. You could use Bezout's identity: if $p\mid ab$ and $p\not\mid a$, then $a$ and $p$ are relatively prime. So $\exists s,r: sa+rp=1$. So $bsa+brp=b$. So $p\mid b$ (since it divides both terms of the LHS).