Prove $\gcd(a+b, a-b) = 1$ or $2\,$ if $\,\gcd(a,b) = 1$

Question

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds.

I think the first step should look something like this:

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

From here I tried to proceed with two cases.
1: $a-b$ is even, which leads to $\gcd(a+b, a-b) = 2$
2: $a-b$ is odd, which leads to $\gcd(a+b, a-b) = 1$

My main problem I think is, that I do not know how I should include $\gcd(a,b) = 1$ in the proof.

Any help is appreciated. Thx in advance.
Cherio Woltan

Answer 1

Let $d$ be a common divisor of $a+b$ and $a-b$, then $d$ divides their sum $2a$ and difference $2b$. If a number divides two numbers it also divides their gcd, thus $d$ divides $2\gcd(a,b) = 2$. That implies that every divisor (including the greatest common divisor) is a divisor of $2$.

---

The same argument again in symbols:

Let $d \mid a+b, a-b$, then $d \mid (a+b)+(a-b) = 2a$ and $d \mid (a+b)-(a-b) = 2b$ so $d \mid \gcd(2a,2b) = 2$.

Answer 2

Hint $\, \ \begin{vmatrix} \rm \color{#0af}{x\!+\!y} & \rm u\!+\!v \\ \rm \color{#0af}{x\!-\!y} & \rm u\!-\!\,v\end{vmatrix}\,$ $=\, \color{#0a0}{\begin{vmatrix} 1 & 1 \\ -1 & 1\end{vmatrix}}$ $\begin{vmatrix}\rm y &\rm v \\ \rm x &\rm u\end{vmatrix}\ $ and $\rm \ \overbrace{\color{#c00}1 = u\,y\!-\!v\,x}^{\text Bezout},\,$ by $\rm\,1=\gcd(x,y)\,$

take $\,\rm det\Rightarrow (u\!-\!v)(\color{#0af}{x\!+\!y})-(u\!+\!v)(\color{#0af}{x\!-\!y}) = \color{#0a0}2\cdot\color{#c00}1$ $\rm \Rightarrow \gcd(\color{#0af}{x\!+\!y,x\!-\!y}) \mid\color{#0a0}2$

i.e. it's true simply because $\,\color{#0a0}{\Delta \!=\! 2}=$ determinant of linear map $\rm\: (x,y)\,\mapsto\, (\color{#0af}{x\!-\!y,\, x\!+\!y}).\,$

---

Generally inverting linear $\rm (x,y)\overset{A}\mapsto (X,Y)$ by Cramer's Rule, i.e. $\rm\color{0a0}{scale}$ by $\rm\color{#c00}{adjugate},\,$ yields

$$\begin{align} \rm\color{#c00}{\begin{bmatrix}\rm\ \, d &\!\!\! \rm -b \\ \!\!\rm -c & \rm a \end{bmatrix}} \color{#0a0}\times&\, \left\{\, \begin{bmatrix}\rm a & \rm b \\ \rm c & \rm d \end{bmatrix} \begin{bmatrix} \rm x \\ \rm y \end{bmatrix} \,=\, \begin{bmatrix}\rm X \\ \rm Y\end{bmatrix}\, \right\}\\[.2em] \Longrightarrow\!\!\!\!\!\!\!\!\!\!\!\!\! &\,\qquad\qquad\, \begin{array}\ \rm\Delta\ x\ =\, \ \ \rm \color{#c00}d\ X \color{#c00}{- b}\ Y \\ \rm\Delta\ y\ = \rm \color{#c00}{-c}\ X + \color{#c00}a\ Y \end{array}^{\phantom{|}} ,\ \ \ \ \rm \Delta\ :=\ \color{#c00}{ad-bc} \end{align}\qquad$$

Hence $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\,x,\Delta\,y\ \Rightarrow\ n\ |\ gcd(\Delta\,x,\Delta\,y)= \Delta\ gcd(x,y)\,$ by here & here.

In particular, if $\rm\:gcd(x,y) = 1\:$ and $\rm\,\Delta\,$ is prime, we conclude that $\rm\:gcd(X,Y) = 1\:$ or $\rm\:\Delta$.

Your problem is simply the special case $\rm\ a = c = d = 1,\ b = -1\ \Rightarrow\ \Delta = ad\!-\!bc = 2$.

Remark $ $ By above we infer $\rm \,n:=\gcd(X,Y)\mid \Delta \gcd(x,y).\,$ Further we have $\rm\ \gcd(x,y)\mid X,Y\,\Rightarrow\, \gcd(x,y)\mid \gcd(X,Y)^{\phantom{|^|}}$ hence

Theorem $\rm\,\ (x,y)\overset{A}\mapsto (X,Y)\,$ linear $\,\Rightarrow\, \bbox[7px,border:1px solid #c00]{\rm\gcd(x,y)\mid \gcd(X,Y)\mid det(A) \gcd(x,y)}$

Worth emphasis: this has a nice arithmetical interpretation in Gaussian integer arithmetic, where the linear map is simply multiplication by $\rm 1 + \it i.\:$ See my other answer here for details.

The above can also be viewed more geometrically in terms of lattices.

Answer 3

Here's a computational proof, similar to the second proof quanta gave. Since $(x,y) = 1$, there are integers $a,b$ such that $ax+by = 1$. Therefore $$ (a+b)(x+y) + (a-b)(x-y) = 2ax + 2by = 2. $$ Thus $(x+y,x-y)\mid 2$.

Answer 4

As I mentioned in a similar question, this is obvious when viewed in Gaussian integer arithmetic.

$$\begin{align}\rm Notice\quad &\rm n\mid a\!-\!b,a\!+\!b\, \Rightarrow\, n\mid a\!-\!b + (a\!+\!b)\ {\it i} = (1\!+\!{\it i})\ (a\!+\!b\, {\it i}),\,\ {\rm so}\,\ n,a,b\in\Bbb Z\\[0.7em] \rm\implies \quad &\rm n\mid \underbrace{(1\!-\!{\it i})\ (1\!+\!{\it i})}_{\large\color{#c00} 2}\, (a\!+\!b\,{\it i})\, \Rightarrow\, n\mid 2a,2b\,\Rightarrow\, n\mid (2a,2b)\!=\!2(a,b) \!=\! \color{#c00}2 \end{align}$$

Remark $\, $ Compare to the method in my other answer: $ $ here we employ the norm $\rm\, N(1 + {\it i}) = \color{#c00}2\ $ vs. there we employ the determinant $ = \color{#c00}2\:$ of the linear map $\rm\ x\to (2+3\ {\it i})\ x$.

Obviously we can generate infinitely many similar exercises by replacing $\rm\ 1+{\it i}\ $ by any nonreal Gaussian integer. For example, via $\rm\ (2+ 3\ {\it i})\ (a+b\ {\it i})\, =\, 2a-3b + (3a+2b)\ {\it i}\ $ we deduce the analogous divisibility result that if $\rm\ gcd(a,b) = 1\ $ then $\rm\ gcd(2a-3b,\, 3a + 2b) = 1\,$ or $\,\color{#c00}{13}.$

Answer 5

If $\gcd (a,b)=1$, then both $a$ and $b$ can't be even simultaneously. Now two cases arise, Case $1$. Both $a$ and $b$ are odd In this case, both $a+b$ and $a-b$ will be even, so their gcd must be an even number, and so $\gcd (a+b, a-b) = \gcd (2a, a-b) = 2$, as $a-b$ is even. Case $2$. One of the $a$ and $b$ is even and the other is odd In this case, both $a+b$ and $a-b$ will be odd, so their $\gcd$ must be an odd number, and in this case $\gcd (a+b, a-b) = \gcd (2a, a-b) = 1$, as $a-b$ is odd. Note: $\gcd (a, a-b)$ can't exceed $1$ as $a$ and $b$ are relatively prime.