[go: up one dir, main page]

The Fibonacci Sequence Modulo $m$

Marc Renault

I have collected here some results about the properties of the Fibonacci sequence under a modulus. I created this page in an attempt to collect and organize many results from a variety of sources, using consistent notation. The objects of interest here are the standard Fibonacci sequence $F = 0, 1, 1, 2, 3, 5, 8, \ldots$, as well as the more general sequence $G = a, b, a+b, a + 2b, 2a + 3b, \ldots$ where $a$ and $b$ are integers. Thank you for visiting and I hope you find this page useful.

Shameless self-promotion

Tools, Tables

Results

  1. The Period - Basic Facts

    1. Definition. By $F \pmod{m}$ we mean the sequence of least nonnegative residues of the terms of the Fibonacci sequence taken modulo $m$. This is a bi-infinite sequence in that given any two consecutive terms, we can find the terms preceding and following those terms. Example: $F \pmod{3} = \ldots, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, \ldots$.
    2. $F \pmod{m}$ is periodic.
      This is a natural consequence of the following two statements:
      • Modulo $m$, there are $m^2$ possible pairs of residues, and hence some pair of consecutive terms of $F \pmod{m}$ must repeat.
      • Any pair of consecutive terms of F(mod m) determines the entire sequence both forward and backward.
    3. Definition. Let $\pi(m)$ denote the period of $F \pmod{m}$. That is, $\pi(m)$ is the least positive integer $k$ such that $F_k \equiv 0$ and $F_{k+1} \equiv 1 \pmod{m}$ (We always take $F_0 = 0$ and $F_1 = 1$.)
      • For $m = 2, 3, 4, \ldots$, the values of $\pi(m)$ are $3, 8, 6, 20, 24, 16, 12, 24, 60, \ldots$. [A001175]. Below, the values of $\pi(m)$ are plotted for $2 \le m \le 3000$.

    4. Given any integer $m$, infinitely many Fibonacci numbers are divisible by $m$.
      • This follows from the facts that $0$ is in the Fibonacci sequence ($F_0 = 0$) and that $F \pmod{m}$ is periodic.
    5. The zeros of $F \pmod{m}$ are evenly spaced.
      • Proof. From the identities $F_{s+t} = F_{s-1}F_{t} + F_{s}F_{t+1}$ and $F_{s-t} = (-1)^t (F_{s}F_{t+1} - F_{s+1}F_{t})$, we see that if $F_s$ and $F_t$ are congruent to 0 mod $m$, then so are $F_{s+t}$ and $F_{s-t}$.
    6. For $m > 2$, $\pi(m)$ is even.
      • Proof. Let $\pi = \pi(m)$. Taking congruences modulo $m$, we see that $F_{\pi} \equiv 0$, $F_{\pi + 1} \equiv 1$, and $F_{\pi - 1} \equiv 1$. Also, $F_{-\pi + 1} \equiv 1$. Suppose that $\pi$ is odd. Applying the identity $F_{-t} = (-1)^{t+1} F_t$, we find $F_{\pi - 1} = -F_{-\pi + 1}$. But then $1 \equiv -1 \pmod{m}$ so we must have $m = 2$.
    7. Upper bound: $\pi(m) \le 6m$ with equality iff $m = 2 \times 5^n$ for $n = 1, 2, 3, \ldots$. [Attributed to K. S. Brown, proof]
      • In the graph above, you see that $\pi(250) = 1500$ and $\pi(1250) = 7500$ stand out.
    8. Lower bound: Given a modulus $m$, let $t > 0$ be chosen so that $L_t \leq m$, where $L_t$ is the $t$th Lucas number $L_0 = 2, L_1 = 1$. Then $\pi(m) \geq 2t$. This lower bound is sharp. [Catlin74]
      • Suppose we wish to find a lower bound for $\pi(987)$. The 14th Lucas number, $L_{14} = 843$. So by the above theorem, $\pi(987) \geq 28$. In fact, $\pi(987) = 32$.
    9. If $n \geq 4$ is even, then $\pi(F_n) = 2n$. If $n \geq 5$ is odd, then $\pi(F_n) = 4n$. [Ehrlich 89, thm 2]
    10. $\pi(m) = m$ iff $m = 24\cdot5^e$ for some nonnegative integer $e$.

  2. Computing $\pi(m)$ based on the prime factorization of $m$

    1. $\pi([m,n]) = [\pi(m), \pi(n)]$. Here, $[x,y]$ denotes the least common multiple of $x$ and $y$.
    2. Corollary 1. If $n \mid m$, then $\pi(n) \mid \pi(m)$.
      • Example: $17 \mid 51$, and $\pi(17) = 36$ and $\pi(51) = 72$. Interestingly, $51/17 = 3$ but $\pi(51)/\pi(17) = 2$.
    3. Corollary 2. If $m$ has prime factorization $m = p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}$, then $\pi(m) = [\pi(p_1^{e_1}), \pi(p_2^{e_2}), \ldots, \pi(p_n^{e_n})]$.
    4. Given a prime $p$, let $t$ be the largest integer such that $\pi(p^t) = \pi(p)$. Then $\pi(p^e) = p^{e-t}\pi(p)$ for all $e \geq t$.
      • For example, $\pi(3^1) = 8$, but $\pi(3^2) = 24$. Thus for the prime 3, $t = 1$ and we have the formula $\pi(3^e) = 3^{e-1}\cdot 8$. Similarly, we find that $\pi(7) = 16$, but $\pi(7^2) \neq 16$. Thus, $\pi(7^e) = 7^{e-1}\cdot 16$.
    5. NOTE: No prime $p$ has been found for which $\pi(p^2) = \pi(p)$. It is an open problem whether any such primes exist. If any do exist, they are called Wall-Sun-Sun primes. So, for every prime that we know of, the formula $\pi(p^e) = p^{e-1}\pi(p)$ holds.
    6. To compute $\pi(p)$, the best we can do is to provide some divisibility conditions.
      • $\pi(2) = 3$
      • $\pi(5) = 20$
      • If $p \equiv \pm 1 \pmod{10}$, then $\pi(p) \mid p - 1$.
      • If $p \equiv \pm 3 \pmod{10}$, then $\pi(p) \mid 2p + 2$ and $\pi(p) \not\mid p + 1$.
      Incidentally, the two divisibility relations in the last point above imply that $4 \mid \pi(p)$.
      See the excellent article Splitting Fields and Periods of Fibonacci Sequences Modulo Primes (reference at bottom of the page) for nice proofs of these facts.

    7. The above facts allow us to construct a fast algorithm for computing $\pi(m)$. The algorithm makes key use of the matrix $U = \matrixb{0 & 1 \\ 1 & 1}$ which has the marvelous property that $U^n = \begin{bmatrix}F_{n-1} & F_{n} \\ F_{n} & F_{n+1}\end{bmatrix}$. One sees that $U^k \equiv I \pmod{m}$ precisely when $\pi(m) \mid k$. In the following algorithm, $U = \small \matrixb{0 & 1 \\ 1 & 1}$ and $I = \small \matrixb{1 & 0 \\ 0 & 1}$. def $\pi(m)$: if $m == 1$: return $1$ if $m$ is prime: $p = m$ if $p == 2$: return $3$ if $p == 5$: return $20$ if $p \equiv \pm 1$ (mod 10): $D$ = the set of even divisors of $p - 1$ else: $D$ = the set of divisors of $2p + 2$ that are not divisors of $p + 1$ find the least $d$ in $D$ such that $U^d \equiv I \pmod{p}$ (of course, use modular exponentiation) if $U^d \equiv I \pmod{p^2}$: print $p$, exit program, publish a paper - you found a Wall-Sun-Sun prime! return $d$ else: factor $m$ as $m = p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}$ return LCM$[p_1^{e_1-1}\pi(p_1), p_2^{e_2-1}\pi(p_2), \ldots, p_n^{e_n-1}\pi(p_n)]$

  3. The Rank, Multiplier, and Order of $F \pmod{m}$ - Introduction

    1. Compute the period, rank, multiplier, and order of $F \pmod{m}$ for $m \lt 100,000,000$.
    2. Definition. The "rank" of $F \pmod{m}$, denoted $\alpha(m)$, is the least positive integer $k$ such that $F_k \equiv 0 \pmod{m}$. For example, $\alpha(7) = 8$ since $F_8 = 21$ and no smaller Fibonacci number is divisible by $7$. $\alpha(m)$ is also called the "restricted period" or the "rank of apparition" of $F \pmod{m}$.
    3. Definition. The "multiplier" of $F \pmod{m}$, denoted $\mu(m)$, is the first residue after the first zero in $F \pmod{m}$. That is, $\mu(m) = F_{\alpha(m) + 1}$.
    4. Definition. The "order" of $F \pmod{m}$, denoted $\omega(m)$, is the multiplicative order of $\mu(m)$, modulo $m$. That is, $\omega(m)$ is the least positive integer $k$ such that $\mu(m)^k \equiv 1 \pmod{m}$. It turns out (proof below) that equivalently, $\omega(m)$ is the number of zeros in one period of $F \pmod{m}$.
    5. Example. Consider $F$ (mod 5): 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 ...
      The period, $\pi(5) = 20$.
      The rank, $\alpha(5) = 5$.
      The multiplier, $\mu(5)$ = 3.
      The order, $\omega(5) = 4$. Observe $3^4 \equiv 1 \pmod{5}$, but $3^1$, $3^2$, $3^3$ $\not\equiv 1 \pmod{5}$.
    6. We will often abbreviate $\alpha = \alpha(m)$, $\beta = \beta(m)$, $\pi = \pi(m)$, and $\mu = \mu(m)$ for ease of notation.

    7. Matrix interpretation. As before, let $U = \matrixb{0 & 1 \\ 1 & 1}$ and $I = \matrixb{1 & 0 \\ 0 & 1}$, and recall that $U^n = \begin{bmatrix}F_{n-1} & F_{n} \\ F_{n} & F_{n+1}\end{bmatrix}$.
      • $\pi$ is the least positive integer such that $U^{\pi} \equiv I \pmod{m}$.
      • $\alpha$ is the least positive integer such that $U^{\alpha}$ is congruent to a scalar multiple of $I$. Namely, $U^{\alpha} \equiv \mu I \pmod{m}$.
    8. $\alpha(m)\omega(m) = \pi(m)$
      • Proof. Since the zeros of $F \pmod{m}$ are evenly spaced and $\alpha$ is the index of the first zero, we find that $\alpha k = \pi$ for some positive integer $k$.
        Then $I \equiv U^\pi \equiv U^{\alpha k} \equiv \mu^k I \pmod{m}$. Consequently, $\mu^k \equiv 1 \pmod{m}$ and we must have $\omega \leq k$.
        If $\omega \lt k$, then $\alpha \omega \lt \pi$, and yet $U^{\alpha \omega} \equiv \mu^{\omega} I \equiv I \pmod{m}$, which contradicts the minimality of $\pi$.
        Thus, $\omega = k$ and we have $\alpha \omega = \pi$.
      • We now have an equivalent interpretation of $\omega(m)$: it is the number of zeros in one period of $F \pmod{m}$.
    9. $\omega(m) = 1$, $2$, or $4$.
      • What a wonderful and curious fact this is! One period of the Fibonacci sequence mod $m$ will always contain either 1, 2, or 4 zeros, no matter what the modulus is.
      • Proof. We know $U^{\alpha} \equiv \mu I \pmod{m}$. Comparing determinants, we get $(-1)^{\alpha} \equiv \mu^2 \pmod{m}$. Squaring both sides yields $1 \equiv \mu^4 \pmod{m}$, so the order of $\mu$, namely $\omega$, must divide 4. Done!

  4. Facts on the Rank of $F \pmod{m}$

    1. $\alpha([m, n]) = [\alpha(m), \alpha(n)]$. This and the other results on $\alpha$ can be found in [Robinson 63].
    2. Corollary 1. If $n \mid m$, then $\alpha(n) \mid \alpha(m)$.
    3. Corollary 2. If $m$ has prime factorization $m = p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}$, then $\alpha(m) = [\alpha(p_1^{e_1}), \alpha(p_2^{e_2}), \ldots, \alpha(p_n^{e_n})]$.
    4. Given an odd prime $p$, let $t$ be the largest integer such that $\alpha(p^t) = \alpha(p)$. Then $\alpha(p^e) = p^{e-t}\alpha(p)$ for all $e \geq t$.
      • IN FACT, for odd primes, the maximal $t$ for which $\alpha(p^t) = \alpha(p)$ is also the maximal $t$ for which $\pi(p^t) = \pi(p)$
      • For the even prime $2$, we get $\alpha(2) = 3$, $\alpha(2^2) = 6$, $\alpha(2^3) = 6$, $\alpha(2^4) = 12$, and for $e \geq 3$, $\alpha(2^e) = 6 \cdot 2^{e-3}$.
    5. Facts on $\alpha(p)$:
      • $\alpha(2) = 3$
      • $\alpha(5) = 5$
      • If $p \equiv 1$ or $9 \pmod{10}$, then $\alpha(p) \mid p - 1$.
      • If $p \equiv 3$ or $7 \pmod{10}$, then $\alpha(p) \mid p + 1$.

  5. Facts on the Order of $F \pmod{m}$

    1. For $p$ any odd prime and $e$ any positive integer, $\omega(p^e) = \omega(p)$. This is explicitly stated and proved in [Renault 96, thm. 3.32], based on a proof by Robinson [Robinson 63, thm. (iv)].
    2. [Vinson 63, thm. 2] Let $p$ be an odd prime, and $e$ any positive integer.
      • $\omega(p^e) = 4$ iff $2 \not\mid \alpha(p)$.
      • $\omega(p^e) = 1$ iff $2 \mid \alpha(p)$ but $4 \not\mid \alpha(p)$.
      • $\omega(p^e) = 2$ iff $4 \mid \alpha(p)$
      • $\omega(2) = 1$, $\omega(4) = 1$, and for $e \geq 3$, $\omega(2^e) = 2$.
      A corollary to the above result: For any odd prime $p$ and positive integer $e$, $\omega(p^e) = \omega(p)$.
    3. [Vinson 63, thm. 3] The relationship between $\omega(m)$ and $\alpha(m)$.
      • $\omega(m) = 4$ iff $m > 2$ and $2 \not\mid \alpha(m)$.
      • $\omega(m) = 1$ iff $8 \not\mid m$ and $2 \mid \alpha(p)$ but $4 \not\mid \alpha(p)$ for every odd prime $p$ that divides $m$.
      • $\omega(m) = 2$ for all other $m$
    4. [Vinson 63, thm. 4] Let $p$ be an odd prime and $e$ any positive integer. Then
      • $\omega(p^e) = 1$ if $p \equiv 11$ or $19 \pmod{20}$.
      • $\omega(p^e) = 2$ if $p \equiv 3$ or $7 \pmod{20}$.
      • $\omega(p^e) = 4$ if $p \equiv 13$ or $17 \pmod{20}$.
      • $\omega(p^e) \neq 2$ if $p \equiv 21$ or $29 \pmod{40}$.
      The following examples show that this theorem is "complete."
      • $p \equiv 1 \pmod{40}$: $\omega(521) = 1$, $\omega(41) = 2$, $\omega(761) = 4$.
      • $p \equiv 9 \pmod{40}$: $\omega(809) = 1$, $\omega(409) = 2$, $\omega(89) = 4$.
      • $p \equiv 21 \pmod{40}$: $\omega(101) = 1$, $\omega(61) = 4$.
      • $p \equiv 29 \pmod{40}$: $\omega(29) = 1$, $\omega(109) = 4$.
    5. Based on Vinson's results above, we can find relationships between $\pi(m), \omega(m)$, and $\alpha(m)$ for any modulus $m > 2$ . [Renault 96, thm. 3.35, cor. 3.38]
      • $\pi(m) \equiv 2 \pmod{4} \Leftrightarrow \omega(m) = 1$. In this case, $\alpha(m) \equiv 2 \pmod{4}$.
      • $\pi(m) \equiv 4 \pmod{8} \Rightarrow \omega(m) = 2$ or $4$. In this case, $\alpha(m) \equiv 2 \pmod{4}$ or $\alpha(m)$ is odd, respectively.
      • $\pi(m) \equiv 0 \pmod{8} \Rightarrow \omega(m) = 2$. In this case, $\alpha(m) \equiv 0 \pmod{4}$.
    6. Previously, we saw that $\pi([m,n]) = [\pi(m), \pi(n)]$ and $\alpha([m,n]) = [\alpha(m), \alpha(n)]$. The same equation does not hold for $\omega$, but the following chart shows the value of $\omega([m,n])$, given values for $\omega(m)$ and $\omega(n)$ [Renault 96, thm. 3.41].
        $\omega(n)$
        1 2 4
        $\omega(m)$ 1 1 2 4 if $m = $ 2
        2 otherwise
        2 2 2 2
        4
        		 4 if $n =$ 2
        2 otherwise
        		 2 4

  6. The Relationship Between $F = 0, 1, 1, 2, 3, \ldots$ and $G = a, b, a+b, a+2b, 2a+3b, \ldots$ Modulo $m$

    1. Now we consider sequences $G$ where $G_n = G_{n-1} + G_{n-2}$ and $G_0 = a$, $G_0 = b$ for some integers $a$ and $b$. We'll look at the properties of these sequences modulo $m$. We will always assume that $(a, b, m) = 1$, for indeed, if they all had a common factor, we could instead consider $\frac{a}{d}$ and $\frac{b}{d}$ modulo $\frac{m}{d}$. As with $F$, sequence $G$ is periodic when taken modulo $m$; we denote the period of $G$ by $\pi_G(m)$. For clarity, we may denote $\pi(m)$ as $\pi_F(m)$.
    2. Matrices. Let $V = \begin{bmatrix}b-a & a \\ a & b\end{bmatrix} = \begin{bmatrix}G_{-1} & G_0 \\ G_0 & G_1\end{bmatrix}$. Then $UV = \begin{bmatrix}G_0 & G_1 \\ G_1 & G_2\end{bmatrix}$, and in general, $U^n V = \begin{bmatrix}G_{n-1} & G_{n} \\ G_{n} & G_{n+1}\end{bmatrix}$.
    3. $G_n = F_{n-1}a + F_n b$.
      • You can prove this by doing the matrix multiplication $U^n V$.
    4. $\pi_G(m)$ is the least positive integer $n$ such that $U^n V \equiv V \pmod{m}$.
    5. $\pi_G(m) \mid \pi_F(m)$.
      • Proof. Let $k = \pi_F(m)$. Certainly, $G$ repeats after $k$ terms, since $U^{k} V \equiv IV \equiv V \pmod{m}$. Thus, it must repeat after some divisor of $k$ terms.
      • The above divisibility relationship gives us a quick brute force algorithm to compute $\pi_G(m)$: simply list the divisors of $\pi_F(m)$ from least to greatest, and find the first divisor $d$ for which $U^d V \equiv V \pmod{m}$.

    6. $\pi_G([m,n]) = [\pi_G(m), \pi_G(n)]$. [Wall 60]
    7. Corollary 1. If $n \mid m$, then $\pi_G(n) \mid \pi_G(m)$.
    8. Corollary 2. If $m$ has prime factorization $m = p_1^{e_1}p_2^{e_2} \cdots p_n^{e_n}$, then $\pi_G(m) = [\pi_G(p_1^{e_1}), \pi_G(p_2^{e_2}), \ldots, \pi_G(p_n^{e_n})]$.
    9. After the above corollary, we would naturally wish to determine $\pi_G(p^e)$ for prime $p$ and positive integer $e$. With Fibonacci numbers, one finds $\pi(p^e) = p^{e-t}\pi(p)$ for some $t$. However, for general $G$, there is no corresponding statement. Thus, several results below focus on determining the value of $\pi_G(p^e)$. Primes can be characterized as either $p = 2$, $p = 5$, $p \equiv \pm 1 \pmod{10}$, or $p \equiv \pm 3 \pmod{10}$, and these cases are handled below.
    10. Let $D = \det(V) = b^2 - ab - a^2$. The value $D$ plays an important role in determining $\pi_G(m)$.
    11. If $(D, m) = 1$, then $\pi_G(m) = \pi_F(m)$.
      • Proof. If $D$ and $m$ are relatively prime, then $V$ is invertible, modulo $m$. Thus $U^n V \equiv V \Leftrightarrow U^n \equiv I \pmod{m}$.
    12. Corollary. The Lucas sequence $L = 2, 1, 3, 4, \ldots$ has $D = -5$. Thus, for any modulus $m$ that is not a multiple of $5$, $\pi_L(m) = \pi_F(m)$. [Wall 60, cor to thm 8]

    13. $\pi_G(2^e) = \pi_F(2^e) = 3\cdot2^{e-1}$. [Wall 60, thm 9]
    14. If $5 \not\mid D$, then $\pi_G(5^e) = \pi_F(5^e) = 4\cdot5^e$. On the other hand, if $5 \mid D$, then $\pi_G(5^e) = (1/5)\pi_F(5^e) = 4\cdot5^{e-1}$. [Wall 60, thm 9]
    15. If prime $p \equiv \pm 3 \pmod{10}$, then $\pi_G(p^e) = \pi_F(p^e)$ for all sequences $G$. [Wall 60, thm 8]
      • Wall's proof shows that if $D \equiv 0 \pmod{p}$, then (after some arithmetic) $5$ is a quadratic residue mod $p$. However, $5$ is NOT a quadratic residue for primes of the form $p \equiv \pm 3 \pmod{10}$, so we must have $D \not\equiv 0 \pmod{p}$. Consequently, $(D, p^e) = 1$ and $\pi_G(p^e) = \pi_F(p^e)$.
      • Also, recall that when $p \equiv \pm 3 \pmod{10}$, we have $\pi_F(p) \equiv 0 \pmod{4}$ and so consequently $\pi_F(p^e) \equiv 0 \pmod{4}$.
    16. For primes $p \equiv \pm 1 \pmod{10}$:
      1. if $\pi_F(p^e) \equiv 0 \pmod{4}$, then $\pi_G(p^e) = \pi_G(p^e)$ for all $G$.
      2. if $\pi_F(p^e) \equiv 2 \pmod{4}$, then there exists a $G$ such that $\pi_G(p^e) \neq \pi_F(p^e)$; in this case, $\pi_G(p^e) = (1/2)\pi_F(p^e)$.
      [Wall 60, thms 10-12]
    17. Corollary. For $p \neq 5$, if $\pi_F(p^e) \equiv 0 \pmod{4}$, then $\pi_G(p^e) = \pi_F(p^e)$.

References

See Also