2
$\begingroup$

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.

$\endgroup$
1

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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)$? $\endgroup$ Oct 22, 2019 at 23:52
  • 1
    $\begingroup$ @moofasa $\ x\mid y\ $ means $x$ divides $y\ $ (standard number theory notation) $\endgroup$ Oct 23, 2019 at 0:30
  • $\begingroup$ So do you mean $\gcd(a,b)\mid \gcd(A,B)$ and $\gcd(A,B) \mid \Delta \gcd(a,b)$ by that? $\endgroup$ Oct 23, 2019 at 1:41
  • $\begingroup$ @moofasa Yes, similar to $\ a < b < c\ \ \ $ $\endgroup$ Oct 23, 2019 at 3:35
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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\} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .