Help proving gcf(a,b) = gcf(a-b,2b-a)?

[Null_Pointer]

how should i think when trying to prove this problem ?

 

[ramsey2879]

how should i think when trying to prove this problem ?

1. If gcf divides both a and b, isn't it true that it also divides any sum or differenceof a and b? How does that apply to the gcf of (a-b,2b-a)?

 

[alphachapmtl]

let s=gcf(a,b), so s|a , s|b, (n|a and n|b implies n|s)
let t=gcf(a-b,2b-a), so t|a-b , t|2b-a, (n|a-b and n|2b-a implies n|t)
we have t|(a-b)+(2b-a)=b and t|(a-b)-b=a
so t|s
we have s|(a)-(b)=a-b and s|2(b)-(a)=2b-a
so s|t
so s=t

 

[Null_Pointer]

let s=gcf(a,b), so s|a , s|b, (n|a and n|b implies n|s)
let t=gcf(a-b,2b-a), so t|a-b , t|2b-a, (n|a-b and n|2b-a implies n|t)
we have t|(a-b)+(2b-a)=b and t|(a-b)-b=a
so t|s
we have s|(a)-(b)=a-b and s|2(b)-(a)=2b-a
so s|t
so s=t

i just have one question, is 'n' in this case the remainder from the euclidean formula ?

 

[ramsey2879]

i just have one question, is 'n' in this case the remainder from the euclidean formula ?

No n can be any divisor, not just the euclidean remainder. Simply put if any number divides both a and b, it also must divide the gcf of (a,b).

 

[robert Ihnot]

However, we have that question of 2b, which could affect the outcome.

 

[ramsey2879]

However, we have that question of 2b, which could affect the outcome.

I think the third line of Null Pointer's post handled that question nicely.

 

[disregardthat]

Use that gcd(m,n)=gcd(m+kn,n) twice, one on each side.

There is a slight typo in the third line mentioned above, it may be the cause of the confusion.