Suppose $a$ is odd and $b$ is even. Prove that $\operatorname{gcd}(a,b) = \operatorname{gcd}(a+b, a-b)$.

Question

This question originates from Pinter's Abstract Algebra, Chapter 22 Exercise E1.

Let $a$ and $b$ be integers. Suppose $a$ is odd and $b$ is even. Prove that $\operatorname{gcd}(a,b) = \operatorname{gcd}(a+b, a-b)$.

Attempt:

Let $d=\operatorname{gcd}(a,b)$ and $d' = \operatorname{gcd}(a+b,a-b)$.

1. Given $a$ is odd and $b$ is even, $d, a+b, a-b$ and $d'$ must all be odd, for the sum or difference of an odd and even number is an odd number, and the common factor of an odd and even number is an odd number.
2. By Theorem 3 in Chapter 22, $d=\operatorname{gcd}(a,b)$ iff $ax+by=d$ for some integers $x$ and $y$. This implies $ax$ is odd, which implies $x$ is odd, for otherwise $d$ would be even contradicting (1).
3. $d' = \operatorname{gcd}(a+b,a-b)$ iff \begin{align*} (a+b)x' + (a-b)y' &= d' & \text{for some }x',y'\in\mathbb{Z} \\ a(x'+y') + b(x'-y') &= d' \\ \implies &d = d' \end{align*} for there exists a unique non-negative generator in the principal ideal of all the linear combinations of $a$ and $b$ (by the proof of Theorem 3 in Chapter 22). In particular, observe that \begin{align*} x &= x' + y' \\ y &= x' - y' \\ x - y &= 2y' \end{align*} $x$ is odd by (2) so $y$ must be odd, for otherwise $x-y$ would not be divisible by 2.

Does this look reasonable?

Answer 1

I think you are over-complicating things. First of all, your statement that $d = \gcd(a,b)$ iff $ax+by = d$ is incorrect. The correct statement is that $d = \gcd(a,b)$ iff $d$ is the smallest positive integer that can be written in the form $ax+by = d$, for some integers $x,y$.

Now, to prove the statement that you wanted to prove, you can argue as follows:

Let $d = \gcd(a,b)$ and $d'= \gcd(a+b, a-b)$.

• First, note that $d|a$ and $d|b$, so $d|(a+b)$ and $d|(a-b)$. So, $d|d'$.
• Second, note that $d'|(a+b)$ and $d'|(a-b)$, so $d'|(a+b+a-b) \Leftrightarrow d'|2a$, and similarly $d'|2b$. But, as you correctly argued above, $a+b$ and $a-b$ are both odd, so $d'$ is also odd. Thus, $\gcd(d',2) = 1$. Given this, $d'|2a$ implies that $d'|a$ and similarly $d'|b$. Thus, $d'|d$.

Now, you have that $d'|d$ and $d|d'$, which can only happen if $d'= d$.

Answer 2

I am not so sure about youre theorem 3 p.22. I think it is only : $d=gcd(a,b) \Rightarrow \exists x,y \in \mathbb{Z}$ s.t. $ax+by=d$ (since else you say that all multiple of $d$ is equal to $gcd(a,b)$ since if $ax+by=d$ then $a(nx)+b(ny)=nd$ for all $n \in \mathbb{Z}$...).

This is how I did it : As you stated $d,d'$ are odd. Moreover $a,b \in (d)$ and $d$ is minimal for this property (we suppose $d$ positive of course), and $a-b,a+b \in (d')$ and $d'$ is minimal for this property.

Since $(d)$ is a group, we have $a+b,a-b \in (d)$. So $d'\leqslant d$.

Since $(d')$ is a group, we have $a+b+a-b=2a \in (d')$. For the same reason $2b \in (d')$. But since $d'$ is odd, this implies $a\in (d')$ and $b \in (d')$. So $d\leqslant d'$.

Finally $d=d'$.