...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...

THE FIBONACCI SEQUENCE MODULO M


Marc Renault

...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...

Contents

Introduction

I. The Period of F(mod m)
II. The Zeros of F(mod m)
III. Fibonacci Subsequences

Identities

See Also

My master’s thesis (1996)
A list of the periods of F(mod m) for m < 2002.
Compute the periods of F(mod m) for m < 10,000,000

Power Fibonacci Sequences (2012) written with Josh Ide, published in the Fibonacci Quarterly.

...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...

Introduction

Here are some of the main results which are known about the Fibonacci sequence under a modulus.  I do not prove all the statements here, but only the ones which are fairly short and interesting, in the hope that the document will have a nice flow. All of the following results, with complete proofs and references, can be found in my master's thesis (links above).

Thanks for dropping by and I hope that you enjoy reading about these amazing properties of the Fibonacci sequence!

...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...

       I.            THE PERIOD OF F(MOD M)

                            A.            The Basics

      1. Definition: By F(mod 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. For example, I am using F(mod 5) as the horizontal rule above.
      2. F(mod m) is periodic. This is a natural consequence of the following two statements:

Description: bullet

Modulo m, there are m2 possible pairs of residues, and hence some pair of consecutive terms of F(mod m) must repeat.

Description: bullet

Any pair of consecutive terms of F(mod m) completely determines the entire sequence.

      1. Definition: Let k(m) denote the period of F(mod m). Let k = k(m) and note the two easy consequences:

Description: bullet

Fk = 0 and Fk+1 = 1 mod m.

Description: bullet

If Fn = 0 and If Fn+1 = 1 mod m, then k|n.

      1. Given any integer m, infinitely many Fibonacci numbers are divisible by m.
        Proof:

Description: bullet

The pair 0,1 is in the Fibonacci sequence, and so, for m > 1, it will appear in F(mod m).

Description: bullet

Since F(mod m) is periodic, this means that the pair 0,1 will appear infinitely many times in F(mod m). This proves our result.

      1. The zeros of F(mod m) are evenly spaced.

Description: bullet

From identities 1 and 2 at the end of this document, it follows that if Fs = Ft = 0 mod m, then Fs+t = 0 mod m.
 

                             B.            Goal: Express the period of F(mod m) in terms of m.

      1. For m > 2, k(m) is even.

Description: bullet

Let k = k(m) and consider all equalities to be congruences modulo m. We will prove the contrapositive of the above statement.

Description: bullet

Since Fk = 0 and Fk+1 = 1, we see Fk-1 = 1. Similarly, F-k+1 = 1. Now assume that k is odd. Then by identity 3 at the end of this document, Fk-1 = -F-(k-1) = -1. Since 1 = -1 mod m, we conclude that m = 2.

      1. If n | m, then k(n) | k(m).

Description: bullet

For example, 17 | 51, and k(17) = 36 and k(51) = 72. Interestingly, though 51/17 = 3, k(51)/k(17) = 2.

      1. Let m be factored into primes, piei. Then k(m) = lcm[k(piei)].    [note, this is  (p_i) ^ (e_i) ]

Description: bullet

By statement (2) above, we see k(piei) | k(m) for all i.
Thus lcm[k(piei)] | k(m).

Description: bullet

Let L = lcm[k(piei)]. Since k(piei) | L for each i, the sequence F(mod piei) repeats in blocks of length L (and maybe less) for each i.
This implies FL = 0 and FL+1 = 1 (mod piei) for all i.
Hence FL = 0 and FL+1 = 1 (mod m) since the piei are relatively prime.
Thus k(m) | L.

      1. For example, 90 = (2)(32)(5).
        k(2) = 3, k(9) = 24, k(5) = 20.
        lcm[3, 24, 20] = 120 = k(90).
    1. This last fact tells us that if we can find k(pe) for primes p, then we can find k(m) for any m, which is our ultimate goal.
       

                            D.            Revised Goal: Express k(pe) in terms of pe.

      1. Given a prime p, let t be the largest integer such that k(pt) = k(p). Then k(pe) = pe-tk(p) for all e >= t.

Description: bullet

For example, k(31) = 8, but k(32) = 16. Thus for the prime 3, t = 1. Now we can find k(3e) for any e we desire. For example, k(34) = 34-1k(3) = (27)(8) = 216.

      1. Conjecture: t = 1 for all primes p. That is, the above theorem can be restated: k(pe) = pe-1k(p).

Now, all we have to do is determine k(p) in order to find k(pe) in order to find k(m), which is our ultimate goal.
 

                             E.            Revised Revised Goal: Express k(p) in terms of p.

Unfortunately, at this point we get stuck. There are no explicit formulas for k(p) in terms of p, but we can find some bounds on the value of k(p).

      1. Upper bound on k(p).
        1. If p = 5n ± 1, then k(p) | (p-1).

For example, k(71) = 70 and k(89) = 44.

        1. If p = 5n ± 2, then k(p) | (2p+2).

Description: bullet

For example, k(73) = 148 and k(47) = 32.

      1. Lower bound on k(m): Given a modulus m, let t > 0 be chosen so that Lt is >= m, where Lt is the tth Lucas number. Then k(m) >= 2t.

Description: bullet

Suppose we wish to find a lower bound for k(987). The 14th Lucas number, L14 = 843. So by the above theorem, k(987) >= 28. In fact, k(987) = 32.
However, this lower bound is not always so precise: k(985) = 1980.

    II.            THE ZEROS OF F(MOD M)

                            A.            Preliminaries

      1. Definition: Let a(m) denote the index of the first Fibonacci number which is divisible by m. We call a(m) the "restricted period" of F(mod m). Equivalently, it is the position of the first zero in the sequence F(mod m).
      2. Definition: Let s(m) denote first residue appearing after the first zero in F(mod m). We call s(m) the "mulitplier" of F(mod m).
      3. Definition: Let b(m) denote the order of s(m), modulo m, if it exists. (We'll see it always exists.)
      4. 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, k(5) = 20.
        The restricted period, a(5) = 5.
        The multiplier is s(5) = 3.
        The order of 3, mod 5, i.e. b(5), is 4 since 34 = 1 (mod 5), but 31, 32, 33 <> 1 (mod 5).
      5. a(m)b(m) = k(m).

Description: bullet

Let a = a(m), b = b(m), k = k(m), s = s(m).
Let Gn denote the sequence F(mod m) except that the starting point of Gn is the nth term of F(mod m). For example, G0 starts off 0 1 1 ... whereas Ga begins 0 s s ...
Essentially, Ga is really just G0 with every term multiplied by s. We can write this as Ga = (s)G0.
Similarly, G2a = (s)Ga = (s2)G0.
Eventually we get Gba = (sb)G0 = G0 since b is the order of s.
Also, since b is the order of s, it follows that ab = k.

Description: bullet

Hence we have another interpretation for b(m): it is the number of zeros in one period of F(mod m).
 

                             B.            Properties of b(m)

      1. b(m) = 1, 2, or 4.

Description: bullet

This is an amazing result. No matter how large our modulus is, every period of F(mod m) will have either 1, 2, or 4 zeros. We present the proof next which is very interesting.

Description: bullet

By identity 4 at the end of this document, Ft2 - Ft+1Ft-1 = (-1)t+1.
So in particular, Fa2 - Fa+1Fa-1 = (-1)a+1.
Since Fa = 0 and Fa+1 = Fa-1 = s, we get -s2 = (-1)a+1.
That is, s2 = (-1)a.
Since these two quantities are congruent modulo m, they have the same order. We know that the order of s is b. Let us denote the order of -1 by c. Hence c = 1 if m = 2, and c = 2 otherwise. Now we equate orders of s2 and (-1)a:
b / gcd(2, b) = c / gcd(a, c).
k = ab = a( (c)gcd(2, b) / gcd(a, c) ).
So k = lcm[a, c]gcd(2, b).
So k = (a or 2a)(1 or 2).
So k = a or 2a or 4a.
In other words, b = 1, 2, or 4.

      1. If p is an odd prime, then b(pe) = b(p).
      2. For m > 2, b(m) = 4 iff a(m) is odd.
      3. b(m) = 1 iff 4 does not divide k(m).
      4. b(m) = 2 iff 4 | k(m) and a(m) is even.
      5. If 3 | m, then b(m) = 2.
         

 III.            FIBONACCI SUBSEQUENCES

                            A.            Example and Definition

      1. Example: Consider the sequence

F(mod 6) = 0 1 1 2 3 5 2 1 3 4 1 5 0 5 5 4 3 1 4 5 3 2 5 1 0 1 1 ...

If we take every third term, we have a new sequence:

0 2 2 4 0 4 4 2 0 2 2 ...

If we take every fourth term, we get

0 3 3 0 3 3 0 3 3 0 3 ...

And, if we take every 11th term we have the sequence

0 5 5 4 3 1 4 5 3 2 5 ...

which is just our original sequence with a new starting point.

      1. Definition: All of the above subsequences of F(mod 6) also exhibit the Fibonacci recurrence relation, mod 6. We call such sequences Fibonacci subsequences.
         

                             B.            Results

      1. If Fz = 0, and Fz+n = Fz+2n, then Fz, Fz+n, Fz+2n, Fz+3n, ... forms a Fibonacci subsequence.
      2. Conjecture: If m is not a multiple of 5, then all Fibonacci subsequences of F(mod m) must contain a zero. Thus, all Fibonacci subsequences of F(mod m) can be found by using the requirements in the above point.
      3. Conjecture: If any four terms of a subsequence of F(mod m) exhibit the Fibonacci recurrence relation, then that sequence is a Fibonacci subsequence.
         

                            C.            Open Questions

      1. Given m, how many Fibonacci subsequences of F(mod m) are there?
      2. How can we classify and describe these Fibonacci subsequences? In the example at the start of the Fibonacci subsequences section we can say that the three example subsequences are 2F(mod 3), 3F(mod 2), and F(mod 6). Given m, what kind of subsequences might appear?
      3. Just about any other question you can ask. There is very little literature in this area, and yet there seem to be some very interesting relationships going on here.

...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...

Identities

1. Fs+t = Fs-1Ft + FsFt+1

2. Fs-t = (-1)t (FsFt+1 - Fs+1Ft)

3. F-t = (-1)t+1 Ft

4. Ft2 - Ft+1Ft-1 = (-1)t+1



Marc Renault