Saturday, December 24, 2016

elementary number theory - Prove that$gcd(a+b, a-b) = gcd(2a, a-b) = gcd(a+b, 2b) $



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


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...