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

**dwsmith** · July 7th 2010, 04:12 PM

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?

**chiph588@** · July 7th 2010, 04:20 PM

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.

**melese** · July 7th 2010, 04:21 PM

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

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

[SOLVED] if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})

[SOLVED] Let p be odd. Then 2(p-3)!\equiv -1 (mod p)

[SOLVED] x^2\equiv 1 (mod p) and x^2\equiv 1 (mod q), where p and q are distinct primes

[SOLVED] 2n^3+3n^2+n\equiv 0 (mod 6)

[SOLVED] a \not\equiv b (mod m), then b \not\equiv a (mod m)