THE ORDER OF THE FIBONACCI AND LUCAS NUMBERS

T. Lengyel

Occidental College, 1600 Campus Road, Los Angeles, CA 90041 (Submitted October 1993)

1. Introduction

In this paper ν_{p}(r) denotes the exponent of the highest power of a prime p which divides r and is referred to as the p-adic order of r. We characterize the p-adic orders ν_{p}(F_{n}) and ν_{p}(L_{n}), i.e., the exponents of a prime p in the prime power decomposition of F_{n} and L_{n}, respectively.

The characterization of the divisibility properties of combinatorial quantities has always been a popular area of research. In particular, finding the highest powers of primes which divide these numbers (e.g., factorials, binomial coefficients [14], Stirling numbers ([2], [1], [10], and [9]) has attracted considerable attention. The analysis of the periodicity modulo any integer ([3], [11], [14], and [8]) of these numbers helps exploring their divisibility properties (e.g., [9]). The periodic property of the Fibonacci and Lucas numbers has been extensively studied (e.g., [16], [13], [17], and [12]). Here we use some of these properties and methods to find ν_{p}(F_{n}) and ν_{p}(L_{n}). An application of the results to the Stirling numbers of the second kind is discussed at the end of the paper.

We note that Halton [5] obtained similar results on the p-adic order of the Fibonacci numbers, and additional references on earlier developments can be found in Robinson [13] and Vinson [15]. The approach presented here is based on a refined analysis of the periodic structure of the Fibonacci numbers by exploring its properties, in particular, around the points where F_{n} ≡ 0 (mod p). (The smallest n such that F_{n} ≡ 0 (mod p) is called the rank of apparition of prime p and is denoted by n(p).) This technique is based on that of Wilcox [17] and provides a simple and self-contained analysis of properties related to divisibility. For instance, we obtain another characterization of the ratio of the period to the rank of apparition [15] in terms of F_{n(p)−1} (mod p) for any prime p.

Knuth and Wilf [7] generalized Kummer’s result on the highest power of a prime that divides the binomial coefficient. Kummer proved that the p-adic order of a binomial coefficient \binom{n}{m} is the number of “carries” that occur when the integers m and n − m are added in pary notation. Knuth and Wilf extended the use of counting “carries” to a broad class of generalized binomial coefficients which includes the Fibonacci numbers (Theorem 2 in [7]).

2 T. Lengyel

Their method is derived for regularly divisible sequences [7], however, it can be modified to include the Lucas numbers, too. We note that L_{2n} = L_{n}^{2} − 2(−1)^{n}; therefore, (L_{2n}, L_{n}) is either 1 or 2 which illustrates that the Lucas numbers are not regularly divisible.

If m = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}} is the prime-decomposition of m, then ν_{m}(N) = min_{1≤i≤k}⌊ν_{p_{i}}(N)/α_{i}⌋. Therefore, without loss of generality, we will focus on the characterization of ν_{p}(F_{n}) and ν_{p}(L_{n}) where p is a prime.

2. The 2- and 5-adic orders

It turns out that 5-adic order of the Fibonacci and Lucas numbers can be computed easily. For the Fibonacci numbers we use the well known identity [16]

(1)  2^{n−1}F_{n} = ∑_{k=0} \binom{n}{2k + 1}5^{k}, n ≥ 1,

and obtain Lemma 1. For all n ≥ 0 we have ν_{5}(F_{n}) = ν_{5}(n). On the other hand, L_{n} is not divisible by 5 for any n. Proof of Lemma 1. Observe that ν_{5}(\binom{n}{2k+1}5^{k}) = ν_{5}(n) − ν_{5}(2k + 1) + ν_{5}(\binom{n−1}{2k}5^{k}) ≥ ν_{5}(n) − ν_{5}(2k + 1) + k > ν_{5}(n), except for k = 0 when ν_{5}(\binom{n}{2k+1}5^{k}) = ν_{5}(n). Identity (1) implies ν_{5}(F_{n}) = ν_{5}(n).

For the Lucas numbers the period of the sequence {L_{n} mod 5} is 4 with the cycle {1, 3, 4, 2}; therefore, 5 can never be a divisor of L_{n}.

