document.write( "Question 1068315: I do not even know where to start with this proof.\r
\n" ); document.write( "\n" ); document.write( "Prove or disprove: let a, b, and c be integers such that a and b are relatively prime and c divides a+b. Prove that gcd(a,c)=gcd(b,c)=1. \n" ); document.write( "

Algebra.Com's Answer #683545 by ikleyn(52781) $\"\"$ $\"About$

You can put this solution on YOUR website!
.
\n" ); document.write( "I do not even know where to start with this proof.\r
\n" ); document.write( "\n" ); document.write( "Prove or disprove: let a, b, and c be integers such that a and b are relatively prime and c divides a+b. Prove that gcd(a,c)=gcd(b,c)=1.
\n" ); document.write( "~~~~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "I will prove the firs statement gcd(a,c) = 1, leaving the second to you.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "Let assume that GCD(a,c) = d > 1.   (GCD is the Greatest Common Divisor).\r\n" );
document.write( "\r\n" );
document.write( "Then d divides both \"a\" and \"c\".                    (*)\r\n" );
document.write( "\r\n" );
document.write( "Since \"c\" divides a+b, then \"d\" divides a+b too.    (**)\r\n" );
document.write( "\r\n" );
document.write( "Now, we have that \"d\" divides \"a\" (Line *) and \"d\" divides a+b (Line **).\r\n" );
document.write( "\r\n" );
document.write( "It implies that \"d\" divides both \"a\" and \"b\".\r\n" );
document.write( "\r\n" );
document.write( "It contradicts to the given fact that \"a\" and \"b\" are relatively simple.\r\n" );
document.write( "\r\n" );
document.write( "Hence, the initial assumption  GCD(a,c) = d > 1  is WRONG.\r\n" );
document.write( "\r\n" );
document.write( "It means GCD(a,c) = 1.\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "When solving such problems, the major move is to make the first step.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );