On a Congruence of Kimball and Webb Involving Lucas Sequences

Christian Ballot Département de Mathématiques et Mécanique Université de Caen F-14032 Caen Cedex France

                  christian.ballot@unicaen.fr

Abstract Given a pair (U_{t}) and (V_{t}) of Lucas sequences, an odd integer ν ≥ 1, and a prime p ≥ ν + 4 of maximal rank ρ_{U}, i.e., such that ρ_{U} is p or p ± 1, we show that ∑_{0<t<ρ_{U}} (V_{t}/U_{t})^{ν} ≡ 0 (mod p^{2}). This extends a result of Kimball and Webb, who proved the case ν = 1. Some further generalizations are also established.

1 Introduction

The main purpose of this note is to provide a common generalization to Theorems 1 and 2 below. Theorem 1. Let ν ≥ 1 be an odd integer. Suppose p ≥ ν + 4 is a prime number. Then

H_{p−1}^{ν} := ∑_{t=1}^{p−1} \frac{1}{t^{ν}} ≡ 0 (mod p^{2}).

Theorem 2. Let U(P, Q), V (P, Q) be a pair of Lucas sequences, p ≥ 5, p ∤ Q, a prime of rank ρ equal to p − ϵ_{p}, where ϵ_{p} = 0 or ±1. Then

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

Theorem 1 appears in the book of Hardy and Wright [3] as Theorem 131 and is one of many generalizations of the 1862 congruence of Wolstenholme [10] which states that

H_{p−1} := 1 + \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{p − 1} ≡ 0 (mod p^{2}),  (1)

i.e., that the numerator of the rational number H_{p−1} is a multiple of p^{2}, whenever p is a prime number at least 5. Sums of the type ∑_{t=1}^{m} 1/t^{ν}, where ν is odd and t is prime to m, were first studied by Leudesdorf [6]. Their values modulo m^{2} have been the subject of many papers and these results were revisited in the paper [9]. Historically, Wolstenholme used the congruence (1) to prove that for all primes p ≥ 5 we have

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

a fact known as Wolstenholme’s congruence. The survey paper [7] mentions many generalizations of the congruence (2), but also contains generalizations of the related congruence (1), particularly in Sections 4 and 8.

Theorem 2, as may not readily appear, is yet another (surprising!) generalization of the congruence (1) of Wolstenholme. Contrary to other known generalizations, its discovery by Kimball and Webb [5], who initially proved it for the special pair of Lucas sequences U(1, −1), V (1, −1) in the paper [4], came much later, and more than 130 years after (1) had appeared. For (P, Q) = (2, 1), we have x^{2} − P x + Q = (x − 1)^{2}, U_{t} = t and V_{t} = 2 for all integers t ≥ 0 so that every prime p has rank p, and we see that the result of Kimball and Webb is indeed a generalization of the congruence of Wolstenholme.

Putting Theorems 1 and 2 next to each other and computing a few sums such as ∑_{t=1}^{7} L_{t}^{3}/F_{t}^{3} (mod 49) or ∑_{t=1}^{9} L_{t}^{5}/F_{t}^{5} (mod 121), where L_{t} and F_{t} are the t-th Lucas and the t-th Fibonacci numbers, and finding in both cases 0 (mod p^{2}) for p = 7 and p = 11, respectively, led to conjecturing (ô res mirabile!) that Theorem 3 holds.

Theorem 3. Let ν ≥ 1 be an odd integer and U(P, Q), V (P, Q) be a pair of Lucas sequences. If p ≥ ν + 4, p ∤ Q, is a prime of maximal rank ρ, i.e., of rank p − ϵ_{p}, where ϵ_{p} = 0 or ±1, then

∑_{t=1}^{ρ−1} \frac{V_{t}^{ν}}{U_{t}^{ν}} ≡ 0 (mod p^{2}).

We briefly remark that Theorem 2 of Kimball and Webb has recently been generalized in several directions. One generalization is found in [8], another in Chapter 4 of [1], and again another in [2], where congruences involving sums of ratios V_{t}/U_{t} of Lucas sequences taken modulo m^{2}, where m may be composite, not necessarily prime, were considered.

Theorem 2 was stated in a mildly generalized form in both papers [1] and [2], in part because it led to the further generalizations found in these papers. In anticipation of yet further tentative generalizations we wish to prove a more general version of Theorem 3, namely Theorem 4. Let ν ≥ 1 be an odd integer. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences and p ∤ Q be a prime number of maximal rank ρ with respect to U(P, Q). Assume further that p − 1 ∤ ν ± 1 if ν ≥ 3 and p − 1 ∤ ν + 1 if ν = 1. Then, for all integers k, we have that

