Results 1 to 2 of 2

Math Help - Congruence & Modulo Proof

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    33

    Congruence & Modulo Proof

    Show that if a, b, and m are integers such that m >= 2 and a is congruent to b mod m then GCD(a, m) = GCD(b, m)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Recall the definition of GCD: d=\gcd(r,s) iff (i) d\mid r and d\mid s and (ii) \forall\,c\in\mathbb Z, c\mid r and c\mid s \Rightarrow c\mid d.

    Now, a\equiv b\pmod m \Rightarrow a=b+km for some k.

    Let d=\gcd(a,m).

    (i) d\mid a and d\mid m \Rightarrow d\mid a-km=b

    \therefore\ d\mid b and d\mid m

    (ii) Suppose c\mid b and c\mid m. Then c\mid b+km=a. So c\mid a and c\mid m; \therefore\ c\mid\gcd(a,m)=d.

    (i) and (ii) \Rightarrow d=\gcd(b,m)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. congruence modulo 2^n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2009, 07:47 PM
  2. proof of a congruence modulo prime powers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 21st 2009, 04:41 AM
  3. Modulo/congruence proof help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 1st 2009, 12:39 PM
  4. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2007, 08:59 PM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 22nd 2007, 04:57 PM

Search Tags


/mathhelpforum @mathhelpforum