document.write( "Question 849358: 3. Prove that if n is odd, then gcd(3n; 3n + 2) = 1. What if n is even? \n" ); document.write( "

Algebra.Com's Answer #511499 by Edwin McCravy(20059) $\"\"$ $\"About$

You can put this solution on YOUR website!
3. Prove that if n is odd, then gcd(3n; 3n + 2) = 1
\n" ); document.write( "

\r\n" );
document.write( "Let gcd(3n; 3n + 2) = d\r\n" );
document.write( "\r\n" );
document.write( "Since n is odd, n=2p-1 for some positive integer p\r\n" );
document.write( "\r\n" );
document.write( "3n = 3(2p-1) = 6p-3 = ad for some positive integer a \r\n" );
document.write( "\r\n" );
document.write( "3n+2 = 6p-3+2 = 6p-1 = bd for some positive integer b,  b > a\r\n" );
document.write( "\r\n" );
document.write( "6p = ad+3 = bd+1\r\n" );
document.write( "\r\n" );
document.write( "bd-ad = 2\r\n" );
document.write( "\r\n" );
document.write( "d(b-a) = 2\r\n" );
document.write( "\r\n" );
document.write( "d = 2/(b-a), so b-a is either 1 or 2 \r\n" );
document.write( "\r\n" );
document.write( "b-a = 2,  since the common divisor of two odd numbers cannot be even.\r\n" );
document.write( "\r\n" );
document.write( "Thus d = 2/2 = 1\r\n" );
document.write( "\r\n" );
document.write( "-----------------------------

\n" ); document.write( "What if n is even?

Let gcd(3n; 3n + 2) = d\r\n" );
document.write( "\r\n" );
document.write( "Since n is even, n=2a for some positive integer p\r\n" );
document.write( "\r\n" );
document.write( "3n = 3(2p) = 6p = ad for some positive integer a \r\n" );
document.write( "\r\n" );
document.write( "3n+2 = 6p+2 = bd for some positive integer b,  b > a\r\n" );
document.write( "\r\n" );
document.write( "6p = ad = bd-2\r\n" );
document.write( "\r\n" );
document.write( "bd-ad = 2\r\n" );
document.write( "\r\n" );
document.write( "d(b-a) = 2\r\n" );
document.write( "\r\n" );
document.write( "d = 2/(b-a), so b-a is either 1 or 2 \r\n" );
document.write( "\r\n" );
document.write( "b-a = 1,  since the common divisor of two even numbers must be even.\r\n" );
document.write( "\r\n" );
document.write( "Thus d = 2/1 = 2\r\n" );
document.write( "\r\n" );
document.write( "Edwin

\n" ); document.write( "

\n" );