document.write( "Question 26115: Show for integers a,b and k that gcd(a,b)=gcd(a,b+ka). \n" ); document.write( "

Algebra.Com's Answer #14181 by venugopalramana(3286) $\"\"$ $\"About$

You can put this solution on YOUR website!
Show for intergers a,b and k that gcd(a,b)=gcd(a,b+ka).
\n" ); document.write( "LET GCD OF A AND B BE G
\n" ); document.write( "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.
\n" ); document.write( "NOW WE HAVE
\n" ); document.write( "B+KA=GB1+KGA1=G(B1+KA1)...SINCE B1,A1 AND K ARE INTEGERS,THIS MEANS
\n" ); document.write( "G|(B+KA)...SO G|A AND G|(B+KA)...SO G IS A COMMON DIVISOR OF A AND B+KA
\n" ); document.write( "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
\n" ); document.write( "A=GA1
\n" ); document.write( "AND IF K=B1 OR NB1 THEN
\n" ); document.write( "B+KA COULD BE =GB1(1+A1)...OR.....GB1(1+NA1)
\n" ); document.write( "BUT GB1 CANNOT DIVIDE A SINCE A1=A/G IS ALREADY PRIME TO B1.HENCE THE RESULT\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );