A proof involving Greatest common divisors

[zoner7]

Homework Statement

If b>0 and a=bq + r, prove that (a,b) = (b,r)

I made an attempt... it didnt really go anywhere.

I think I can say that (a,b) = am + bn and (b,r) = bp + rq.
maybe...
a = bq + r
b = rp + s
You can see that I have absolutely no idea how to solve this.

Any help would be greatly appreciated. Thank you in advance.

 

[jeffreydk]

It follows from the Euclidean Algorithm; Consider if c divides a and b, then let a=cs and b=ct with s,t being integers. Then

$$r=a-bq=cs-(ct)q=c(s-tq) \Rightarrow c | r$$

And therefore c also divides b and r. Can you think of how the rest should go?

 

[zoner7]

It follows from the Euclidean Algorithm; Consider if c divides a and b, then let a=cs and b=ct with s,t being integers. Then

$$r=a-bq=cs-(ct)q=c(s-tq) \Rightarrow c | r$$

And therefore c also divides b and r. Can you think of how the rest should go?

well... I didn't accomplish too much. What exactly is my final goal supposed to be? What should I be showing next?

I tried to say
r = bq + w
w = r-bp
w = r - ctp
w c(s - tq) - ctq
w = c(s - t(q - p))

and then i decided that I wasn't really doing anything correctly and examined the equation
r - r = bq
q - c(s - tq) = bq
a = cs - ctq = bq
cs - cs - ctq = bq
bq = bq...
Clearly this is wrong...

So what am I trying to accomplish in the end?

 

[boombaby]

Now you have c|a and c|b. you get c|r from jeffreydk's hint.
Then you have c|b and c|r, which implies c|gcd(b,r), which means c is a common divisor of b and r.
if c=gcd(a,b), you are supposed to show c is actually the GREATEST common divisor of b and r

here's another way, gcd(a,b)|gcd(b,r) and gcd(b,r)|gcd(a,b) will imply they are equal. I think you have already got gcd(a,b)|gcd(b,r), you can prove gcd(b,r)|gcd(a,b) in a similar way.

 

[zoner7]

Now you have c|a and c|b. you get c|r from jeffreydk's hint.
Then you have c|b and c|r, which implies c|gcd(b,r), which means c is a common divisor of b and r.
if c=gcd(a,b), you are supposed to show c is actually the GREATEST common divisor of b and r

here's another way, gcd(a,b)|gcd(b,r) and gcd(b,r)|gcd(a,b) will imply they are equal. I think you have already got gcd(a,b)|gcd(b,r), you can prove gcd(b,r)|gcd(a,b) in a similar way.

alright. that makes sense based on the proof of a GCD. Thank you. I probably got it from here.

 

[zoner7]

well... I think I am dropping this class. its simply not making sense, and this is supposed to be one of the easier problems

I said
let r = cp
b = rq + w
w = b - rq
w = ct - cpq
w = c(t - pq)
implies c divides w

but I don't think this implies c divided (a,b)...

anyone know some good resources where I can get some help?

 

[boombaby]

foget about b=rq+w, focus on a=bx+r. Now a=c*something+c*something...can you get it now?

Also you would notice that,
1,a=bq+r. if c|a and c|b, you proved that c|r
now look at this one
2,b=rp+w. you have c|b and c|r, you proved that c|w
See? you are doing exactly the same thing two times.

 

[zoner7]

Well, I just tried it, wrote everything out and then realized that I made the same error that i did last time.

I guess I'm not really sure how to set the problems up in the first place. Clearly I don't understand something quite integral to the topic at hand.

What exactly am I saying when i write a = bx + r and a = bq+ r? Why is r the same for both of them? Why isn't a separate value required?

im calling it quits on this one... i can't figure it out.
I just don't understand the concepts at hand. Until I learn them, attempting this is futile.