0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user296602 Feb 23 '16 at 3:30
  • $\begingroup$ 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 $\endgroup$ – Matt Feb 23 '16 at 3:34
  • 1
    $\begingroup$ Why do you think it doesn't help? What is a way to say $p | a$ as a congruence? $\endgroup$ – user296602 Feb 23 '16 at 3:35
  • $\begingroup$ hmmm... couldn't you write a= b+km from the definition of congruence? $\endgroup$ – Matt Feb 23 '16 at 3:41
  • $\begingroup$ No. That's the statement that $a \equiv b \pmod m$ (or modulo $k$). You should review the definition of $\mod p$. $\endgroup$ – user296602 Feb 23 '16 at 3:41
0
$\begingroup$

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$.

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

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.