Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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?

share|improve this question
8  
@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
2  
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
1  
How do you want the result generalized? – Ilmari Karonen Aug 30 '11 at 18:20
4  
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
2  
@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
show 7 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
Yes, I have seen and I think, it is not good enough to use for my post – Gandhi Aug 30 '11 at 17:50
@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
yes sir. I got it! thank you. – Gandhi Aug 31 '11 at 3:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.