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