Results 1 to 3 of 3

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

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    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.
    Last edited by chiph588@; July 7th 2010 at 05:40 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by dwsmith View Post
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 15th 2011, 09:04 AM
  2. [SOLVED] Let p be odd. Then 2(p-3)!\equiv -1 (mod p)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 12th 2010, 04:42 PM
  3. Replies: 2
    Last Post: July 10th 2010, 06:14 PM
  4. [SOLVED] 2n^3+3n^2+n\equiv 0 (mod 6)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 9th 2010, 12:44 AM
  5. [SOLVED] a \not\equiv b (mod m), then b \not\equiv a (mod m)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 5th 2010, 03:44 AM

/mathhelpforum @mathhelpforum