# Explain why $\gcd(x,y)=\gcd(\frac{x+y}{2},\frac{x-y}{2})$ if $x$,$y$ are odd integers.

If $x$,$y$ are odd integers, argue that

$$\gcd(x,y)=\gcd\left(\frac{x+y}{2},\frac{x-y}{2}\right)\;.$$

I'm having a difficult time with this:

First, I tried a few examples to check that my professor didn't once again make an obvious mistake, because he's very good at that. Poor guy..

$$\gcd(5,3)=\gcd\left(\frac{5+3}{2},\frac{5-3}{2}\right)=1$$

$$\gcd(15,3)=\gcd\left(\frac{15+3}{2},\frac{15-3}{2}\right)=3$$

-

HINT: Suppose that $d\mid x$ and $d\mid y$; then clearly $d\mid x+y$ and $d\mid x-y$. Since $x$ and $y$ are odd, $x+y$ and $x-y$ are even, so there are integers $m$ and $n$ such that $x+y=2m$ and $x-y=2n$. Thus, $d\mid 2m$ and $d\mid 2n$. But $d$ must be odd (why?), so $d\mid m$ and $d\mid n$. Thus, $\gcd\{x,y\}\mid\gcd\{m,n\}$.
Now suppose that $d\mid m$ and $d\mid n$. Can you show that $d\mid x$ and $d\mid y$, so that you can conclude that $\gcd\{m,n\}\mid\gcd\{x,y\}$?