# Prove that if $ab \equiv 0 \pmod p$, where p is a prime number, then $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$

Prove that if $ab \equiv 0 \pmod p$, where p is a prime number, then $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$.

All I have right now is that the prime divisibility property may help with the then part of this problem.

• What is the "prime divisibility property"? If it's what I think it is, then this is literally just a one-line application of the definition of congruence. – user296602 Feb 23 '16 at 3:30
• The prime divisibility property says that if p|(a1*a2*... ar), then p divides on of the a's. But now that I look at it, I don't think it helps here – Matt Feb 23 '16 at 3:34
• Why do you think it doesn't help? What is a way to say $p | a$ as a congruence? – user296602 Feb 23 '16 at 3:35
• hmmm... couldn't you write a= b+km from the definition of congruence? – Matt Feb 23 '16 at 3:41
• No. That's the statement that $a \equiv b \pmod m$ (or modulo $k$). You should review the definition of $\mod p$. – user296602 Feb 23 '16 at 3:41

The ideal $(p) \subset \mathbb Z$ is prime, thus if $ab \in (p)$, then $a \in (p)$ or $b \in (p)$.

In other words:

$ab \equiv 0 \pmod p \implies ab=pk \implies p|a$ or $p|b \implies a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$.

• Just for clarification: what property is used here? I think I know but I'm not 100% sure. – Matt Feb 23 '16 at 3:48
• A prime number which divides a product must divide at least one factor. – Maffred Feb 23 '16 at 3:54
• This comes from the unique factorization in $\mathbb Z$ into prime factors. – Maffred Feb 23 '16 at 3:55
• That is what I thought it was. Thanks so much – Matt Feb 23 '16 at 3:55

Remember that in the integers, for a prime $\;p\;\;,\;\;\;p|a\iff a=kp\;,\;\;a,k\in\Bbb Z\;$ , and then $\;a=0\pmod p\iff p|a\iff a=kp\;$ , so by what you wrote in your second comment below your question:

$$ab=0\pmod p\iff p|ab\iff p|a\;\;\text{or}\;\;p|b\iff$$

$$a=kp\;\;\text{or}\;\;b=mp\;,\;\;k,m\in\Bbb Z\iff a=0\pmod 0\;\;\text{or}\;\;b=0\pmod p$$