In order to derive the 2-adic orders of F_{n} and L_{n}, we use congruences proved by Jacobson [6]. Lemma A. (Lemma 2 in [6]) Let k ≥ 5 and s ≥ 1. Then F_{2^{k−3}3s} ≡ s2^{k−1} (mod 2^{k}). Lemma B. (Lemma 4 in [6]) Let k ≥ 5 and n ≥ 0 and assume n ≡ 0 (mod 6). Then F_{n+2^{k−3}3} ≡ F_{n} + 2^{k−1} (mod 2^{k}). Lemma C. (Lemma 5 in [6]) Let n ≥ 0 and assume n ≡ 3 (mod 6). Then F_{n} ≡ 2 (mod 32).

We assume that n ≥ 1 from now on. If n ≡ 1 or 2 (mod 3), then we know that F_{n} ≡ 1 (mod 2); thus ν_{2}(F_{n}) = 0 for n ≡ 1, 2 (mod 3). Lemma A yields ν_{2}(F_{12n}) = ν_{2}(n) + 4. By Lemma C, we get ν_{2}(F_{n}) = 1 if n ≡ 3 (mod 6), and Lemma B (in the more convenient form F_{n} ≡ F_{n+12} + 16 (mod 32)) implies that F_{6} = 8 ≡ F_{18} + 16 ≡ F_{30} ≡ F_{42} + 16 ≡ ⋯ (mod 32), and in general, F_{12n+6} ≡ −8 or 8 (mod 32); therefore, ν_{2}(F_{12n+6}) = 3.

THE ORDER OF THE FIBONACCI AND LUCAS NUMBERS 3

Similarly, L_{n} ≡ 1 (mod 2) for n ≢ 0 (mod 3). By the duplication formula F_{2n} = F_{n}L_{n}, it follows that ν_{2}(L_{n}) = ν_{2}(F_{2n})−ν_{2}(F_{n}). Therefore, ν_{2}(L_{6n+3}) = 2 and ν_{2}(L_{6n}) = 1, for it turns out that ν_{2}(L_{12n}) = ν_{2}(L_{12n+6}) = 1.

In summary, Lemma 2.

