# Homework Help: Proof using greatest common divisor.

1. Dec 13, 2012

### bonfire09

1. The problem statement, all variables and given/known data
The problem went "If c|a and c|b then c|gcd(a,b) where cεN and a,bεZ"

2. Relevant equations

3. The attempt at a solution
My proof went like this " Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Lets
start with cd=ax+by where d,x,yεZ since the gcd(a,b) can be rewritten as a linear combination.
Substituting a and b we get cd=(cr)ax+(cs)ay <=> cd=c(rax+say) where rax+sayεZ. Hence
c|gcd(a,b).

is this right?

2. Dec 13, 2012

### Zondrina

Notice where I've bolded. You jumped out too far there. You're right to say that :

It's also good that you realize the gcd is a linear combination, but that does not automatically imply what you've stated here.

What you should say is suppose gcd(a,b) = d for some integer d. Then it follows that gcd(a,b) = d = ax + by for some integers x and y.

Now using d = ax + by the rest of your proof will follow smoothly.

3. Dec 13, 2012

### dextercioby

c is a common divisor of a and b so in particular it is equal to the gcd. This part is trivial. Assume now that c is a common divisor smaller (in modulus) than gcd. You need to show that there's x integer so that gcd = x c.

Assume a = c alpha, b = c beta. What happens if (alpha,beta) =1, i.e. gcd(alpha,beta)=1 ? Who's c ?

4. Dec 13, 2012

### bonfire09

I agree the first part of my proof makes a leap but not a very big leap. So my proof should read like this " Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Suppose gcd(a,b) = d for some integer d. Then it follows that gcd(a,b) = d = ax + by for some integers x and y. Thus ct=d for some tεZ which becomes ct=ax+by. Substituting a and b we get ct=(cr)ax+(cs)ay <=> ct=c(rax+say) where rax+sayεZ. Hence c|gcd(a,b).

It makes the proof look cleaner but doesn't change much. I used the fact that gcd(a,b) by definition can be written as a linear combination of some multiples of integers a and b.

Last edited: Dec 13, 2012
5. Dec 13, 2012

### Zondrina

Er what I was thinking was if :
a=cr and b=cs

d = ax + by
d = crx + csy
d = c(rx + sy)

And hence c divides d. Making the substitution for d is redundant.

6. Dec 13, 2012

### bonfire09

oh I realize I made an error in my original proof. "Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Suppose gcd(a,b) = d for some integer d. Then it follows that gcd(a,b) = d = ax + by for some integers x and y. Thus ct=d for some tεZ which becomes ct=ax+by. Substituting a and b we get ct=(cr)x+(cs)y <=> ct=c(rx+sy) (right here where I left a)where rx+syεZ. Hence c|gcd(a,b).

Yeah its redundant. I wouldn't say its a bad thing as it can be fixed. But I just wanted to verify that the idea's in this proof are on the right track. Ill clean this proof up.

Last edited: Dec 13, 2012
7. Dec 13, 2012

### Zondrina

Yes it's the right idea for sure. Just saying why do more work than you have to right ;)?