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: *

*$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$.
A: Hint: by pigeonhole principle the Fibonacci sequence mod 8 is eventually periodic...
A: If you take the Fibonacci sequence and look at each term's reminder when divided by 8, a pattern emerges.  You can then see how long the pattern is and then compute what the $1995^{th}$ term's remainder will be.
A: Hint: You don't need to calculate the $n$-th fibonacci number just to get the remainder when dividing by $8$. You know that $a_n=a_{n-1} + a_{n-2}$, meaning that $$a_n\equiv a_{n-1}+a_{n-2}\mod 8$$
That way, you can calculate:
r(a_1)=1, r(a_2)=1, r(a_n) = (r(a_(n-1)) + r(a_(n-2))) % 8
