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$:


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?

  • 1
    $\begingroup$ Take a look at the following question (and answers for it) which appeared here recently. math.stackexchange.com/questions/241006/… $\endgroup$ – coffeemath Mar 11 '13 at 0:07
  • 2
    $\begingroup$ 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. $\endgroup$ – Ivan Loh Mar 11 '13 at 0:42
  • $\begingroup$ $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)$. $\endgroup$ – A.S Mar 11 '13 at 0:49
  • 1
    $\begingroup$ See this paper: people.brandeis.edu/~gessel/47a/2000/papers/seltzer.pdf $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – awllower Mar 11 '13 at 3:57
  • 1
    $\begingroup$ And notice the paper linked by Ivan Loh, in the above comments, in which some theorems might be of interest. $\endgroup$ – awllower Mar 11 '13 at 4:30

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.