S := ∑_{t=kρ+1}^{(k+1)ρ−1} \frac{V_{t}^{ν}}{U_{t}^{ν}} ≡ 0 (mod p^{2}).

Note that if p ≥ ν + 4 then p − 1 ∤ ν ± 1 when ν ≥ 3 and p − 1 ∤ ν + 1 when ν = 1 so that Theorem 4 implies Theorem 3 by setting k = 0.

A secondary purpose of our note is to indicate how one can obtain further results that combine the approach taken in [2], i.e., congruences with composite moduli m of maximal ranks, with the general odd exponents ν ≥ 1 of the present paper. This is done in the third and final section.

Throughout this note we assume familiarity with Lucas sequences. The introduction of the paper [2] contains references to Lucas theory and useful remarks and definitions concerning ranks of primes and integers, and congruences of rational numbers modulo an integer m.

2 Proof of Theorem 4

We begin by a few lemmas and remarks.

Lemma 5. Let ν ≥ 1 be an odd integer, p be a prime number and x and y be two rational integers whose sum is divisible by p. Then there is a rational integer c, which may depend on ν, such that

x^{ν} + y^{ν} ≡ c(xy)^{(ν−1)/2}(x + y) (mod p^{2}).  (3)

Proof. Choosing c = 1 we see that (3) holds for ν = 1. We proceed by strong induction on ν. So given ν ≥ 3 we assume that for each i = 1, …, (ν − 1)/2, we have

x^{ν−2i} + y^{ν−2i} ≡ c_{i}(xy)^{(ν−2i−1)/2}(x + y) (mod p^{2}),

for some c_{i} ∈ ℤ.

Expanding (x + y)^{ν} by Newton’s formula and pairing terms in x^{k}y^{ν−k} with terms in x^{ν−k}y^{k}, we find that

x^{ν} + y^{ν} = (x + y)^{ν} − \binom{ν}{1}xy(x^{ν−2} + y^{ν−2}) − \binom{ν}{2}x^{2}y^{2}(x^{ν−4} + y^{ν−4})

− ⋯ − \binom{ν}{(ν − 1)/2}(xy)^{(ν−1)/2}(x + y).

The term (x+y)^{ν} is divisible by p^{2} and, by the inductive hypothesis, each term (xy)^{i}(x^{ν−2i} + y^{ν−2i}) is congruent to c_{i}(xy)^{(ν−1)/2}(x + y) modulo p^{2} for some integer c_{i}. Hence, putting c = − ∑ c_{i}\binom{ν}{i}, i = 1, …, (ν − 1)/2, the lemma follows.

Lemma 6. Let p be an odd prime and e ≥ 0 be an integer such that p − 1 ∤ e if e ≥ 1. Then the sum ∑_{t=1}^{p} t^{e} is divisible by p.

Proof. If e is 0, then the result is trivial. Assume e ≥ 1. If g is a primitive root modulo p, then g^{e} ≢ 1 (mod p). But ∑_{t=1}^{p} t^{e} ≡ ∑_{t=1}^{p}(gt)^{e} (mod p). Hence, p divides (g^{e} − 1) ∑_{t=1}^{p} t^{e}.

Given a pair U, V of Lucas sequences with parameters (P, Q) we denote the discriminant P^{2} − 4Q by D and recall a few relevant identities. For all integers s and t, we have

2U_{s+t} = U_{s}V_{t} + U_{t}V_{s},  (4)
4Q^{t} = V_{t}^{2} − DU_{t}^{2},  (5)
2Q^{t}U_{s−t} = U_{s}V_{t} − U_{t}V_{s},  (6)
2Q^{t}V_{s−t} = V_{s}V_{t} − DU_{s}U_{t}.  (7)

We are ready for a proof of Theorem 4.

Proof. All unmarked sums are taken with indices running from kρ + 1 to (k + 1)ρ − 1. Also we put r := (2k + 1)ρ. Then we see that

S = \frac{1}{2} ∑ (\frac{V_{t}^{ν}}{U_{t}^{ν}} + \frac{V_{r−t}^{ν}}{U_{r−t}^{ν}} ) = \frac{1}{2} ∑ \frac{V_{t}^{ν}U_{r−t}^{ν} + U_{t}^{ν}V_{r−t}^{ν}}{U_{t}^{ν}U_{r−t}^{ν}} .

Put x = V_{t}U_{r−t} and y = U_{t}V_{r−t}. Then, by equation (4), x + y = 2U_{r}, which is divisible by p. Thus, by Lemma 5, we have for some integer c

