Thursday, June 27, 2019

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



I started by saying that gcd 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...