Prove $\gcd(a+b, a-b) = 1$ or $2\,$ if $\,\gcd(a,b) = 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$.

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

This is true simply because $\,\Delta = 2\,$ is the determinant of the linear map $\rm\: (x,y)\,\mapsto\, (x\!-\!y,\, x\!+\!y).\:$ More generally, inverting a linear map by Cramer's Rule, i.e. $\rm\color{#0a0}{scaling}$ by the $\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.

I advise not doing a proof by cases. That was my initial attempt, but I found myself going through a logical rabbit hole with no end in sight. I suggest attempting to show that the common divisor, call it $d$, satisfies $d\leq2$, which implies that $d=1$ or $2$.

Here is a proof using the above strategy. Here are a few lemmas that will assist us in our deductions.

I adopt the notation $\gcd(a,b) = (a,b)$.

$\enspace$$\enspace$Lemma 1 If $a \mid b$ and $b\neq0$, then $|a| \leq |b|$

$\enspace$$\enspace$Lemma 2 If $a \mid b$ and $a \mid c$, then for every integer $m$ and $n$, $a\mid(mb+nc)$

$\enspace$$\enspace$Lemma 3 For every integer $a$,$b$ and $c$, $(a+bc,b)=(a,b)$

$\enspace$$\enspace$ Lemma 4 For every integer $a$ and $b$, if $(a,b)=1$, there are integers $x$ and $y$ such that $ax+by=1$

Now for the proof.

Proof: Suppose $(a,b)=1$. Then from lemma 4, there are integers $x$ and $y$ such that

$$ax+by=1 \tag{1}$$

Let $d=(a+b,a-b)$ (Recall that $d>0$ by definition.

From lemma 3, we can write

$$d=(2a,a-b)$$ $$d=(2b,a-b)$$

Since $d$ is the greatest common divisor of $2a$, $a-b$, and $2b$, it follows that $d$ also divides each of them. In particular, $d\mid 2a$ and $d\mid2b$. Hence, from lemma 2, we know that $d\mid(2am+2bn)$ for arbitrary integers $m$ and $n$.

By lemma 1, we can translate $d\mid(2am+2bn)$ into the inequality

$$d \leq 2(am+bn) \tag{2}$$

Since equation $(2)$ is true for every integer $m$ and $n$, we can allow $m$ and $n$ to represent particular integers by universal instantiation*

In our case, let $m=x$ and $n=y$. Then $am+bn = ax+by$, which allows us to conclude from $(1)$ that $am+bn = 1$.

Therefore, we substitute $am+bn=1$ into $(2)$ to conclude that

$$d \leq 2 \tag{3}$$

which implies that $d=1$ or $d=2$.

• Universal instantiation is the rule of inference that allows us to conclude that a proposition for a particular element in a domain is true given that that the statement is true for every element in the domain. For example, if the statement, "All women are wise" is true, then the statement "Kaity is wise" is also true.

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.