# Fibonacci modular results 2

In my study I understand that the Fibonacci sequence mod $k$ is periodic, with period less than $k^2$. Can any one generalize this with good proof?

• @Gandhi: I see you have asked 11 questions on this site so far, yet you have not accepted or upvoted any of the answers you have received. It is considered polite on this site both to upvote any answers you find useful and to formally accept the answer to each question that you find most helpful. (To do the latter, click the little check mark by the answer.) – Mike Spivey Aug 30 '11 at 17:49
• Sir, I accepted the answers. As well as I am responding to every answer by writing a positive comment. Let me know, if there is an other way to respond. So that, I will do in the future questions. – Gandhi Aug 30 '11 at 18:18
• How do you want the result generalized? – Ilmari Karonen Aug 30 '11 at 18:20
• Mike is talking about the procedure described towards the end of this FAQ-entry. In brief, you can vote on the answers on the left of them, that is you have a number inside up- and down-arrows. Click on the up-arrow if you found an answer really useful. If one of the answer did answer your query, you can accept it by clicking on the checkmark sign right below the arrows. – t.b. Aug 30 '11 at 18:25
• @all: Please stop downvoting this question for reasons other than mathematical ones. Evidently, Gandhi showed good will and is unaware of the site's workings. If you're downvoting for mathematical reasons, please leave an explanation. – t.b. Aug 30 '11 at 18:26

HINT  If you consider an n'th order linear recurrence in "system form", i.e. as a shift map on n-tuples then the periodicity is obvious, being cycles of a permutation on a finite set. See my comments about reinventing the wheel (cycle) in this answer and this one.
• @Gandhi: Yes, it is good enough. The cycle consists of distinct pairs of elements of integers modulo $k$. There are $k^2$ such pairs, but the pair $(0,0)$ will never occur for if it did then all the Fibonacci number would be divisible by $k$, and they aren't. Thus the maximum length of the cycle is $k^2-1<k^2$. Or did you actually ask something else? – Jyrki Lahtonen Aug 30 '11 at 20:58