V_{t}^{ν}U_{r−t}^{ν} + U_{t}^{ν}V_{r−t}^{ν} ≡ 2cU_{r}(V_{t}U_{r−t}U_{t}V_{r−t})^{(ν−1)/2} (mod p^{2}).

Therefore, if p^{2} | cU_{r}, then S ≡ 0 (mod p^{2}). So we assume p^{2} ∤ cU_{r}. Then S ≡ 0 (mod p^{2}) if and only if p divides

∑ \frac{(V_{t}U_{r−t}U_{t}V_{r−t})^{(ν−1)/2}}{U_{t}^{ν}U_{r−t}^{ν}} .  (8)

By the subtraction formulas (6) and (7), we find that

(2U_{r−t})^{(ν−1)/2} ≡ (−1)^{(ν−1)/2}Q^{−(ν−1)t/2}U_{t}^{(ν−1)/2}V_{r}^{(ν−1)/2} (mod p), and
(2V_{r−t})^{(ν−1)/2} ≡ Q^{−(ν−1)t/2}V_{t}^{(ν−1)/2}V_{r}^{(ν−1)/2} (mod p).

Thus, there exist integers λ_{1} and λ_{2}, prime to p and not dependent on t, such that modulo p the numerator of the t-th term in (8) is equal to λ_{1}Q^{−(ν−1)t}U_{t}^{ν−1}V_{t}^{ν−1}, while its denominator is equal to λ_{2}Q^{−νt}U_{t}^{2ν} since (2U_{r−t})^{ν} ≡ −Q^{−νt}U_{t}^{ν}V_{r}^{ν} (mod p). Indeed, by (5), p ∤ V_{r}. Thus, p^{2} divides S iff

p divides ∑ \frac{Q^{t}V_{t}^{ν−1}}{U_{t}^{ν+1}} .

By (5) we see that 4Q^{t}V_{t}^{ν−1} = V_{t}^{ν+1} − DU_{t}^{2}V_{t}^{ν−1}. Hence, S is zero modulo p^{2} iff p divides

∑ \frac{V_{t}^{ν+1}}{U_{t}^{ν+1}} − D ∑ \frac{V_{t}^{ν−1}}{U_{t}^{ν−1}} .  (9)

Note that since p is an odd prime and p ∤ Q, if s and t are distinct integers that belong to the interval (kρ, (k + 1)ρ), then V_{s}/U_{s} and V_{t}/U_{t} are distinct modulo p by (6). Also, if D is a quadratic residue modulo p, then V_{t}/U_{t} and ±\sqrt{D} are not congruent modulo p by (5).

If ρ is p+1, then, as t varies from k(p+1)+1 to k(p+1)+p, V_{t}/U_{t} (mod p) runs through all of ℤ/pℤ. Thus, by Lemma 6, as ν ≢ ±1 (mod p − 1), we find that both sums appearing in (9) are divisible by p. The same divisibilities hold if ρ is p, since, then, only the residue 0 (mod p) is absent from each of the two sums. If ρ is p − 1, then, as t varies from kρ + 1 to kρ + p − 2, V_{t}/U_{t} (mod p) runs through all of ℤ/pℤ but ±\sqrt{D} (mod p). Hence we deduce respectively that

∑ (\frac{V_{t}}{U_{t}} )^{ν±1} + (\sqrt{D})^{ν±1} + (−\sqrt{D})^{ν±1} ≡ 0 (mod p).

So we find that

∑ \frac{V_{t}^{ν+1}}{U_{t}^{ν+1}} − D ∑ \frac{V_{t}^{ν−1}}{U_{t}^{ν−1}} ≡ (0 − 2D^{(ν+1)/2}) − D(0 − 2D^{(ν−1)/2}) ≡ 0 (mod p).

Remark 7. If D = 0, then the hypothesis p − 1 ∤ ν + 1 suffices.

3 Two more theorems

Given a Lucas sequence U(P, Q) and an integer m prime to Q we denote the rank of m in U by ρ(m).

By the definition which was introduced and motivated in [2], we say that a composite integer m ≥ 1 has maximal rank with respect to a Lucas sequence U(P, Q) if every prime power dividing m has maximal rank and the ranks of any two such prime powers are relatively prime. A power p^{a} has maximal rank in U(P, Q) iff p has maximal rank and the rank ρ(p^{a}) is equal to p^{a−1}ρ(p).

Here, unlike in the paper [2], we will not look for an exhaustive theorem dealing with sums of terms V_{t}^{ν}/U_{t}^{ν} modulo squares of integers of maximal rank, but the partial results we will state and sketch will be enough to see how one could obtain such congruences.

We start by an extension of Theorem 4 to prime powers. The case ν = 1 is in fact a corollary of Theorem 12 of [2].

