document.write( "Question 408264: Show 5n+3 and 7n+4 are relatively prime for all n \n" ); document.write( "
Algebra.Com's Answer #287692 by richard1234(7193)\"\" \"About 
You can put this solution on YOUR website!
Suppose that there exists some k such that 5n + 3 ≡ 7n + 4 ≡ 0 (mod k). If this is the case, then the difference between 7n + 4 and 5n + 3 must also be 0 mod k, i.e.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "2n + 1 ≡ 5n + 3 (mod k), in addition (5n + 3) - (2n + 1) ≡ 0, so\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "3n + 2 ≡ 0 (mod k)\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "6n + 4 ≡ 0 (mod k)\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "This implies 6n + 4 ≡ 7n + 4 ≡ 0 (mod k) so n ≡ 0 (mod k). However, if n ≡ 0 (mod k), then 5n + 3 ≡ 3 (mod k) and 7n + 4 ≡ 4 (mod k) so this implies that 3 ≡ 4 (mod k), contradiction (unless k = 1). Hence, 5n + 3 and 7n + 4 are relatively prime (for all integers n).\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "I kinda feel like there's a shorter way to prove this...care to find another solution?\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );