1
$\begingroup$

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?

$\endgroup$
  • 8
    $\begingroup$ @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.) $\endgroup$ – Mike Spivey Aug 30 '11 at 17:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Gandhi Aug 30 '11 at 18:18
  • 1
    $\begingroup$ How do you want the result generalized? $\endgroup$ – Ilmari Karonen Aug 30 '11 at 18:20
  • 4
    $\begingroup$ 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. $\endgroup$ – t.b. Aug 30 '11 at 18:25
  • 2
    $\begingroup$ @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. $\endgroup$ – t.b. Aug 30 '11 at 18:26
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I have seen and I think, it is not good enough to use for my post $\endgroup$ – Gandhi Aug 30 '11 at 17:50
  • 1
    $\begingroup$ @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? $\endgroup$ – Jyrki Lahtonen Aug 30 '11 at 20:58
  • $\begingroup$ yes sir. I got it! thank you. $\endgroup$ – Gandhi Aug 31 '11 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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