Results 1 to 3 of 3

Math Help - congruence

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    5

    congruence

    Is there anyone who can help me where to start. I'm having a hard time to figure this problem out. Thanks

    Show that if a, b, and m are integers such that m ≥ 2 and a ≡ b( mod m), then gcd(a,m) = gcd(b,m).
    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
    a \equiv b \ (\text{mod } m) \ \Leftrightarrow a = b + km for some integer k.

    Let  d = (a,m). Since d \mid a and d \mid m, it follows from a = b+km that d \mid b and is thus a common divisor of b and m.

    Let c be any common divisor of b and m. With a similar argument, we have that c \mid a. By definition, since d is the greatest common divisor of a and m, we have that c \leq d.

    This means that any common divisor of b and m is less than d. Can you conclude?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    5
    thanks for the help, i now know what to conclude
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 11:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 02:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 06:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 10:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 11:57 AM

Search Tags


/mathhelpforum @mathhelpforum