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

• Jul 7th 2010, 04:12 PM
dwsmith
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?
• Jul 7th 2010, 04:20 PM
chiph588@
Quote:

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.
• Jul 7th 2010, 04:21 PM
melese
Quote:

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