$a$ and $b$ are integers where $a$ is odd prove that $\gcd(a,b) = \gcd(a, a+2b)$
I know from $\gcd$ and divisibility of integer combinations that $\gcd(a,b)=d$
and that $d\mid a$ and $d\mid(a+2b)$, therefore $d$ is a common divisor of $a$ and $a+2b$. I'm having trouble with using the fact that $a$ is odd, and how to show that $d$ is the greatest common divisor. Thanks
Best Answer
Because $a$ is odd, there are $u,v\in\mathbb{Z}$ so that $$ au+2v=1\tag1 $$ Let $g=(a,b)$, then there are $x,y\in\mathbb{Z}$ so that $$ ax+by=g\tag2 $$ Multiplying $(1)$ and $(2)$ yields $$ a(aux+2vx+uby)+2bvy=g\tag3 $$ and then adding $avy-avy=0$ gives $$ a(aux+2vx+uby-vy)+(a+2b)vy=g\tag4 $$ So we know that $(a,a+2b)\mid g$; however, $g\mid a$ and $g\mid a+2b$, therefore, $$ (a,a+2b)=g=(a,b)\tag5 $$