...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...
THE FIBONACCI
SEQUENCE MODULO M
Marc Renault
...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...
...011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...
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...
A.
The Basics
 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 biinfinite
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.
 F(mod 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(mod m) must repeat.


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

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

F_{k} = 0 and F_{k+1}
= 1 mod m.


If F_{n} = 0 and If F_{n+1}
= 1 mod m, then kn.

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

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


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.

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

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

B.
Goal: Express the period of F(mod m) in terms of m.
 For m
> 2, k(m) is even.

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


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

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

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

 Let m be factored into primes, p_{i}^{e}_{i}.
Then k(m) = lcm[k(p_{i}^{e}_{i})].
[note, this is (p_i) ^
(e_i) ]

By statement (2) above, we see k(p_{i}^{e}_{i})
 k(m) for all i.
Thus lcm[k(p_{i}^{e}_{i})]
 k(m).


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

 For
example, 90 = (2)(3^{2})(5).
k(2) = 3, k(9) = 24, k(5) = 20.
lcm[3, 24, 20] = 120 = k(90).
 This last fact tells
us that if we can find k(p^{e}) for
primes p, then we can find k(m) for any m, which is our ultimate goal.
D.
Revised Goal: Express k(p^{e})
in terms of p^{e}.
 Given a
prime p, let t be the largest integer such
that k(p^{t}) = k(p). Then k(p^{e}) = p^{et}k(p)
for all e >= t.

For example, k(3^{1}) = 8, but k(3^{2}) =
16. Thus for the prime 3, t = 1. Now we can find k(3^{e}) for any e
we desire. For example, k(3^{4}) = 3^{41}k(3) = (27)(8) =
216.

 Conjecture:
t = 1 for all primes p. That is, the above theorem can be restated: k(p^{e}) = p^{e1}k(p).
Now, all we have to do is determine k(p) in order to find k(p^{e}) 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).
 Upper bound on k(p).
 If p = 5n ±
1, then k(p)  (p1).

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

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

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

 Lower
bound on k(m): Given a modulus m, let t > 0 be chosen so that L_{t}
is >= m, where L_{t} is the t^{th}
Lucas number. Then k(m) >= 2t.

Suppose we wish to find a lower bound for k(987). The 14th
Lucas number, L_{14} = 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.

A.
Preliminaries
 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).
 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).
 Definition:
Let b(m) denote the order of s(m), modulo m, if it exists. (We'll
see it always exists.)
 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 3^{4} = 1 (mod 5),
but 3^{1}, 3^{2}, 3^{3} <> 1 (mod 5).
 a(m)b(m) = k(m).

Let a = a(m), b = b(m), k = k(m), s = s(m).
Let G_{n} denote the sequence F(mod m) except
that the starting point of G_{n} is the n^{th}
term of F(mod m). For example, G_{0} starts off 0 1 1 ... whereas G_{a} begins 0 s s ...
Essentially, G_{a} is really just G_{0}
with every term multiplied by s. We can write this as G_{a}
= (s)G_{0}.
Similarly, G_{2a} = (s)G_{a} = (s^{2})G_{0}.
Eventually we get G_{ba} = (s^{b})G_{0} = G_{0} since b is
the order of s.
Also, since b is the order of s, it follows that ab
= k.


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)
 b(m) =
1, 2, or 4.

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.


By identity 4 at the end of this
document, F_{t}^{2}  F_{t+1}F_{t1} = (1)^{t+1}.
So in particular, F_{a}^{2}  F_{a+1}F_{a1}
= (1)^{a+1}.
Since F_{a} = 0 and F_{a+1} = F_{a1}
= s, we get s^{2} = (1)^{a+1}.
That is, s^{2} = (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 s^{2} 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.

 If p is
an odd prime, then b(p^{e}) = b(p).
 For m > 2, b(m) =
4 iff a(m) is odd.
 b(m) = 1 iff 4 does not divide k(m).
 b(m) = 2 iff 4  k(m) and a(m) is even.
 If 3  m, then b(m) =
2.
A.
Example and Definition
 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.
 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
 If F_{z} = 0, and F_{z+n}
= F_{z+2n}, then F_{z}, F_{z+n}, F_{z+2n}, F_{z+3n},
... forms a Fibonacci subsequence.
 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.
 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
 Given
m, how many Fibonacci subsequences of F(mod m) are there?
 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?
 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...
1.
F_{s+t} = F_{s1}F_{t} + F_{s}F_{t+1}
2. F_{s}_{t} = (1)^{t}
(F_{s}F_{t+1}  F_{s+1}F_{t})
3. F_{t} = (1)^{t+1} F_{t}
4. F_{t}^{2}  F_{t+1}F_{t1} = (1)^{t+1}
Marc Renault