document.write( "Question 495491: Show that every two successive terms of the Fibonacci sequence are relatively prime by induction \n" ); document.write( "

Algebra.Com's Answer #336242 by richard1234(7193) $\"\"$ $\"About$

You can put this solution on YOUR website!
The base cases are true.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Assume that for some n>2 that

and

are relatively prime, and we want to show that

and

are also relatively prime. By definition,\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "For any prime p satisfying

(mod p), it is apparent that

(mod p), because the nth and (n-1)th terms have no common factor other than 1. Hence, their sum

(mod p) for all p|(F_n) so we are done. \n" ); document.write( "

\n" );