gcd of a,a+b

Printable View

• May 15th 2012, 12:30 PM
Ant
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!
• May 15th 2012, 01:08 PM
Deveno
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.
• May 15th 2012, 01:19 PM
Ant
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??
• May 15th 2012, 02:24 PM
Deveno
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)).
• May 15th 2012, 02:37 PM
Ant
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!