Results 1 to 2 of 2

Thread: 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: $\displaystyle d=\gcd(r,s)$ iff (i) $\displaystyle d\mid r$ and $\displaystyle d\mid s$ and (ii) $\displaystyle \forall\,c\in\mathbb Z,$ $\displaystyle c\mid r$ and $\displaystyle c\mid s$ $\displaystyle \Rightarrow$ $\displaystyle c\mid d.$

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

    Let $\displaystyle d=\gcd(a,m).$

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

    $\displaystyle \therefore\ d\mid b$ and $\displaystyle d\mid m$

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

    (i) and (ii) $\displaystyle \Rightarrow$ $\displaystyle 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: Nov 3rd 2009, 06:47 PM
  2. proof of a congruence modulo prime powers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 21st 2009, 03:41 AM
  3. Modulo/congruence proof help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 1st 2009, 11:39 AM
  4. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 27th 2007, 07:59 PM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Feb 22nd 2007, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum