The Congruence of Wolstenholme for Generalized Binomial Coefficients Related to Lucas Sequences

Christian Ballot Département de Mathématiques et Mécanique Université de Caen F14032 Caen Cedex France

              christian.ballot@unicaen.fr

Abstract

In recent years much research has been carried out on extending Wolstenholme classical congruence modulo the cube of a prime to higher prime powers. Here we show that this work can be done in much broader generality by replacing ordinary binomials by Lucasnomials, which are generalized binomial coefficients related to fundamental Lucas sequences. The paper builds on earlier work of Kimball and Webb in relation to the Fibonacci sequence and on recent work of the author related to congruences involving sums of quotients of Lucas sequences. The paper offers what may be a surprising line of development for very classical congruences.

1 Introduction

In 1862 Wolstenholme [37] established a now well-known congruence for binomial coefficients, namely

Theorem 1. Let p be a prime number ≥ 5. Then

\binom{2p − 1}{p − 1} ≡ 1 (mod p^{3}).  (1)

Babbage [1], in 1819, had actually shown that congruence (1) held modulo p^{2} for all primes p greater than 2. There is a survey paper [24] on the numerous generalizations of Theorem 1 discovered since the paper of Wolstenholme appeared in 1862. This survey also contains many other related results.

We focus first our attention on the sligthly more general congruence

\binom{(k + 1)p − 1}{p − 1} ≡ 1 (mod p^{3}),  (2)

which holds for all primes p ≥ 5 and all nonnegative integers k. According to the survey [24], congruence (2) was proved in 1900 by Glaisher [12, p. 21], [13, p. 33].

If A = (A_{n})_{n≥0} is a sequence of complex numbers where A_{0} = 0 and all A_{n} ≠ 0 for n > 0, then one defines, for m and n nonnegative integers, the generalized binomial coefficient

\binom{m}{n}_{A} = \begin{cases}\frac{A_{m}A_{m−1}...A_{m−n+1}}{A_{n}A_{n−1}...A_{1}} , & if m ≥ n ≥ 1; \\ 1, & if n = 0; \\ 0, & otherwise. \end{cases}  (3)

The well-written paper [14] contains a number of early references about these coefficients and investigated several of their general properties. We point out another early reference [34], not often quoted, in which Ward gives two equivalent criteria that imply the integrality of the generalized coefficients \binom{m}{n}_{A} of a sequence of integers A. One of them is that A be a strong divisibility sequence, i.e., one for which A_{gcd(m,n)} = gcd(A_{m}, A_{n}) for all m > n > 0; the other criterion is expressed in terms of ranks of appearance of prime powers in A. The rank of appearance ρ = ρ_{A}(x) of a nonzero integer x with respect to A is, if it exists, the least positive integer t such x divides the integer A_{t}. The equivalence of the two criteria of Ward was essentially rediscovered in [21]. When A is the Fibonacci sequence F = (F_{n})_{n≥0}, defined by F_{0} = 0, F_{1} = 1 and F_{n+2} = F_{n+1} + F_{n} for all n ≥ 0, these binomial coefficients are called Fibonomials. Many papers have studied their properties.

Kimball and Webb [19, Lemma 3] proved an analogue of the Wolstenholme-Glaisher congruence (2), which we rewrite as a theorem below.

Theorem 2. Let p be a prime at least 7 whose rank of appearance ρ in the Fibonacci sequence is of the form p − ϵ_{p}, where ϵ_{p} is ±1. Then for all integers k ≥ 0

\binom{(k + 1)ρ − 1}{ρ − 1}_{F} ≡ ϵ_{p}^{k} (mod p^{3}),  (4)

where the symbol \binom{∗}{∗}_{F} stands for the Fibonomial coefficient.

Some papers have considered the generalized binomial coefficients when A is a fundamental Lucas sequence, that is, a sequence U = U(P, Q) satisfying

U_{0} = 0, U_{1} = 1 and U_{n+2} = P U_{n+1} − QU_{n}, for all n ≥ 0,  (5)

where (P, Q) is a pair of integers, Q nonzero. We will refer to these generalized binomials as Lucasnomial coefficients, or Lucasnomials, in the sequel. Ordinary binomials are Lucasnomial coefficients with parameters (P, Q) = (2, 1), whereas the Fibonomials correspond to (P, Q) = (1, −1). Thus it makes sense to look for a simple congruence for the general Lucasnomial

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} (mod p^{3}),  (6)

valid for an arbitrary Lucas sequence U, that would encompass both the congruence (2) and Theorem 2.

Here ρ represents the rank of appearance of the prime p in U. It is known to exist for all primes p not dividing Q and, for p odd, to divide p − ϵ_{p}, where ϵ_{p} is the Legendre character (D | p) and D is P^{2} − 4Q. To obtain a congruence modulo p^{3} it is necessary to require, as in Theorem 2, that the rank ρ be maximal, i.e., be equal to p − ϵ_{p}. Note that the rank of any prime p is maximal and equal to p for U_{n} = n (D = 0, ϵ_{p} = 0). However, the case ϵ_{p} = 0 only occurs for p = 5 for the Fibonacci sequence F = U(1, −1), a case that Theorem 2 does not address. A calculation for p = 5 yields

\binom{2ρ − 1}{ρ − 1}_{F} = \binom{9}{4}_{F} ≡ 1 (mod 125).  (7)

This residue of 1 at least conforms to what one gets in (2), but does not match the expression ϵ_{p}^{k} of Theorem 2 which would yield 0.

Thus, one needs to generalize the results of the paper [19] from Fibonomial coefficients to Lucasnomial coefficients and include the case ϵ_{p} = 0 in the analysis. However, some of the results leading to Theorem 2 in [19] seem, at first sight, to depend on idiosyncracies of the Fibonacci sequence. Thus, a few numerical calculations helped us believe in the existence of a generalization and were useful in guiding us to it.

Theorem 3. Let U = U(P, Q) be a fundamental Lucas sequence with parameters P and Q. Let p ≥ 5, p ∤ Q, be a prime whose rank of appearance ρ in U is equal to p − ϵ_{p}, where ϵ_{p} is the Legendre character (D | p), D = P^{2} − 4Q. Then for all integers k ≥ 0

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ (−1)^{kϵ_{p}}Q^{kρ(ρ−1)/2} (mod p^{3}),  (8)

where the symbol \binom{∗}{∗}_{U} stands for the Lucasnomial coefficient.

Remark 4. Theorem 3 implies that for all k ≥ 0

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ \binom{2ρ − 1}{ρ − 1}_{U}^{k} (mod p^{3}).

Remark 5. Congruence (2), Theorem 2 and, as readily checked, congruence (7) are implied by Theorem 3. Indeed, the sequence A_{n} = n is U_{n}(2, 1), for which Q = 1 and ϵ_{p} = 0 for all primes. To see that Theorem 2 is a corollary of Theorem 3, it suffices to check that

ϵ_{p} = −(−1)^{ρ(ρ−1)/2},

for every odd prime p > 5 of maximal rank in the Fibonacci sequence U(1, −1). All primes of rank p ± 1 in the Fibonacci sequence must be congruent to 3 (mod 4), since by Euler’s criterion for Lucas sequences (19) we need to have (−1 | p) = −1. If ϵ_{p} = 1, that is, if ρ = p − 1, then ρ(ρ − 1) ≡ 2 (mod 4) so that −(−1)^{ρ(ρ−1)/2} = +1 = ϵ_{p}. If ϵ_{p} = −1, that is, ρ = p + 1, then ρ(ρ − 1) ≡ 0 (mod 4) so −(−1)^{ρ(ρ−1)/2} = −1 = ϵ_{p}.

Remark 6. Although throughout the paper we assume rank maximality, not all is lost when a prime does not have maximal rank. As will be easily inferred from the proof of Theorem 3, we have for general rank a weaker congruence albeit valid for all p ≥ 3 which we state below.

Theorem 7. If a prime p ≥ 3, p ∤ Q, has rank ρ in U(P, Q), then for all integers k ≥ 0

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ (−1)^{k(ρ−1)}Q^{kρ(ρ−1)/2} (mod p^{2}).

Remark 8. Various other Lucasnomial generalizations of the Glaisher congruence (2), besides Theorems 3 and 7, are possible. For one instance, retaining p instead of ρ in the terms of the congruence but replacing p in the modulus by U_{p}, we can prove the theorem.

Theorem 9. Suppose U(P, Q) is a fundamental Lucas sequence with P and Q coprime and U_{2}U_{3}U_{4}U_{6} nonzero. Let p ≥ 5 be a prime. Then for all k ≥ 0 we have the congruence

\binom{(k + 1)p − 1}{p − 1}_{U} ≡ Q^{kp(p−1)/2} (mod U_{p}^{2}).

When U_{p} is a prime then p is the rank of U_{p} so that, in that case, Theorem 9 follows from Theorem 7. For U(1, −1), the Fibonacci sequence, the congruence in Theorem 9 may be deduced from the statement of a problem posed by Ohtsuka [26]. Generalizing the published solution to this problem [4], one can derive Theorem 9.

Section 2 of the paper is devoted to some relevant additional remarks on Lucas sequences, some useful lemmas and to proofs of Theorem 3 and Theorem 7.

For all primes p ≥ 5 and all nonnegative integers k and ℓ, we have the congruence

\binom{kp}{ℓp} ≡ \binom{k}{ℓ} (mod p^{3}).  (9)

This congruence supersedes congruence (2) and was first proved in a collective paper [10] which appeared in 1952. It was reproved by Bailey some forty years later in the paper [2], where the case (k, ℓ) = (2, 1), which is equivalent to Wolstenholme’s congruence (1), is proved first before an induction on k yielded congruence (2) and another proof by induction gave (9). Interestingly another simple argument, combinatorial, reduces the proof of (9) to that of the case (k, ℓ) = (2, 1) in the book [31, solution of exercise 1.14, p. 165].

Similarly in [19], Theorem 2 is used by the authors to produce an analogue of (9) for the Fibonacci sequence U = F. That is, in our notation, for primes p ≥ 7 of rank ρ = p − ϵ_{p}, where ϵ_{p} = ±1, their result [19, p. 296] states that

\binom{kρ}{ℓρ}_{F} ≡ ϵ_{p}^{(k−ℓ)ℓ}\binom{k}{ℓ}_{F′} (mod p^{3}),  (10)

where F′_{t} = F_{ρt} for all t ≥ 0, k, ℓ are integers satisfying k ≥ ℓ ≥ 1. Section 3 states and proves a congruence, Theorem 13, for Lucasnomials \binom{kρ}{ℓρ}_{U} (mod p^{3}) that subsumes the congruences (9) and (10). Here again the proof of this more general result is easily derived from Theorem 3. We raise in passing the question of the existence of a combinatorial argument that would reduce Theorem 13 to the case (k, ℓ) = (2, 1). Lucasnomial coefficients received two distinct combinatorial interpretations in the paper [30], both of which were explained another time in [8]. Also a q-analogue of (9) that uses q-binomial coefficients was established in the paper [32].

In the fourth section, we selected three congruences for binomials \binom{2p−1}{p−1} (mod p^{5}), namely (25), (26) and (27), and establish for each a generalization to Lucasnomial coefficients \binom{2ρ−1}{ρ−1}_{U} (mod p^{5}) for primes p ≥ 7 of maximal rank ρ in U. Not to lengthen an already long introduction we only state the example of congruence (27), i.e.,

\binom{2p − 1}{p − 1} ≡ 1 − p^{2} ∑_{0<t<p} \frac{1}{t^{2}} (mod p^{5}),

which generalizes into

\binom{2ρ − 1}{ρ − 1}_{U} ≡ (−1)^{ρ−1}Q^{\frac{ρ(ρ−1)}{2}} (1 − 4\frac{U_{ρ}^{2}}{V_{ρ}^{2}} ∑_{0<t<ρ} \frac{Q^{t}}{U_{t}^{2}} ) (mod p^{5}),

where U(P, Q) is a fundamental Lucas sequence and V its companion Lucas sequence. The V sequence is defined by V_{0} = 2, V_{1} = P and the same recursion, V_{n+2} = P V_{n+1} − QV_{n} for all n ≥ 0, as the U sequence. Thus, the companion Lucas sequence of U_{n}(2, 1) = n is V_{n}(2, 1) = 2, for all n ≥ 0. At the basis of these results are congruences modulo a prime p or modulo p^{2} for generalized harmonic sums ∑_{t=1}^{ρ−1}(V_{t}/U_{t})^{ν} which are compiled in Lemma 10. We recall that Theorem 1 is intimately linked with the congruence ∑_{t=1}^{p−1} 1/t ≡ 0 (mod p^{2}) for primes p ≥ 5.

Note that the condition that p be of maximal rank in U may be viewed as a quadratic analogue of Artin’s conjecture which gives a positive density (equal to a positive rational number times Artin’s constant) for the set of primes p for which a given a is a primitive root (mod p), when a is a non-square integer and |a| ≥ 2. Hooley [17] proved Artin’s conjecture conditionally to some generalized Riemann hypotheses. So did Roskam [28, 29] for the set of primes p for which a fundamental unit of a quadratic field has maximal order modulo (p). Thus, given U(P, Q), Q not a square, our theorems presumably should also concern sets of primes of positive densities.

In recent years congruences for ordinary binomials \binom{2p−1}{p−1} (mod p^{e}) have been established for larger and larger exponents e [24, pp. 4–6]. No doubt there must be higher corresponding congruences for Lucasnomials. In fact, we end Section 4 with such a congruence, expressed in Theorem 28, when e = 6. Generalizations of (25) are stated in Theorems 20 and 27, those of (26) and the above congruence (27) appear in Theorems 21 and 24 respectively. We added an appendix as a short fifth section where the integrality of all Lucasnomial coefficients \binom{m}{n}_{U} is asserted for all U Lucas sequences, including degenerate cases, provided we make a reasonable amendment to the definition (3).

Familiarity with Lucas sequences is assumed throughout the paper, but the reader may want to consult the introduction of [7] and the references it mentions. Chapter 4 of the book [36] is a useful introduction to these sequences.

Lucasnomial coefficients have already been the object of generalizations of classical arithmetic properties of ordinary binomial coefficients. Kummer’s theorem giving the exact power of a prime p in the binomial coefficient \binom{m+n}{n} as the number of carries in the addition of m and n in radix p was extended to generalized binomials \binom{m+n}{n}_{A}, when A is a strong divisibility sequence of positive integers [21]. That includes, in particular, all Lucas sequences U(P, Q) with positive terms when P and Q are coprime. A further Kummer rule pertaining to generalized binomials \binom{∗}{∗}_{U}, valid for an arbitrary nondegenerate fundamental U Lucas sequence, appears in the preprint [3].

Also various generalizations of the celebrated theorem of Lucas:

\binom{mp + r}{np + s} ≡ \binom{m}{n}\binom{r}{s} (mod p),

where r and s are nonnegative integers less than the prime p, were achieved in terms of Lucasnomials \binom{mp+r}{np+s}_{U}, often under restrictive hypotheses on the Lucas sequence U(P, Q) [35, 16, 18].

In fact both the theorems of Kummer and of Lucas had been generalized in an earlier paper [11] but with respect to q-binomial coefficients.

2 Preliminaries and a proof of Theorem 3

Lucas theory is often developed with the two hypotheses that U(P, Q) is nondegenerate and gcd(P, Q) is 1. The Lucas sequence U(P, Q) is called degenerate whenever the ratio of the zeros α and β of x^{2} − P x + Q is a root of unity. We do not make any of these assumptions here. If U is degenerate then we must have U_{2}U_{3}U_{4}U_{6} = 0. Indeed, if α ≠ β then U_{t} = \frac{α^{t}−β^{t}}{α−β} and the ratio α/β, lying in the quadratic field ℚ(\sqrt{D}), must be a second, third, fourth or sixth root of unity. Thus, some terms of the sequence U will be 0, but rather than discard those Lucas sequences from our analysis, we make a small amendment to the definition (3) to ensure that the corresponding Lucasnomials \binom{m}{n}_{U} are well-defined as rational numbers. Although the hypotheses of Theorems 3 and 13 or of the theorems of Section 4 if applied to a prime p ≥ 11 prevent the corresponding Lucasnomials from having zero terms, this is not necessarily the case if p = 5 or p = 7. With gcd(P, Q) > 1, the Lucas sequence A = U(P, Q) is no longer a strong divisibility sequence. Nevertheless A, or λA, λ an integer, satisfies some ‘convexity’ property. Namely for all prime powers p^{a} (a ≥ 1), p ∤ Q, and for all x and y ≥ 1, we have

# {t ∈ [x + y], p^{a} | A_{t}} ≥ # {t ∈ [x], p^{a} | A_{t}} + # {t ∈ [y], p^{a} | A_{t}}.  (11)

Here, if z is an integer ≥ 1, [z] denotes the set of natural numbers 1, 2, …, z. This property holds because for such prime powers p^{a}, we have p^{a} | U_{t} iff ρ(p^{a}) | t, where ρ(p^{a}) is the rank of appearance of p^{a} in U, and because ⌊x + y⌋ ≥ ⌊x⌋ + ⌊y⌋ for all real numbers x and y.

The convention we adopt for the generalized binomials \binom{m}{n}_{A} of definition (3) is that if there are zero terms in the product ∏_{i=1}^{n} \frac{A_{m+1−i}}{A_{i}} then

a 0 in the numerator and a 0 in the denominator cancel out as a 1.  (12)

With convention (12), property (11) satisfied by A = λU, for all Lucas sequences U, guarantees that the generalized binomial \binom{m}{n}_{A} is a well-defined rational number. Indeed this property implies that the number of 0 terms in the numerator of ∏_{i=1}^{n} \frac{A_{m+1−i}}{A_{i}} is at least that of its denominator. It also implies that \binom{m}{n}_{A}, m and n nonnegative integers, has nonnegative p-adic valuation for all primes p ∤ Q. In fact we can show it is always a rational integer. ^{1}

As already mentioned, to each fundamental Lucas sequence U(P, Q) we associate a companion Lucas sequence V = V (P, Q) which obeys recursion (5), but has initial values V_{0} = 2 and V_{1} = P. The following identities are all classical ones and are all valid no matter what the value of gcd(P, Q) is. We will use them throughout the paper.

2U_{s+t} = U_{s}V_{t} + U_{t}V_{s},  (13)
2V_{s+t} = V_{s}V_{t} + DU_{s}U_{t},  (14)
V_{t}^{2} − DU_{t}^{2} = 4Q^{t},  (15)
U_{2t} = U_{t}V_{t},  (16)
V_{2t} = V_{t}^{2} − 2Q^{t},  (17)
2Q^{t}U_{s−t} = U_{s}V_{t} − U_{t}V_{s}.  (18)

1See our short Appendix.

We referred to Euler’s criterion for Lucas sequences in our introduction. The criterion states that

p | U_{(p−ϵ_{p})/2} iff Q is a square modulo p,  (19)

where U(P, Q) is a fundamental Lucas sequence and p is a prime that does not divide 2DQ [36, pp. 84–85].

Note that our theorems and the lemmas of Section 4 all deal with primes p ≥ 5 of maximal rank. In their statements, we sometimes omit to mention the condition p ∤ Q, because that condition is necessary. Indeed, if p | Q, then, by (5), U_{t} ≡ P^{t−1} (mod p). Thus, p has no rank, because if p divided P, then ρ(p) would be equal to 2, as U_{2} = P, a contradiction.

Given a prime p of rank ρ and a nonnegative integer ν, we write

Σ_{ν} := ∑_{0<t<ρ} \frac{V_{t}^{ν}}{U_{t}^{ν}} and Σ_{1,1} := ∑_{0<s<t<ρ} \frac{V_{s}V_{t}}{U_{s}U_{t}} .  (20)

The proof of Theorem 3 we are about to write uses a few lemmas which we state first.

Lemma 10. Let (U, V) be a pair of Lucas sequences with parameters P and Q. Let ν be a nonnegative integer. If p ∤ Q is a prime at least ν + 3 of maximal rank ρ, i.e., of rank p − ϵ_{p}, where ϵ_{p} = 0 or ±1, then ^{2}

Σ_{ν} ≡ \begin{cases}0 (mod p^{2}), & if ν is odd; \\ 0 (mod p), & if ϵ_{p} = −1 or 0; \\ −2D^{ν/2} (mod p), & if ν is even and ϵ_{p} = 1. \end{cases}  (21)

Moreover, if p is an odd prime not dividing Q of any rank ρ, then

Σ_{ν} ≡ 0 (mod p), for all odd ν.  (22)

Proof. The case ν odd of (21) is Theorem 3 of [5]. (The case ν = 1 first appeared, nearly complete, as the main theorem of the paper [20], but also, nearly, as a corollary of the main theorem of [27], and as a particular case of [6, Thm. 4.1], or of [7, Thms. 3 and 12].)

The case ν even can be treated with the very same arguments used in the last part of the proof of Theorem 4 of [5, p. 5]. (The basic facts, noted first in [20], are that, by (18), all V_{t}/U_{t} are distinct (mod p) for t ∈ (0, ρ) and no V_{t}/U_{t} is ±\sqrt{D} (mod p) by (15); also p | ∑_{t=1}^{p} t^{e} if p − 1 ∤ e). The condition p ≥ ν + 3 is a sufficient condition which guarantees that p − 1 ∤ ν for ν ≥ 2 even.

The additional congruence (22) for ν odd, but without the restrictions that ρ be maximal and p ≥ ν + 3, is a consequence of the congruence (mod p^{2}) on the sixth line of the proof of Theorem 4 of [5, p. 4].

2unless ν = 0 and ϵ_{p} = 0, when Σ_{0} ≡ −1 (mod p).

Lemma 11. Let (U, V) be a pair of Lucas sequences with parameters P and Q. If p ∤ 6Q is a prime of maximal rank ρ in U, then

Σ_{1,1} ≡ \begin{cases}0 (mod p), & if ϵ_{p} = 0 or − 1; \\ D (mod p), & if ϵ_{p} = 1. \end{cases}

Proof. We have Σ_{1}^{2} = Σ_{2} + 2Σ_{1,1} so that Σ_{1,1} ≡ −\frac{1}{2}Σ_{2} (mod p), since, by Lemma 10, p^{4} divides Σ_{1}^{2} and Σ_{2} is either 0 or −2D (mod p).

Lemma 12. Let V = V (P, Q) be a companion Lucas sequence. Let p ∤ Q be an odd prime of rank ρ and t ≥ 0 an integer. Then modulo p^{2} we have

V_{tρ} ≡ \begin{cases}2Q^{tρ/2}, & if t is even; \\ −2Q^{tρ/2}, & if t is odd and ρ is even. \end{cases}

Proof. Assume t is even. By (15), V_{tρ/2}^{2} ≡ 4Q^{tρ/2} (mod p^{2}) since p divides U_{tρ/2}. However, by (17), V_{tρ} = V_{tρ/2}^{2} − 2Q^{tρ/2} ≡ 2Q^{tρ/2} (mod p^{2}).

Suppose t odd and ρ even. Since p divides U_{tρ}, but not U_{tρ/2}, we see by (16) that p divides V_{tρ/2}. So by (17) we find that V_{tρ} ≡ −2Q^{tρ/2} (mod p^{2}).

We are now ready for a proof of Theorem 3.

Proof. We have

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} = \frac{∏_{t=1}^{ρ−1} U_{kρ+t}}{∏_{t=1}^{ρ−1} U_{t}} .

By the addition formula (13), we find that

2^{ρ−1} ∏_{t=1}^{ρ−1} U_{kρ+t} = ∏_{t=1}^{ρ−1}(V_{kρ}U_{t} + U_{kρ}V_{t})

≡ (V_{kρ}^{ρ−1} + V_{kρ}^{ρ−2}U_{kρ}Σ_{1} + V_{kρ}^{ρ−3}U_{kρ}^{2}Σ_{1,1}) × ∏_{t=1}^{ρ−1} U_{t}  (23)

≡ (V_{kρ}^{ρ−1} + V_{kρ}^{ρ−3}U_{kρ}^{2}Σ_{1,1}) × ∏_{t=1}^{ρ−1} U_{t} (mod p^{3}),

since p divides U_{kρ} and, by Lemma 11, Σ_{1} is 0 (mod p^{2}).

We first examine the cases ρ is p + 1 and ρ is p. In those cases U_{kρ}^{2}Σ_{1,1} is 0 (mod p^{3}) by Lemma 11. Hence,

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ (\frac{V_{kρ}}{2} )^{ρ−1} (mod p^{3}).

If ρ is p, then, by (15) and the fact that p^{3} | DU_{kρ}^{2}, we see that V_{kρ}^{2} ≡ 4Q^{kρ} (mod p^{3}). Therefore,

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ (Q^{kρ})^{(ρ−1)/2} (mod p^{3}),

