Honestly I don't have a strong idea. I don't know where to even begin, I have considered that the $\gcd(a,b)$ is somehow less than $a-b$, but I'm not even sure why that would be the case.. Any help would be great!
Asked
Active
Viewed 982 times
4 Answers
3
Some hints. Let $g=\gcd(a,b)$. We want to show that $g\mid{\rm RHS}$.
(1) $g$ is a factor of $a-b$ because. . .
(2) therefore $g$ is a factor of $|a-b|$ because. . .
(3) therefore $g$ is a factor of $\frac{1}{2}|a-b|$ because. . . (this is the hard bit)
(4) and it is obvious that $g$ is a factor of $b$, so
(5) $g$ is a factor of ${\rm RHS}$.
See if you can fill in all the reasons where indicated by dots.
Now you have to do the same kind of thing in the other direction: let $h={\rm RHS}$ and prove that $h$ is a factor of ${\rm LHS}$.
Good luck!
David
- 82,662
1
$d|a$ and $d|b$
Iff $d|a-b$ and $d|b$
Iff $d|(a-b)/2$ and $d|b$ (for $d$ is odd)
Same set of common divisors so same gcd
Karthik C
- 2,581
1
I am pretty sure you know Euclidean algorithm, which, basically, says $gcd(a,b)=gcd(|a-b|,b)$. Since $b$ is odd, and $|a-b|$ is even, $2$ divides the latter, but not the former, so that $gcd(|a-b|,b)=gcd(\frac{|a-b|}{2},b)$.
Vadim
- 5,637
0
If $\,d\mid b\,$ then $\,d\,$ is $\rm\color{#c00}{odd}$, so $\, d\mid a \!\iff\! d\mid a\!-\!b = \color{#c00}2(a\!-\!b)/2 \!\overset{\large\,\ d,\,\color{#c00}2\,\ \rm coprime}\iff\! d\mid(a\!-\!b)/2.\,$ So $\,a,b\,$ and $\,a,(a\!-\!b)/2\,$ have same set $S$ of common divisors $d,$ so same greatest common divisor $(= \max\ S)$
Remark $\ $ More generally, a similar proof shows $\,(cd,b) = (c(d,b),b).\,$ Your is the special case where $\,(d,b) = 1,\,$ viz. $\,d=2,\,\ b\,$ odd, $\,c = (a\!-\!b)/2.$
Bill Dubuque
- 272,048