THE p-ADIC ORDER OF SOME FIBONOMIAL COEFFICIENTS

DIEGO MARQUES AND PAVEL TROJOVSKÝ

Abstract. Let (F_{n})_{n≥0} be the Fibonacci sequence. For 1 ≤ k ≤ m, the Fibonomial coefficient is defined as

\left[{m \atop k}\right]_{F} = \frac{F_{m−k+1} ⋯ F_{m−1}F_{m}}{F_{1} ⋯ F_{k}} .

In 2013, the authors and Sellers proved that if p is a prime number such that p ≡ −2 or 2 (mod 5), then p | \left[{p^{a+1} \atop p^{a}}\right]_{F} for all integers a ≥ 1. In this paper, we generalize this result by proving the exact division

p^{⌈(a+δ_{p,2})/2⌉} ∥ \left[{p^{a+1} \atop p^{a}}\right]_{F} ,

for all prime p and a ≥ 1 (where δ_{i,j} denotes the Kronecker delta). Moreover, we shall prove that if p ≡ −1 or 1 (mod 5), then p ∤ \left[{p^{a+1} \atop p^{a}}\right]_{F} for all integers a ≥ 1 confirming therefore a recent conjecture.

1. Introduction

Let (F_{n})_{n≥0} be the Fibonacci sequence given by the recurrence relation F_{n+2} = F_{n+1} + F_{n}, with F_{0} = 0 and F_{1} = 1. These numbers are well-known for possessing amazing properties (consult [5] together with its very extensive annotated bibliography for additional references and history).

In 1915, Fontené published a one-page note [1] suggesting a generalization of binomial coefficients, replacing the natural numbers by the terms of an arbitrary sequence (A_{n}) of real or complex numbers.

Since at least the 1960s, there has been much interest in the Fibonomial coefficients \left[{m \atop k}\right]_{F}, which correspond to the choice A_{n} = F_{n}, thus are defined, for 1 ≤ k ≤ m, as

\left[{m \atop k}\right]_{F} := \frac{F_{m−k+1} ⋯ F_{m−1}F_{m}}{F_{1} ⋯ F_{k}} ,  (1.1)

and for k > m, \left[{m \atop k}\right]_{F} = 0. (See, for example, Gould [2] as well as numerous papers referenced therein.) It is surprising that this quantity will always take integer values.

Some authors have been interested in searching for divisibility properties of Fibonomial coefficients. For instance, in 1974, Gould [3] proved several such properties where one of them is an analogous to Hermite’s identity for binomial coefficients.

In recent papers, the authors [13, 14] proved, among other things, that p | \left[{p^{a+1} \atop p^{a}}\right]_{F} for all integers a ≥ 1 and p ∈ {2, 3}. Also, in 2013, the authors and J. Sellers [15] proved that for all primes p such that p ≡ −2 or 2 (mod 5), the number \left[{p^{a+1} \atop p^{a}}\right]_{F} is divisible by p, for all integers a ≥ 1.

Key words and phrases. Generalized binomial coefficients, Fibonacci numbers, Fibonacci coefficients, order of appearance, p-adic order, divisibility.

Here, we are interested in the highest power of p which divides \left[{p^{a+1} \atop p^{a}}\right]_{F}. Our first result is the following

Theorem 1.1. Let p be a prime such that p ≡ −2 or 2 (mod 5). Then p^{⌈(a+δ_{p,2})/2⌉} ∥ \left[{p^{a+1} \atop p^{a}}\right]_{F} , for all integers a ≥ 1. Here, δ_{i,j} denotes the Kronecker delta.

As usual, a^{k} ∥ b means that a^{k} | b, but a^{k+1} ∤ b.

In the same paper [15], the following conjecture about the remaining cases of p, suggested by the referee, was raised.

Conjecture 1.2. If p ≡ −1 or 1 (mod 5), then \left[{p^{a+1} \atop p^{a}}\right]_{F} is not divisible by p, for any integer a ≥ 1.

Note that this conjecture, together with [15, Theorem 1.1] and [15, Proposition 2.4], leads to the following result for all odd primes p

p | \left[{p^{a+1} \atop p^{a}}\right]_{F} for all integers a ≥ 1 ⟺ p = 5 or p ≡ −2 or 2 (mod 5).

