# 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 $\displaystyle ab\equiv 0 \ \mbox{(mod p)}$, then $\displaystyle a\equiv 0 \ \mbox{(mod p)}$ or $\displaystyle b\equiv 0 \ \mbox{(mod p)}$

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

Correct?
• Jul 7th 2010, 04:20 PM
chiph588@
Quote:

Originally Posted by dwsmith
Standard letter meanings.

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

Since $\displaystyle ab\equiv 0 \ \mbox{(mod p)}$, $\displaystyle mp|(ab)\rightarrow \ mp|a \ \mbox{or} \ mp|b$. Hence, $\displaystyle ab\equiv 0 \ \mbox{(mod p)}$, then $\displaystyle a\equiv 0 \ \mbox{(mod p)}$ or $\displaystyle 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 $\displaystyle ab\equiv 0 \ \mbox{(mod p)}$, then $\displaystyle a\equiv 0 \ \mbox{(mod p)}$ or $\displaystyle b\equiv 0 \ \mbox{(mod p)}$

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

Correct?

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