Results 1 to 3 of 3

Math Help - Prove these GCD(greast common denominator

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    8

    Post Prove these GCD(greast common denominator

    1) For all integers a,b we have gcd(a,b) = gcd(2a + b, 3a + 2b)

    2) For all integers a,b,c with c> 0 we have gcd(ac,bc) = c gcd(a, b)

    3) For all integers a,b,c we have gcd(ab,c) = 1 if and only if gcd(a,c) = gcd(b,c)=1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by hellohollar View Post
    1) For all integers a,b we have gcd(a,b) = gcd(2a + b, 3a + 2b)

    2) For all integers a,b,c with c> 0 we have gcd(ac,bc) = c gcd(a, b)

    3) For all integers a,b,c we have gcd(ab,c) = 1 if and only if gcd(a,c) = gcd(b,c)=1

    For example (1): supose gcd(2a + b, 3a + 2b) = d ==> there exist integers n, m s.t.

    3a + 2b = md
    2a + b = nd --- rest these two equations an get
    --------------
    a + b = (m-n)d --- now rest this from the the second eq. above:

    a = (m + 2n)d

    But then d divides a and d divides 2a + b ==> d divides b ==> d = 1 .

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    You've shown that d|a and d|b, what's left is to show that there's no integer greater than d such that it also divides a and b ... then we can say gcd(a,b) = d ...

    You could also try the other way around (I think this works better) ... let c = gcd(a,b) => c|a and c|b => c|2a+b and c|3a+2b

    Now we assume that there exists an integer d greater than c such that d|2a+b and d|3a+2b. We follow what you did and get that d|a and d|b, but c is the gcd => c > d ... contradiction, so d must be less than or equal to c => c = gcd(2a+b,3a+2b)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. find the common denominator
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 20th 2011, 07:31 PM
  2. [SOLVED] Common Denominator ?
    Posted in the Algebra Forum
    Replies: 5
    Last Post: July 21st 2011, 04:49 AM
  3. common denominator with variables
    Posted in the Algebra Forum
    Replies: 5
    Last Post: November 29th 2010, 07:00 AM
  4. Common denominator
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 31st 2010, 02:27 AM
  5. common denominator
    Posted in the Algebra Forum
    Replies: 10
    Last Post: November 8th 2009, 07:57 AM

Search Tags


/mathhelpforum @mathhelpforum