4
$\begingroup$

Question:

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

My attempt:

First we prove $\gcd(a+b, a-b) = \gcd(2a, a-b)$.

Let $ d = \gcd(a+b, a-b)$ and $ \ e = \gcd(2a, a-b)$

$ d|a+b$ and $ \ d|a-b \implies \exists m,n \in \mathbb{Z}$ such that $ \ a+b = dm$ and $\ a-b = dn \implies a + a -dn = dm \implies 2a = dm + dn \implies 2a = d(m+n) \implies d|2a$

So, $ \ d|a-b$ and $ \ d |2a \implies d\le e$

$e|2a$ and $ \ e|a-b \implies \exists m,n \in \mathbb{Z}$ such that $ \ 2a = em$ and $\ a-b = en \implies 2a - (a-b) = a + b = em-en = e(m-n) \implies e|(a+b)$

So, $ \ e|(a-b)$ and $ \ e |(a+b) \implies e\le d$

Hence $ e =d$

Similarly, if I prove that $\gcd(a+b, a-b) = \gcd(a+b, 2b)$, will the proof be complete?

I am not quite sure if this is the correct way to prove the problem. My professor used a similar approach to prove that $ \ \gcd(a,b) = \gcd( a- kb, b)$.

$\endgroup$
1
$\begingroup$

Your approach is correct. However a few steps can be shortened.

Let $d=\gcd(a+b,a-b)$, then $d | a+b$ and $d | a-b$, thus $d$ divides all linear combinations of $a+b$ and $a-b$, in particular $d|(a+b)-(a-b)=2b$ and $d|(a+b)+(a-b)=2a$. Thus $d$ divides both $2a$ and $2b$.

Now you can take it from here.

$\endgroup$
2
  • $\begingroup$ Now I have to prove if $ d| 2a $ and $d|a-b$ then $d|a+b$ and $d|a-b$. Then, I have to prove if $d|a+b$ and $d|2b$ then $d|a+b$ and $d|a-b$. Am i right? $\endgroup$ – user444945 Aug 5 '17 at 18:29
  • $\begingroup$ @JoshMitkitzel That sounds as the right approach. Just use a different letter than $d$ for each of those GCDs. $\endgroup$ – Anurag A Aug 5 '17 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy