Q:

If $F_n$ is the $n^{th}$ Fibonacci number, how do I find $F_{340}$ (mod $7$)?

Consider the following problem

If $F_n$ is the $n^{th}$ Fibonacci number, what is $F_{340}$ (mod $7$)?

My first try was to use Binet's Formula to find a closed form for $F_{340}$ and then apply the usual modulo computation techniques. The problem is that this is an extremely large number! So now I am not sure what to do.

A:

Hint. Consider the sequence $f_n:=F_n \pmod{7}$. Then
$f_{n+1}\equiv f_{n}+f_{n-1}  \pmod{7}$. 
Moreover for $n\geq 0$, $f_n$ is equal to
$$0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1\dots$$
Since we have again the couple 0,1 and the next term is determined by the two previous terms, the sequence is periodic! The period is $0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1$ with length $16$.

