The Fibonacci sequence is the sequence 0, 1, 1, 2, 3, 5, ...
where the first and second terms are 1 and each term after that is the sum of the previous two terms.
What is the remainder when the 100th term of the sequence is divided by 8?
Fibonacci cycle length mod 8 is 12:
\(\small{ \begin{array}{|r|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Cycle} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline \text{Remainder } \pmod{8} & 0 & 1 & 1 & 2 & \color{red}3 & 5 & 0 & 5 & 5 & 2 & 7 & 1 \\ \hline & f_0=0 & f_1=1 & f_2=1 & f_3=2 & f_4=3 & f_5=5 & f_6=8 & f_7=13 & f_8=21 & f_9=34 & f_{10}=55 & f_{11}=89 \\ & f_{12} & f_{13} & f_{14} & f_{15} & f_{16} & f_{17} & f_{18} & f_{19} & f_{20} & f_{21} & f_{22} & f_{23} \\ & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ & f_{96} & f_{97} & f_{98} & f_{99} & \color{red}{f_{100}} \\ \hline \end{array} }\)
\(\begin{array}{|rcll|} \hline && f_{100} \pmod{8} \\ &\equiv& f_{100\pmod{12}} \pmod{8} \\ &\equiv& f_{4} \pmod{8} \\ &\equiv& 3 \pmod{8} \\ \hline \end{array} \)
The remainder when the 100th term of the sequence is divided by 8 is 3
