[math-fun] Fibonacci mod n question
Consider the Fibonacci sequence F_0 = 0, F_1 = 1, F_2 = 1, ... reduced mod n for fixed n >= 2. This gives a sequence that is clearly periodic, since there are at most n^2 consecutive pairs in Z/nZ. Define fp(n) := the least period of {F_k mod n}. (For example, fp(9) = 24.) QUESTION: What is a formula for fp(n) in general? --Dan Asimov
=Dan Asimov ...QUESTION: What is a formula for fp(n) in general?
Interesting question, but isn't this basically asking for a formula for the multiplicative order of the matrix [1 1] [0 1] mod n? I understand that's hard for just integers; should we expect it to be easier in matrix land? (but fp(n) sounds like a great candidate for the OEIS!)
I guess if what I just said is true then the question is equivalent to asking for what k does n divide both F[k] and F[k+2]. (But I should probably shut up since I don't have time to finish working this out...)
participants (2)
-
dasimov＠earthlink.net -
Marc LeBrun