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!