yielding the result in that case. Suppose ρ is p+1. By Lemma 12 there is an integer, or a halfinteger, λ such that \frac{V_{kρ}}{2} = (−1)^{k}Q^{kρ/2} +λp^{2}. Raising both members of the previous equation to the pth power gives (V_{kρ}/2)^{p} ≡ (−1)^{k}Q^{kρp/2} (mod p^{3}). But (−1)^{k} = (−1)^{−k} = (−1)^{kϵ_{p}} so the theorem follows.

Suppose now ϵ_{p} is 1, that is, ρ is p − 1. By Lemma 11, Σ_{1,1} ≡ D (mod p) so that U_{kρ}^{2}Σ_{1,1} ≡ DU_{kρ}^{2} (mod p^{3}). But, by (15), DU_{kρ}^{2} = V_{kρ}^{2} − 4Q^{kρ}. Therefore, we have

2^{ρ−1}\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ 2V_{kρ}^{ρ−1} − 4Q^{kρ}V_{kρ}^{ρ−3} (mod p^{3}).

This gives

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ (\frac{V_{kρ}}{2} )^{p} · α_{p,k} (mod p^{3}),
with  α_{p,k} := 2(\frac{2}{V_{kρ}} )^{2} − Q^{kρ}(\frac{2}{V_{kρ}} )^{4}.

By Lemma 12, V_{kρ}/2 ≡ (−1)^{k}Q^{kρ/2} (mod p^{2}). Raising the previous congruence to the pth power yields (V_{kρ}/2)^{p} ≡ (−1)^{k}Q^{kpρ/2} (mod p^{3}), while inverting it yields the existence of an integer μ such that 2/V_{kρ} ≡ (−1)^{k}Q^{−kρ/2} + μp^{2} (mod p^{3}). Thus, we find that, modulo p^{3},

α_{p,k} ≡ 2((−1)^{k}Q^{−kρ/2} + μp^{2})^{2} − Q^{kρ}((−1)^{k}Q^{−kρ/2} + μp^{2})^{4}
≡ (2Q^{−kρ} + (−1)^{k}4Q^{−kρ/2}μp^{2}) − Q^{kρ}(Q^{−2kρ} + (−1)^{k}4Q^{−3kρ/2}μp^{2})
= Q^{−kρ}.

Thus, we end up with

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ (−1)^{k}Q^{kpρ/2}Q^{−kρ} = (−1)^{kϵ_{p}}Q^{kρ(p−2)/2} (mod p^{3}),

which yields the theorem.

The above proof is the first that came to us. It proceeds case by case according to whether the value of the rank of p is p+1, p or p−1 and, thus, appears somewhat miraculous. Although we initially wrote case by case proofs for the higher congruences of Section 4, we ended up presenting a global and thus less seemingly miraculous approach at least for Theorems 21 and 24.

We now prove Theorem 7 using the elements of the proof of Theorem 3.

Proof of Theorem 7. Since, in (23), U_{kρ} is 0 (mod p) and, by (22), Σ_{1} is also 0 (mod p), we find that for all primes p ≥ 3

\binom{(k + 1)ρ − 1}{ρ − 1}_{U} ≡ (\frac{V_{kρ}}{2} )^{ρ−1} (mod p^{2}).

By (15), (V_{kρ}/2)^{2} ≡ 4Q^{kρ}/4 = Q^{kρ} (mod p^{2}). Thus, if ρ is odd, then (V_{kρ}/2)^{ρ−1} ≡ (Q^{kρ})^{(ρ−1)/2} = (−1)^{k(ρ−1)}Q^{kρ(ρ−1)/2} (mod p^{2}). If k is even, then, by Lemma 12, V_{kρ}/2 ≡ Q^{kρ/2} (mod p^{2}) and the result holds by raising the congruence to the power ρ − 1. If k is odd and ρ even, then, again by Lemma 12, V_{kρ}/2 ≡ −Q^{kρ/2} = (−1)^{k}Q^{kρ/2} (mod p^{2}), which raised to the power ρ − 1 yields the theorem.

3 Lucasnomials \binom{kρ}{ℓρ}_{U} (mod p^{3})

Here is our common generalization of the Ljunggren et al. congruence (9) and Kimball and Webb’s theorem (10).

Theorem 13. Let U, V be a pair of Lucas sequences with parameters P and Q. Let p ≥ 5, p ∤ Q, be a prime whose rank of appearance ρ is p±1 or p. Then, for all nonnegative integers k and ℓ, we have

\binom{kρ}{ℓρ}_{U} ≡ ((−1)^{ρ−1}Q^{ρ(ρ−1)/2})^{ℓ(k−ℓ)}\binom{k}{ℓ}_{U′} (mod p^{3}),  (24)

where U′ is the sequence U_{ρ} × U(V_{ρ}, Q^{ρ}).

Proof. Note that if ρ is maximal, then the factor (−1)^{ϵ_{p}} of Theorem 3 may be replaced by (−1)^{ρ−1}. We only need a proof in case k > ℓ ≥ 1. With convention (12) we may write

\binom{kρ}{ℓρ}_{U} = \frac{U_{kρ}U_{kρ−1} ⋯ U_{(k−ℓ)ρ+1}}{U_{ℓρ}U_{ℓρ−1} ⋯ U_{1}}

= \frac{U_{kρ}U_{(k−1)ρ} ⋯ U_{(k−ℓ+1)ρ}}{U_{ℓρ}U_{(ℓ−1)ρ} ⋯ U_{ρ}} · \frac{∏_{i=k−ℓ}^{k−1} ∏_{t=1}^{ρ−1} U_{iρ+t}}{∏_{i=0}^{ℓ−1} ∏_{t=1}^{ρ−1} U_{iρ+t}}

= \binom{k}{ℓ}_{U′} · \frac{∏_{i=k−ℓ}^{k−1} ∏_{t=1}^{ρ−1} U_{iρ+t}}{( ∏_{t=1}^{ρ−1} U_{t})^{ℓ}} · \frac{( ∏_{t=1}^{ρ−1} U_{t})^{ℓ}}{∏_{i=0}^{ℓ−1} ∏_{t=1}^{ρ−1} U_{iρ+t}}

= \binom{k}{ℓ}_{U′} · ∏_{i=k−ℓ}^{k−1} \binom{(i + 1)ρ − 1}{ρ − 1}_{U} · ( ∏_{i=0}^{ℓ−1} \binom{(i + 1)ρ − 1}{ρ − 1}_{U})^{−1}

≡ \binom{k}{ℓ}_{U′} · \binom{2ρ − 1}{ρ − 1}_{U}^{∑_{i=k−ℓ}^{k−1} i−∑_{i=0}^{ℓ−1} i} ( by Remark 4 )
= \binom{k}{ℓ}_{U′} · \binom{2ρ − 1}{ρ − 1}_{U}^{ℓ(k−ℓ)} (mod p^{3}),

yielding, by Theorem 3, the theorem.

Remark 14. If p ≥ 3, p ∤ Q, is a prime and no assumption is made about its rank, then congruence (24) holds modulo p^{2}. This is established by following the proof of Theorem 13 and using Theorem 7. Remark 15. If, in Theorem 13, U_{ρ} ≠ 0 then we might as well set U′ equal to U(V_{ρ}, Q^{ρ}). Remark 16. If U = U(2, 1), then U_{t} = t and U′_{t} = pt, or U′_{t} = t by the above remark. Thus the theorem implies that

\binom{kp}{ℓp} ≡ \binom{k}{ℓ}_{U′} = \binom{k}{ℓ} (mod p^{3}),

which is the classical congruence (9) of Ljunggren et alii. For U = U(1, −1) and ϵ_{p} = ±1 we saw in Remark 5 that ϵ_{p} = −(−1)^{ρ(ρ−1)/2} = −Q^{ρ(ρ−1)/2} so that Theorem 13 implies (10).

Since we took care of including all cases of Lucas sequences in our theorems, we provide an example of an application of Theorem 13 to a degenerate Lucas sequence.

Example 17. Consider U(2, 2). Its first terms are

0, 1, 2, 2, 0, −4, −8, −8, 0, 16, 32, 32, 0, …

