The Fibonacci Sequence Mod M

Master's Thesis by Marc Renault
Wake Forest University, 1996 Contents:

• Chapter 1: Leonardo of Pisa and the Fibonacci Sequence
• Chapter 2: The Binet Formula
• Chapter 3: Modular Representations of Fibonacci Sequences
  • Section 3.1: The Period
  • Section 3.2: The Distribution Of Residues
  • Section 3.3: The Zeros Of F(mod m)
• Chapter 4: Personal Findings
  • Section 4.1: Spirolaterals And The Fibonacci Sequence
  • Section 4.2: Fibonacci Subsequences
• Appendix A: The First 30 Fibonacci and Lucas Numbers
• Appendix B: k(m), a(m), and b(m) for 2 £ m £ 1000
• Appendix C: One Period Of F(mod m) for 2 £ m £ 50
• Bibliography

---

Please note: This document was originally written in LaTeX, and then converted to HTML using "tth" (see very end for link and more info). I think that everything got converted correctly, but I apologize for any strange notation or missing pictures that may have resulted during the conversion.

---

Chapter 1:
Leonardo of Pisa and the Fibonacci Sequence

Fibonacci, the pen name of Leonardo of Pisa which means son of Bonacci, was born in Pisa, Italy around 1170. Around 1192 his father, Guillielmo Bonacci, became director of the Pisan trading colony in Bugia, Algeria, and some time thereafter they traveled together to Bugia. From there Fibonacci traveled throughout Egypt, Syria, Greece, Sicily, and Provence where he became familiar with Hindu-Arabic numerals which at that time had not been introduced into Europe.

He returned to Pisa around 1200 and produced Liber Abaci in 1202. In it he presents some of the arithmetic and algebra he encountered in his travels, and he introduces the place-valued decimal system and Arabic numerals. Fibonacci continued to write mathematical works at least through 1228, and he gained a reputation as a great mathematician. Not much is known of his life after 1228, but it is commonly held that he died some time after 1240, presumably in Italy.

Despite his many contributions to mathematics, Fibonacci is today remembered for the sequence which comes from a problem he poses in Liber Abaci. The following is a paraphrase:

A man puts one pair of rabbits in a certain place entirely surrounded by a wall. The nature of these rabbits is such that every month each pair bears a new pair which from the end of their second month on becomes productive. How many pairs of rabbits will there be at the end of one year?

If we assume that the first pair is not productive until the end of the second month, then clearly for the first two months there will be only one pair. At the start of the third month the first pair will beget a pair giving us a total of two pair. During the fourth month the original pair begets again but the second pair does not, giving us three pair, and so on.

Assuming none of the rabbits die we can develop a recurrence relation. Let there be F_n pairs of rabbits in month n, and F_n+1 pairs of rabbits in month n+1. During month n+2, all the pairs of rabbits from month n+1 will still be there, and of those rabbits the ones which existed during the n^th month will give birth. Hence F_n+2 = F_n+1 + F_n. The sequence which ensues when F₁ = F₂ = 1 is called the Fibonacci sequence and the numbers in the sequence are the Fibonacci numbers.

n:	1	2	3	4	5	6	7	8	9	10	11	12	...
Fn:	1	1	2	3	5	8	13	21	34	55	89	144	...

Thus the answer to Fibonacci's problem is 144.

Interestingly, it was not until 1634 that this recurrence relation was written down by Albert Girard.

Despite its simple appearance the Fibonacci sequence contains a wealth of subtle and fascinating properties. For example,

Theorem 1.1 Successive terms of the Fibonacci sequence are relatively prime.

Proof:  Suppose that F_n and F_n+1 are both divisible by a positive integer d. Then their difference F_n+1 - F_n = F_n-1 will also be divisible by d. Continuing, we see that d|F_n-2, d|F_n-3, and so on. Eventually, we must have d|F₁. Since F₁ = 1 clearly d = 1. Since the only positive integer which divides successive terms of the Fibonacci sequence is 1, our theorem is proved.

One of the purposes of this chapter and the next is to develop many of the identities needed in chapters three and four. All of these can be found in either [4] or [20]. Given the recursive nature of the sequence, proof by induction is often a useful tool in proving identities and theorems involving the Fibonacci numbers. One of the most useful is the following.

Identity 1.2 F_m+n = F_m-1F_n + F_mF_n+1.

Proof:  Let m be fixed and we will proceed by inducting on n. When n = 1, then F_m+1 = F_m-1F₁ + F_mF₂ = F_m-1 + F_m which is true.

Now let us assume the identity is true for n = 1, 2, 3, ¼, k, and we will show that it holds for n = k+1. By assumption

Fm+k = Fm-1Fk + FmFk+1

and

Fm+(k-1) = Fm-1Fk-1 + FmFk.

Adding the two we get F_m+k + F_m+(k-1) = F_m-1(F_k + F_k-1) + F_m(F_k+1 + F_k) which implies F_m+(k+1) = F_m-1F_k+1 + F_mF_k+2 which is precisely our identity when n = k + 1.

As an example of this identity, we see that F₁₂ = F₈₊₄ = F₇F₄ + F₈F₅ = 13(3) + 21(5) = 144.

It is often useful to extend the Fibonacci sequence backward with negative subscripts. The Fibonacci recurrence can be written as F_n = F_n+2 - F_n+1 which allows us to do this.

n:	...	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	...
Fn:	...	13	-8	5	-3	2	-1	1	0	1	1	2	3	...

Sequences such as the Fibonacci sequence which can be extended infinitely in both directions are called ``bilateral".

With some inspection another useful identity presents itself:

Identity 1.3 F_-n = (-1)ⁿ⁺¹F_n.

Now we can combine the above two identities to obtain

Identity 1.4 F_m-n = (-1)ⁿ(F_mF_n+1 - F_m+1F_n)

Another important fact about the Fibonacci sequence is easily tackled with induction.

Theorem 1.5 F_m | F_mn for all integers m,n.

Proof:  Let m be fixed and we will induct on n. If either m or n equals zero, then the theorem is true by easy inspection. For n = 1 it is clear that F_m | F_m.

Now let us assume that the theorem holds for n = 1, 2, ..., k and we will show that it also holds for n = k+1. Using identity 1.2 we see F_m(k+1) = F_mk-1F_m + F_mkF_m+1. By assumption F_m | F_mk, and so F_m divides the entire right side of the equation. Hence F_m divides F_m(k+1) and the theorem is proved for n ³ 1. Since F_mn differs from F_-mn by at most a factor of -1, then F_m | F_mn for n £ -1 as well.

A surprising result, with a surprisingly simple geometric proof is demonstrated in the following identity.

Identity 1.6 F₁² + F₂² + F₃² + ¼+ F_n² = F_nF_n+1.

Proof:  We can think of the squares of Fibonacci numbers as areas, and then put them together in the manner below.

Picture Omitted

