+0

0
33
1
+140

The Fibonacci sequence is the sequence 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?

Apr 11, 2019

#1
+21978
+3

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

Apr 11, 2019
edited by heureka  Apr 11, 2019