5
$\begingroup$

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$

1 Answers 1

2

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\}$?