We can find the area of the above rectangle by summing the squares, F₁² + F₂² + F₃² + F₄² + F₅² + F₆², or by multiplying height times width, F₆ ·(F₅ + F₆) = F₆ ·F₇. The general case for the sum of the squares of n Fibonacci numbers follows easily.

The following identity will be useful to us and it, too, can be proved geometrically.

Identity 1.7 F_n² + F_n+1² = F_2n+1.

Proof:  

Picture Omitted

Fn + Fn+1 = Fn+2

The area above can be represented as F_n-1F_n+1 + F_nF_n+2. From identity 1.2 this simplifies to F_{n + (n+1)} = F_2n+1.

Here is another identity involving the square of Fibonacci numbers.

Identity 1.8 F_n+1 F_n-1 - F_n² = (-1)ⁿ.

Proof:  

Fn+1 Fn-1 - Fn2 = (Fn-1 + Fn) Fn-1 - Fn2 = Fn-12 + Fn (Fn-1 - Fn) = Fn-12 - Fn Fn-2 = -(Fn Fn-2 - Fn-12).

We can now repeat the above process on the last line to attain

-(Fn Fn-2 - Fn-12) = (-1)2 (Fn-1 Fn-3 - Fn-22) = (-1)3 (Fn-2 Fn-4 - Fn-32) : = (-1)n (F1 F-1 - F02) = (-1)n

It was the 19th century number theorist Edouard Lucas who first attached Fibonacci's name to the sequence we have been studying. He also investigated generalizations of the sequence.

A generalized Fibonacci sequence, G, is one in which the usual recurrence relation G_n+2 = G_n+1 + G_n holds, but G₀ and G₁ may take on arbitrary values. The Lucas sequence, L, is an example of a generalized Fibonacci sequence where L₀ = 2 and L₁ = 1. It continues 2, 1, 3, 4, 7, 11, .... There are many interesting relationships between the Fibonacci and Lucas sequences, and we give two of the most basic here.

Identity 1.9 L_n = F_n-1 + F_n+1.

Proof:  We will prove the identity by induction. It is easy to see that L₁ = 1 = 0 + 1 = F₀ + F₂ and L₂ = 3 = 1 + 2 = F₁ + F₃. Now suppose that the identity holds for L_r and L_r+1:

Lr = Fr-1 + Fr+1 Lr+1 = Fr + Fr+2

Adding the two equations gives us L_r+2 = F_r+1 + F_r+3 and subtracting the top equation from the bottom yields L_r-1 = F_r-2 + F_r. Thus the identity holds for all positive and negative r.

Identity 1.10 F_2n = F_n L_n.

Proof:  F_2n = F_n+n = F_n-1 F_n + F_n F_n+1 = F_n (F_n-1 + F_n+1) = F_nL_n.

We make a distinction between a Fibonacci sequence, meaning any generalized Fibonacci sequence, and the Fibonacci sequence, meaning the sequence with G₀ = 0 and G₁ = 1.

Some authors generalize the sequence even more by using the relation S_n+2 = bS_n+1 + aS_n. A further generalization examines sequences with the relation S_n = c₁S_n-1 + c₂S_n-2 + ¼+ c_kS_n-k for constants k and c_i. Throughout this paper we will concentrate primarily on the Fibonacci sequence, though we will have occasion to make use of the generalized form G_n+2 = G_n+1 + G_n. We end this chapter with two identities from [20] involving the generalized Fibonacci sequence.

Identity 1.11 G_m+n = F_n-1G_m + F_nG_m+1.

Proof:  For the cases n = 0 and n = 1 we have

Gm = F-1Gm + F0Gm+1 Gm+1 = F0Gm + F1Gm+1

which is true since F_-1 = 1, F₀ = 0, and F₁ = 1. By adding the two equations it is easy to see that our identity continues to hold for n = 2, 3, ¼ and so on. Subtracting the first equation from the second indicates that the identity also holds for negative n.

Identity 1.12 G_m-n = (-1)ⁿ(F_nG_m+1 - F_n+1G_m)

Proof:  This identity follows by substituting -n for n in the above identity and then using identity 1.3.

---

Chapter 2:
The Binet Formula

While the recurrence relation and initial values determine every term in the Fibonacci sequence, it would be nice to know a formula for F_n so we wouldn't have to compute all the preceding Fibonacci numbers. Such a formula was discovered by Jacques-Philippe-Marie Binet in 1843. Vajda [20] observes that this was actually a ``rediscovery" since Abraham DeMoivre knew about this formula as early as 1718. However, history has favored Binet with the credit. Much of the material in this chapter can be found in [20].

Let us find the values for x which will give us the generalized Fibonacci sequence xⁿ⁺² = xⁿ⁺¹ + xⁿ. Since we are not concerned with the case where x = 0 which gives us the trivial sequence, we may divide through by xⁿ to attain x² = x + 1, that is, x² - x - 1 = 0. The two roots of this equation are

t = 1+Ö5 2 s = 1-Ö5 2 .

(2.1)

Note the following properties of t and s:

t+ s = 1,     t- s = Ö5,     ts = -1

(2.2)

Now 1, t, t², t³, ¼ and 1, s, s², s³, ¼ are in fact generalized Fibonacci sequences since tⁿ⁺² = tⁿ⁺¹ + tⁿ and sⁿ⁺² = sⁿ⁺¹ + sⁿ. Indeed, any linear combination of tⁿ and sⁿ forms the n^th term of some Fibonacci sequence.

Gn = atn + bsn

(2.3)

As we see, (atⁿ + bsⁿ) + (atⁿ⁺¹ + bsⁿ⁺¹) = a(tⁿ + tⁿ⁺¹) + b(sⁿ + sⁿ⁺¹) = atⁿ⁺² + bsⁿ⁺².

Any Fibonacci sequence can be expressed this way for particular values of a and b. We show this by expressing a and b in terms of G₀, G₁, t, and s.

First, notice that G₀ = a+ b and G₁ = at+ bs. Since b = G₀ - a we can write

G1 = at+ (G0 - a)s = a(t- s) + G0s = aÖ5 + G0s

which implies

a = G1 - G0s Ö5 .

(2.4)

Similarly a = G₀ - b and so

G1 = (G0 - b)t+ bs = G0t+ b(s- t) = G0t- bÖ5

which implies

b = G0t- G1 Ö5 .

(2.5)

Now, once we know G₀ and G₁ we can use equations 2.4 and 2.5 to determine a and b, and then the formula for G_n follows from equation 2.3.

For example, in the Fibonacci sequence F₀ = 0 and F₁ = 1, and so a = 1/Ö5 and b = -1/Ö5. Thus

Fn = tn - sn Ö5 .

(2.6)

In the Lucas sequence L₀ = 2 and L₁ = 1.

a = 1-2s Ö5 = (t+s)-2s Ö5 = t-s Ö5 = 1.

b = 2t-1 Ö5 = 2t-(t+s) Ö5 = t-s Ö5 = 1.

Thus

Ln = tn + sn.

(2.7)

DeMoivre was able to derive the formula for F_n in a different way, using generating functions. We demonstrate this technique next.

Let g(x) = å_{i = 0}^¥F_ixⁱ. It follows that g(x) - F₀x⁰ - F₁x¹ = g(x) - x. Hence

g(x) - x = ¥ å i = 2  Fixi = ¥ å i = 2  (Fi-1xi + Fi-2xi) = x ¥ å i = 1  Fixi+x2 ¥ å i = 0  Fixi = xg(x) + x2g(x).

Now we have g(x) - xg(x) - x²g(x) = x. That is,

g(x) = x 1-x-x2 = x 1-(t+s)x+tsx2 = x (1-tx)(1-sx) = (t-s)x Ö5(1-tx)(1-sx) = 1-sx Ö5(1-tx)(1-sx) - 1-tx Ö5(1-tx)(1-sx) = 1 Ö5(1-tx) - 1 Ö5(1-sx) .

Expressing [1/( 1-tx)] and [1/( 1-sx)] as the sums of geometric series we get

g(x) = 1 Ö5 (1 + tx + t2 x2 + ¼) - 1 Ö5 (1 + sx + s2 x2 + ¼) = [(t-s)x + (t2 - s2)x2 + ¼] / Ö5

The coefficient of xⁿ, in other words F_n, is (tⁿ - sⁿ)/Ö5, just as we suspected.

We can use the generating function to attain some unusual results. Taking our equation

g(x) = x 1-x-x2 = ¥ å i = 0  Fixi

and dividing through by x we get

1 1-x-x2 = ¥ å i = 0  Fixi-1.

(2.8)

When x = 1/2,

4 = ¥ å i = 0  Fi 2i-1

which implies

2 = ¥ å i = 0  Fi 2i .

(2.9)

Another remarkable summation identity is obtained by differentiating both sides of equation (2.8)

1+2x (1-x-x2)2 = ¥ å i = 0  (i-1)Fixi-2.

When x = 1/2,

32 = ¥ å i = 0  (i-1)Fi 2i-2 8 = ¥ å i = 0  (i-1)Fi 2i = ¥ å i = 0  iFi 2i - ¥ å i = 0  Fi 2i 8 = ¥ å i = 0  iFi 2i - 2 10 = ¥ å i = 0  iFi 2i . (2.10)

The next identity is clearly more complicated than those we've looked at before, yet its proof yields readily to the Binet formula. The interesting thing about it is that it gives us insight into the recurrence relation governing subsequences of the Fibonacci sequence. This identity shows how every n^th term of the Fibonacci sequence is related.

Identity 2.1 F_m+n = L_nF_m + (-1)ⁿ⁺¹F_m-n.

Proof:  

LnFm + (-1)n+1Fm-n = (tn + sn)( tm - sm Ö5 ) + (-1)n+1( tm-n-sm-n Ö5 ) = tm+n - tnsm + sntm - sm+n Ö5 + (-1)n+1tm-n - (-1)n+1sm-n Ö5 = tm+n - (-1)nsm-n + (-1)ntm-n - sm+n - (-1)ntm-n + (-1)nsm-n Ö5 = tm+n - sm+n Ö5 = Fm+n

It is easy to see that when n = 1 in the above identity, we get the usual Fibonacci recurrence relation, F_m+1 = (1)F_m + (1)F_m-1. When n = m we get identity 1.10: F_2n = L_n F_n.

Identity 2.2 F_n = [1/( 2^n-1)][ ( n || 1 ) + ( n || 3 ) 5 + ( n || 5 ) 5² + ( n || 7 ) 5³ + ¼].

Proof:  

Fn = tn - sn Ö5 = 1 2nÖ5 [(1+Ö5)n - (1-Ö5)n]

Now expand using the binomial theorem:

= 1 2nÖ5 é ê ë æ ç è 1 + æ ç è n 1 ö ÷ ø Ö5 + æ ç è n 2 ö ÷ ø Ö52 + æ ç è n 3 ö ÷ ø Ö53 + ¼ ö ÷ ø - æ ç è 1 - æ ç è n 1 ö ÷ ø Ö5 + æ ç è n 2 ö ÷ ø Ö52 - æ ç è n 3 ö ÷ ø Ö53 + ¼ ö ÷ ø ù ú û = 1 2n-1Ö5 é ê ë æ ç è n 1 ö ÷ ø Ö5 + æ ç è n 3 ö ÷ ø Ö53 + æ ç è n 5 ö ÷ ø Ö55 + ¼ ù ú û = 1 2n-1 é ê ë æ ç è n 1 ö ÷ ø + æ ç è n 3 ö ÷ ø 5 + æ ç è n 5 ö ÷ ø 52 + æ ç è n 7 ö ÷ ø 53 + ¼ ù ú û

Lastly in this chapter we use t and s to demonstrate some simple greatest-integer identities. Though we will not use these, much research has been done in this area and they are certainly of interest in their own right.

Identity 2.3 F_n = ë[(tⁿ)/( Ö5)] + ¹/₂ û for all n.

Proof:   | F_n - [(tⁿ)/( Ö5)] | = | [(sⁿ)/( Ö5)] | < ¹/₂ for all n.

Identity 2.4 F_n+1 = ëtF_n + ¹/₂ û for n ³ 2.

Proof:  |F_n+1 - tF_n| = |[(tⁿ⁺¹ - sⁿ⁺¹)/( Ö5)] - [(tⁿ⁺¹ - sⁿt)/( Ö5)]| = |[(sⁿ(t-s))/( Ö5)]| = |sⁿ| < ¹/₂ for all n ³ 2.

---

Chapter 3:
Modular Representations of Fibonacci Sequences

One way to learn some fascinating properties of the Fibonacci sequence is to consider the sequence of least nonnegative residues of the Fibonacci numbers under some modulus. One of the first modern inquiries into this area of research was made by D. D. Wall [22] in 1960, though J. L. Lagrange made some observations on these types of sequences in the eighteenth century. Typically, the variable m will be used only to denote a modulus.

3.1  The Period

Perhaps the first thing one notices when the Fibonacci sequence is reduced mod m is that it is periodic. For example,

F(mod 4)	=	0 1 1 2 3 1 0 1 1 2 3 ...
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 2 3 ...

See appendix C for a list of the Fibonacci sequence under various moduli.

Any (generalized) Fibonacci sequence modulo m must repeat. After all, there are only m² possible pairs of residues and any pair will completely determine a sequence both forward and backward. If we ignore the pair 0,0 which gives us the trivial sequence, then we know that the period of any Fibonacci sequence mod m has a maximum length of m² - 1.

It will always happen that the first pair to repeat will be the pair we started with. Suppose that this were not so. Then we might have the sequence a,b,...,x,y,...,x,y,... where the pair a,b is not contained in the block x,y,...,x,y. However, we know that this block repeats backward as well as forward, and so the pair a,b cannot be in the sequence. This gives us our contradiction.

We can say some things about where the zeros will appear in the modular representation of the Fibonacci sequence. Recall from identities 1.2 and 1.4 that

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

If F_s º F_t º 0 then clearly F_s+t º 0 and F_s-t º 0. Hence all the zeros of F(mod m) are evenly spaced throughout the sequence. Since F(mod m) is periodic for any m and F₀ = 0 we can say that any integer will divide infinitely many Fibonacci numbers. In addition, all the Fibonacci numbers divisible by a given integer are evenly spaced throughout the sequence.

We know that F(mod m) is periodic, so the question naturally presents itself: What is the relationship between the modulus of a sequence and its period? We will examine some results in this area.

Each author seems to have his or her own notation, but the following definitions come from Wall. Let k(m) denote the period of the Fibonacci sequence modulo m. Let h(m) denote the period of any generalized Fibonacci sequence modulo m. From our previous example we see that k(4) = 6 and k(5) = 20. The following are some immediate consequences of the definition.

Fn º Fn+r ·k(m) mod m Gn º Gn+r ·h(m) mod m Fk(m) º 0 mod m (3.1) Fk(m)-1 º Fk(m)+1 º Fk(m)+2 º 1 mod m (3.2)

We will often use the fact that if F_n º 0 (mod m) and F_n+1 º 1 (mod m) then k(m)|n. This result follows immediately from the periodicity of F(mod m).

We now demonstrate some very general properties of F(mod m) using our notation. The following three theorems can be found in [22]. The reader is encouraged to examine the table in appendix B which gives the period of F(mod m) for 2 £ m £ 1000, and observe the behavior of k(m) as m varies. After noticing that F(mod m) is periodic one notices that almost all of the periods are even. Though Wall provides the next theorem, the proof is the author's.

Theorem 3.1 For m ³ 3, k(m) is even.

Proof:  For ease of notation let k = k(m), and we will consider all congruences to be taken modulo m. From identity 1.3 we know that if t is odd then F_t = F_-t and if t is even then F_t = -F_-t. We will assume k to be odd and show that m must equal 2.

We know that F₁ = F_-1 º F_k-1. Now k-1 is even so F_k-1 = -F_1-k º -F₁. Thus F₁ º -F₁, and as a result m = 2.

Another curious feature of F(mod m) is that k(n)|k(m) whenever n|m. Surprisingly, this property is true of generalized Fibonacci sequences as well.

Theorem 3.2 If n|m, then for a given Fibonacci sequence, h(n) | h(m).

Proof:  Let h = h(m). We need to show that G(mod n) repeats in blocks of length h. We do this by showing that G_i º G_i+h (mod n) regardless of our choice for i. Certainly we know that G_i º G_i+h (mod m), so for some 0 £ a < m we have G_i = a + mx and G_i+h = a + my.

Now say m = nr and let us substitute nr for m in the previous two equations. Then G_i = a + nrx and G_i+h = a + nry. We can say that a = a¢+ nw (0 £ a¢ < n) and this time substitute for a in the previous equations. Now G_i = a¢+ n(w+rx) and G_i+h = a¢+ n(w+ry). Of course this implies that G_i º G_i+h (mod n) which was needed to be shown.

We can make this theorem more exact by expressing h(m) in terms of h(p_i^e_i) where m has the prime factorization m = Õp_i^e_i.

Theorem 3.3 Let m have the prime factorization m = Õp_i^e_i. Then h(m) = lcm[h(p_i^e_i)], the least common multiple of the h(p_i^e_i).

Proof:  By our previous theorem h(p_i^e_i) | h(m) for all i. It follows that lcm[h(p_i^e_i)] | h(m).

Second, since h(p_i^e_i) | lcm[h(p_i^e_i)] we know G(mod p_i^e_i) repeats in blocks of length lcm[h(p_i^e_i)]. Hence G_{lcm[h(pi^ei)]} º G₀ and G_{lcm[h(pi^ei)]+1} º G₁ (mod p_i^e_i) for all i. Since all the p_i^e_i are relatively prime, the Chinese Remainder Theorem assures us that G_{lcm[h(pi^ei)]} º G₀ and G_{lcm[h(pi^ei)]+1} º G₁ (mod m). Thus G(mod m) repeats in blocks of length lcm[h(p_i^e_i)] and we can say that h(m) | lcm[h(p_i^e_i)]. This concludes the proof.

Hence we have reduced the problem of characterizing k(m) into the problem of characterizing k(p^e). Before we develop theorems which speak to this problem, however, we look at a related result. We see in the following theorem that it is not necessary to break a modulus all the way into its prime factorization in order to attain information about k(m).

Theorem 3.4 h([m,n]) = [h(m), h(n)] where brackets denote the least common multiple function.

Proof:  Since m|[m,n] and n|[m,n] we know that h(m)|h([m,n]) and h(n)|h([m,n]). It follows that [h(m), h(n)] | h([m,n]).

Say we have the prime factorization [m,n] = p₁^e₁ ¼p_t^e_t. Then h([m,n]) = h(p₁^e₁ ¼p_t^e_t) = [h(p₁^e₁) ¼h(p_t^e_t)]. Since p_i^e_i divides m or n for all i, certainly h(p_i^e_i) divides h(m) or h(n) for all i. Thus [h(p₁^e₁) ¼h(p_t^e_t)] | [h(m), h(n)]. In other words, h([m,n]) | [h(m), h(n)].

Hence h([m,n]) = [h(m), h(n)].

Now we turn our attention back to the matter of solving k(p^e) in terms of p^e. The general case of this theorem is somewhat involved, so to motivate the ideas we look at a couple of specific cases. We will demonstrate that k(2^e) = 3 ·2^e-1 and k(5^e) = 4 ·5^e. These results can be found in [11], but the proofs there are somewhat incomplete. For example, Kramer and Hoggatt show that F_3·2^e-1 º 0 (mod 2^e) and F_3·2^e-1+1 º 1 (mod 2^e) and they immediately conclude that k(2^e) = 3·2^e-1. However, this only demonstrates that k(2^e) | 3·2^e-1. The proof below takes this point into consideration.

Theorem 3.5 k(2^e) = 3·2^e-1.

Proof:  By inspection, k(2) = 3 and k(4) = 6, so the theorem holds for e = 1, 2. Suppose k(2^r) = 3 ·2^r-1, so that F_3·2^r-1 º 0 and F_3·2^r-1+1 º 1 (mod 2^r) and we will induct on r.

By identity 1.10,

F3·2r = (F3·2r-1)(F3·2r-1-1 + F3·2r-1+1)

The first factor on the right, F_3·2^r-1 º 0 (mod 2^r). It is an easy matter to see that every third Fibonacci number is even and the rest are odd, so the second factor on the right, F_3·2^r-1-1 + F_3·2^r-1+1 º 0 (mod 2). Thus their product, F_3·2^r º 0 (mod 2^r+1).

By identity 1.7,

F3·2r+1	=	(F3·2r-1)2	+	(F3·2r-1+1)2
	º	(0 or 2r)2	+	(1 or 2r+1)2	(mod 2r+1)
	º	0	+	1	(mod 2r+1)
	º	1			(mod 2r+1)

Thus we know k(2^r+1) | 3·2^r.

We know that k(2^r) | k(2^r+1), and by our induction hypothesis k(2^r) = 3·2^r-1. Thus k(2^r+1) = either 3·2^r-1 or 3·2^r. We will show that the latter is true by proving F_3·2^r-1+1 \not º 1 (mod 2^r+1). More precisely, we will prove that F_3·2^r-1+1 º 2^r + 1 (mod 2^r+1).

Let us add this statement to our induction hypothesis: assume F_3·2^r-2 º 0 and F_3·2^r-2+1 º 2^r-1+1 (mod 2^r). By inspection this is the case for r = 3. We will induct on r to show that F_3·2^r-1+1 º 2^r + 1 (mod 2^r+1).

By identity 1.7,

F3·2r-1+1 = (F3·2r-2+1)2 + (F3·2r-2)2.

Let us look at the first term on the right.

F3·2r-2+1 º (2r-1+1) or (2r-1+1+2r) mod 2r+1 (2r-1+1)2 = 22r-2+2r+1 º 2r+1 mod 2r+1 (2r-1+1+2r)2 = (3·2r-1+1)2 = 9·22r-2 + 3·2r +1 º 2r+1 mod 2r+1

Thus

(F3·2r-2+1)2 º 2r + 1 mod 2r+1.

Let us look at the second term on the right.

F3·2r-2 º 0 or 2r mod 2r+1 02 º 0 mod 2r+1 (2r)2 = 22r º 0 mod 2r+1

Thus

(F3·2r-2)2 º 0 (mod 2r+1).

Consequently F_3·2^r-1+1 º 2^r + 1 (mod 2^r+1) and the theorem follows.

Before we prove a similar theorem for k(5^e) we first need to mention a lemma which provides insight into one of the divisibility properties of the Fibonacci sequence.

Lemma 3.6 Let p be an odd prime and suppose p^t | F_n but p^t+1 \not| F_n for some t ³ 1. If p \not| v then p^t+1 | F_nvp but p^t+2 \not| F_nvp.

The proof of this lemma is too involved to be examined here, but it can be found in [20].

Since F₅ = 5, clearly 5 goes into F₅ once. By the the lemma then, 5 goes into F_{n ·5^t} exactly t times if 5 \not| n.

Theorem 3.7 k(5^e) = 4 ·5^e.

Proof:  First we will show that for all e, F_{4 ·5^e} º 0 and F_{4 ·5^e +1} º 1 (mod 5^e). By the lemma above clearly F_{4 ·5^e} º 0 (mod 5^e). From identity 1.7 we have

F4 ·5e +1 = (F2 ·5e)2 + (F2 ·5e +1)2.

Applying our lemma to the first term on the right gives us (F_{2 ·5^e})² º 0² º 0 (mod 5^e). By identity 1.8, the second term on the right, (F_{2 ·5^e +1})² = F_{2 ·5^e} F_{2 ·5^e+2} + (-1)^{2 ·5e +2} º 1 (mod 5^e).

Thus we know that F_{4 ·5^e} º 0 and F_{4 ·5^e +1} º 1 (mod 5^e) and it follows that k(5^e) | 4 ·5^e for all e.

We proceed now by induction using the hypothesis k(5^r) = 4 ·5^r. By inspection this is the case for r = 1. We induct on r to show k(5^r+1) = 4 ·5^r+1.

Since 4 ·5^r = k(5^r) | k(5^r+1) and k(5^r+1) | 4 ·5^r+1, we know k(5^r+1) = either 4 ·5^r or 4 ·5^r+1. In the first case, F_{4 ·5^r} contains exactly r factors of 5 and hence F_{4 ·5^r} \not º 0 (mod 5^r+1). Hence we must have k(5^r+1) = 4 ·5^r+1 and our theorem is proved.

We have proved k(p^e) = p^e-1k(p) for p = 2 and p = 5, and we now turn to proving it for all p. While the general theorem is slightly less strict than these special cases, it does give us great insight into the periodic behavior of the Fibonacci sequence. One proof, by Robinson[15], also shows how matrices may be used to discover facts about the Fibonacci sequence. We will be working with the matrix U defined by

U = é ê ë 0 1 1 1 ù ú û

which has the property that

Un = é ê ë Fn-1 Fn Fn Fn+1 ù ú û .

(3.3)

This matrix has been called the Fibonacci matrix because of this property. Note that U^k(m) = I + mB º I (mod m) for some 2 ×2 matrix B. And, if Uⁿ º I (mod m) then k(m) | n.

Theorem 3.8 If t is the largest integer such that k(p^t) = k(p) then k(p^e) = p^e-tk(p) for all e ³ t.

Proof:  Since U^k(pe) = I + p^eB we can write U^pk(pe) = (I + p^eB)^p = I^p + ( p || 1 ) I^p-1(p^eB) + ( p || 2 ) I^p-2(p^eB)² + ¼. Thus U^pk(pe) º I (mod p^e+1). Clearly U^k(pe+1) º I (mod p^e+1) and so we have k(p^e+1) | pk(p^e). Combine this fact with the knowledge that k(p^e) | k(p^e+1) and as a result k(p^e+1) = k(p^e) or pk(p^e).

Now let us assume that k(p^e+1) = pk(p^e) and we will induct on e to arrive at k(p^e+2) = pk(p^e+1).

By assumption k(p^e) ¹ k(p^e+1) and so we know that U^k(pe) = I + p^eB where p \not| B. Hence U^pk(pe) = (I + p^eB)^p = I^p + ( p || 1 ) I^p-1(p^eB) + ( p || 2 ) I^p-2(p^eB)² + ¼ º I + p^e+1B (mod p^e+2). (The astute reader may notice that this congruence does not actually hold for p = 2, e = 1. However, since we have proven the case for p = 2 in theorem 3.5 we may assume p ³ 3.) That is, U^k(pe+1) = U^pk(pe) º I + p^e+1B \not º I (mod p^e+2). This implies k(p^e+1) ¹ k(p^e+2) so we must have k(p^e+2) = pk(p^e+1) and the induction is complete.

Now let t be the largest e such that k(p^e) = k(p). Then k(p^e) = k(p) for 1 £ e £ t and k(p^e) = k(p^e-t) for e ³ t.

Remarkably, the conjecture that t = 1 for all primes has existed since Wall's paper in 1960, but neither a proof nor a counter example has yet been found. Once again we have been able to reduce the problem of finding the period of the Fibonacci sequence given a modulus. All that remains (other than proving t = 1 for all primes, of course) is to characterize k(p) in terms of p. However, this undertaking has proven to be extraordinarily difficult, and the best we can do is to describe some bounds on k(p).

Theorems 3.11 through 3.13 will describe upper bounds on k(p), but we must first take some time to develop certain divisibility properties of the Fibonacci sequence found in [20]. We will make use of these three facts for primes, p:

(i) æ ç è p n ö ÷ ø º 0 (mod p) for 1 £ n £ p-1 (ii) æ ç è p-1 n ö ÷ ø º (-1)n (mod p) for 0 £ n £ p-1 (iii) æ ç è p+1 n ö ÷ ø º 0 (mod p) for 2 £ n £ p-1

We will also use the following lemma:

Lemma 3.9 5 is a quadratic residue modulo primes of the form 5t ±1 and a quadratic nonresidue modulo primes of the form 5t ±2.

Proof:  Using the Legendre symbol and the law of quadratic reciprocity we know that (⁵/_p) = (^p/₅) since 5 is a prime of the form 4t+1. Then,

æ ç è 5 5t+1 ö ÷ ø = æ ç è 5t+1 5 ö ÷ ø = æ ç è 1 5 ö ÷ ø = 1 æ ç è 5 5t-1 ö ÷ ø = æ ç è 5t-1 5 ö ÷ ø = æ ç è 4 5 ö ÷ ø = 1.

However,

æ ç è 5 5t+2 ö ÷ ø = æ ç è 5t+2 5 ö ÷ ø = æ ç è 2 5 ö ÷ ø = -1 æ ç è 5 5t-2 ö ÷ ø = æ ç è 5t-2 5 ö ÷ ø = æ ç è 3 5 ö ÷ ø = -1.

Using identity 2.2 we have 2^p-1F_p = ( p || 1 ) + ( p || 3 ) 5 + ¼+ ( p || p ) 5^{[(p-1)/ 2]}. Applying (i) above and Fermat's theorem we get F_p º 5^{[(p-1)/ 2]} (mod p). Now from the lemma we know that 5^{[(p-1)/ 2]} º 1 (mod p) if and only if p = 5t ±1, and 5^{[(p-1)/ 2]} º -1 (mod p) if and only if p = 5t ±2. Hence,

If a prime p is of the form 5t ±1 then Fp º 1 (mod p).

If a prime p is of the form 5t ±2 then Fp º -1 (mod p).

The converse of these statements is not true, for in fact F₂₂ = 17711 = 85(22) + 1 º 1 (mod 22), and quite clearly, 22 is not prime.

Again we use identity 2.2 and see 2^p-2F_p-1 = (( p-1) || 1 ) + (( p-1) || 3 ) 5 + ¼+ (( p-1) || ( p-2 )) 5^{[(p-3)/ 2]}. By (ii) above, 2^p-2F_p-1 º -(1 + 5 + 5² + ¼+ 5^{[(p-3)/ 2]}) (mod p). Summing the geometric series yields,

2p-2 Fp-1 º - 5[(p-1)/ 2]-1 4 mod p.

Clearly if 5^{[(p-1)/ 2]} º 1 (mod p) then 2^p-2 F_p-1 º 0 (mod p). Certainly 2^p-2 \not º 0 (mod p) so it would have to be that F_p-1 º 0 (mod p). Hence,

If a prime p is of the form 5t ±1 then F_p-1 º 0 (mod p).

Finally, identity 2.2 gives us 2^pF_p+1 = (( p+1) || 1 ) + (( p+1) || 3 ) 5 + ¼+ (( p+1) || p ) 5^{[(p-1)/ 2]}. By (iii) above, 2^pF_p+1 º (( p+1) || 1 ) + (( p+1) || p ) 5^{[(p-1)/ 2]} = (p+1) + (p+1)5^{[(p-1)/ 2]} º 1 + 5^{[(p-1)/ 2]} (mod p). Now when 5^{[(p-1)/ 2]} º -1 (mod p) we will have 2^p F_p+1 º 0 (mod p). Since 2^p º 2 (mod p), it would have to be that F_p+1 º 0 (mod p). Thus,

If a prime p is of the form 5t ±2 then F_p+1 º 0 (mod p).

Collecting our results provides us with the following theorem.

Theorem 3.10 If a prime p is of the form 5t ±1 then F_p-1 º 0 and F_p º 1 (mod p). If a prime p is of the form 5t ±2 then F_p º -1 and F_p+1 º 0 (mod p).

Now at last we can present some theorems concerning the character of k(p).

Theorem 3.11 If p is a prime, p ¹ 5, then k(p) | p²-1.

Proof:  By inspection, k(2) = 3, and the theorem holds for p = 2. Now let us assume p odd. To prove the theorem we will show that F_p²-1 º 0 and F_p² º 1 (mod p).

If p = 5t ±1 then p|F_p-1. We know that p-1|p²-1 and so F_p-1|F_p²-1. Hence p|F_p²-1. If p = 5t ±2 then p|F_p+1. We know that p+1|p²-1 and so F_p+1|F_p²-1. Hence p|F_p²-1. Thus for all p ¹ 5, F_p²-1 º 0 (mod p).

To prove F_p² º 1 (mod p), we first note that 2^p2-1 F_p² = (( p²) || 1 ) + (( p²) || 3 ) 5 + ¼+ (( p²) || ( p² )) 5^{[(p2-1)/ 2]}. Now 2^p2-1 = (2^p-1)^p+1 º 1 (mod p) and (( p²) || n ) º 0 (mod p) for 1 £ n £ p²-1. Hence F_p² º (5^{[(p-1)/ 2]})^p+1 º (±1)^p+1 º 1 (mod p).

Thus the theorem is proved.

Theorem 3.12 If a prime p is of the form 5t ±1 then k(p)|p-1.

Proof:  Since p = 5t ±1, theorem 3.10 tells us that F_p-1 º 0 and F_p º 1 (mod p). Hence F(mod p) repeats in blocks of length p-1. Thus k(p)|p-1.

Theorem 3.13 If a prime p is of the form 5t ±2 then k(p) | 2p+2.

Proof:  Suppose p = 5t ±2. By theorem 3.10 then, F_p+1 º 0 (mod p). Since p+1 | 2p+2 and the zeros of F(mod p) are evenly spaced, we can say F_2p+2 º 0 (mod p).

We also know that F_p º -1 (mod p). By the usual recurrence relation then, F_p+2 º F_p+3 º -1 (mod p). Now we can write F_2p+3 = F_(p+1)+(p+2) = F_pF_p+2 + F_p+1F_p+3 º (-1)(-1) + (0)(-1) º 1 (mod p).

Thus k(p)|2p+2.

We now consider upper and lower bounds for k(m) where m can be any integer m ³ 2. It was noted earlier that k(m) £ m²-1, but can we do better than this? One method of determining an upper bound is to use the two preceding theorems to show that k(p) = p² - 1 if and only if p = 2 or 3. Then by application of theorem 3.8 it can be proved that k(p^e) < (p^e)² - 1 for e ³ 2. Finally, we can use theorem 3.4 to demonstrate that k(m) < m²-1 for all composite m.

However, the author would like to propose a more elegant way of proving this inequality. If k(m) = m² - 1 for some m, then every possible pair of residues except 0,0 appears in F(mod m). It will be seen in section 3.3 that a single period of F(mod m) contains at most four zeros. Consequently, F(mod m) contains at most four 0, r pairs where 1 £ r < m. Hence, for m ³ 6 there is some 0,r pair not represented in F(mod m) and we must have k(m) < m² - 1. It is a simple matter to check the remaining cases. When m = 2 or 3, k(m) = m² - 1 and when m = 4 or 5, k(m) < m² - 1.

Unfortunately, empirical evidence indicates that this upper bound becomes less and less precise as m increases. For 2 £ m £ 299 we find by inspection that k(m) £ 6m. For 300 £ m £ 1000 we find k(m) £ 4m. There does not appear to be any other material published concerning upper bounds on k(m).

A sharp lower bound on k(m) was given by Paul Catlin[5] in 1974. We see here an interesting interaction between the Lucas and Fibonacci numbers. We present his theorem without proof.

Theorem 3.14 Given a modulus m > 2, let t be any natural number such that L_t £ m. Then k(m) ³ 2t with equality if and only if L_t = m and t is odd.

In the beginning of the section we saw some results which helped to define the overall character of h(m) and thus of k(m). In the last part of this section we present some results due to Wall on the relationship between h(m) and k(m). The first of these is strikingly simple.

Theorem 3.15 h(m) | k(m).

Proof:  For ease of notation, let k = k(m). Applying identity 1.11 and then equations 3.1 and 3.2 we get G_k = F_k-1G₀ + F_kG₁ º G₀ (mod m) and G_k+1 = F_kG₀ + F_k+1G₁ º G₁ (mod m). Thus G(mod m) repeats in blocks of length k(m). From this we can conclude h(m) | k(m).

We can elicit equality between h(m) and k(m) by putting stricter conditions on m.

Theorem 3.16 If a prime p is of the form 5t ±2 then h(p^e) = k(p^e).

Proof:  For ease of notation, let h = h(p^e). Certainly,

Gh - G0 º 0 mod pe, and Gh-1 - G1 º 0 mod pe.

By identity 1.11 the above is equivalent to

(Fh-1G0+FhG1) - G0 = G1 Fh + G0(Fh-1-1) º 0 mod p (Fh-1G1+Fh+1G2)- G1 = G2 Fh + G1(Fh-1-1) º 0 mod p

We now have a system of equations which we may treat as a matrix with determinant D = G₁² - G₀G₂. We will assume that D º 0 (mod p) and arrive at a contradiction.

When D º 0 (mod p) then G₁² - G₀G₂ = G₁² - G₀(G₀ + G₁) = G₁² - G₀G₁ - G₀² º 0 (mod p). This last congruence is impossible if p = 2 (we ignore the trivial case G₀ = G₁ = 0) so we may assume p to be odd. Multiply both sides by -4.

4G02 + 4G0G1 - 4G12 º 0 mod p

Add 5G₁² to both sides.

4G02 + 4G0G1 + G12 = (2G0 + G1)2 º 5G12 mod p

Now multiply both sides by G₁^p-3 and apply Fermat's theorem to the right.

G1p-3(2G0 + G1)2 º 5 mod p

Since p is odd, this implies that 5 is a quadratic residue modulo p. However, by lemma 3.9, this contradicts our hypothesis that p = 5t ±2. Therefore, D \not º 0 (mod p), and this implies that D \not º 0 (mod p^e).

Since the determinant of our matrix is not congruent to zero (mod p^e), it must have a unique solution modulo p^e. Certainly F_h º 0 and (F_h-1-1) º 0 (mod p^e) satisfy the system, and so F_h º 0 and F_h-1 º 1 (mod p^e). From the recurrence relation, F_h+1 º 1 (mod p^e) as well.

Since h = h(p^e) our results tell us that k(p^e) | h(p^e). By theorem 3.15 we know h(p^e) | k(p^e). Hence h(p^e) = k(p^e).

Wall proved several other results regarding the relationship between h(m) and k(m). We present some of these here without proof. As usual, p denotes a prime number.

Theorem 3.17 Let D = G₁² - G₀G₁ - G₀². If gcd(D,m) = 1 then h(m) = k(m).

Theorem 3.18 If h(p^e) = 2t + 1 for some generalized Fibonacci sequence, then k(p^e) = 4t+2.

Theorem 3.19 If p > 2 and k(p^e) = 4t + 2 then there exists some generalized Fibonacci sequence where h(p^e) = 2t+1.

Theorem 3.20 Let p be odd and p ¹ 5. If h(p^e) is even then h(p^e) = k(p^e).

We end the section with two curious theorems pertaining to the period of F(mod m) which did not seem to fit logically elsewhere within this section. We defer their proofs to the end of section 3.3 where we will have developed other ideas sufficiently to make their proofs easy. The curious feature here is that the modulus of the sequence is an actual Fibonacci or Lucas number. Theorem 3.45 can be found in [7] and theorem 3.46 can be found in [17].

Theorem 3.45  If n ³ 5 is odd then k(F_n) = 4n. If n ³ 4 is even then k(F_n) = 2n.

Theorem 3.46  If n ³ 3 is odd then k(L_n) = 2n. If n ³ 2 is even then k(L_n) = 4n.

These theorems indicate that for any even t ³ 6 there is some m such that k(m) = t. Also, k(m) can not equal 4, otherwise F₄ = 3 º 0 and F₃ = 2 º 1 (mod m) which is not possible. Hence the range of k(m) is 3 union the set of all even numbers greater than or equal to 6.

3.2  The Distribution Of Residues

In this section we look at what is known about the distribution of residues within a single period of F(mod m). That is, how frequently each residue is expected to appear. We start off with a more specific question: for which moduli will all the residues appear with equal frequency within a single period? If F(mod m) exhibits this property it is said to be uniform or uniformly distributed. Kuipers and Shiue[12] proved that the only time F(mod m) can possibly be uniform is when m = 5^e.

It is not difficult to see that if F(mod m) is uniform, then necessarily m|k(m). We use this requirement to prove that 5 is the only prime for which F(mod p) is uniform.

We first note that by inspection F(mod 2) is not uniform but F(mod 5) is, with each residue appearing four times per period. Let us consider odd primes p.

If p = 5t ±1 then F(mod p) cannot be uniform. For such p, we know k(p) | p-1, but p \not| p-1 and so p \not| k(p).

If p = 5t ±2 then F(mod p) cannot be uniform. In this case k(p) | 2p+2, but for odd p we know p \not| 2p+2. Hence p \not| k(p). Thus 5 is the only prime for which F(mod p) is uniform.

Now we mention a second fact about uniform distribution: if F(mod m) is uniform and n|m, then F(mod n) is also uniform. Suppose m = nr. Then in one period of F(mod m) each of the residues 0, 1,..., n-1 occurs with equal frequency as do the residues n, n+1,..., 2n-1, and so on until (r-1)n, (r-1)n + 1,..., rn - 1. Thus within k(m) terms of F(mod n) the residues 0, 1, 2, ¼, (n-1) appear with equal frequency, say t times. Since k(n) | k(m) we can find these k(m) terms by simply repeating the first k(n) terms. If [k(m)/ k(n)] = u, then within k(n) terms each residue appears ^t/_u times. Hence F(mod n) is uniform.

Putting these two facts together provides us with the following theorem.

Theorem 3.21 The only possible values of m for which F(mod m) is uniform are m = 5^e.

It takes a very clever proof to finally settle the issue as we will demonstrate next. Niederreiter provided such a proof in [14].

Theorem 3.22 F(mod 5^e) is uniform for all integers e ³ 1.

Before we start in earnest, we present the basic idea behind the proof. We know that k(5^e) = 4 ·5^e and so ``it will suffice to show that among the first 4 ·5^e elements of the sequence, we find exactly four elements, or, equivalently, at most four elements from each residue class mod 5^e."

For example, modulo 5 we see that the residue 3 appears exactly four times per period. Modulo 25, the residues 3, 8, 13, 18, and 23 each appear exactly four times in one period. Each of the five sections in figure 3.1 represents one period mod 5, and the bottom portion shows where the residues 3, 8, 13, 18, and 23 appear in relation to the threes.

Picture Omitted

Figure 0.1: Comparing residues mod 5 and mod 25. The residues mod 25 are ``stratified" to display them more clearly.

Proof:  Let us assume that F(mod 5^r-1) is uniform and we will use induction on r. We have seen that the hypothesis holds for r = 2.

Consider integers a and b such that 0 £ a < 5^r-1 and 0 £ b < 5^r. (In the figure we show a = 3 and r = 2.) F_n º a (mod 5^r-1) has four solutions: n = c₁, c₂, c₃, c₄, with 0 £ c₁, c₂, c₃, c₄ < 4 ·5^r-1. Suppose b º a (mod 5^r-1) and n = d is a solution to F_n º b (mod 5^r) where 0 £ d < 4 ·5^r. Then F_d º a (mod 5^r-1). Hence by periodicity we must have d º c_i (mod 4 ·5^r-1) for some i. We will show that there is only one solution d such that d º c_i (mod 4·5^r) for each i.

Suppose m º n (mod 4 ·5^r-1) and F_m º F_n (mod 5^r). Let 0 £ m,n < 4 ·5^r, and without loss of generality, say m £ n. We will prove that, in fact, m = n.

From identity 2.2, F_n º F_m (mod 5^r) implies

å j = 0  5j æ ç è n 2j+1 ö ÷ ø º 2n-m å j = 0  5j æ ç è m 2j+1 ö ÷ ø mod 5r.

Now 4 ·5^r-1 | n-m and by the Euler-Fermat theorem, f(5^r) = 5^r - 5^r-1 = 4 ·5^r-1. Thus 2^n-m º 1 (mod 5^r). Hence we have,

å j = 0  5j é ê ë æ ç è n 2j+1 ö ÷ ø - æ ç è m 2j+1 ö ÷ ø ù ú û º 0 mod 5r

(3.4)

Here we use the known identity (( s+t) || u ) = å_{i = 0}^u ( s || i ) ( t || ( u-i )) to obtain ( n || ( 2j+1 )) = å_{i = 0}^2j+1 (( n-m) || i ) ( m || ( 2j+1-i )) . That is,

æ ç è n 2j+1 ö ÷ ø = æ ç è m 2j+1 ö ÷ ø + 2j+1 å i = 1  æ ç è n-m i ö ÷ ø æ ç è m 2j+1-i ö ÷ ø .

Substituting this result into equation (3.4) gives us

å j = 0  é ê ë 2j+1 å i = 1  5j æ ç è n-m i ö ÷ ø æ ç è m 2j+1-i ö ÷ ø ù ú û º 0 mod 5r.

We claim that for j ³ 1 each term in brackets is divisible by 5^r. Consider 5^j(( n-m) || i ) = [(5^j(n-m)!)/( i!(n-m-i)!)]. Cancelling out 5's from i! against 5^j always leaves at least one power of 5 in the latter. This is so since the largest value for i is 2j+1 and the largest exponent t such that 5^t divides (2j+1)! is given by

t = ¥ å i = 1  ë 2j+1 5i û < ¥ å i = 1  2j+1 5i = 2j+1 4 < j.

(The above identity can be found in [4]).

Since there is a factor of 5^r-1 in n-m we get the desired divisibility property. Hence only the term corresponding to j = 0 remains. That is, n-m º 0 (mod 5^r). Now we can say that 5^r | n-m and 4 ·5^r-1 | n-m. Thus 4 ·5^r | n-m. We know that 0 £ m,n < 4 ·5^r, and so we must conclude that n = m.

Therefore any residue mod 5^r appears at most four times, which implies that each residue must appear exactly four times, which gives us F(mod 5^r) is uniform. The induction is complete and the theorem proved.

While F(mod m) is uniformly distributed only for m = 5^e, one wonders if there is at least a predictable distribution of residues under different moduli. In 1992 E. T. Jacobson[10] fully described the distribution of residues in F(mod 2^e) and F(mod 2ⁱ ·5^j) for i ³ 5, and j ³ 0. We present his results below without proof.

Let v(m,b) be the number of occurrences of b as a residue in one period of F(mod m). We have seen that v(5^e, b) = 4 for all b (mod 5^e).

Theorem 3.23 For F(mod 2^e) the following is true:

For 1 £ e £ 4:

v(2,0) = 1

v(2,1) = 2

v(4,0) = v(4,2) = 1

v(8,0) = v(8,2) = v(16,0) = v(16,8) = 2

v(16,2) = 4

v(2e,b) = 1 if b º 3 (mod 4) and 2 £ e £ 4

v(2e,b) = 3 if b º 1 (mod 4) and 2 £ e £ 4

v(2e,b) = 0 in all other cases.

For e ³ 5:

v(2e,b) =

1, if b º 3 (mod 4) 2, if b º 0 (mod 8) 3, if b º 1 (mod 4) 8, if b º 2 (mod 32) 0, for all other residues.

For F(mod 2ⁱ ·5^j) where i ³ 5, and j ³ 0, the following is true:

v(2i ·5j,b) =

1, if b º 3 (mod 4) 2, if b º 0 (mod 8)