# Thread: if ab\equiv 0 (mod p), then a\equiv 0 (mod p) or b\equiv 0 (mod p).

1. ## if ab\equiv 0 (mod p), then a\equiv 0 (mod p) or b\equiv 0 (mod p).

Standard letter meanings.

if $ab\equiv 0 \ \mbox{(mod p)}$, then $a\equiv 0 \ \mbox{(mod p)}$ or $b\equiv 0 \ \mbox{(mod p)}$

Since $ab\equiv 0 \ \mbox{(mod p)}$, $mp|(ab)\rightarrow \ mp|a \ \mbox{or} \ mp|b$. Hence, $ab\equiv 0 \ \mbox{(mod p)}$, then $a\equiv 0 \ \mbox{(mod p)}$ or $b\equiv 0 \ \mbox{(mod p)}$.

Correct?

2. Originally Posted by dwsmith
Standard letter meanings.

if $ab\equiv 0 \ \mbox{(mod p)}$, then $a\equiv 0 \ \mbox{(mod p)}$ or $b\equiv 0 \ \mbox{(mod p)}$

Since $ab\equiv 0 \ \mbox{(mod p)}$, $mp|(ab)\rightarrow \ mp|a \ \mbox{or} \ mp|b$. Hence, $ab\equiv 0 \ \mbox{(mod p)}$, then $a\equiv 0 \ \mbox{(mod p)}$ or $b\equiv 0 \ \mbox{(mod p)}$.

Correct?
Just look at the prime factorization of a and b. Your claim follows immediately.

Edit: This is circular reasoning as the fundamental theorem of arithmetic uses Euclid's Lemma. To find a proof look on Wikipedia.

3. Originally Posted by dwsmith
Standard letter meanings.

if $ab\equiv 0 \ \mbox{(mod p)}$, then $a\equiv 0 \ \mbox{(mod p)}$ or $b\equiv 0 \ \mbox{(mod p)}$

Since $ab\equiv 0 \ \mbox{(mod p)}$, $mp|(ab)\rightarrow \ mp|a \ \mbox{or} \ mp|b$. Hence, $ab\equiv 0 \ \mbox{(mod p)}$, then $a\equiv 0 \ \mbox{(mod p)}$ or $b\equiv 0 \ \mbox{(mod p)}$.

Correct?
You have an incorrect step here: " $mp|(ab)\rightarrow \ mp|a \ \mbox{or} \ mp|b$".
You start with $ab\equiv 0(mod\ p)$, or equivalently, $p|ab$. Then according to Euclid's Lemma either $p|a$ or $p|b$. Hence, $ab\equiv 0(mod\ p)$.