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

I already proved that $$\gcd(a,b) \leq \gcd(a+b,a-b) \leq 2\gcd(a,b)$$. I need to prove that we have $$\gcd(a+b,a-b)=\gcd(a,b)$$ or $$\gcd(a+b,a-b)=2\gcd(a,b)$$.

I know this is true for when $$\gcd(a,b)=1$$, since when $$a,b$$ are of different parity, $$\gcd(a+b,a-b)=1$$ and when they both are odd, $$\gcd(a+b,a-b)=2$$. However, I am struggling to prove that this is true for any pair of integers $$a,b$$ where $$\gcd(a,b)>1$$.

Based on numerical results (obtained on Mathematica) I think if WLOG $$a$$ is odd, then $$\gcd(a+b,a-b)=2\gcd(a,b)$$ when $$b$$ is odd and $$\gcd(a+b,a-b)=\gcd(a,b)$$ when $$b$$ is even. My main trouble comes from when both $$a$$ and $$b$$ are even, since I can't seem to easily generalize the results based off what Mathematica gives me as an output.

Any suggestions/ideas on how to approach this problem would be greatly appreciated.

• – lhf
Oct 22, 2019 at 10:06

Factor out the gcd $$d = (a,b)$$ to reduce to coprime case:  let $$\,a = da', b = db'$$ so $$(a',b')=1\,$$ so

$$\ \ \ (a\!-\!b,a\!+\!b) = (da'\!-db',da'\!+db') = d(a'\!-b',a'\!+b') = d\,$$ or $$\,2d,\,$$ by coprime case

Alternatively apply the theorem below, whose short simple proof is here.

Theorem $$\$$ If $$\,(a,b)\overset{M}\mapsto (A,B)\,$$ is linear then $$\,\gcd(a,b)\mid \gcd(A,B)\mid \Delta \gcd(a,b),\,$$ $$\Delta = \det M$$

The OP is the special case $$A,B = a\!-\!b, a\!+\!b\,$$ so $$\,\Delta =2\,$$ which yields the sought result.

• I don't understand the notation you use in the statement of the theorem -- what is meant by the bars in $\gcd(a,b) | \gcd(A,B) | \Delta\gcd(a,b)$? Oct 22, 2019 at 23:52
• @moofasa $\ x\mid y\$ means $x$ divides $y\$ (standard number theory notation) Oct 23, 2019 at 0:30
• So do you mean $\gcd(a,b)\mid \gcd(A,B)$ and $\gcd(A,B) \mid \Delta \gcd(a,b)$ by that? Oct 23, 2019 at 1:41
• @moofasa Yes, similar to $\ a < b < c\ \ \$ Oct 23, 2019 at 3:35

Hint. Any number dividing $$a-b$$ and $$a+b$$ divides $$2b$$ and $$2a$$. (Adding ($$\pm$$) the two quantities)

Let do this: $$(a+b,a-b) = (a+b+a-b,a-b) = (2a,a-b) = \left\{\begin{array}{c} a-b \text{ Has More 2's than } a \\ a-b \text{ Has 2's At Most As } a \\ \end{array}\right\} \Longrightarrow$$ $$\Longrightarrow (2a,a-b) = \left\{\begin{array}{c} 2(a,a-b)=2(a,a-b-a)=2(a,-b)=2(a,b) \\ (a,a-b)=(a,a-b-a)=(a,-b)=(a,b) \\ \end{array}\right\}$$