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

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

-

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\text{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 | a+b, a-b$, then $d | (a+b)+(a-b) = 2a$ and $d | (a+b)-(a-b) = 2b$ so $d | \text{gcd}(2a,2b) = 2$.

-
Great! I had to think a little about your prove but hopefully now I got it. Thx again... –  Woltan Apr 13 '11 at 13:02

This holds true simply because $2$ is the determinant of the linear map $\rm\: (x,y)\to (x-y,\ x+y)\:.\:$ More generally, inverting a linear map by Cramer's Rule (multiplying by the adjugate) yields

$$\rm\begin{pmatrix} a & \rm b \\\\ \rm c & \rm d \end{pmatrix}\ \begin{pmatrix} x \\\\ \rm y \end{pmatrix}\ =\ \begin{pmatrix} X \\\\ \rm Y\end{pmatrix}\ \ \ \Rightarrow\ \ \ \begin{array} \rm\Delta\ x\ \ \ =\ \ \ \rm d\ X - b\ Y \\\\ \rm\Delta\ y\ =\ \rm -c\ X + a\ Y \end{array}\ ,\quad\quad \Delta\ =\ ad-bc$$

Therefore $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y)\:.$

So, 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\:.$

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

-

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

-

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

Notice $\rm\ n\ |\ a-b,\ a+b\ \Rightarrow\ n\ |\ a-b + (a+b)\ i\ =\ (1+i)\ (a+b\ i)\$

Hence $\rm\ n\ |\ (1-i)\ (1+i)\ (a+bi)\:,\$ i.e. $\rm\ n\ |\ 2\ (a+b\ i)\$ so $\rm\ n\ |\ 2\$ since $\rm\ (a,b) = 1\:$

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

Compare this approach to that in my other answer: here we employ the norm $\rm\ N(2+3\ i) = 13\$ vs. there we employ the determinant $= 13\:$ of the linear map $\rm\ x\to (2+3\ i)\ x\:.$

-

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.

-