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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.