# Using Bezouts Lemma to prove $\gcd(a,b)=\gcd(a, a+2b)$ where $a$ is odd

So I have the following case:

Suppose $a,b \in \mathbb Z$ where $a$ is odd. Prove that $\gcd(a,b)=\gcd(a, a+2b)$

Here is what I have:

Since $a$ is odd, $a = 2k+1, k \in \mathbb Z$.

By Bezouts Lemma, $\exists \space f, g \in \mathbb Z$ such that $\gcd(2k+1,2b) = f(2k+1) + g(b)$

Similarily by Bezouts Lemma, $\exists \space m, n \in \mathbb Z$ such that $\gcd(2k+1,2k+1+2b) = (2k+1)(m) + (2k+1+2b)(n)$

$=2km+m+2kn+n+2bn$

$= 2k(m+n) + (m+n) + 2bn$

$= (m+n)(2k+1) + 2n(b)$

Thus if $f = m+n$ and $2n=g$, $\gcd(a,b)=\gcd(a, a+2b)$

Is this ok? Can I just say that if $f = m+n$ and $g=2n$ then the gcd's will match? Or am I missing a step?

I think you have proved the easier direction but not the whole statement.

First, by Bézout's lemma, $\exists m, n \in \mathbb{Z}$ such that $\gcd(a, a + 2b) = am + (a + 2b)n$

$\implies am + (a + 2b)n = a(m + n) + b(2n)$

So $\gcd(a, b) \mid \gcd(a, a + 2b)$

This is essentially what you have proved. Note that you still have to prove $\gcd(a, a + 2b) \mid \gcd(a, b)$

Again by Bézout's lemma, $\exists x, y \in \mathbb{Z}$ such that $\gcd(a, 2b) = ax + 2by$

$\implies ax + 2by = ax + 2by = ax - ay + ay + 2by = a(x - y) + (a + 2b)y$

So $\gcd(a, a + 2b) \mid \gcd(a, 2b)$

Observe that if we can show $\gcd(a, b) = \gcd(a, 2b)$, then $\gcd(a, a + 2b) \mid \gcd(a, b)$

It suffices to show $\{$common divisors of $a, b\} = \{$common divisors of $a, 2b\}$

Take any $c \mid a, b$

We have $c \mid a$ and $c \mid b \mid 2b$

Conversely, take any $c \mid a, 2b$

Since $a$ is odd, $c$ being a divisor of $a$ must be odd

So $c$ and $2$ are coprime

By Euclid's lemma, $c \mid 2b \implies c \mid b$

We have $c \mid a$ and $c \mid b$

We conclude $\{$common divisors of $a, b\} = \{$common divisors of $a, 2b\}$

So $\gcd(a, b) = \max \{$common divisors of $a, b\} = \max \{$common divisors of $a, 2b\} = \gcd(a, 2b)$

Finally, since $\gcd(a, b) \mid \gcd(a, a + 2b)$ and $\gcd(a, a + 2b) \mid \gcd(a, b)$, we obtain $\gcd(a, b) = \gcd(a, a + 2b)$

Hope this help!