SOLUTION: Show for integers a,b and k that gcd(a,b)=gcd(a,b+ka).

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

RELATED QUESTIONS
How do i show for intergers a, b and k that gcd(a,b)= gcd(a,b+ka). Thank... (answered by venugopalramana)

Show for intergers a,b and k that gcd(a,b)=gcd(a,b+ka). PLEASE NEED HELP WITH THIS... (answered by venugopalramana)

Show that gcd(a,gcd(b,c))=gcd(gcd(a,b),c) Ie show that gcd operator is associative (answered by Edwin McCravy)

How do i show for intergers a,b and c from which at most one is 0(zero):... (answered by venugopalramana)

Given that a * b = 270 and GCD(a,b)=5, find LCM... (answered by jim_thompson5910)

I can see that it's true but how can I prove that ab=gcd(a,b)lcm(a,b) for any postive... (answered by AnlytcPhil)

Hello! I have problems proving that if {{{GCD (a, b) = 1}}} then {{{GCD (a * c, b) =... (answered by aaaaaaaa)

Give the gcd(a,b) and integral linear combination of a and b a=30031 and b=12449 I... (answered by venugopalramana)

I do not even know where to start with this proof. Prove or disprove: let a, b, and c... (answered by ikleyn)