|
Question 26115: Show for integers a,b and k that gcd(a,b)=gcd(a,b+ka).
Answer by venugopalramana(3286)   (Show Source):
You can put this solution on YOUR website! Show for intergers a,b and k that gcd(a,b)=gcd(a,b+ka).
LET GCD OF A AND B BE G
HENCE G|A AND G|B....THAT IS A=GA1.....AND B=GB1.....WHERE A1 AND B1 ARE INTEGERS RELATIVELY PRIME TO EACH OTHER..THAT IS GCD OF A1 AND B1 IS 1.
NOW WE HAVE
B+KA=GB1+KGA1=G(B1+KA1)...SINCE B1,A1 AND K ARE INTEGERS,THIS MEANS
G|(B+KA)...SO G|A AND G|(B+KA)...SO G IS A COMMON DIVISOR OF A AND B+KA
NOW TO SHOW THAT IT IS THE GREATEST INTEGER OR A1 AND B1+KA1 ARE RELATIVELY PRIME TO EACH OTHER.WE KNOW ALREADY A1 AND B1 ARE PRIME TO EACH OTHER.HENCE ONLY IF K IS A MULTIPLE OF B THEN ONLY B1+KA1 CAN HAVE A COMMON FACTOR OF GB1 OR ITS MULTIPLE WHICH IS DEFINITELY MORE THAN G.HENCE WE HAVE
A=GA1
AND IF K=B1 OR NB1 THEN
B+KA COULD BE =GB1(1+A1)...OR.....GB1(1+NA1)
BUT GB1 CANNOT DIVIDE A SINCE A1=A/G IS ALREADY PRIME TO B1.HENCE THE RESULT
|
|
|
| |
