DIVISIBILITY PROPERTIES BY MULTISECTION

Tamás Lengyel

Occidental College, 1600 Campus Road, Los Angeles, CA 90041 December 2000

1. INTRODUCTION

The p-adic order, ν_{p}(r) (often also denoted by ρ_{p}(r)), of r is the exponent of the highest power of a prime p which divides r. We characterize the p-adic order ν_{p}(F_{n}) of the F_{n} sequence using multisection identities. The method of multisection is a helpful tool in discovering and proving divisibility properties. Here it leads to invariants of the modulo p^{2} Fibonacci generating function for p ≠ 5. The proof relies on some simple results on the periodic structure of the series F_{n}.

The periodic properties of the Fibonacci and Lucas numbers have been extensively studied (e.g., [13]). (For a general discussion of the modulo m periodicity of integer sequences see [8].) The smallest positive index n such that F_{n} ≡ 0 (mod p) is called the rank of apparition (or rank of appearance or Fibonacci entrypoint) of prime p and is denoted by n(p). The notion of rank of apparition n(m) can be extended to arbitrary modulus m ≥ 2. The order of p in F_{n(p)} will be denoted by e = e(p) = ν_{p}(F_{n(p)}) ≥ 1. Interested readers might consult [6] and [9] for a list of relevant references on the properties of ν_{p}(F_{n}).

The main focus of this paper is the multisection based derivation of some important divisibility properties of F_{n} (Theorem A) and L_{n} (Theorem D). A result similar to Theorem A was obtained by Halton [4]. A different derivation using a Kummer-like theorem was given in [7]. This latter approach expresses the padic order of generalized binomial coefficients in terms of the number of “carries.” Theorem A can be generalized to include other linear recurrent sequences and a proof without using generating functions was given in [6, Exercise 3.2.2.11]. The latter approach is implicitly based on multisections.

The generating functions of the Fibonacci and Lucas numbers are f(x) = ∑_{n=0}^{∞} F_{n}x^{n} = x/(1 − x − x^{2}) and h(x) = ∑_{n=0}^{∞} L_{n}x^{n} = (2 − x)/(1 − x − x^{2}), respectively. In this paper the general coefficients of these generating functions will be determined by multisection identities, as we prove Theorem A [9]: For all n ≥ 0 we have

ν_{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}

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

The cases p = 2 and p = 5 are discussed in Sections 2 and 3, respectively. The general case is completed in Section 4. The case of p = 2 has been discussed in [5] using a different approach. The multisection based technique offers a simplified treatment of this case. We extend the method to the Lucas numbers in Section 5.

By the m-section of a power series g(x) = ∑_{n=0}^{∞} a_{n}x^{n} we mean the extraction of the sum of terms a_{l}x^{l} in which l is divisible by m. We use the resulting power series g_{m}(x) = ∑_{n=0}^{∞} a_{mn}x^{mn} in its modified form g_{m}(x^{1/m}) = ∑_{n=0}^{∞} a_{mn}x^{n} and call it the m-section, too. The corresponding sequence {a_{mn}}_{n=0}^{∞} of coefficients is referred to as the m-section of the sequence {a_{n}}_{n=0}^{∞}. The notion of m-section can be generalized to form a sum of terms with index l ranging over a fixed congruence class of integers modulo m. It will be used in Sections 2 and 5. There are various general multisection identities (cf. [10, p. 131] or [1, p84.]), and they can be helpful in proving divisibility patterns (e.g., [2]). The m-section of the Fibonacci sequence leads to the form

∑_{n=0}^{∞} F_{mn}x^{n} = \frac{F_{m}x}{1 − L_{m}x + (−1)^{m}x^{2}} .  (1)

The denominators are referred to as Lucas factors. For other application of Lucas factors see [11].

The present proof of Theorem A is based on a multisection invariant. In fact, we will see in (5), (13), and (14) that x/(1 − x)^{2} or x/(1 + x)^{2} is an invariant of the properly sected Fibonacci generating function taken mod p^{2} for every prime p ≠ 5. The power of p can be easily improved.

We shall need some facts on the location of zeros in the series {F_{n} mod m}_{n≥0}.