In this paper, we also confirm this conjecture. We shall state it for the sake of preciseness.

Theorem 1.3. Conjecture 1.2 is true.

We organize this paper as follows. In Section 2, we will recall some useful properties of the Fibonacci numbers such as a result concerning the p-adic order of F_{n}. Section 3 is devoted to the proof of these theorems.

2. Auxiliary results

Before proceeding further, we recall some facts for the convenience of the reader.

Lemma 2.1. We have

(a) For all primes p, F_{p−( \frac{5}{p})} ≡ 0 (mod p) where (\frac{a}{q}) denotes the Legendre symbol of a with respect to a prime q > 2.

(b) (De Polignac formula) For all n ≥ 1, it holds that

ν_{p}(n!) = ∑_{j=1}^{∞} ⌊\frac{n}{p^{j}} ⌋ ,

where the p-adic order (or valuation) of r, ν_{p}(r), is the exponent of the highest power of a prime p which divides r.

Item (a) can be proved by using the well-known Binet’s formula:

F_{n} = \frac{α^{n} − β^{n}}{α − β}, for n ≥ 0,

where α = (1+\sqrt{5})/2 and β = (1−\sqrt{5})/2. The proof of item (b) can be found in [16, Theorem 4.2].

Before stating the next lemma, we recall that for a positive integer n, the order (or rank) of appearance of n in the Fibonacci sequence, denoted by z(n), is defined as the smallest positive integer k, such that n | F_{k}. (Some authors also call it the order of apparition, as it was called by Lucas, or the Fibonacci entry point.) There are several results on z(n) in the literature, for example, recently, the first author [7, 8, 9, 10, 11, 12] found closed formulas for this function at some integers related to the Fibonacci and Lucas sequences.

Lemma 2.2. (Cf. Lemma 2.2 (c) of [8]) If n | F_{m}, then z(n) | m.

Note that Lemma 2.1 (a) together with Lemma 2.2 implies that z(p) | p − (\frac{5}{p}) for all primes p ≠ 5. Also, it is well-known that (\frac{5}{p}) = −1 or 1 according to the residue of p modulo 5. More precisely, we have that if p ≠ 5 is a prime, then z(p) | p + 1 if p ≡ −2 or 2 (mod 5) and z(p) | p − 1 otherwise.

Lemma 2.3. (Cf. Lemma 2.3 of [11]) For all primes p ≠ 5, we have that gcd(z(p), p) = 1.

The p-adic order of Fibonacci numbers has been completely characterized, see [4, 6, 18, 19]. For instance, from the main results of Lengyel [6], we extract the following result.

Proposition 2.4. For n ≥ 1, we have

ν_{2}(F_{n}) = \begin{cases}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{cases}

and for any prime p > 2

ν_{p}(F_{n}) = \begin{cases}ν_{p}(n) + ν_{p}(F_{z(p)}), & if n ≡ 0 (mod z(p)); \\ 0, & if n ≢ 0 (mod z(p)). \end{cases}

A proof of a more general result can be found in [6, p. 236-237 and Section 5].

Now we are ready to deal with the proof of the theorems.

3. Proofs

3.1. Proof of Theorem 1.1. In order to avoid unnecessary repetitions, let us suppose that p > 2 and that a is even (the case p = 2 and when a is odd can be handled in much the same way).

Thus, here we want to prove that

ν_{p} (\left[{p^{a+1} \atop p^{a}}\right]_{F} ) = ⌈\frac{a}{2}⌉

holds for every odd prime p such that p ≡ −2 or 2 (mod 5) for all integer a ≥ 1.

We start the proof by proceeding exactly as in the beginning of the proof of [15, Theorem 1.1]. However, we shall repeat that argument for the convenience of the reader.

By the definition of the Fibonomial coefficient (1.1), we have

\left[{p^{a+1} \atop p^{a}}\right]_{F} = \frac{F_{(p−1)p^{a}+1} ⋯ F_{p^{a+1}}}{F_{1} ⋯ F_{p^{a}}} .  (3.1)

Our goal now is to compare the p-adic order of the numerator and denominator in (3.1). Since p | F_{n} if and only if z(p) | n (by Proposition 2.4), we need only to consider the p-adic order of the (p^{a} − 1)/z(p) numbers F_{z(p)}, F_{2z(p)}, F_{3z(p)}, …, F_{p^{a}−1} in the denominator and F_{(p−1)p^{a}+2}, F_{(p−1)p^{a}+2+z(p)}, F_{(p−1)p^{a}+2+2z(p)}, …, F_{p^{a+1}−z(p)+1} in the numerator. So, in the first case, we use Proposition 2.4 to obtain

S_{1} := ν_{p}(F_{1} ⋯ F_{p^{a}})
= ν_{p}(F_{z(p)}) + ν_{p}(F_{2z(p)}) + ⋯ + ν_{p}(F_{p^{a}−1})
= (ν_{p}(z(p)) + ν_{p}(F_{z(p)})) + (ν_{p}(2z(p)) + ν_{p}(F_{z(p)})) + ⋯ + (ν_{p}(p^{a} − 1) + ν_{p}(F_{z(p)}))
= ν_{p}(z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p}(p^{a} − 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (3.2)

Note that a is even and z(p) | p + 1 (since p ≡ −2 or 2 (mod 5)). Thus (p^{a} − 1)/z(p) is an integer.

For the p-adic order of the numerator, we proceed as before to get

S_{2} := ν_{p}(F_{(p−1)p^{a}+1} ⋯ F_{p^{a+1}})
= ν_{p}(F_{(p−1)p^{a}+2}) + ⋯ + ν_{p}(F_{p^{a+1}−z(p)+1})
= ν_{p}((p − 1)p^{a} + 2) + ⋯ + ν_{p}(p^{a+1} − z(p) + 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)})
= ν_{p}(p(p^{a} − p^{a−1} + z(p) − 2)) + ⋯ + ν_{p}(p(p^{a} − 1)) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)})
= ν_{p}(p^{a} − p^{a−1} + z(p) − 2) + ⋯ + ν_{p}(p^{a} − 1) + \frac{p^{a−1} + 1}{z(p)} +
+ (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (3.3)

Observe that there exist several common terms in sums (3.2) and (3.3), so combining them we get

S_{2} − S_{1} = \frac{p^{a−1} + 1}{z(p)} − (ν_{p}(1z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p} (\frac{p^{a} − p^{a−1} − 2}{z(p)}z(p)))
= \frac{p^{a−1} + 1}{z(p)} − ν_{p} ((\frac{p^{a} − p^{a−1} − 2}{z(p)})!) .

Now, we shall use the De Polignac formula together with some properties of the fractional part of x, defined as {x} = x − ⌊x⌋. Since, for j ≥ a, it holds that

p^{j}z(p) ≥ 3p^{a} > p^{a} − p^{a−1} − 2

and after a straightforward calculation, we arrive at

S_{2} − S_{1} = \frac{p^{a−1} + 1}{z(p)} − ∑_{j=1}^{a−1} ⌊\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}⌋

= \frac{p^{a−1} + 1}{z(p)} − ∑_{j=1}^{a−1} (\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}) + ∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\}

= \frac{2(p^{a} − 1)}{z(p)(p − 1)p^{a−1}} + ∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} .  (3.4)

Now, let us see what happens with {(p^{a} − p^{a−1} − 2)/(p^{j}z(p))} depending on the parity of j. We have that

\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)} = p^{a−j−1} \frac{(p − 1)}{z(p)} − \frac{2}{p^{j}z(p)}.

Since p ≡ −1 (mod z(p)) and a is even, we obtain

p^{a−j−1}(p − 1) ≡ \begin{cases}2 (mod z(p)), & if 2 | j; \\ p − 1 (mod z(p)), & if 2 ∤ j. \end{cases}

Thus

\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)} ≡ \begin{cases}\frac{2}{z(p)} − \frac{2}{p^{j}z(p)} (mod 1), & if 2 | j; \\ \frac{p−1}{z(p)} − \frac{2}{p^{j}z(p)} (mod 1), & if 2 ∤ j. \end{cases}

Now, we use that (p − 1)/z(p) ≡ −2/z(p) (mod 1) (because (p + 1)/z(p) is an integer) together with the facts that {x} = x, if 0 ≤ x < 1, {n + x} = {x} and {n − x} = 1 − {x}, for any positive integer n, to get

\{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} = \begin{cases}\frac{2}{z(p)} (1 − \frac{1}{p^{j}} ) , & if 2 | j; \\ 1 − \frac{2}{z(p)} (1 + \frac{1}{p^{j}} ) , & if 2 ∤ j. \end{cases}