Theorem 8. Let ν ≥ 1 be an odd integer and U, V be a pair of Lucas sequences with parameters P and Q. Suppose p ∤ Q is a prime satisfying p > (ν +3)/2, p ≠ ν and p ≠ ν +2. Assume p^{a} has maximal rank for some integer a ≥ 1. Then for all integers k we have

S := ∑_{t∈I} \frac{V_{t}^{ν}}{U_{t}^{ν}} ≡ 0 (mod p^{2a}),

where I is the set of integers in (kρ(p^{a}), (k + 1)ρ(p^{a})) \ ρ(p)ℤ.

Proof. The proof is actually an extension of that of Theorem 4. It is easy to upgrade Lemma 5. Suppose p^{a} | x + y. Then for each odd integer ν ≥ 1 there is a rational integer c such that

x^{ν} + y^{ν} ≡ c(xy)^{(ν−1)/2}(x + y) (mod p^{2a}).  (10)

Note that the sum S contains p^{a−1}(ρ(p)−1) terms. We now have r = (2k +1)ρ(p^{a}). So 2cU_{r} is at least divisible by p^{a}. So we will be through if we can show that the sum corresponding to the sum in (8) is 0 (mod p^{a}). But that will be true if the expression in (9) is also 0 (mod p^{a}), where now both sums are taken over all integers t in I. At this point note that Lemma 6 can also be upgraded so that ∑_{t=1}^{p^{a}} t^{e} ≡ 0 (mod p^{a}) provided, again, p − 1 ∤ e. Indeed, if g is a primitive root modulo p^{a}, then it reduces to a primitive root modulo p, so p ∤ g^{e} − 1 if p − 1 ∤ e and this gives the lemma. Note that as t varies through I all V_{t}/U_{t} are distinct modulo p^{a}. If ρ(p) is p + 1, then since the cardinality of I is p^{a} we deduce that

∑_{t∈I} (\frac{V_{t}}{U_{t}} )^{ν±1} ≡ ∑_{t∈ℤ/p^{a}} t^{ν±1} ≡ 0 (mod p^{a}).

If ρ(p) is p then V_{t} is never 0 (mod p) and the terms V_{t}/U_{t} (mod p^{a}) run through all invertible elements of ℤ/p^{a}ℤ as t runs through I. Thus g being a primitive root modulo p^{a} and φ being Euler’s totient function, we find that

∑_{t∈I} (\frac{V_{t}}{U_{t}} )^{ν±1} ≡ ∑_{t=0}^{φ(p^{a})−1} g^{(ν±1)t} = \frac{g^{(ν±1)φ(p^{a})} − 1}{g^{ν±1} − 1} ≡ 0 (mod p^{a}),

since g^{(ν±1)} − 1 is not divisible by p. This argument is not valid if ν = 1 and the exponent of g is ν − 1. But in that case the result nevertheless holds because

D ∑_{t∈I} (\frac{U_{t}}{V_{t}} )^{ν−1} = D · |I| ≡ 0 (mod p^{a}),

so the expression in (9) is 0 (mod p^{a}).

If ρ(p) is p − 1, then I contains p^{a} − 2p^{a−1} elements. So V_{t}/U_{t} (mod p^{a}) runs through all ℤ/p^{a} except ±\sqrt{D} + ip (mod p^{a}) for i = 1, 2, …, p^{a−1}. Hence, (V_{t}/U_{t})^{2} (mod p^{a}) hits each nonzero quadratic residue in ℤ/p^{a} twice except all D + ip, for i = 1, …, p^{a−1}, as t runs through I. Therefore,

∑_{t∈I} (\frac{V_{t}}{U_{t}} )^{ν+1} ≡ ∑_{i=1}^{p^{a}}(i^{2})^{(ν+1)/2} − 2 ∑_{j=1}^{p^{a−1}}(D + jp)^{(ν+1)/2} (mod p^{a}).

Now

∑_{j=1}^{p^{a−1}}(D + jp)^{(ν+1)/2} = ∑_{u=0}^{(ν+1)/2} \binom{(ν + 1)/2}{u}D^{(ν+1)/2−u}p^{u} ∑_{j=1}^{p^{a−1}} j^{u}.

As p−1 > (ν +1)/2, p^{a−1} | ∑_{j=1}^{p^{a−1}} j^{u} and, unless u = 0, p^{a} | p^{u} ∑_{j=1}^{p^{a−1}} j^{u}. Hence, as p ≠ ν +2, we have

∑_{t∈I} (\frac{V_{t}}{U_{t}} )^{ν+1} ≡ 0 − 2D^{(ν+1)/2}p^{a−1} (mod p^{a}).

