# 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 $\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?

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

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