So Theorem 13 applies to p = 5 since its rank is maximal and equal to 4. Choose, say k = 3 and ℓ = 2. By our extended definition of (3), we have \binom{3}{2}_{U′} = 1 and (−1)^{ℓ(k−ℓ)ϵ_{p}}Q^{ℓ(k−ℓ)ρ(ρ−1)/2} = 2^{12}. Computing \binom{12}{8}_{U} we may verify the congruence modulo 125, which in that case is an equality, since

\binom{12}{8}_{U} = \frac{U_{11} · U_{10} · U_{9}}{U_{3} · U_{2} · U_{1}} = \frac{16 · 32 · 32}{2 · 2 · 1} = 2^{12}.

4 Lucasnomials \binom{2ρ−1}{ρ−1}_{U} (mod p^{5})

The congruence of Wolstenholme has been studied to prime powers higher than the third. In particular, we have, for all primes p ≥ 7,

\binom{2p − 1}{p − 1} ≡ 1 + p ∑_{0<t<p} \frac{1}{t} + p^{2} ∑_{0<s<t<p} \frac{1}{st} (mod p^{5})  (25)

≡ 1 + 2p ∑_{0<t<p} \frac{1}{t} (mod p^{5})  (26)

≡ 1 − p^{2} ∑_{0<t<p} \frac{1}{t^{2}} (mod p^{5}).  (27)

We will find congruences for the Lucasnomial coefficients \binom{2ρ−1}{ρ−1}_{U}, valid for a general fundamental Lucas sequence U, modulo the fifth power of a prime of maximal rank ρ, which generalize the three congruences above. Expanding the binomial \binom{2p−1}{p−1}, as was done more generally for Lucasnomials in the proof of Theorem 3, one falls naturally on the congruence (25). This expansion appears, for instance, in the proof of Proposition 1 in [25]. Congruence (26) is a special case of Theorem 3 of the paper [38] and was known to hold for primes p ≥ 5 modulo p^{4} much earlier, while congruence (27) appears in [23, p. 385].

Given a prime p of rank ρ we make a formal definition to complete the notation introduced in (20).

Definition 18. If ν ≥ 1 is an integer, then

Σ_{ν, ··· ,ν (k times)} := ∑ (\frac{V_{t_{1}}}{U_{t_{1}}} )^{ν} ⋯ (\frac{V_{t_{k}}}{U_{t_{k}}} )^{ν},

the sum being over all (t_{1}, …, t_{k}) in (0, ρ)^{k}, t_{1} < t_{2} < ⋯ < t_{k}.

If 1 ≤ ν_{1} < ν_{2} are two integers, then Σ_{ν_{1},··· ,ν_{1}, ν_{2},··· ,ν_{2}} , where ν_{u}, u = 1 or 2, is respectively repeated k_{u} times, is defined as

∑ (\frac{V_{t_{1}}}{U_{t_{1}}} )^{ν_{1}} ⋯ (\frac{V_{t_{k_{1}}}}{U_{t_{k_{1}}}} )^{ν_{1}}(\frac{V_{s_{1}}}{U_{s_{1}}} )^{ν_{2}} ⋯ (\frac{V_{s_{k_{2}}}}{U_{s_{k_{2}}}} )^{ν_{2}},

the sum being over all (t_{1}, t_{2}, …, t_{k_{1}}) and (s_{1}, s_{2}, …, s_{k_{2}}) such that t_{i} ≠ s_{j}, for all i and j, and 0 < t_{1} < t_{2} < ⋯ < t_{k_{1}} < ρ, 0 < s_{1} < s_{2} < ⋯ < s_{k_{2}} < ρ. The notation can be extended to more than two distinct ν exponents, but we won’t need such sums in this paper.

Thus, for instance, the sums Σ_{1,3}, Σ_{2,2}, Σ_{1,1,2} and Σ_{1,1,1,1} are respectively

∑_{s, t} \frac{V_{s}V_{t}^{3}}{U_{s}U_{t}^{3}} , ∑_{s<t} \frac{V_{s}^{2}V_{t}^{2}}{U_{s}^{2}U_{t}^{2}} , ∑_{\begin{matrix}r<s, \\ t∈(0,ρ) \end{matrix}} \frac{V_{r}V_{s}V_{t}^{2}}{U_{r}U_{s}U_{t}^{2}} , ∑_{q<r<s<t} \frac{V_{q}V_{r}V_{s}V_{t}}{U_{q}U_{r}U_{s}U_{t}} ,

where in each sum q, r, s and t are distinct integers in the interval (0, ρ).

Lemma 19. We have for all primes p ≥ 7 of maximal ranks

Σ_{1,1,1} ≡ 0 (mod p^{2}) and Σ_{1,1,1,1} ≡ \begin{cases}0 (mod p), if ϵ_{p} = 0 or − 1; \\ D^{2} (mod p), if ϵ_{p} = 1. \end{cases}

Proof. We have the linear system

Σ_{1}^{3} − Σ_{3} = 3Σ_{1,2} + 6Σ_{1,1,1},
Σ_{1} · Σ_{1,1} = Σ_{1,2} + 3Σ_{1,1,1}.

Because p^{2} divides both Σ_{1} and Σ_{3}, Σ_{1}^{3} − Σ_{3} and Σ_{1} · Σ_{1,1} are each 0 (mod p^{2}). Since the determinant of the system is prime to p, Σ_{1,2} and Σ_{1,1,1} are both 0 (mod p^{2}).

From Lemma 10 with p > 5, which yields the values of Σ_{2} and Σ_{4} (mod p), we deduce that

Σ_{2,2} = \frac{1}{2}(Σ_{2}^{2} − Σ_{4}) ≡ \begin{cases}0 (mod p), if ϵ_{p} = 0 or − 1; \\ 3D^{2} (mod p), if ϵ_{p} = 1. \end{cases}

Now Σ_{1,3} = Σ_{1} · Σ_{3} − Σ_{4} ⟹ Σ_{1,3} ≡ −Σ_{4} (mod p). Moreover, 2Σ_{1,1,2} + 2Σ_{2,2} + Σ_{1,3} = Σ_{1,2} · Σ_{1} ≡ 0 (mod p).

Thus, Σ_{1,1,2} is 0 (mod p), if ϵ_{p} is 0 or −1, and Σ_{1,1,2} is −4D^{2} (mod p), if ϵ_{p} is 1.

Therefore, as 6Σ_{1,1,1,1} = Σ_{1,1}^{2} − Σ_{2,2} − 2Σ_{1,1,2}, we obtain, using Lemma 11, the desired congruences for Σ_{1,1,1,1}.

Our first theorem is a generalization of congruence (25).

Theorem 20. Let (U, V) be a pair of Lucas sequence with parameters P and Q. Let p be a prime at least 7 of maximal rank ρ equal to p − ϵ_{p}. Then

\binom{2ρ − 1}{ρ − 1}_{U} ≡ (\frac{V_{ρ}}{2} )^{ρ−1}(1 + \frac{U_{ρ}}{V_{ρ}} ∑_{0<t<ρ} \frac{V_{t}}{U_{t}} + \frac{U_{ρ}^{2}}{V_{ρ}^{2}} ∑_{0<s<t<ρ} \frac{V_{s}V_{t}}{U_{s}U_{t}} + R) (mod p^{5}),

where R = \frac{ϵ_{p}(1 + ϵ_{p})}{2} \frac{D^{2}U_{ρ}^{4}}{V_{ρ}^{4}} = \begin{cases}0, if ϵ_{p} = 0 or − 1; \\ D^{2}U_{ρ}^{4}/V_{ρ}^{4}, if ϵ_{p} = 1. \end{cases}

Proof. Expanding the product 2^{ρ−1} ∏_{t=1}^{ρ−1} U_{ρ+t} = ∏_{t=1}^{ρ−1}(V_{ρ}U_{t} + U_{ρ}V_{t}) as we did early in the proof of Theorem 3, but up to the fourth power of U_{ρ}, yields that 2^{ρ−1}\binom{2ρ−1}{ρ−1}_{U} is congruent to

V_{ρ}^{ρ−1} + V_{ρ}^{ρ−2}U_{ρ}Σ_{1} + V_{ρ}^{ρ−3}U_{ρ}^{2}Σ_{1,1} + V_{ρ}^{ρ−4}U_{ρ}^{3}Σ_{1,1,1} + V_{ρ}^{ρ−5}U_{ρ}^{4}Σ_{1,1,1,1} (mod p^{5}).

Applying the congruences obtained in Lemma 19 to the last two terms of the above sum yields the theorem.

