Results 1 to 8 of 8

Math Help - GCD proof

  1. #1
    Junior Member mremwo's Avatar
    Joined
    Oct 2010
    From
    Tampa, FL
    Posts
    53

    GCD proof

    I am using == to denote congruency:
    a== b (modm) meaning a is congruent to b (modm)
    (or m divides a-b)

    Suppose A is the set of integers
    Let a,b,m be elements of A such that m>=2.

    Prove "If a == b(modm) then gcd(a,m)=gcd(b,m)"

    Everytime I try to do this, I get stuck.

    Thank you for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mremwo View Post
    I am using == to denote congruency:
    a== b (modm) meaning a is congruent to b (modm)
    (or m divides a-b)

    Suppose A is the set of integers
    Let a,b,m be elements of A such that m>=2.

    Prove "If a == b(modm) then gcd(a,m)=gcd(b,m)"

    Everytime I try to do this, I get stuck.

    Thank you for your help.
    a\equiv b\text{ mod }m\implies a=b+km and so (a,m)=(b+km,m)=(b,m).


    Is that not ok?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781
    It took me some time to confirm (b + km, m) = (b, m). For any number d, d | b + km and d | m iff d | b and d | m.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    I'm not sure if I'm missing something here. But isn't it as simple as to show that

    (b + km, m) | (b,m)
    AND
    (b,m) | (b + km, m)

    Is there something I'm missing plz?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781
    Quite possible that I am missing something, but the easiest way to show (b + km, m) | (b,m) that I found was to show that d | b + km and d | m implies d | b and d | m.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Absolutely - but showing that is trivial. Isn't it? I'm just curious when you said it took you time - I have been reading your posts for quite some time and you sure have a reputation so wanted to be sure if there is somhething I have not understood?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    I think this is easier (and perhaps slightly neater, as you don't have that lemma in the middle):

    Note that,
    gcd(a, m) = ar_1 + ms_1
    and
    gcd(b, m) = br_2 + ms_2.

    Take the difference to see that gcd(a, m) \equiv gcd(b, m) \text{ mod }m. This gives you that gcd(a, m)=gcd(b, m) as gcd(a, m) < m and gcd(b, m) < m.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781
    Quote Originally Posted by aman_cc View Post
    Absolutely - but showing that is trivial. Isn't it?
    Yes, it's pretty simple.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum