Subject: The fibonacci file
Dr. Zeilberger,
I'm sending you the Fibonacci html file as an attachment. Thanks for your
interest!
Marc
Content-Description:
The Fibonacci Sequence Modulo M, by Marc Renault
011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...
THE FIBONACCI SEQUENCE MODULO M
011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...
011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...
- Here are some of the main results which are known about the
Fibonacci sequence under a modulus. Also, the section on
Fibonacci subsequences is an area where I have done original
research. 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.
Thanks for dropping by and I hope that you enjoy reading
about these amazing properties of the Fibonacci sequence!
011230331404432022410112303314044320224101123033140443202241011230331404432022410112303314044320224101123033140443202241011...
- THE PERIOD OF F(MOD M)
- 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 bi-infinite
sequence in that given any two consecutive terms, we can
find the terms preceeding 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 k|n.
- 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.
- 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_{k-1} = 1. Similarly, F_{-k+1} = 1.
Now assume that k is odd. Then
by identity 3 at the end of this document, F_{k-1}
= -F_{-(k-1)} = -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}^{ei}. Then k(m) =
lcm[k(p_{i}^{ei})].
- By statement (2) above,
we see k(p_{i}^{ei}) |
k(m) for all i.
Thus lcm[k(p_{i}^{ei})]
| k(m).
- Let L = lcm[k(p_{i}^{ei})].
Since k(p_{i}^{ei}) | L for each i,
the sequence F(mod p_{i}^{ei}) 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}^{ei}) for all i.
Hence F_{L} = 0 and F_{L+1} = 1 (mod m)
since the p_{i}^{ei} 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.
- 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^{e-t}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^{4-1}k(3) = (27)(8) = 216.
- Conjecture: t = 1 for all primes p. That is, the above
theorem can be restated: k(p^{e}) = p^{e-1}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.
- 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) | (p-1).
- 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.
- THE ZEROS OF F(MOD M)
- 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).
- 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_{t-1}
= (-1)^{t+1}.
So in particular, F_{a}^{2} - F_{a+1}F_{a-1}
= (-1)^{a+1}.
Since F_{a} = 0 and F_{a+1} = F_{a-1}
= 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.
- FIBONACCI SUBSEQUENCES
- 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.
- 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.
- 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_{s-1}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_{t-1}
= (-1)^{t+1}
Marc Renault