The sequence is cyclic modulo any m, because of the only finitely many pairs of residues modulo m, and because the sequence can be uniqly desided from two consecutive element. Therefore we will at some point have 1 ,1 (modulo m). And before that we will have had: ... -1, 1,0,1,1. Therefore there exits an a_k =-1 (mod m). And this solves the problem

Why can't the sequence be cyclic from $a_k$ where $k>2$ ?

Lyub4o wrote: Why can't the sequence be cyclic from $a_k$ where $k>2$ ? Because the equation $a_k = a_{k+2}-a_{k-1}$ shows that "forward periodicity" is equivalent to "backward periodicity" (this is kind of what soemanden does: he actually thinks of the sequence as being indexed over all integers, he notices that $a_{-1} = 0$ and then proves that the sequence is purely periodic mod m). More concrete: suppose that the sequence is only periodic starting at $a_k$ (with $k>1$), with period $\pi$. Then $a_{k} = a_{k+\pi}$, $a_{k+1} = a_{k+1+\pi}$, which implies $a_{k-1} = a_{k+1}-a_k = a_{k+1+\pi}-a_{k+\pi} = a_{k-1+\pi}$, so the sequence was already periodic starting from $a_{k-1}$. Induct.