Since a similar argument is valid for ν−1 instead of ν+1 we see that ∑_{t∈I} \frac{V_{t}^{ν+1}}{U_{t}^{ν+1}} −D ∑_{t∈I} \frac{V_{t}^{ν−1}}{U_{t}^{ν−1}} is congruent to

(0 − 2p^{a−1}D^{(ν+1)/2}) − D(0 − 2p^{a−1}D^{(ν−1)/2}) = 0 (mod p^{a}).

Theorem 9. Let ν ≥ 1 be an odd integer and U, V be a pair of Lucas sequences with parameters P and Q. Suppose m is a positive integer prime to Q of maximal rank. Assume further that each prime factor p of m satisfies p > (ν + 3)/2, p ≠ ν and p ≠ ν + 2. Then for all integers k we have

S := ∑_{t∈I} \frac{V_{t}^{ν}}{U_{t}^{ν}} ≡ 0 (mod m^{2}),

where I is the set of integers in (kρ(m), (k + 1)ρ(m)) \ ⋃_{p|m} ρ(p)ℤ.

The proof we sketch is similar to, but simpler than that of Theorem 14 of the paper [2].

Proof. Assume for simplicity that k = 0. We proceed by induction on the number of distinct prime factors of m. If m is a prime power, then this is Theorem 8. Say m = p^{a}n, where p ∤ n is prime and n > 1. It suffices to show that S ≡ 0 (mod n^{2}). Note that since n has maximal rank the theorem will hold for n by the inductive hypothesis. Write S as S^{∗} − S^{∗∗}, where

S^{∗} := ∑_{i=0}^{ρ(p^{a})−1} ∑_{\begin{matrix}t=iρ(n)+1 \\ ρ(q) ∤ t, if q|n \end{matrix}}^{(i+1)ρ(n)−1} (\frac{V_{t}}{U_{t}} )^{ν},

and

S^{∗∗} := ∑_{\begin{matrix}t=1 \\ ρ(q) ∤ t, if q|n \end{matrix}}^{p^{a−1}ρ(n)} (\frac{V_{ρ(p)t}}{U_{ρ(p)t}} )^{ν} = ∑_{i=0}^{p^{a−1}−1} U_{ρ(p)}^{−ν} ∑_{\begin{matrix}t=iρ(n)+1 \\ ρ(q) ∤ t, if q|n \end{matrix}}^{(i+1)ρ(n)−1} (\frac{V′_{t}}{U′_{t}} )^{ν},

where the sequences U′_{t} = U_{ρ(p)t} · U_{ρ(p)}^{−1} and V′_{t} = V_{ρ(p)t} are the Lucas sequences associated with (P′, Q′) = (V_{ρ(p)}, Q^{ρ(p)}) and the letter q stands for a prime. Note that all inner sums in S^{∗} are 0 (mod n^{2}) and that, as n has maximal rank with respect to U′, the same is true, by our inductive hypothesis again, of the inner sums of S^{∗∗}.

Example 10. Consider the Lucas sequences U and V with parameters P = 1 and Q = −9. Then D = 37, ρ(7) = 6 and ρ(37) = 37. Thus, m = 259 = 7 · 37 has maximal rank. Hence, by Theorem 9, we have for ν = 1, 3 or 9

∑_{t} (\frac{V_{t}}{U_{t}} )^{ν} ≡ 0 (mod 7^{2} · 37^{2}),

where t runs over all integers between 1 and 222 = 6 · 37 except for multiples of 6 or 37.

4 Acknowledgments

We thank a nearly anonymous referee for writing typed and handwritten suggestions meant to improve the clarity of some points in the paper.

References

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

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

[3] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford at the Clarendon Press, London, 1960.

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

[5] W. Kimball and W. Webb, Some generalizations of Wolstenholme’s theorem, in Applications of Fibonacci Numbers 8 (Rochester, NY, 1998), Kluwer Acad. Publ., 1999, 213–218.

[6] C. Leudesdorf, Some results in the elementary theory of numbers, Proc. Lond. Math. Soc., 20 (1889), 199–212.

[7] R. Meštrović, 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.

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

[9] I. Sh. Slavutskii, Leudesdorf’s theorem and Bernoulli numbers, Arch. Math.(Brno), 35 (1999) 299–303.

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

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11A07. Keywords: Lucas sequence, rank of appearance, congruence, Wolstenholme, Leudesdorf.

Received July 22 2013; revised versions received November 9 2013; November 28 2013. Published in Journal of Integer Sequences, December 15 2013.

Return to Journal of Integer Sequences home page.