ν_{2}(F_{n}) = \{ \begin{matrix}0, & if n ≡ 1, 2 mod 3, \\ 1, & if n ≡ 3 mod 6, \\ 3, & if n ≡ 6 mod 12, \\ ν_{2}(n) + 2, & if n ≡ 0 mod 12, \end{matrix}

and

ν_{2}(L_{n}) = \{ \begin{matrix}0, & if n ≡ 1, 2 mod 3, \\ 2, & if n ≡ 3 mod 6, \\ 1, & if n ≡ 0 mod 6. \end{matrix}

3. p-adic orders

In this section we assume that p is a prime different from 2 and 5. It is well known that either F_{p−1} or F_{p+1} is divisible by p for every prime p.

Let n = n(m) be the first positive index for which F_{n} ≡ 0 (mod m). This index is often called the rank of apparition (appearance) or Fibonacci entry-point of m. The order of p in F_{n(p)} will be denoted by e = e(p), i.e., e = e(p) = ν_{p}(F_{n(p)}) ≥ 1, F_{n(p)} ≡ 0 (mod p^{e}) and F_{n(p)} ≢ 0 (mod p^{e+1}). In this paper k(m) denotes the period modulo m of the Fibonacci series.

We shall need Theorem A. (Theorem 3 in [16]) The terms for which F_{n} ≡ 0 (mod m) have subscripts that form a simple arithmetic progression. That is, n = x · d for x = 0, 1, 2, …, and some positive integer d = d(m), gives all n with F_{n} ≡ 0 (mod m).

Note that d(m) is exactly n(m), and d(p^{i}) = d(p) = n(p), for all 1 ≤ i ≤ e(p). It also follows that F_{m} ≢ 0 (mod p) unless m is a multiple of n(p). Clearly, (p, n(p)) = 1. From now on we will focus on indices of the form cn(p)p^{α} where c ≥ 1 and α ≥ 0 integers, and (c, p) = 1.

We prove Theorem. For p ≠ 2 and 5,

(2)  ν_{p}(F_{n}) = \{ \begin{matrix}ν_{p}(n) + e(p), & if n ≡ 0 (mod n(p)), \\ 0, & if n ≢ 0 (mod n(p)), \end{matrix}

and

(3)  ν_{p}(L_{n}) = \{ \begin{matrix}ν_{p}(n) + e(p), & if k(p) ≠ 4n(p) and n ≡ \frac{n(p)}{2} (mod n(p)), \\ 0, & otherwise. \end{matrix}

Proof of the Theorem. The basic idea of the proof is based on the identity [16]

(4)  F_{an} = 2^{1−a}F_{n}(KF_{n}^{2} + aL_{n}^{a−1}),

where K is an integer. We set a = p, α ≥ 1, and n = cn(p)p^{α−1} such that (c, p) = 1. Identity (4) and Theorem A imply that

F_{cn(p)p^{α}} = 2^{1−p}F_{cn(p)p^{α−1}}(K′p^{2} + pL_{cn(p)p^{α−1}}^{p−1}),

with some integer K′; therefore,

ν_{p}(F_{cn(p)p^{α}}) = ν_{p}(F_{cn(p)p^{α−1}}) + 1,

for (F_{n}, L_{n}) is either 1 or 2, and inductively,

(5)  ν_{p}(F_{cn(p)p^{α}}) = ν_{p}(F_{cn(p)}) + α.

We now prove ν_{p}(F_{cn(p)}) = ν_{p}(F_{n(p)}). The multiplication identity [4]

(6)  F_{kn} ≡ kF_{n}F_{n+1}^{k−1} (mod F_{n}^{2})

yields F_{cn(p)} ≡ cF_{n(p)}F_{n(p)+1}^{c−1} (mod p^{2e}) by setting n = n(p), k = c, and e = e(p). We show that (F_{n(p)+1}, p) = 1 by deriving the congruences

(7)  F_{n(p)+1}^{2} ≡ F_{n(p)−1}^{2} ≡ \{ \begin{matrix}−1 mod p, & if k(p) = 4n(p), \\ +1 mod p, & otherwise, \end{matrix}

which prove that ν_{p}(F_{cn(p)}) = ν_{p}(F_{n(p)}), for (c, p) = 1, and ν_{p}(F_{n(p)}) = e < 2e. Identity (5) implies ν_{p}(F_{cn(p)p^{α}}) = ν_{p}(F_{n(p)}) + α = e(p) + α and identity (2).

In order to prove identity (7), we set

(8)  F_{n(p)−1} ≡ x (mod p),

and observe that the Fibonacci series around the term F_{n(p)} ≡ 0 (mod p) must have the form ⋯, −8x, 5x, −3x, 2x, −x, x, 0, x, x, 2x, 3x, 5x, 8x, · · ·. This sequence can be continued backward until we reach the term F_{1} = 1, i.e., (−1)^{n(p)}F_{n(p)−1}x ≡ 1 (mod p). The forward continuation yields F_{2n(p)−1} ≡ F_{n(p)−1}x (mod p). If n(p) is even then

(9)  F_{n(p)−1}x ≡ 1 (mod p)

and by identity (8), x^{2} ≡ 1 (mod p) follows, i.e., F_{n(p)−1} ≡ x ≡ ±1 (mod p). On the other hand, F_{n(p)−1}x ≡ 1 (mod p) implies that if x ≡ 1 (mod p) then k(p) = n(p), and n(p)/2 is odd (see [17], Theorem 1, case (iv)). It follows that k(p) is not a multiple of 4 thus p ≡ ±1 (mod 10) (see [16], Corollary, p. 529). On the other hand, if x ≡ −1 (mod p) then F_{n(p)−1} ≡ −1, F_{2n(p)−1} ≡ F_{n(p)−1}x ≡ 1 (mod p), therefore, k(p) = 2n(p).

If n(p) is odd then F_{n(p)−1}x ≡ −1 (mod p), and similarly to identity (8) we set

F_{2n(p)−1} ≡ y (mod p)

and repeat the previous argument by substituting the even 2n(p) for n(p) and y for x. Here we have F_{2n(p)−1}y ≡ 1 and y^{2} ≡ 1 (mod p) with y ≡ F_{2n(p)−1} ≡ F_{n(p)−1}x ≡ −1 (mod p). By identity (8), we obtain that x^{2} ≡ −1 (mod p). We know from [16] that k(p) must be even and a multiply of n(p), therefore k(p) = 4n(p) must hold. This case occurs, for example, if p is 13, 17, or 61.

To prove identity (3), we apply the duplication formula L_{n} = \frac{F_{2n}}{F_{n}} from which we can easily deduce ν_{p}(L_{n}). We have three cases: either n ≢ 0 (mod n(p)) and 2n ≢ 0 (mod n(p)), or n ≢ 0 (mod n(p)) but 2n ≡ 0 (mod n(p)), or n ≡ 0 (mod n(p)).

In the first case, ν_{p}(F_{2n}) = ν_{p}(F_{n}) = 0 implies that ν_{p}(L_{n}) = 0. Similarly, the third case yields ν_{p}(F_{2n}) = ν_{p}(F_{n}) = ν_{p}(n) + e(p) and ν_{p}(L_{n}) = 0. The second case can never happen if n(p) is odd, that is, k(p) = 4n(p). Otherwise, n = d· \frac{n(p)}{2} must hold with some odd integer d; therefore, ν_{p}(F_{2n}) = ν_{p}(F_{dn(p)}) = ν_{p}(d) + e(p) while ν_{p}(F_{n}) = 0 for n is not a multiple of n(p). The p-adic order of L_{n} is now ν_{p}(n) + e(p).

In passing, we note that we fully characterized \frac{k(p)}{n(p)} in terms of x ≡ F_{n(p)−1} (mod p) and we found Lemma 3.

k(p) = n(p), iff x ≡ 1 mod p,
k(p) = 2n(p), iff x ≡ −1 mod p,
k(p) = 4n(p), iff x^{2} ≡ −1 mod p.

In the first case, p must have the form 10l ± 1 while the third case requires that p = 4l + 1.

We note that identities (6) and (7) actually imply Lemma 4. For every even c and p such that (c, p) = 1,

F_{cn(p)} ≡ \{ \begin{matrix}(−1)^{\frac{c−2}{2}} cF_{n(p)}F_{n(p)+1} (mod p^{2}), & if k(p) = 4n(p), \\ cF_{n(p)}F_{n(p)+1} (mod p^{2}), & otherwise. \end{matrix}

For every odd c and p such that (c, p) = 1,

F_{cn(p)} ≡ \{ \begin{matrix}(−1)^{\frac{c−1}{2}} cF_{n(p)} (mod p^{2}), & if k(p) = 4n(p), \\ cF_{n(p)} (mod p^{2}), & otherwise. \end{matrix}

The theorem yields ν_{p}(F_{cn(p)p^{α}}) = α + 1 if e(p) = ν_{p}(F_{n(p)}) = 1. We note that a prime p is called a primitive prime factor of F_{n} if p|F_{n}, but p does not divide any preceding number in the sequence. According to our notation p is a primitive prime factor of F_{n(p)}. We can consider the primitive part F′_{n} of F_{n} for which F_{n} = F′_{n} · F′′_{n} such that (F′_{n}, F′′_{n}) = 1, and p divides F′_{n} if and only if p is a primitive prime factor of F_{n}. If we set m = n(p) then F′_{m} is square-free exactly if e(p′) = 1 for every primitive prime factor p′ of F_{m}, e.g., for p′ = p. (Clearly, m = n(p′) for all these prime factors.) It appears, however, that saying anything about F′_{n} being square-free is a difficult problem ([12], p. 49). The interested reader will find a lively discussion on the primitive prime factors of the generalized Lucas sequences in [12].

4. An application

It turns out that the 5-adic analysis of the series F_{n} and L_{n} plays a major role in determining ν_{5}(k!S(n, k)) where S(n, k) denotes the Stirling numbers of the second kind and n = a · 5^{q}, k = 2b · 5^{z}, a, b, and q are positive integers such that (a, 5) = (b, 5) = 1, and 4|a, while z is a nonnegative integer. For instance, if q is sufficiently large and z > 0 then we can derive the identities

k! S(n, k) ≡ −2 · 5^{\frac{b}{2} 5^{z}−1}L_{b·5^{z}} (mod 5^{q+1}), if b is even,

and

k! S(n, k) ≡ 2 · 5^{\frac{b·5^{z} −1}{2}} F_{b·5^{z}} (mod 5^{q+1}), if b is odd.

In general, for even k, we obtain

ν_{5}(k! S(n, k)) = \{ \begin{matrix}\frac{k}{4} − 1, & if k ≡ 0, 4, 8, 12, 16 (mod 20), \\ \frac{k−2}{4}, & if k ≡ 2, 6, 14 (mod 20), \\ \frac{k−2}{4} + ν_{5}(k), & if k ≡ 10 (mod 20), \\ \frac{k−2}{4} + ν_{5}(k + 2), & if k ≡ 18 (mod 20). \end{matrix}

THE ORDER OF THE FIBONACCI AND LUCAS NUMBERS 7

Notice that for n = a·5^{q}, 4|a, (a, 5) = 1, and q sufficiently large, ν_{5}(k! S(n, k)) can depend on n only if k is odd. Actually, it does depend on n if and only if k/5 is an odd integer. The proof will appear in a forthcoming paper. We note that the above identities are generalizations of the identity

ν_{2}(k!S(n, k)) = k − 1,

where n = a · 2^{q}, a is odd, and q is sufficiently large (see [9]).

Acknowledgment

The author would like to thank the referee for helpful comments and drawing his attention to a significant reference.

\underline{References}

1. Clarke, F., Hensel’s lemma and the divisibility by primes of Stirling-like numbers, preprint, 1993

2. Davis, D. M., Divisibility by 2 of Stirling-like numbers, Proceedings of the American Mathematical Society 110(1990), 597-600.

3. Gessel, I., Congruences for Bell and tangent numbers, Fibonacci Quarterly 19(1981), 137-144.

4. Graham, R. L., Knuth, D. E., and Patashnik, O., Concrete Mathematics, Addison-Wesley, Reading, MA, 1989.

5. Halton, J. H., On the divisibility properties of Fibonacci numbers, Fibonacci Quarterly 4(1966), 217-240.

6. Jacobson, E., Distribution of the Fibonacci numbers mod 2^{k}, Fibonacci Quarterly 30(1992), 211-215.

7. Knuth, D. E. and Wilf, H. S., The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math. 396(1989), 212-219.

8. Kwong, Y. H. Harris, Periodicities of a class of infinite integer sequences modulo M, J. Number Theory 31(1989), 64-79.

8 T. Lengyel

9. Lengyel, T., On the divisibility by 2 of the Stirling numbers of the second kind. Fibonacci Quarterly 32(1994), 194-201.

10. Lundell, A., A divisibility property for Stirling numbers, J. Number Theory 10(1978), 35-54.

11. Nijenhuis, A. and Wilf, H. S., Periodicities of partition functions and Stirling numbers modulo p, J. Number Theory 25(1987), 308-312.

12. Ribenboim, P., The Little Book of Big Primes, Springer-Verlag, New York–Berlin, 1990.

13. Robinson, D. W., The Fibonacci matrix modulo m, Fibonacci Quarterly 1(1963), 29-36.

14. Sved, M., Divisibility–with visibility, Math. Intelligencer 10(1988), 56-64.

15. Vinson, J., The relation of the period modulo m to the rank of apparition of m in the Fibonacci sequence, Fibonacci Quarterly 1(1963), 37-45.

16. Wall, D. D., Fibonacci series modulo m, Amer. Math. Monthly 67(1960), 525-532.

17. Wilcox, H., Fibonacci sequences of period n in groups, Fibonacci Quarterly 24(1986), 356-361.

AMS Classification Numbers: 11B39, 11B50, 11B73