Results 1 to 9 of 9

Math Help - Help with a congruence proof

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Canada
    Posts
    7

    Help with a congruence proof

    The question asks you to find if a statement is true, if it is, prove it. If it is not, give a counterexample.
    If a2 = b2 (mod p), then a = b (mod p), where p is prime.
    Note the underlined equal signs are actually meant to be congruence signs. Is there a way to insert congruence signs in this forum?

    I based my proof on the properties of congruences which states that if a = b (mod m), and c = d (mod m), then ac = bd (mod m).
    a = b (mod m)
    a = b + mk
    (a)(a) = (b + mk)(b + mk)
    a2 = b2 + 2mbk + m2k2
    a2 = b2 + m(2bk + mk2) 2bk + mk2 is an integer, say t
    a2 = b2 + mt

    Therefore a2 = b2 (mod m)

    I personally don't see why this proof would not hold if the modulus is prime. Then again, I'm not great with proofs. Can I stick a "p" in place of "m" in my proof and call it a day? Or does the fact the modulus is prime complicate things?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1

    Re: Help with a congruence proof

    Quote Originally Posted by notinsovietrussia View Post
    The question asks you to find if a statement is true, if it is, prove it. If it is not, give a counterexample.
    If a2 = b2 (mod p), then a = b (mod p), where p is prime.
    Note the underlined equal signs are actually meant to be congruence signs. Is there a way to insert congruence signs in this forum?
    Note that a^2\equiv_p b^2 means p|(a^2-b^2) which implies p|[(a-b)(a+b)].
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Canada
    Posts
    7

    Re: Help with a congruence proof

    Quote Originally Posted by Plato View Post
    Note that a^2\equiv_p b^2 means p|(a^2-b^2) which implies p|[(a-b)(a+b)].
    Hmm, when I originally attempted to prove this I went down this road, but stalled. If you brought this up, it must be significant. This was my approach...

    If p|(a^2-b^2)

    then p|[(a-b)(a+b)]

    so either p|(a-b) or p|(a+b)


    if p|(a-b)

    then a=b+pk

    which means a\equiv_p b


    if p|(a+b)

    then a=-b+pk

    which means a\equiv_p -b, but since -b is not neccesarily congruent to b (mod p) we cannot conclude that a\equiv_p b.


    So that's where I stalled...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Help with a congruence proof

    The original statement is false. In post #1, you proved the converse.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2012
    From
    Canada
    Posts
    7

    Re: Help with a congruence proof

    So by proving the converese I disporved the original statement?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Help with a congruence proof

    Quote Originally Posted by notinsovietrussia View Post
    So by proving the converese I disporved the original statement?
    No. If you proved A -> B, it says nothing about B -> A. The latter statement can be true or false.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2012
    From
    Canada
    Posts
    7

    Re: Help with a congruence proof

    Quote Originally Posted by emakarov View Post
    No. If you proved A -> B, it says nothing about B -> A. The latter statement can be true or false.
    I see. That makes sense. Well I handed in my assignment with the original proof because I really couldn't come up with anything better. I guess I will find out how we were supposed to prove prove/disprove it when I get it back. Thanks for the assistance.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Help with a congruence proof

    If you'd like, you can post the correct answer once you know it so that other people who will read the thread later may have the complete picture.

    Also, the converse of an implication should not be confused with the negation. The converse of A -> B is B -> A. The negation applies to any proposition, and the negation ~(A -> B) of an implication is equivalent to A /\ ~B. Proving the negation of a statement indeed disproves that statement.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Help with a congruence proof

    Quote Originally Posted by notinsovietrussia View Post
    The question asks you to find if a statement is true, if it is, prove it. If it is not, give a counterexample.
    If a2 = b2 (mod p), then a = b (mod p), where p is prime.
    You answer it like this:

    The statement is false.

    Counter-example: 3 is prime. Since 1^2 \cong 1 \ mod \ 3, and 2^2 \cong 4 \cong 1 \ mod \ 3, have that

    1^2 \cong 2^2 \ mod \ 3, but 1 \ncong 2 \ mod \ 3.
    Last edited by johnsomeone; October 12th 2012 at 06:31 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2010, 12:30 PM
  2. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 15th 2009, 06:12 AM
  3. another congruence proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 02:41 PM
  4. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 11:02 AM
  5. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2008, 07:16 AM

Search Tags


/mathhelpforum @mathhelpforum