Write A_{1} = {1, 3, 5, …, a − 1} and A_{2} = {2, 4, 6, …, a − 2}. Therefore, the summation in (3.4) can be written as

∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} = ∑_{j∈A_{1}} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} + ∑_{j∈A_{2}} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\}

= ∑_{j∈A_{1}} (1 − \frac{2}{z(p)} − \frac{2}{z(p)p^{j}} ) + ∑_{j∈A_{2}} (\frac{2}{z(p)} − \frac{2}{z(p)p^{j}} ) .

After some easy computations, we get

∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} = \frac{a}{2} (1 − \frac{2}{z(p)}) − \frac{2p^{1−a} (p^{a} − 1)}{(p^{2} − 1) z(p)} + \frac{a − 2}{z(p)} − \frac{2p^{−a} (p^{a} − p^{2})}{(p^{2} − 1) z(p)}.

Combining this with equality (3.4) yields

ν_{p} (\left[{p^{a+1} \atop p^{a}}\right]_{F} ) = S_{2} − S_{1} = \frac{2(p^{a} − 1)}{z(p)(p − 1)p^{a−1}} + \frac{−4p + 4p^{1−a} + az(p)(p − 1)}{2z(p)(p − 1)} = \frac{a}{2}.

This completes the proof. □

3.2. Proof of Theorem 1.3. Again, we must compare the p-adic order of the numerator and denominator in (3.1). Thus, we must only consider the p-adic order of the (p^{a} − 1)/z(p) numbers F_{z(p)}, F_{2z(p)}, F_{3z(p)}, …, F_{p^{a}−1} in the denominator and F_{(p−1)p^{a}+z(p)}, F_{(p−1)p^{a}+2z(p)}, F_{(p−1)p^{a}+3z(p)}, …, F_{p^{a+1}−1} in the numerator. So, in the first case, we use Proposition 2.4 to obtain

S_{1} := ν_{p}(F_{1} ⋯ F_{p^{a}})
= ν_{p}(F_{z(p)}) + ν_{p}(F_{2z(p)}) + ⋯ + ν_{p}(F_{p^{a}−1})
= (ν_{p}(z(p)) + ν_{p}(F_{z(p)})) + (ν_{p}(2z(p)) + ν_{p}(F_{z(p)})) + ⋯ + (ν_{p}(p^{a} − 1) + ν_{p}(F_{z(p)}))
= ν_{p}(z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p}(p^{a} − 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (3.5)

Note that z(p) | p − 1 (since p ≡ −1 or 1 (mod 5)). Thus (p^{a} − 1)/z(p) is an integer. For the p-adic order of the numerator, we proceed as before to get

S_{2} := ν_{p}(F_{(p−1)p^{a}+1} ⋯ F_{p^{a+1}})
= ν_{p}(F_{(p−1)p^{a}+z(p)}) + ⋯ + ν_{p}(F_{p^{a+1}−1})
= ν_{p}((p − 1)p^{a} + z(p)) + ⋯ + ν_{p}(p^{a+1} − 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)})
= ν_{p}((p^{a} − p^{a−1} + z(p)) + ⋯ + ν_{p}(p^{a} − 1) + (\frac{p^{a−1} − 1}{z(p)})
+ (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (3.6)

Observe that there exist several common terms in sums (3.5) and (3.6), so combining them (and using that p ∤ z(p)) we get

S_{2} − S_{1} = \frac{p^{a−1} − 1}{z(p)} − (ν_{p}(z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} ) z(p)))
= \frac{p^{a−1} − 1}{z(p)} − (ν_{p}(1) + ⋯ + ν_{p} (\frac{p^{a} − p^{a−1}}{z(p)} ))
= \frac{p^{a−1} − 1}{z(p)} − ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!) .

Thus, in order to prove this theorem, it suffices to show that

\frac{p^{a−1} − 1}{z(p)} = ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!), for p ≡ ±1 (mod 5),

which yields ν_{p}(\left[{p^{a+1} \atop p^{a}}\right]_{F}) = S_{2} −S_{1} = 0. For that, we shall use Lemma 2.1 (b). Thus we obtain

ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!) = ∑_{j=1}^{∞} ⌊\frac{p^{a−1−j}(p − 1)}{z(p)}⌋ = ∑_{j=1}^{a−1} ⌊\frac{p^{a−1−j}(p − 1)}{z(p)}⌋ + ∑_{j=a}^{∞} ⌊\frac{p^{a−1−j}(p − 1)}{z(p)}⌋ .

