Thursday, June 27, 2019

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



I started by saying that $\gcd(a,b) = d_1$ and $\gcd(a+b,\gcd(a,b)) = d_2$



Then I tried to show that $\ d_1 \ge d_2, d_1 \le d_2$.



I know that $\ d_2 | \gcd(a+b, d_1)$ hence $\ d_2 \le d_1 $.



How do I prove that $\ d_2 \ge d_1$ ?


Answer




If $\gcd(a,b)=d_1$ then $a = d_1 x$ and $b= d_1 y$, where $x,y$ are integers. Consequently,
$$\gcd(a+b,\gcd(a,b))=\gcd(d_1(x+y),d_1) = d_1\gcd(x+y,1)=d_1.$$


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