|
Question 25736: How do i show for intergers a, b and k that gcd(a,b)= gcd(a,b+ka).
Thank You
Answer by venugopalramana(3286)   (Show Source):
You can put this solution on YOUR website! How do i show for intergers a, b and k that gcd(a,b)= gcd(a,b+ka).
LET GCD(A,B+KA)=D
HENCE D=AX+(B+KA)Y...WHERE X AND Y ARE INTEGERS.
D=A(X+KY)+BY..SINCE K IS AN INTEGER,X+KY IS AN INTEGER.
SO D IS THE GCD OR MULTIPLE OF GCD OF A AND B.
IF WE ASSUME GCD(A,B)=G...
THEN G|D..........................................I
SIMILARLY,SINCE GCD(A,B)=G WE GET
G=PA+QB...WHERE P AND Q ARE INTEGERS
G=PA-KAQ+QB+KAQ=A(P-KQ)+Q(B+KA).....(P-KQ) AND Q ARE INTEGERS.
SO G IS THE GCD OR MULTIPLE OF GCD OF A AND B+KA
HENCE D|G.......................................II
I AND II CAN BE TRUE ONLY IF D=G...PROVED
|
|
|
| |
