SOLUTION: Show that every two successive terms of the Fibonacci sequence are relatively prime by induction

Algebra ->  Test -> SOLUTION: Show that every two successive terms of the Fibonacci sequence are relatively prime by induction      Log On


   

Question 495491: Show that every two successive terms of the Fibonacci sequence are relatively prime by induction
Answer by richard1234(7193) About Me  (Show Source):
You can put this solution on YOUR website!
The base cases are true.

Assume that for some n>2 that and are relatively prime, and we want to show that and are also relatively prime. By definition,

.

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.