Proof using greatest common divisor.

[bonfire09]

Homework Statement

The problem went "If c|a and c|b then c|gcd(a,b) where cεN and a,bεZ"

Homework Equations

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?

 

[STEMucator]

Homework Statement

The problem went "If c|a and c|b then c|gcd(a,b) where cεN and a,bεZ"

Homework Equations

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?

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

a=cr and b=cs

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.

 

[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 ?

 

[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.

 

[STEMucator]

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.

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.

 

[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 ideas in this proof are on the right track. Ill clean this proof up.

 

[STEMucator]

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 ideas in this proof are on the right track. Ill clean this proof up.

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