# Fibonacci Sequence in $\mathbb Z_n$.

Consider a Fibonacci sequence, except in $\mathbb Z_n$ instead of $\mathbb Z$:

$$F(1) = F(2) = 1$$ $$F(n+2) = F(n+1) + F(n)$$

It is easy to see that each of these sequences must cycle through some sequence and repeat. Consider, for example, the sequence in $\mathbb Z_4$:

$$1,1,2,3,1,0,1,1,2,3,1,0,\dots$$

Is there a nice way to describe the length of the sequence that results before repeating? Clearly, it must be less than $n^2$, since that would cycle through all possible combinations of $a,b$ with $a,b \in \mathbb Z_n$, and once you repeat two combinations, you have a cycle.

\begin{align*} \mathbb Z_2: 1,1,0,\dots & 3 \\ \mathbb Z_3: 1,1,2,0,2,2,1,0,\dots & 8 \\ \mathbb Z_4: 1,1,2,3,1,0,\dots & 6 \\ \mathbb Z_5: 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,\dots & 20 \end{align*}

Examining the sequences above, it seems "obvious" that there's some pattern (just look at how $0$ occurs every $5$th number). Is there a "nice" way to describe these sequences (such as a way to calculate the $k^{th}$ term in a sequence), and, in particular, a rule for the lengths of the cycles?

-
Take a look at the following question (and answers for it) which appeared here recently. math.stackexchange.com/questions/241006/… – coffeemath Mar 11 '13 at 0:07
Using Binet's formula, it is relatively easy to construct a formula for taking $\pmod{n}$, where $n$ is divisible by only primes congruent to $\pm 1 \pmod{5}$ (Since by quadratic reciprocity these are the primes with $5$ as a quadratic residue and relatively prime to $10$, so that $\sqrt{5}, \frac{1}{\sqrt{5}}, \frac{1}{2}$ can all be expressed as integers $\pmod{p}$) Combining with some algebraic number theory, you can get some more results as well. en.wikipedia.org/wiki/Pisano_period will probably be of interest as well. – Ivan Loh Mar 11 '13 at 0:42
$0$s must be evenly spaced and if the prime factors of $n$ are $p_1 , p_2, \dots$, then $\pi(n) < n^2 - \sum_i \pi(p_i)$. – Andrew Salmon Mar 11 '13 at 0:49
See this paper: people.brandeis.edu/~gessel/47a/2000/papers/seltzer.pdf – Ivan Loh Mar 11 '13 at 1:02

I found a way to do this with prime $n.$ Not sure how well it extends to prime powers.

We want to know what happens to the pair of consecutive entries $(x,y),$ shifting over one to get $(y,x+y).$ So we define the matrix $$A \; = \; \left( \begin{array}{rr} 0 & 1 \\ 1 & 1 \end{array} \right) ,$$ and note $$\left( \begin{array}{rr} 0 & 1 \\ 1 & 1 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) \; = \; \left( \begin{array}{c} y \\ x+ y \end{array} \right)$$

We find $A^2 = A + I,$ as well as $A^{-1} = A - I.$ As a result, the set of sums of powers of $A$ make a commutative ring; we calculate $$A^3 = 2A + I,$$ $$A^4 = 3A + 2I,$$ $$A^5 = 5A + 3I,$$ $$A^6 = 8A + 5I,$$ $$A^7 = 13A + 8I,$$ $$A^8 = 21A + 13I,$$ and so on. We do not know for sure that we have a repetition until we have repeated the pair $(x,y).$ Next, what if we regard the coefficients in this ring as elements of the field $\mathbf Z / p \mathbf Z ?$

We would like to know the smallest $m$ such that $$A^m \equiv I \pmod p.$$ There are two parts to this. We illustrate first. $$A^3 \equiv I \pmod 2.$$ $$A^4 \equiv 2I \pmod 3, 2^2 \equiv 1 \pmod 3, A^8 \equiv I \pmod 3.$$ $$A^5 \equiv 3I \pmod 5, 3^4 \equiv 1 \pmod 5, A^{20} \equiv I \pmod 5.$$ $$A^8 \equiv 6I \pmod 7, 6^2 \equiv 1 \pmod 7, A^{16} \equiv I \pmod 7.$$ For each prime, the second exponent is a factor of $p-1,$ as $$\lambda^{p-1} \equiv 1 \pmod p.$$

I forgot one item earlier. If $p \equiv 2,3 \pmod 5,$ then there are no solutions to $x^2 - x - 1 \pmod p,$ the thing is irreducible, and our ring of matrices is a field with $p^2$ elements. The set of nonzero elements is a multiplicative group with $p^2 - 1$ elements. It follows that, with our $A^m \equiv I \pmod p,$ that $m | (p^2 - 1).$

For $p = 5$ or $p \equiv 1,4 \pmod 5,$ the ring has zero divisors, given explicitly by the factors of $x^2 - x - 1 \pmod p$ and scalar multiples of those. Annoying. On the other hand, for $p \equiv 1,4 \pmod 5$ it appears $A^{p-1} \equiv I \pmod p,$ true for $p=11,19,29,31,41,$ and perhaps provable.

From the link given in comments above about Pisano periods, I finally understand how to do $p \equiv 1,4 \pmod 5.$ Let $\phi$ be either of the two distinct roots of $\phi^2 - \phi - 1 \equiv 0 \pmod p.$ Then, with the numbering $F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5,$ we find $$F_n = \frac{\phi^n - (1-\phi)^n}{2 \phi - 1}.$$ Using $a^{p-1} \equiv 1 \pmod p$ and $\phi^2 \equiv \phi + 1 \pmod p$ and $\frac{1}{\phi} \equiv \phi - 1 \pmod p,$ we find both $$F_{p-1} \equiv 0 \pmod p, \; \; \; F_{p-2} \equiv 1 \pmod p.$$ From our earlier discussion of the matrix $A,$ we see that $$A^n = F_n A + F_{n-1} I,$$ pointed out below by awllower. So $$A^{p-1} = F_{p-1} A + F_{p-2} I \equiv I \pmod p.$$ As a result, any such sequence, Fibonacci or Lucas or what have you, repeats with period $p-1$ or some divisor thereof.

-
Notice that finding the smallest $m$ with $A^m\equiv I\pmod p$ is equivalent with finding $m$ such that $p\mid F_m$ and $F_{m-1}\equiv 1\pmod p$, where $F_m$ is the $m$-th Fibonacci number. – awllower Mar 11 '13 at 3:57
And notice the paper linked by Ivan Loh, in the above comments, in which some theorems might be of interest. – awllower Mar 11 '13 at 4:30