Remainder of a high fibonacci number I found a question in my assessment book:
What is the remainder when the 1995th number of the
fibonacci sequence is divided by 8?

How to solve? 

*

*$a_{ 0} \equiv 0 \bmod 8$

*$a_{ 1} \equiv 1 \bmod 8$

*$a_{ 2} \equiv 1 \bmod 8$

*$a_{ 3} \equiv 2 \bmod 8$

*$a_{ 4} \equiv 3 \bmod 8$

*$a_{ 5} \equiv 5 \bmod 8$

*$a_{ 6} \equiv 0 \bmod 8$

*$a_{ 7} \equiv 5 \bmod 8$

*$a_{ 8} \equiv 5 \bmod 8$

*$a_{ 9} \equiv 2 \bmod 8$

*$a_{10} \equiv 7 \bmod 8$

*$a_{11} \equiv 1 \bmod 8$


You can prove by induction that $a_{i} \equiv a_{i-12} \bmod 8$, hence $a_{i} \equiv a_{i \bmod 12} \bmod 8$
Therefore $a_{1995} \equiv a_{3} \bmod 8 \equiv 2 \bmod 8$
So the remainder of the $1995th$ ($0$-based count) Fibonacci number divided by $8$ is $2$.
