Thread: prove any 2 successive terms of fibonacci sequence are relatively prime

for the fibonacci sequuence, show that (x_(n+1), x_n) = 1.

so i started by assuming that there exists at least 1 n such that x_(n+1) and x_n are not relatively prime which means that x_(n+1) = c x_n. then using the definition of the fibonacci sequence that x_(n+1) = x_n + x_(n-1), i expand the right side out until i get x_(n+1) = (n-2)c (x_2) + x_1 but x_1 = x_2 = 1 by the definition of the fibonacci sequence so i am left with x_(n+1) = (n-2)c + 1. from here i am a little stuck. before i went on to say x_n = (n-3)c + 1 and x_(n-1) = (n-4)c + 1 and used those to derive a contradiction but as i look at it now i realize that is not the correct reasoning since x_(n+1) = (n-2)c + 1 does not hold for all n. how would i be able to proceed from my last step? thanks.

The fact that x_(n+1) and x_n are not relatively prime does not necessarily mean that x_(n+1) = c x_n.

See The Math Forum.

If a+b=c, and if d divides any two of a,b,c, then it also divides the third. So, if d divides consecutive Fibonacci numbers, then d also divides the one before that pair. Repeat the argument to show that d divides every Fibonacci number prior to that pair.