Remainder of a high fibonacci number

Question

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?

Answer 1

• $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$.

Answer 2

Hint: by pigeonhole principle the Fibonacci sequence mod 8 is eventually periodic...

Answer 3

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.

Answer 4

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