We now prove a congruence formula that generalizes (26), but also generalizes Theorem 3 when k = 1. The method of proof brings out the factor (−1)^{ϵ_{p}}Q^{ρ(ρ−1)/2} naturally, albeit in the equivalent form (−1)^{ρ−1}Q^{ρ(ρ−1)/2}. It is particularly appealing because it only contains two terms, no more than (26), and is valid regardless of the value of the maximal rank ρ.

Theorem 21. Let (U, V) be a pair of Lucas sequence with parameters P and Q. Let p be a prime at least 7 of maximal rank ρ equal to p − ϵ_{p}. Then

\binom{2ρ − 1}{ρ − 1}_{U} ≡ (−1)^{ρ−1}Q^{\frac{ρ(ρ−1)}{2}} (1 + 2\frac{U_{ρ}}{V_{ρ}} ∑_{0<t<ρ} \frac{V_{t}}{U_{t}} ) (mod p^{5}).

Proof. All unmarked sums and products are for t running from 1 to ρ − 1. Note that ∏ U_{t} = ∏ U_{ρ−t}. Thus by (18) we may write

2^{ρ−1}Q^{∑ t} ∏ U_{t} = ∏ 2Q^{t}U_{ρ−t} = ∏(U_{ρ}V_{t} − V_{ρ}U_{t})
= (−V_{ρ})^{ρ−1} ∏ (1 − \frac{U_{ρ}}{V_{ρ}} \frac{V_{t}}{U_{t}} ) ∏ U_{t}.

Therefore

(−1)^{ρ−1}Q^{ρ(ρ−1)/2} = (\frac{V_{ρ}}{2} )^{ρ−1} ∏ (1 − \frac{U_{ρ}}{V_{ρ}} \frac{V_{t}}{U_{t}} ),

so that (−1)^{ρ−1}Q^{ρ(ρ−1)/2} is congruent to

(\frac{V_{ρ}}{2} )^{ρ−1}(1 − \frac{U_{ρ}}{V_{ρ}} Σ_{1} + \frac{U_{ρ}^{2}}{V_{ρ}^{2}} Σ_{1,1} − \frac{U_{ρ}^{3}}{V_{ρ}^{3}} Σ_{1,1,1} + \frac{U_{ρ}^{4}}{V_{ρ}^{4}} Σ_{1,1,1,1}) (mod p^{5}).  (28)

Note that from (28) we recover the congruence

(−1)^{ρ−1}Q^{ρ(ρ−1)/2} ≡ (\frac{V_{ρ}}{2} )^{ρ−1} (mod p^{2}).  (29)

Subtracting the expansion in (28) from that of \binom{2ρ−1}{ρ−1}_{U} obtained in the proof of Theorem 20, we find that

\binom{2ρ − 1}{ρ − 1}_{U} − (−1)^{ρ−1}Q^{ρ(ρ−1)/2} ≡ (\frac{V_{ρ}}{2} )^{ρ−1}(2\frac{U_{ρ}}{V_{ρ}} Σ_{1} + 2\frac{U_{ρ}^{3}}{V_{ρ}^{3}} Σ_{1,1,1})
≡ 2(\frac{V_{ρ}}{2} )^{ρ−1} \frac{U_{ρ}}{V_{ρ}} Σ_{1} (mod p^{5}),

since Σ_{1,1,1} is 0 (mod p^{2}) by Lemma 19. In the above congruence as \frac{U_{ρ}}{V_{ρ}} Σ_{1} is 0 (mod p^{3}) we

may, by (29), replace (\frac{V_{ρ}}{2} )^{ρ−1} by (−1)^{ρ−1}Q^{ρ(ρ−1)/2} and deduce our theorem.

Lemma 22. Suppose ν is a nonnegative integer. Let p ≥ ν + 5 be a prime of maximal rank, say ρ. Then

∑_{0<t<ρ} \frac{4Q^{t}}{U_{t}^{2}} \frac{V_{t}^{ν}}{U_{t}^{ν}} = Σ_{ν+2} − DΣ_{ν} ≡ \begin{cases}0 (mod p^{2}), if ν is odd; \\ 0 (mod p), if ν is even. \end{cases}

Proof. We have

∑_{0<t<ρ} \frac{4Q^{t}}{U_{t}^{2}} \frac{V_{t}^{ν}}{U_{t}^{ν}} = ∑_{0<t<ρ} \frac{(V_{t}^{2} − DU_{t}^{2})}{U_{t}^{2}} \frac{V_{t}^{ν}}{U_{t}^{ν}} = Σ_{ν+2} − DΣ_{ν}.

If ν is odd, then, p ≥ ν + 5 implies, by Lemma 10, that both Σ_{ν} and Σ_{ν+2} are 0 (mod p^{2}). If ν is even, then both Σ_{ν+2} and DΣ_{ν} are 0 (mod p), when ρ is p or p + 1, by Lemma 10. If ρ is p − 1, then by the same lemma Σ_{ν+2} − DΣ_{ν} ≡ −2D^{\frac{ν+2}{2}} − D(−2D^{ν/2}) ≡ 0 (mod p).

Lemma 23. We have for all primes p ≥ 7 of maximal rank ρ

−2Σ_{1} ≡ \frac{U_{ρ}}{V_{ρ}} ∑_{0<t<ρ} \frac{4Q^{t}}{U_{t}^{2}} (mod p^{4}).

Proof. All sums are over an index t running from 1 to ρ − 1.

−2Σ_{1} = − ∑ (\frac{V_{t}}{U_{t}} + \frac{V_{ρ−t}}{U_{ρ−t}} ) = −2U_{ρ} ∑ \frac{1}{U_{t}U_{ρ−t}} , by (13),
= −2U_{ρ} ∑ \frac{2Q^{t}}{U_{t}(U_{ρ}V_{t} − U_{t}V_{ρ})}, using (18),
= 2\frac{U_{ρ}}{V_{ρ}} ∑ \frac{2Q^{t}}{U_{t}^{2}(1 − \frac{V_{t}}{U_{t}} \frac{U_{ρ}}{V_{ρ}} )}
≡ \frac{U_{ρ}}{V_{ρ}} ∑ \frac{4Q^{t}}{U_{t}^{2}} (1 + \frac{V_{t}}{U_{t}} \frac{U_{ρ}}{V_{ρ}} + \frac{V_{t}^{2}}{U_{t}^{2}} \frac{U_{ρ}^{2}}{V_{ρ}^{2}} ) (mod p^{4}),

yielding the lemma because, by Lemma 22, U_{ρ}^{ν+1} ∑ \frac{4Q^{t}}{U_{t}^{2}} \frac{V_{t}^{ν}}{U_{t}^{ν}} is 0 (mod p^{4}), for ν = 1 and ν = 2, if p ≥ 7.

From Theorem 21, it is not difficult to reach a third theorem that generalizes (27). Theorem 24. Let (U, V) be a pair of Lucas sequence with parameters P and Q. Let p be a prime at least 7 of maximal rank ρ equal to p − ϵ_{p}. Then

\binom{2ρ − 1}{ρ − 1}_{U} ≡ (−1)^{ϵ_{p}}Q^{\frac{ρ(ρ−1)}{2}} (1 − 4\frac{U_{ρ}^{2}}{V_{ρ}^{2}} ∑_{0<t<ρ} \frac{Q^{t}}{U_{t}^{2}} ) (mod p^{5}).

Proof. In the congruence for the Lucasnomial \binom{2ρ−1}{ρ−1}_{U} of Theorem 21 we may replace 2\frac{U_{ρ}}{V_{ρ}} Σ_{1} by −\frac{U_{ρ}^{2}}{V_{ρ}^{2}} ∑ \frac{4Q^{t}}{U_{t}^{2}} since by Lemma 23 the two expressions are congruent modulo p^{5}. Remark 25. In stating Theorem 24 we chose the expression −4\frac{U_{ρ}^{2}}{V_{ρ}^{2}} ∑ \frac{Q^{t}}{U_{t}^{2}} rather than −\frac{U_{ρ}^{2}}{V_{ρ}^{2}} Σ_{2}+ \frac{U_{ρ}^{2}}{V_{ρ}^{2}} (ρ − 1)D because it contains only one term; that term is 0 (mod p^{3}) and it reduces to −p^{2} ∑ \frac{1}{t^{2}} for U = U(2, 1). Lemma 26. We have for all primes p ≥ 7 of maximal rank ρ

