Thread: GCD Proof

if I have x and y be odd integers. Then 2gcd(x,y) = gcd(x+y,x-y). I am completely lost for what to do. I may be over think this but help would greatly be appreciated. This is what I have so far:

Let d = gcd(x,y) and e = gcd(x+y, x-y). To prove that e = 2d it suffices to show that 2d|e and e|2d. To show that 2d|e we need to show that 2d|(x-y) and 2d|(x+y). Thus e = (x+y)s + (x-y)t and d = xk + yl and 2d = 2xk + 2yl. (x-y) with x and y being always odd will always return even so x-y = 2n and (x+y) with x and y being always odd will always return even so x-y = 2m for some s,t,k,l,n and m in Z. Thus,

2n = (2xk + 2yl)z

2n = 2xkz +2ylz

n = xkz + ylz

2m = (2xk + 2yl)z

2m = 2xkz + 2ylz

m = xkz+ylz

But honestly I dont even know if this is right. I need help!! I have 2 others like this and have no clue where to go!!

First, we set d=gcd(x,y) and e=gcd(x+y,x-y)

Now we will show that 2d<=e and that e<=2d. I would say that this is the most common way of proving equalities involving gcd.

First, observe that since d|x and d|y, we have d|(x+y) and d|(x-y). Since x and y are both odd we also have 2|(x+y) and 2|(x-y). Once again, because x and y are both odd, we know that d is also odd and so it follows that 2d|x+y and 2d|x-y. Hence, 2d<=e.

For the other direction, observe that since e|(x+y) and e|(x-y), we have e|(x+y+x-y) and e|(x+y-(x-y)). So, e|2x and e|2y. Since x and y are both odd, this implies that e<=2d.

Therefore, 2d=e as desired.

Hope this helps!

Optikal