Theorem B (Theorem 3 in [13]): The terms for which F_{n} ≡ 0 (mod m) have subscripts that form a simple arithmetic progression. That is, for some positive integer d = d(m) and for x = 0, 1, 2, …, n = x · d 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_{l} ≢ 0 (mod p) unless l is a multiple of n(p).

We denote the modulo m period of the Fibonacci series by π(m). Gauss proved that the ratio \frac{π(p)}{n(p)} is 1, 2, or 4. In fact, we get

Lemma C [9]: The ratio \frac{π(p)}{n(p)} can be fully characterized in terms of x ≡ F_{n(p)−1} ≡ F_{n(p)+1} (mod p) by

π(p) = \{ \begin{matrix}n(p), & iff x ≡ 1 (mod p), \\ 2n(p), & iff x ≡ −1 (mod p), \\ 4n(p), & iff x^{2} ≡ −1 (mod p). \end{matrix}

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

We also will repeatedly use two identities (cf. (23) and (24) in [12]) for the Lucas numbers with arbitrary integers h ≥ 0:

L_{2h} = 2(−1)^{h} + 5F_{h}^{2},  (2)
L_{h}^{2} = 4(−1)^{h} + 5F_{h}^{2}.  (3)

It is worth noting that our proofs of Theorems A and D rely on three congruences for the Lucas numbers (cf. Lemmas 1, 2, and 3) which in turn can be significantly improved (cf. Lemmas 1’, 2’ and 3’) using the theorems.

2. THE CASE OF p = 2

By adding together the six 6-sections ∑_{n=0}^{∞} F_{6n+l}x^{6n+l}, l = 0, 1, …, 5, of the generating function f(x), we obtain

f(x) = \frac{x + x^{2} + 2 x^{3} + 3 x^{4} + 5 x^{5} + 8 x^{6} − 5 x^{7} + 3 x^{8} − 2 x^{9} + x^{10} − x^{11}}{1 − 18 x^{6} + x^{12}}

which is equivalent to the recurrence relation F_{n+12} = 18F_{n+6} − F_{n}, F_{0} = 0, F_{1} = 1, …, F_{11} = 89. This immediately implies that

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

It remains to be proven that

ν_{2}(F_{12· n}) = ν_{2}(n) + 4.  (4)

To this end, first we note that

Lemma 1: L_{12· 2^{k}} ≡ 2 (mod 2^{2}) for all k ≥ 0.

In fact, the modulo 4 period of F_{n} is 6, and this implies L_{6j} ≡ 2F_{6j+1} ≡ 2 (mod 4) for every integer j ≥ 0.

By identity (1), we obtain that for all k ≥ 0

∑_{n=0}^{∞} \frac{F_{12· 2^{k}n}}{F_{12· 2^{k}}} x^{n} = \frac{x}{1 − L_{12· 2^{k}}x + x^{2}} ≡ \frac{x}{(1 − x)^{2}} ≡ ∑_{n=1}^{∞} nx^{n} (mod 2^{2}) (5)

We have F_{12} = 144 = 2^{4} · 9. By setting k = 0 and n = 2 in (5) it follows that F_{12· 2}/F_{12} ≡ 2 (mod 2^{2}), thus ν_{2}(F_{24}) = ν_{2}(F_{12}) + 1 = 5. In general, we use n = 2 and observe that ν_{2}(F_{12· 2^{k+1}}) = ν_{2}(F_{12· 2^{k}})+1 = … = ν_{2}(F_{12})+k+1 = 4+ν_{2}(2^{k+1}) follows by a simple inductive argument. We complete the proof of (4) by noting that for n odd ν_{2}(F_{12· 2^{k}n}) = ν_{2}(F_{12· 2^{k}}) holds by (5).

A sharper version of Lemma 1 can be derived from Theorem A (once it has been proven):

Lemma 1’: L_{12· 2^{k}} ≡ 2 (mod 2^{2k+6}) for all k ≥ 0.

Proof of Lemma 1’. We note that L_{12· 2^{k}} ≡ 2 (mod 2^{k+3}) can be easily derived from the periodicity of F_{n}, for L_{12· 2^{k}} ≡ 2F_{12· 2^{k}+1} ≡ 2 (mod 2^{k+3}) as π(2^{l}) = 12· 2^{l−3}, l ≥ 1. We notice, however, that the sharper L_{12} = 322 ≡ 2 (mod 2^{6}) also holds. Moreover, identity (2) yields L_{12· 2^{k+1}} ≡ 2 (mod F_{12· 2^{k}}^{2}), and we derive that L_{12· 2^{k+1}} ≡ 2 (mod (2^{4+k})^{2}) using Theorem A. Accordingly, we can replace the exponent of p in identity (5).

3. THE CASE OF p = 5

This case is a little more involved. We will find ν_{5}(F_{5^{k}n}), k ≥ 1, in terms of ν_{5}(F_{5^{k}}) in three steps. In the first two we assume that (n, 5) = 1 then we deal with the case of n = 5.

First we take the 5-section of f(x) and obtain

∑_{n=0}^{∞} \frac{F_{5n}}{F_{5}} x^{n} = \frac{x}{1 − 11x − x^{2}} ≡ \frac{x}{1 − x − x^{2}} ≡ ∑_{n=1}^{∞} F_{n}x^{n} (mod 5)

which guarantees that ν_{5}(F_{5n}) = ν_{5}(F_{5}) if (n, 5) = 1. In the second step we try to generalize this relation for indices of the form 5^{k}n, (n, 5) = 1, k ≥ 2. We shall need

Lemma 2: L_{5^{k+1}} − L_{5^{k}} ≡ 0 (mod 25) for k ≥ 1.

Proof of Lemma 2. By identity (3), we have for k ≥ 1 that

L_{5^{k+1}}^{2} − L_{5^{k}}^{2} ≡ 0 (mod F_{5^{k}}^{2}).

It follows that

(L_{5^{k+1}} − L_{5^{k}})(L_{5^{k+1}} + L_{5^{k}}) ≡ 0 (mod 25)  (6)

by Theorem B. Clearly,

L_{5^{k+1}} ≡ L_{5^{k}} ≡ L_{5} ≡ 1 (mod 5),  (7)

thus the factor L_{5^{k+1}} + L_{5^{k}} cannot be a multiple of 5. Therefore, L_{5^{k+1}} − L_{5^{k}} ≡ 0 (mod 25) by identity (6).

We note that ν_{5}(F_{25}) = 2. It is true that for k ≥ 1

∑_{n=0}^{∞} (\frac{F_{5^{k+1}n}}{F_{5^{k+1}}} − \frac{F_{5^{k}n}}{F_{5^{k}}})x^{n} = \frac{x}{1 − L_{5^{k+1}}x − x^{2}} − \frac{x}{1 − L_{5^{k}}x − x^{2}}
= (L_{5^{k+1}} − L_{5^{k}})\frac{x}{1 − L_{5^{k+1}}x − x^{2}} \frac{x}{1 − L_{5^{k}}x − x^{2}} .

The first factor is divisible by 25 according to Lemma 2. For (n, 5) = 1, we get

ν_{5}(F_{5^{k}n}/F_{5^{k}}) = ν_{5}(F_{5^{k−1}n}/F_{5^{k−1}}) = … = ν_{5}(F_{5n}/F_{5}) = 0,  (8)

i.e., ν_{5}(F_{5^{k}n}) = ν_{5}(F_{5^{k}}) by induction on k ≥ 1.

Now we turn to the case of n = 5. For k ≥ 1 and n = 5 we get that F_{5^{k+2}}/F_{5^{k+1}} ≡ F_{5^{k+1}}/F_{5^{k}} (mod 25); therefore, ν_{5}(F_{5^{k+2}}) = ν_{5}(F_{5^{k+1}}) + 1 = … = ν_{5}(F_{5}) + k + 1 by induction using ν_{5}(F_{25}/F_{5}) = 1. The proof of the case p = 5 is now complete.

Note that, once it is proven, Theorem A guarantees the much stronger Lemmas 2’: L_{5^{k+1}} ≡ L_{5^{k}} (mod 5^{2k}) for k ≥ 1.

We note that an alternative derivation of (8) is possible by (7) but without using Lemma 2:

\frac{x}{1 − L_{5^{k+1}}x − x^{2}} \frac{x}{1 − L_{5^{k}}x − x^{2}} ≡ ∑_{n=0}^{∞} F_{n}^{(2)}x^{n} (mod 5)

with F_{n}^{(2)} being the 2-fold convolution of the sequence F_{n}. The m-fold convolution of the sequence F_{n} is defined by

F_{n}^{(m)} = ∑_{i_{1}+i_{2}+···+i_{m}=n} F_{i_{1}}F_{i_{2}} … F_{i_{m}}

which has the generating function [f(x)]^{m}. Note that by identity (7.61) in [3, p.354] F_{n}^{(2)} = \frac{1}{5}(2nF_{n+1} − (n + 1)F_{n}) = \frac{n}{5}(2F_{n+1} − F_{n}) − \frac{1}{5}F_{n} = \frac{n}{5}L_{n} − \frac{1}{5}F_{n}. We can easily find the period of F_{n}^{(m)} by the general theory (cf. [8]) or by simple inspection. The latter approach provides us with the actual elements of the period. It is clear that 100 is the modulo 25 period of nL_{n} − F_{n}, and nL_{n} − F_{n} is divisible by 25 if n is divisible by 5. It follows that 5|F_{n}^{(2)} if 5|n.

4. THE GENERAL CASE In this section p is a prime different from 2 and 5, and n denotes an integer

for which ν_{p}(n) is either 0 or 1. We will either use an n(p)p^{k}- or a 2n(p)p^{k}-section in obtaining the required divisibility properties. First we prove Lemma 3: For any prime p ≡ 3 (mod 4)

L_{n(p)p^{k}} ≡ \{ \begin{matrix}2 (mod p^{2}), & if π(p)/n(p) = 1 \\ −2 (mod p^{2}), & if π(p)/n(p) = 2 \end{matrix} .

Proof of Lemma 3. Formula (3) yields that if h ≥ 0 is even then L_{2h}^{2} − L_{h}^{2} ≡ 0 (mod F_{h}^{2}). Note that n(p) is even for p ≡ 3 (mod 4) [13]. By setting h = n(p)p^{k} we obtain

(L_{2n(p)p^{k}} − L_{n(p)p^{k}})(L_{2n(p)p^{k}} + L_{n(p)p^{k}}) ≡ 0 (mod p^{2})  (9)

Therefore, either

L_{2n(p)p^{k}} ≡ L_{n(p)p^{k}} (mod p^{2})  (10)

or

L_{2n(p)p^{k}} ≡ −L_{n(p)p^{k}} (mod p^{2}),  (11)

for otherwise both L_{2n(p)p^{k}} − L_{n(p)} and L_{2n(p)p^{k}} + L_{n(p)p^{k}} will be divisible by p. It would lead to L_{n(p)p^{k}} ≡ 0 (mod p) which is impossible as L_{n(p)p^{k}} ≡ 2F_{n(p)p^{k}+1} (mod p). According to identity (2), L_{2n(p)} = 2 + 5F_{n(p)}^{2} which yields L_{2n(p)} ≡ 2 (mod p^{2}) and also

L_{2n(p)p^{k}} ≡ 2 (mod p^{2})  (12)

by Theorem B [13].

If π(p)/n(p) = 1 then F_{n(p)+1} ≡ 1 (mod p) by Lemma C, and we get L_{2n(p)} ≡ L_{n(p)} ≡ 2 (mod p) and, similarly, L_{2n(p)p^{k}} ≡ L_{n(p)p^{k}} ≡ 2F_{2n(p)p^{k}+1} ≡ 2 (mod p) leading to (10). If π(p)/n(p) = 2 then F_{n(p)+1} ≡ −1 (mod p) and L_{2n(p)} ≡ −L_{n(p)} ≡ 2 (mod p) and L_{2n(p)p^{k}} ≡ −L_{n(p)p^{k}} ≡ 2 (mod p) corresponding to (11).

We are now able to finish the proof of Theorem A. In the case of π(p)/n(p) = 1 and 2, we can use

∑_{n=0}^{∞} \frac{F_{n(p)· p^{k}n}}{F_{n(p)· p^{k}}} x^{n} = \frac{x}{1 − L_{n(p)· p^{k}}x + x^{2}} ≡ \frac{x}{(1 ± x)^{2}} ≡ ∑_{n=1}^{∞}(∓1)^{n−1}nx^{n} (mod p^{2})

(13)

which proves ν_{p}(F_{n(p)p^{k}n}) = ν_{p}(F_{n(p)p^{k}}) + ν_{p}(n) for ν_{p}(n) ≤ 1. In particular, by setting n = p we obtain ν_{p}(F_{n(p)p^{k+1}}) = ν_{p}(F_{n(p)p^{k}}) + 1, and ν_{p}(F_{n(p)p^{k+1}}) = e(p) + k + 1 follows by induction on k ≥ 0. In summary, we derived that ν_{p}(F_{n(p)p^{k}n}) = e(p) + k + ν_{p}(n) and the proof is now complete.

On the other hand, if π(p)/n(p) = 4 then we switch from using a n(p)p^{k}-section to a 2n(p)p^{k}-section. By the duplication formula (cf. [3] or [12]) we get F_{2n(p)p^{k}n} = F_{n(p)p^{k}n}L_{n(p)p^{k}n} for any integer n > 0. This yields ν_{p}(F_{2n(p)p^{k}n}) = ν_{p}(F_{n(p)p^{k}n}). We consider

∑_{n=0}^{∞} \frac{F_{2n(p)p^{k}n}}{F_{2n(p)p^{k}}} x^{n} = \frac{x}{1 − L_{2n(p)p^{k}}x + x^{2}} .

Identity (12) implies that

∑_{n=0}^{∞} \frac{F_{2n(p)p^{k}n}}{F_{2n(p)p^{k}}} x^{n} ≡ \frac{x}{(1 − x)^{2}} ≡ ∑_{n=1}^{∞} nx^{n} (mod p^{2}).  (14)

The proof can be concluded as above for ν_{p}(F_{n(p)p^{k}n}) = ν_{p}(F_{2n(p)p^{k}n}) = ν_{p}(F_{2n(p)}) + k + ν_{p}(n) = ν_{p}(F_{n(p)}) + k + ν_{p}(n) = e(p) + k + ν_{p}(n).

By means similar to Lemma 1’, we can prove a stronger version of Lemma 3

Lemma 3’: For any prime p ≡ 3 (mod 4)

L_{n(p)p^{k}} ≡ \{ \begin{matrix}2 (mod p^{2(k+e(p))}), & if π(p)/n(p) = 1 \\ −2 (mod p^{2(k+e(p))}), & if π(p)/n(p) = 2 \end{matrix} .

Proof of Lemma 3’. We know that ν_{p}(F_{n(p)p^{k}}^{2}) = 2(k +e(p)) by Theorem A. Thus we can replace p^{2} by p^{2(k+e(p))} in identities (9)–(14).

We note that according to Lemmas 1’ and 3’, the denominators of the multisection identities (5), (13), and (14) have either 1 or −1 as a double root modulo some p-power with exponent 2k + 6 or 2(k + e(p)). This observation, combined with the remarks made in the proofs of the lemmas, helps in obtaining the full description of the structure of the periods of the corresponding multisected sequences [cf. (5), (13), and (14)] with respect to above mentioned p-power moduli (p ≠ 5).

5. LUCAS NUMBERS

By using methods we applied to the Fibonacci sequence, we obtain

∑_{n=0}^{∞} L_{n}x^{n} = \frac{2 + x + 3 x^{2} + 4 x^{3} + 7 x^{4} + 11 x^{5} − 18 x^{6} + 11 x^{7} − 7 x^{8} + 4 x^{9} − 3 x^{10} + x^{11}}{1 − 18 x^{6} + x^{12}}

which proves that

ν_{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}

If p = 5 then the modulo 5 periodic pattern of L_{n} is 2, 1, 3, 4, and thus 5 |̸L_{n}.

If p ≠ 2, 5 then the order ν_{p}(L_{n}) can be derived easily by the duplication formula and Theorem A (see [9]). Here, for the sake of uniformity, we use multisection identities. We need the companion multisection identity to (1) for the Lucas sequence

h_{m}(x) = ∑_{n=0}^{∞} L_{mn}x^{n} = \frac{2 − L_{m}x}{1 − L_{m}x + (−1)^{m}x^{2}} .  (15)

As L_{n} = F_{2n}/F_{n}, we see that L_{n} is divisible by p only if 2n is a multiple of n(p) while n is not; in other words if n is an odd multiple of n(p)/2. This implies that we have to deal only with the case in which n(p) is even. The generalized \frac{n(p)}{2}–sected Lucas sequence will suffice to prove

Theorem D: If p ≠ 2 and π(p)/n(p) ≠ 4, then, for every k ≥ 0 and m = (n(p)/2) p^{k}

l(x) = ∑_{2 |̸n} \frac{L_{mn}}{L_{m}} x^{n} ≡ \{ \begin{matrix}\frac{x(1+x^{2})}{(1−x^{2})^{2}} ≡ ∑_{2 |̸n} nx^{n} (mod p^{2}), & if π(p)/n(p) = 1 \\ \frac{x(1−x^{2})}{(1+x^{2})^{2}} ≡ ∑_{2 |̸n}(−1)^{\frac{n−1}{2}} n x^{n} (mod p^{2}), & if π(p)/n(p) = 2 \end{matrix}

yielding ν_{p}(L_{n}) = ν_{p}(n) + e(p) if n ≡ n(p)/2 (mod n(p)).

Proof of Theorem D. Note that the conditions guarantee that n(p) is even. We discuss the case in which π(p)/n(p) = 1 with k = 0 only, while the other cases can be carried out similarly. We note that

L_{n(p)/2} l(x) = h_{n(p)/2}(x) − h_{n(p)}(x^{2}).

It is known that n(p)/2 is odd if π(p)/n(p) = 1 (cf. [9]). The common denominator of the above difference can be simplified. In fact, according to identity (15), the denominator of h_{n(p)}(x^{2}) is 1 − L_{n(p)}x^{2} + x^{4} = 1 − (L_{n(p)/2}^{2} + 2)x^{2} + x^{4} by L_{n(p)} = L_{n(p)/2}^{2} − 2(−1)^{n(p)/2} which follows by (2) and (3). We get 1 − L_{n(p)}x^{2} + x^{4} = (1 − x^{2})^{2} − L_{n(p)/2}^{2}x^{2} ≡ (1 − x^{2})^{2} (mod p^{2}). Finally, it is easy to see that l(x) simplifies to

\frac{x(1 + x^{2})}{(1 − x^{2})^{2}} (mod p^{2}).

The exponent of p can be increased to 2(k + e(p)) in the above proof and therefore in the theorem also.

ACKNOWLEDGMENT

I wish to thank Greg Tollisen and the anonymous referee for making many helpful suggestions and comments that improved the presentation of this paper.

REFERENCES

1. L. Comtet. Advanced Combinatorics. Dordrecht: D. Reidel, 1974.

2. I. Gessel and T. Lengyel. “On the Order of Stirling Numbers and Alternating Binomial Coefficient Sums.” The Fibonacci Quarterly 39.5 (2001):444– 54.

3. R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. 2nd ed. Reading, MA: Addison-Wesley, 1994.

4. J. H. Halton. “On the Divisibility Properties of Fibonacci Numbers.” The Fibonacci Quarterly 4.3 (1966):217–40.

5. E. Jacobson. “Distribution of the Fibonacci Numbers Mod 2^{k}.” The Fibonacci Quarterly 30.3 (1992):211–15.

6. D. E. Knuth. The Art of Computer Programming, vol. 2: Seminumerical Algorithms. 2nd ed. Reading, MA: Addison-Wesley, 1981.

7. D. E. Knuth and H. S. Wilf. “The power of a prime that divides a generalized binomial coefficient.” J. Reine Angew. Math. 396 (1989):212–19.

8. Y. H. Kwong. “Periodicities of a Class of Infinite Integer Sequences Modulo m.” J. of Numb. Theory 31 (1989):64–79.

9. T. Lengyel. “The Order of the Fibonacci and Lucas Numbers.” The Fibonacci Quarterly 33.3 (1995):234–29.

10. J. Riordan. An Introduction to Combinatorial Analysis. New York: Wiley, 1958.

11. I. Strazdin. “Lucas Factors and a Fibonomial Generating Function.” In Applications of Fibonacci Numbers, 7:401–404. Dordrecht: Kluwer, 1998.

12. S. Vajda. Fibonacci & Lucas Numbers, and the Golden Section, Theory and Applications. Chichester: Ellis Horwood, 1989.

13. D. D. Wall. “Fibonacci Series Modulo m.” Amer. Math. Monthly 67 (1960):525-532.

AMS Classification Numbers: 11B39, 05A15, 11B50, 11B37