3
$\begingroup$

This question already has an answer here:

Prove that if $a$ and $b$ are relatively prime, then $\gcd(a+b, a-b) = 1$ or $2$.

I started off by putting $\gcd(a+b, a-b) = d$. This implies that there are two relatively prime integers $x_1, x_2$, such that

$dx_1 = a+b$

$dx_2 = a -b$

Adding the first equation to the second gives us: $d(x_1 + x_2) = 2a$, and subtracting the second from the first gives us $d(x_1 - x_2) = 2b$. This implies that $d\mid2a, d\mid2b \implies \gcd(2a, 2b) = d \implies d = 2\cdot \gcd(a,b) \implies d = 2$.

This is based on the fact that $\gcd(x_1 + x_2, x_1 - x_2) = 1$, which is in fact the statement of the problem. How do I prove this? Can I somehow use the Euclidean Algorithm for this.

$\endgroup$

marked as duplicate by Martin Sleziak, Sahiba Arora, Xam, B. Goddard, Daniel Fischer Jul 29 '17 at 10:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ You don't necessarily have $\gcd (2a,2b) = d$, and $d = 1$ does happen. Use $\gcd (a+b,a-b) = \gcd(a+b,2b)$. If $p$ is a prime dividing $b$, can it divide $a+b$? $\endgroup$ – Daniel Fischer Aug 1 '13 at 14:52
  • $\begingroup$ If you have established that $d$ divides $2a$ and $2b$, then it follows that $d=1$ or $d=2$ as $a$ and $b$ are relatively prime. $\endgroup$ – Levon Haykazyan Aug 1 '13 at 14:54
  • 2
    $\begingroup$ The error in your proof is that $d|2a$ and $d|b$ is not that $\gcd(2a,2b)=d$ because you have proven only $d$ divides $2a$ and $2b$ but not that it is the greatest such number. So, what we do get is that $d|\gcd(2a,2b)=2\gcd(a,b)=2$. $\endgroup$ – OR. Aug 1 '13 at 14:58
  • $\begingroup$ @DanielFischer: I see your point. Excellent use of the Euclidean Algorithm. I would suggest you turn it into an answer. I'll accept it. $\endgroup$ – Gerard Aug 1 '13 at 15:05
12
$\begingroup$

HINT:

Let $d$ divides both $a+b$ and $a-b$

$\implies d $ divides $a+b+a-b=2a$ and $a+b-(a-b)=2b$

$\implies d $ divides $(2a,2b)=2(a,b)=2$

$\endgroup$
3
$\begingroup$

If $ax+by=1$ then $$\begin{align}2&=2ax+2by \\&=(a-b)x + (a+b)x + (b-a)y+(b+a)y \\&= (a-b)(x-y)+(a+b)(x+y)\end{align}$$

$\endgroup$
2
$\begingroup$

Here are two solutions that use the euclidean algorithm more directly:

(1) $\gcd(a+b,a-b) = \gcd(a+b,2a) \mid \gcd(2(a+b),2a) = \gcd(2b,2a) = 2·\gcd(b,a)$.

(2) $\gcd(a+b,a-b) = \gcd(a+b,2a) \mid \gcd(a+b,2)·\gcd(a+b,a) \mid 2·\gcd(b,a)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.