\frac{U_{ρ}}{V_{ρ}} Σ_{1} ≡ \frac{U_{ρ}^{2}}{V_{ρ}^{2}} Σ_{1,1} − \frac{1}{2} \frac{U_{ρ}^{2}}{V_{ρ}^{2}} (ρ − 1)D (mod p^{5}).

Proof. By Lemma 23, we see that

\frac{U_{ρ}}{V_{ρ}} Σ_{1} ≡ −\frac{1}{2} \frac{U_{ρ}^{2}}{V_{ρ}^{2}} ∑_{0<t<ρ} \frac{4Q^{t}}{U_{t}^{2}} (mod p^{5}).

By Lemma 22,

∑_{0<t<ρ} \frac{4Q^{t}}{U_{t}^{2}} = Σ_{2} − D(ρ − 1).

Thus, as Σ_{2} = Σ_{1}^{2} − 2Σ_{1,1} ≡ −2Σ_{1,1} (mod p^{4}), the lemma follows.

By using Lemma 26 and Theorem 21 we obtain another generalization of (25) slightly different from that given in Theorem 20, which we now state.

Theorem 27. Let (U, V) be a pair of Lucas sequences with parameters P and Q. Let p be a prime at least 7 of maximal rank ρ equal to p − ϵ_{p}. Then \binom{2ρ−1}{ρ−1}_{U} is congruent to

(−1)^{ϵ_{p}}Q^{\frac{ρ(ρ−1)}{2}} (1 + \frac{U_{ρ}}{V_{ρ}} ∑_{0<t<ρ} \frac{V_{t}}{U_{t}} + \frac{U_{ρ}^{2}}{V_{ρ}^{2}} ∑_{0<s<t<ρ} \frac{V_{s}V_{t}}{U_{s}U_{t}} − \frac{1}{2}D\frac{U_{ρ}^{2}}{V_{ρ}^{2}} (ρ − 1)) (mod p^{5}).

We end the paper with a congruence for \binom{2ρ−1}{ρ−1}_{U} modulo p^{6}. It generalizes Theorem 2.4 of [33] which says that

\binom{2p − 1}{p − 1} ≡ 1 + 2p ∑_{0<t<p} \frac{1}{t} + \frac{2p^{3}}{3} ∑_{0<t<p} \frac{1}{t^{3}} (mod p^{6}),

for all primes p ≥ 7, and also generalizes our Theorem 21.

Theorem 28. Let (U, V) be a pair of Lucas sequences with parameters P and Q. Let p be a prime at least 7 of maximal rank ρ. Then

\binom{2ρ − 1}{ρ − 1}_{U} ≡ (−1)^{ρ−1}Q^{\frac{ρ(ρ−1)}{2}} (1 + 2\frac{U_{ρ}}{V_{ρ}} ∑_{0<t<p} \frac{V_{t}}{U_{t}} + \frac{2}{3} \frac{U_{ρ}^{3}}{V_{ρ}^{3}} ∑_{0<t<p} \frac{V_{t}^{3}}{U_{t}^{3}} ) (mod p^{6}).

Proof. We proceed as in Lemma 19 to show that Σ_{1,1,1,1,1} ≡ 0 (mod p) (in fact 0 modulo p^{2}). By Lemma 10, the expressions Σ_{1} · Σ_{4} − Σ_{5}, Σ_{1,1} · Σ_{3}, Σ_{1} · Σ_{1,3} and Σ_{1} · Σ_{2,2} are all 0 (mod p^{2}), so we deduce, successively, that the sums Σ_{1,4}, Σ_{1,1,3}, Σ_{2,3} and Σ_{1,2,2} are each 0 (mod p^{2}). Therefore, modulo p^{2}, we obtain the linear system

Σ_{1} · Σ_{1,1,1,1} ≡ 5 Σ_{1,1,1,1,1} + Σ_{1,1,1,2},
Σ_{1}^{5} − Σ_{5} ≡ 120 Σ_{1,1,1,1,1} + 60 Σ_{1,1,1,2}.

As its determinant, 2^{2} · 3^{2} · 5, is prime to p, and its left members are each 0 (mod p^{2}), we find that Σ_{1,1,1,1,1} ≡ 0 (mod p^{2}).

Since Σ_{1,1,1,1,1} is 0 (mod p), both the congruence for \binom{2ρ−1}{ρ−1}_{U}, derived from the proof of Theorem 20, and congruence (28) remain valid when we raise the modulus from p^{5} to p^{6}. Hence,

\binom{2ρ − 1}{ρ − 1}_{U} − (−1)^{ρ−1}Q^{ρ(ρ−1)/2} ≡ (\frac{V_{ρ}}{2} )^{ρ−1}(2\frac{U_{ρ}}{V_{ρ}} Σ_{1} + 2\frac{U_{ρ}^{3}}{V_{ρ}^{3}} Σ_{1,1,1}) (mod p^{6}).  (30)

Suppose first that ϵ_{p} = −1 or ϵ_{p} = 0. Then, as Σ_{1,1} ≡ 0 (mod p), we find that (29) is valid modulo p^{3}. Thus, we may replace (V_{ρ}/2)^{ρ−1} in (30) by (−1)^{ρ−1}Q^{ρ(ρ−1)/2} and obtain that

\binom{2ρ − 1}{ρ − 1}_{U} ≡ (−1)^{ρ−1}Q^{ρ(ρ−1)/2}(1 + 2\frac{U_{ρ}}{V_{ρ}} Σ_{1} + 2\frac{U_{ρ}^{3}}{V_{ρ}^{3}} Σ_{1,1,1}) (mod p^{6}).  (31)

Looking at the linear system at the start of the proof of Lemma 19 modulo p^{3} we find the system of congruences

3Σ_{1,2} + 6Σ_{1,1,1} ≡ −Σ_{3},
Σ_{1,2} + 3Σ_{1,1,1} ≡ 0.

Solving for Σ_{1,1,1}, we see that Σ_{1,1,1} ≡ \frac{Σ_{3}}{3} (mod p^{3}), which inserted in congruence (31) yields the theorem.

Suppose now ϵ_{p} = 1. By (28) and Lemma 11, congruence (29), when the modulus is increased to p^{3}, becomes

(−1)^{ρ−1}Q^{ρ(ρ−1)/2} ≡ (V_{ρ}/2)^{ρ−1}(1 + DU_{ρ}^{2}/V_{ρ}^{2}) (mod p^{3}).

Thus we may replace (V_{ρ}/2)^{ρ−1} in (30) by (−1)^{ρ−1}Q^{ρ(ρ−1)/2}(1 − DU_{ρ}^{2}/V_{ρ}^{2}), multiply out the resulting expression and remove the term in U_{ρ}^{5}Σ_{1,1,1} which is 0 (mod p^{7}) to find that

\binom{2ρ − 1}{ρ − 1}_{U} ≡ (−1)^{ρ−1}Q^{ρ(ρ−1)/2}(1 + 2\frac{U_{ρ}}{V_{ρ}} Σ_{1} + 2\frac{U_{ρ}^{3}}{V_{ρ}^{3}} (Σ_{1,1,1} − DΣ_{1})) (mod p^{6}).

Because Σ_{1} is 0 (mod p^{2}) and Σ_{1,1} ≡ D (mod p), the linear system of Lemma 19 taken modulo p^{3} is

3Σ_{1,2} + 6Σ_{1,1,1} ≡ −Σ_{3},
Σ_{1,2} + 3Σ_{1,1,1} ≡ DΣ_{1}.

Solving for Σ_{1,1,1} yields Σ_{1,1,1} ≡ DΣ_{1} + Σ_{3}/3 and the theorem holds.

5 Appendix on the integrality of Lucasnomials

Lucas, with a nearly complete justification, indirectly asserted the integrality of Lucasnomials in his memoir [22, p. 203] by stating that the product of n consecutive terms of a (nondegenerate) U sequence is divisible by the product U_{1} … U_{n}. Various proofs have appeared, often with restrictions on the sequence U. In fact, they have been shown to be integral via a combinatorial argument [9]. But with convention (12) we want to prove their integrality in full generality.

Proposition 29. Let U = (U_{n}) be a Lucas sequence with parameters P and Q. With the adoption of convention (12) the Lucasnomial coefficients \binom{m}{n}_{U} are rational integers for all nonnegative integers m and n.

