Results 1 to 5 of 5
Like Tree3Thanks
  • 1 Post By Deveno
  • 2 Post By Deveno

Math Help - gcd of a,a+b

  1. #1
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    137
    Thanks
    4

    gcd of a,a+b

    Hi,

    I'm completely stumped on how to approach this question. As I can't see a way of knowing the prime factorization of a+b...

    Prove that:
    gcd(a, a + b) = gcd(a + b, b)

    Thanks for any help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: gcd of a,a+b

    suppose d|a and d|(a+b). then surely d divides b = (a+b) - a.

    on the other hand, suppose k|b and k|(a+b). then surely k divides (a+b) - b = a.

    thus shows that the sets of common divisors of a and a+b and b and a+b are both contained in the set of common divisors of a and b.

    but if t|a and t|b, then t divides a+b as well, showing that the set of common divisors of a and b is contained in both sets of common divisors of (a,a+b) and (b,a+b).

    hence all 3 sets are equal.

    an example: let a = 60 and b = 84. then gcd(60,84) = 12. and, as expected, gcd(60,144) = 12, and gcd(84,144) = 12.
    Thanks from Ant
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    137
    Thanks
    4

    Re: gcd of a,a+b

    thanks!

    is it sufficient to say:

    On the one hand we have, d|a and d|(a+b) implies d|b

    And on the other hand we have, d|b and d|(a+b) implies d|a

    So the set of divisors of a and a+b is the same as the set of divisors of b and a+b. Thus the largest divisor for a and a+b is the same as the larges divisor of b and a+b and so gcd(a,a+b)=gcd(b,a+b)

    is the above okay??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: gcd of a,a+b

    yes. that is sufficient. i included the extra to show that both sets are the same as the common divisors of a and b. this can often be used in calculation, since one can use subtraction to "cut down the size" of the numbers being used. for example to find gcd(2143,3427):

    gcd(2143,3427) = gcd(2143,1284) = gcd(859,1284) = gcd(425,859) = gcd(425,434) = gcd(9,434).

    then, since 434 is not divisible by 3, we have gcd(2143,3427) = 1.

    another example: find the gcd of (1428,7238):

    gcd(1428,7238) = gcd(1428,5810) = gcd(1428,4382) = gcd(1428,2954) = gcd(1428,1526) = gcd(98,1428)

    and since 1428 = (98)(14) + 56, applying this repeatedly (14 times, in fact) gives:

    gcd(98,1428) = gcd(56,98) = gcd(42,56) = gcd(14,42) = gcd(14,28) = gcd(14,14) = 14.

    in other words, the euclidean algorithm for finding the gcd is just using this property we just established, over and over again. the beauty of this, is that subtraction is a LOT easier to deal with conceptually, than "division" (although if b is a lot larger than a, it will be more efficient to divide by a (find out how many multiples of a you have to subtract from b)).
    Thanks from Ant and jsndacruz
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    137
    Thanks
    4

    Re: gcd of a,a+b

    thank you so much! that's very useful.

    So the Euclidean Algorithm is just a more efficient (but like you say, less conceptually clear) application of this fact. Imo, for number which are roughly the same size, the above is much nicer way of working out the gcd. Thank you for spelling out the connection!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum