$\gcd(a,b) = \gcd(a, a+2b)$ where $a$ is an odd integer

Question

$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

Answer 1

If $d\mid a$ and $d\mid b$, then $d\mid a+2b$.

Now, suppose that $d\mid a$ and that $d\mid a+2b$. Then $d\mid2b$. But $d\mid a$ and $a$ is odd. Therefore, $d$ is odd. Since $d$ is odd and $d\mid2b$, $d\mid b$.

So, I proved that $d$ is a common divider of $a$ and $b$ if and only if $d$ is a common divider of $a$ and $a+2b$. In particular, the pairs $(a,b)$ and $(a,a+2b)$ have the same greatest common divider.

Answer 2

If $d$ is a divisor of $a$ and $a+2b$, first it is odd and, second, it is a divisor of $a+2b-a=2b$. As $d$ is odd, it is coprime with $2$, so by Gauß' lemma, it divides $b$.

Answer 3

Do you know that $\gcd (a,b) = \gcd(a, b \pm ka)$ for any integer $k$?

So $\gcd(a, a+ 2b) = \gcd(a, (a + 2b) -a) = \gcd(a,2b)$.

And do you know that if $\gcd(a, m) = 1$ then $\gcd(a,mb) = \gcd(a, b)$?

So as $a$ is odd, $\gcd(a,2) = 1$ so $\gcd(a,2b) = \gcd(a,b)$.

.... So do you know those facts? They are easy to prove.

Answer 4

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 $$