# Thread: Prove these GCD(greast common denominator

1. ## 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

2. Originally Posted by hellohollar
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

3. 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)