Here's another way to look at the problem. The next number is in the Fibonacci sequence is determined by the previous two; you don't need to know its entire history. If you are working modulo $n$ then the number of possible states is $n^2$. You have a finite state machine. In your case, you are working modulo $5$ so $25$ states. You can map the transitions easily.
State $(0, 0)$ is dull it just stays where it is.
Starting at the usual state $(0, 1)$ gives this loop:
$$(0,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (2,3) \rightarrow (3,0)$$
$$\rightarrow (0,3) \rightarrow (3,3) \rightarrow (3,1) \rightarrow (1,4) \rightarrow (4,0)$$
$$\rightarrow (0,4) \rightarrow (4,4) \rightarrow (4,3) \rightarrow (3,2) \rightarrow (2,0)$$
$$\rightarrow (0,2) \rightarrow (2,2) \rightarrow (2,4) \rightarrow (4,1) \rightarrow (1,0)$$
which then repeats. This is just Arthur's answer in a slightly different format.
That's $20$ states in a loop. Together with the trivial loop of $(0,0)$, that's $21$ states and there must be $4$ that did not occur. These form a loop.
$$(1,3) \rightarrow (3,4) \rightarrow (4,2) \rightarrow (2,1)$$
Similarly, you will find loops for any modulus but it is kind of a coincidence that every 5th Fibonacci number is a multiple of $5$. For example, work in modulus $2$ and you get a loop of $3$ not $2$. Every second number is not even. The pattern is odd, odd, even. In modulus $3$, you get a loop of $8$ states so not every 3rd is a multiple of $3$.
A little searching found this which looks interesting but I have not fully read it yet: The Period of the Fibonacci Sequence Modulo j.