Proof. If all U_{n}, n > 0, are nonzero then the frequently used induction argument [15, 16, 18] based on the general Lucas identity U_{n+1}U_{m−n} − QU_{n}U_{m−n−1} = U_{m} works fine. We repeat the argument here. The induction is on m. So one proves the integrality of the Lucasnomial \binom{m}{n}_{U} for m > n ≥ 1 by observing that

U_{n+1}\binom{m − 1}{n}_{U} − QU_{m−n−1}\binom{m − 1}{n − 1}_{U} =
(U_{n+1} \frac{U_{m−n}}{U_{n}} − QU_{m−n−1}) · \binom{m − 1}{n − 1}_{U} =
\frac{U_{m}}{U_{n}} · \binom{m − 1}{n − 1}_{U} = \binom{m}{n}_{U} ,

completing the induction. If some term U_{n}, n ≥ 1, is 0 then U is degenerate and, as we saw early in Section 2, ρ(∞) ∈ {2, 3, 4, 6}, where ρ(∞) is the least positive integer t such that U_{t} = 0. Note that we may always assume m ≥ 2n. Thus the Lucasnomial \binom{m}{n}_{U} is the quotient of a product of n consecutive U terms of indices all larger than n divided by U_{n}U_{n−1} ⋯ U_{1}. If ρ(∞) = 2, i.e., U_{2} = P = 0, then U_{2k+1} = (−1)^{k}Q^{k} and U_{2k} = 0, (k ≥ 0). Then \binom{m}{n}_{U} is up to sign a positive power of Q. If ρ(∞) = 3, then, as U_{3} = P^{2} − Q, the first few terms of U are 0, 1, P, 0, −P^{3}, −P^{4}, 0, P^{6}, P^{7}, 0, · · ·. So |U_{t}| = P^{t−1} if 3 ∤ t. If ρ(∞) = 4, then, as U_{4} = P^{3} − 2P Q and P ≠ 0, P^{2} = 2Q and we see that |U_{t}| = 2^{⌊t/2⌋}(P′)^{t−1} if 4 ∤ t, where P = 2P′. Omitting the 0 terms when 4 | t, powers of 2 and P′ in U_{t} are nondecreasing functions of t. A similar result holds for ρ(∞) equal to 6 when P^{2} = 3Q and, omitting terms divisible by 6, powers of 3 and of P′ in U_{t} are nondecreasing functions of t, where in this case P = 3P′. The integrality of the Lucasnomials follows readily.

6 Acknowledgments

We thank an anonymous referee for his clear report and few formal suggestions.

References

[1] C. Babbage, Demonstration of a theorem relating to prime numbers, Edinburgh Philosophical J., 1 (1819), 46–49.

[2] D. F. Bailey, Two p^{3} variations of Lucas’ theorem, J. Number Theory, 35 (1990), 208– 215.

[3] C. Ballot, Divisibility of Fibonomials and Lucasnomials via a general Kummer rule, Fibonacci Quarterly, to appear.

[4] C. Ballot, A Lucas type congruence with Fibonomials (solution to advanced problem H-737), Fibonacci Quart., 53 (2015) 94–95, 191.

[5] C. Ballot, On a congruence of Kimball and Webb involving Lucas sequences, J. Integer Seq., 17 (2014), Article 14.1.3.

[6] C. Ballot, Lucas sequences with cyclotomic root field, Dissertationes Math., 490 (2013), 92 pp.

[7] C. Ballot, A further generalization of a congruence of Wolstenholme, J. Integer Seq., 15 (2012), Article 12.8.6.

[8] A. Benjamin and E. Reiland, Combinatorial proofs of Fibonomial identities, to appear in the Proceedings of the 16th International Conf. on Fibonacci Numbers and their Applic., July 2014, Rochester, NY, 7 pp.

[9] A. Benjamin and S. Plott, A combinatorial approach to Fibonomial coefficients, Fibonacci Quart., 46/47 (2008/09), 7–9.

[10] V. Brun, J. O. Stubban, J. E. Fjeldstad, R. Tambs Lyche, K. E. Aubert, W. Ljunggren, E. Jacobsthal. On the divisibility of the difference between two binomial coefficients. Den 11te Skandinaviske Matematikerkongress, Trondheim, 1949, pp. 42–54. Johan Grundt Tanums Forlag, Oslo, 1952.

[11] R. D. Fray, Congruence properties of ordinary and q-binomial coefficients. Duke Math. J., 34, (1967) 467–480.

[12] J. W. L. Glaisher, Congruences relating to the sums of products of the first n numbers and to other sums of products, Quart. J. Math. 31 (1900), 1–35.

[13] J. W. L. Glaisher, On the residues of the sums of products of the first p − 1 numbers, and their powers, to modulus p^{2} or p^{3}, Quart. J. Math. 31 (1900), 321–353.

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

[15] V. E. Hoggatt, Jr., Fibonacci numbers and generalized binomial coefficients, Fibonacci Quart., 5 (1967) 383–400.

[16] J. M. Holte, Residues of generalized binomial coefficients modulo a prime, Fibonacci Quart., 38 (2000) 227–238.

[17] C. Hooley, On Artin’s conjecture, J. Reine Angew. Math. 225 (1967), 209–220.

[18] H. Hu and Z.-W. Sun, An extension of Lucas’ theorem, Proc. Amer. Math. Soc. 129 (2001), 3471–3478.

[19] W. Kimball and W. Webb, A congruence for fibonomial coefficients modulo p^{3}, Fibonacci Quart., 33 (1995) 290–297.

[20] W. Kimball and W. Webb, Some generalizations of Wolstenholme’s theorem, Applications of Fibonacci Numbers 8 Kluwer Acad. Publ., 1999, pp. 213–218.

[21] D. Knuth and H. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math. 396 (1989), 212–219.

[22] É. Lucas, Théorie des fonctions simplement périodiques, Amer. J. Math., 1 (1878), 184–240, 289–321.

[23] R. J. McIntosh, On the converse of Wolstenholme’s theorem, Acta Arith., 71 (1995), 381–389.

[24] R. Meštrovic̀, Wolstenholme’s theorem: Its generalizations and extensions in the last hundred and fifty years (1862–2012), preprint available at

    http://arxiv.org/abs/1111.3057v2.

[25] R. Meštrovic̀, Congruences for Wolstenholme primes, preprint available at

    http://arxiv.org/abs/1108.4178.

[26] H. Ohtsuka, Problem H-737, Fibonacci Quart., 51 (2013), 186.

[27] H. Pan, A generalization of Wolstenholme’s harmonic series congruence, Rocky Mountain J. Math., 38 (2008), 1263–1269.

[28] H. Roskam, A quadratic analogue of Artin’s conjecture on primitive roots. J. Number Theory 81 (2000), 93–109.

[29] H. Roskam, Erratum: “A quadratic analogue of Artin’s conjecture on primitive roots” [J. Number Theory 81 (2000), 93–109], J. Number Theory 85 (2000), 108.

[30] B. Sagan and C. Savage, Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences, Integers 10 (2010) #A52.

[31] R. Stanley, Enumerative Combinatorics, Volume 1. Second edition. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, 2012.

[32] A. Straub, A q-analog of Ljunggren’s binomial congruence, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp. 897–902, Discrete Math. Theor. Comput. Sci. Proc., 2011.

[33] R. Tauraso, More congruences for central binomial coefficients. J. Number Theory, 130 (2010), 2639–2649.

[34] M. Ward, Note on divisibility sequences. Bull. Amer. Math. Soc. 42 (1936), 843–845.

[35] D. L. Wells, Lucas’ theorem for generalized binomial coefficients, Ph. D. thesis, Washington State University, 1992.

[36] H. C. Williams, Édouard Lucas and Primality Testing, Wiley, Canadian Math. Soc. Series of Monographs and Advanced Texts, 1998.

[37] J. Wolstenholme, On certain properties of prime numbers, Q. J. Pure Appl. Math., 5 (1862), 35–39.

[38] J. Zhao, Bernoulli numbers, Wolstenholme’s theorem, and p^{5} variations of Lucas’ theorem. J. Number Theory, 123 (2007), 18–26.

2010 Mathematics Subject Classification: Primary 11A07; Secondary 11B65, 11B39. Keywords: generalized binomial coefficient, Wolstenholme’s congruence, Lucas sequence, rank of appearance.

Received October 24 2014; revised versions received December 18 2014; February 25 2015; March 21 2015; March 26 2015. Published in Journal of Integer Sequences, May 19 2015.

Return to Journal of Integer Sequences home page.