Results 1 to 3 of 3

Math Help - Congruence Proof

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    Congruence Proof

    If a \equiv b (mod n), prove that gcd(b,n) = gcd(a,n).
    I've tried working with the relationship between these equations but haven't had much luck. Thanks for any help in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Let: d_1 = \gcd (a,n) > 0 and d_2 = \gcd (b,n) > 0

    By definition:  a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km

    Since d_1 \mid a and d_1 \mid km, then d_1 \mid b.

    But this means d_1 is a common divisor of both b and n. Every common divisor of two integers divides their greatest common divisor.

    So: d_1 \mid d_2

    You can similarly show that: d_2 \mid d_1

    This implies: d_1 = d_2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,454
    Thanks
    1868
    Quote Originally Posted by o_O View Post
    Let: d_1 = \gcd (a,n) > 0 and d_2 = \gcd (b,n) > 0

    By definition:  a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km

    Since d_1 \mid a and d_1 \mid km, then d_1 \mid b.
    You mean "n", not "m" here, don't you?

    But this means d_1 is a common divisor of both b and n. Every common divisor of two integers divides their greatest common divisor.

    So: d_1 \mid d_2

    You can similarly show that: d_2 \mid d_1

    This implies: d_1 = d_2
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 22nd 2010, 03:50 PM
  2. Congruence proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 10th 2009, 11:03 AM
  3. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 5th 2009, 10:34 AM
  4. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2008, 08:16 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 19th 2007, 10:13 AM

Search Tags


/mathhelpforum @mathhelpforum