The Lucas sequence is the sequence 1, 3, 4, 7, 11, where the first term is 1, the second term is 3 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?
The Lucas sequence is the sequence 1, 3, 4, 7, 11, where the first term is 1,
the second term is 3 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?
\(\begin{array}{|r|r|r|} \hline n & L_n & L_n \pmod{8} \\ \hline 1 & 1 & \color{green}1 \\ 2 & 3 & \color{green}3 \\ 3 & 4 & \color{green}4 \\ 4 & 7 & \color{red}-1 \\ 5 & 11 & \color{red}3 \\ 6 & 18 & \color{red}2 \\ 7 & 29 & \color{red}-3 \\ 8 & 47 & \color{red}-1 \\ 9 & 76 & \color{red}-4 \\ 10 & 123 & \color{red}3 \\ 11 & 199 & \color{red}-1 \\ 12 & 322 & \color{red} 2 \\ \hline 13 & 521 & \color{green}1 \\ 14 & 843 & \color{green}3 \\ 15 & 1364 & \color{green}4 \\ 16 & 2207 & \color{red}-1 \\ \ldots \\ 100 & 792070839848372253127 & -1 \text{ or } 7 \\ \hline \end{array} \)
\(\text{The cycle of $L_n \pmod{8}$ is $\mathbf{12}$ } : \color{green}1,\ \color{green}3,\ \color{green}4,\ \color{red}-1,\ \color{red}3,\ \color{red}2,\ \color{red}-3,\ \color{red}-1,\ \color{red}-4,\ \color{red}3,\ \color{red}-1,\ \color{red} 2 \)
\(\text{To $n = 100$ we have $\left\lfloor\dfrac{100}{8}\right\rfloor = 12$ full cycles and a remainder of $4$.} \\ \text{And the $4th$ value in the cycle is $ \mathbf{-1}$}\)
\(\text{The remainder when the $100th$ term of the sequence $L_{100}=792070839848372253127$ is divided by $8$ }\\ \text{is $\mathbf{-1}$ or what's the same is $ \mathbf{7}$ }\)