document.write( "Question 408264: Show 5n+3 and 7n+4 are relatively prime for all n \n" ); document.write( "
Algebra.Com's Answer #287749 by Edwin McCravy(20063)\"\" \"About 
You can put this solution on YOUR website!
\r\n" );
document.write( "You could use Euclid's algorithm:\r\n" );
document.write( "\r\n" );
document.write( "Euclid's algorithm for gcd states if a and b are positive \r\n" );
document.write( "integers and all qi and ri are non-negative integers then if\r\n" );
document.write( "\r\n" );
document.write( " a = q0b + r0 \r\n" );
document.write( " b = q1r0 + r1 \r\n" );
document.write( "r0 = q2r1 + r2 \r\n" );
document.write( "r1 = q3r2 + r3\r\n" );
document.write( "...\r\n" );
document.write( "rk-3 = qk-1rk-2 + rk-1\r\n" );
document.write( "rk-2 = qkrk-1 + rk\r\n" );
document.write( "\r\n" );
document.write( "where if rk = 0 then gcd(a,b) = rk-1.\r\n" );
document.write( "\r\n" );
document.write( "7n+4 = 1(5n+3) + (2n+1)\r\n" );
document.write( "5n+3 = 2(2n+1) + (n+1)\r\n" );
document.write( "2n+1 = 1(n+1) + 1\r\n" );
document.write( " n+1 = 1(n+1) + 0\r\n" );
document.write( "\r\n" );
document.write( "So gcd(7n+4,5n+3) = 1\r\n" );
document.write( "\r\n" );
document.write( "Edwin
\n" ); document.write( "
\n" );