# Thread: A Tricky Fibonacci Sequence Identity

1. ## A Tricky Fibonacci Sequence Identity

The Fibonacci Sequence is define as Fn=Fn-2 + Fn-1 where F0=0 and F1=1;

Suppose that a Fibonacci number Fn is divisible by some positive integer d, and Fn+1=k (2).

Show that Fn (congruent) kF0 (mod d) and Fn+1 (congruent) kF1 (mod d).

I tried to use the given information i.e d|Fn --> Fn=dL for some L (1)

and I used the definition of Fn and the given Fn+1=k and added both equation (1) and (2) to arrive at an identity similar but different to what is required.

Can you kindly shed some light on this matter!

Thanks

2. $d\mid F_n\implies F_n\equiv 0 \bmod{d}$ and $F_0=0$...

$F_1=1$ and $F_{n+1}=k \implies F_{n+1}\equiv k\bmod{d}$. Can you see why?

3. Hmm.. I'm a little concused as to why Fn+1- k / d ??

Cna you explain why please?

Thanks

4. Is it because Fn cong 0 mod can be modified to Fn+1 cong k*F0 mod d ?