Now, note that for 1 ≤ j ≤ a − 1, the number p^{a−1−j}(p − 1)/z(p) is an integer and for j ≥ a, it holds that

0 < \frac{p^{a−1−j}(p − 1)}{z(p)} ≤ \frac{p − 1}{pz(p)} ≤ \frac{p − 1}{3p} < 1,

where we used that z(p) ≥ 3 for any prime p. In conclusion, we get

ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!) = ∑_{j=1}^{a−1} (\frac{p^{a−1−j}(p − 1)}{z(p)}) = \frac{p^{a−1} − 1}{z(p)}

as desired. The proof is therefore complete. □

4. acknowledgements

The authors wish to thank the referee for their helpful comments. This research was supported by the project Prifino EU CZ. This work was made during a very enjoyable visit of the first author to Department of Mathematics at University of Hradec Králové. He thanks the people of this institution for their hospitality. He was also supported in part by CNPq (Conselho Nacional de Pesquisa) and FAP-DF (Fundação de Apoio a Pesquisa do Distrito Federal).

References

[1] G. Fontené, Généralisation d’une formule connue, Nouv. Ann. Math. 4 (1915), 112.

[2] H. W. Gould, The bracket function and Fontené–Ward generalized binomial coefficients with application to Fibonomial coefficients, Fibonacci Quart. 7 (1969), 23–40.

[3] H. W. Gould, Generalization of Hermite’s divisibility theorems and the Mann-Shanks primality criterion for s-Fibonomial arrays, Fibonacci Quart. 12 (1974), 157–166.

[4] J. H. Halton, On the divisibility properties of Fibonacci numbers, Fibonacci Quart. 4 (1966), 217–240.

[5] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, 2001.

[6] T. Lengyel, The order of the Fibonacci and Lucas numbers, Fibonacci Quart. 33 (1995), 234–239.

[7] D. Marques, On integer numbers with locally smallest order of appearance in the Fibonacci sequence, Internat. J. Math. Math. Sci. 2011 (2011), Article ID 407643.

[8] D. Marques, On the order of appearance of integers at most one away from Fibonacci numbers, Fibonacci Quart. 50 (2012), 36–43.

[9] D. Marques, The order of appearance of product of consecutive Fibonacci numbers, Fibonacci Quart. 50 (2012), 132–139.

[10] D. Marques, The order of appearance of powers of Fibonacci and Lucas numbers, Fibonacci Quart. 50 (2012), 239–245.

[11] D. Marques, Fixed points of the order of appearance in the Fibonacci sequence, Fibonacci Quart. 51 (2013), 346–351.

[12] D. Marques, Sharper upper bounds for the order of appearance in the Fibonacci sequence. Fibonacci Quart. 51 (2013), 233–238.

[13] D. Marques and P. Trojovský, On parity of Fibonomial coefficients, Util. Math., to appear.

[14] D. Marques and P. Trojovský, On divisibility properties of Fibonomial coefficients by 3, J. Integer Seq. 15 (2012), Article 12.6.4.

[15] D. Marques, J. Sellers and P. Trojovský, On divisibility properties of certain Fibonomial coefficients by p, Fibonacci Quart. 51 (2013) 78–83.

[16] I. Niven, H. S. Zuckermann and H. L. Montgomery, An introduction to the theory of numbers, Wiley, 1991.

[17] P. Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer-Verlag, 2000.

[18] D. W. Robinson, The Fibonacci matrix modulo m, Fibonacci Quart. 1 (1963), 29–36.

[19] J. Vinson, The relation of the period modulo m to the rank of apparition of m in the Fibonacci sequence, Fibonacci Quart. 1 (1963), 37–45.

MSC2010: 11B39

Departamento de Matemática, Universidade de Brasília, Brasília, 70910-900, Brazil

E-mail address: diego@mat.unb.br

Department of Mathematics, Faculty of Science, University of Hradec Králové, Rokitanského 62, Hradec Králové, 50003, Czech Republic

E-mail address: pavel.trojovsky@uhk.cz