A Further Generalization of a Congruence of Wolstenholme

Christian Ballot L.M.N.O., CNRS UMR 6139 Université de Caen F-14032 Caen Cedex France

                  christian.ballot@unicaen.fr

Abstract

Given a pair (U_{t}) and (V_{t}) of Lucas sequences, Kimball and Webb showed that ∑_{0<t<ρ_{U}} \frac{V_{t}}{U_{t}} ≡ 0 (mod p^{2}), if p is a prime ≥ 5 whose rank ρ_{U} is maximal, that is to say, ρ_{U} is p or p±1. We extend their result replacing p by a composite integer m of maximal rank, thereby providing a generalization of a classical congruence of Leudesdorf.

1 Introduction

In an 1862 paper of Wolstenholme [16], we find the congruence

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

i.e., the numerator of the rational number H_{p−1} is a multiple of p^{2}, whenever p is a prime number at least 5. Many elementary generalizations of this congruence were subsequently discovered, some before, some after 1900. Chapter VIII of the book [4] provides an attractive selection of some of the results that extend the congruence of Wolstenholme. Leudesdorf [9], in 1889, studied the sums ∑_{t=1}^{m} 1/t^{ν}, where m is a positive integer, ν is an odd positive integer, and t runs over all integers from 1 to m that are prime to m. The simplest and most striking case, as Chowla refers to it, of the results of Leudesdorf is that of ν = 1 and m prime to 6, for which we have that the sum ∑_{t=1}^{m} 1/t, t prime to m, is congruent to 0 (mod m^{2}), a clear generalization of the Wolstenholme congruence. Chowla [3] actually gave a concise half-page natural proof of this case. The theorem of Leudesdorf we will refer to in this paper is Theorem 128 of [4]. It corresponds to the case ν = 1 without the restriction that m be prime to 6. Hardy and Wright refer to it as a comprehensive generalization of Wolstenholme’s congruence. Thus, it predicts Wolstenholme’s congruences for H_{p−1} not just for primes prime to 6, i.e., primes ≥ 5, but also for p equal to 2 and 3. We state this Leudesdorf theorem below.

Theorem 1. Let m be an integer ≥ 1. Then

∑_{\begin{matrix}t=1 \\ gcd(t,m)=1 \end{matrix}}^{m} \frac{1}{t} is congruent to 0 (mod m^{2}/e_{m}),

where

e_{m} = \begin{cases}4, & if m = 2^{a}, a ≥ 1; \\ gcd(m, 6), & otherwise. \end{cases}

Interestingly, a new elementary generalization of the congruence (1) of Wolstenholme was only discovered relatively recently by Kimball and Webb [8]. It involves Lucas sequences! If U and V are a pair of Lucas sequences, then the sums ∑ V_{t}/U_{t} are also 0 (mod p^{2}), where t runs over all integers from 1 to ρ(p) − 1, where p is a prime at least 5, and ρ(p) denotes the rank of appearance of p in the U sequence, provided, this rank is either p − 1, p, or p + 1, that is, p has maximal rank.^{1}

This result was shown to hold for the special pair of Lucas sequences consisting of the Fibonacci and of the Lucas numbers in a slightly earlier paper by the same authors [7].

It should briefly be mentioned that this result of Kimball and Webb was further generalized by Pan [13] who showed that, for w_{m} > 1, we have

∑_{t=1}^{m−1} \frac{V_{t}}{U_{t}} ≡ \frac{(m^{2} − 1)D}{6} · \frac{U_{m}}{V_{m}} (mod w_{m}^{2}),  (2)

where m is an integer ≥ 5, D is the discriminant of the characteristic polynomial associated with the pair of Lucas sequences U and V, and w_{m} is the largest factor of U_{m} which is prime to the product U_{2}U_{3} ⋯ U_{m−1}. ^{2}

We recall that given a pair of integers P and Q, Q nonzero, the two Lucas sequences U = (U_{t})_{t≥0} and V = (V_{t})_{t≥0} are second order integral linear recurrences (X_{t}) that both satisfy the recursion

X_{t+2} = P X_{t+1} − QX_{t}, for all t.  (3)

Their two initial terms then fully defines them. We have U_{0} = 0 and U_{1} = 1, whereas V_{0} = 2 and V_{1} = P. We write U(P, Q) and V (P, Q) when the dependence on P and Q needs to be reminded. If the zeros of their characteristic polynomial x^{2} − P x + Q are distinct, say α and β, then the t-th terms of the U and V sequences are given by the so-called Binet formulas, i.e.,

1The case ρ(p) = p was only considered in the paper [8] when D, the discriminant of the characteristic polynomial of the Lucas sequences, is 0. But the general case can easily be handled as was done in the preprint [1, Thm. 40].

2The only case of the Kimball and Webb congruence not implied by (2) is when p is 5 of rank 4. However, defining w_{4} as the largest factor of U_{4} prime to 3U_{2}U_{3} would have been sufficient to cover this missing case.

U_{t} = \frac{α^{t} − β^{t}}{α − β} and V_{t} = α^{t} + β^{t}.  (4)

In case x^{2} − P x + Q has a double zero α, then the Binet formulas become

U_{t} = tα^{t−1} and V_{t} = 2α^{t}.  (5)

The rank of appearance ρ(m), or ρ_{U}(m), of an integer m is the least positive index t such that m divides U_{t}. It is known to exist for all m prime to Q. The rank of a prime p not dividing Q is either equal to p, or is a divisor of p ± 1. For (P, Q) = (2, 1), 1 is a double zero of x^{2} − P x + Q. Thus, U_{t} = t and V_{t} = 2. Applying the theorem of Kimball and Webb to this particular pair of Lucas sequences yields congruence (1).

We restate the main theorem of Kimball and Webb [8], but in a slightly generalized form, as it appeared in Chapter 3 of the paper [1].

Theorem 2. Let p be a prime at least 5 which is not a factor of Q. Assume the rank ρ of p is maximal. Let k be an integer. Then the sum

∑_{t∈I_{p,k}} \frac{V_{t}}{U_{t}} is congruent to 0 (mod p^{2}),

where I_{p,k} is the set of integers in the interval (kρ, (k + 1)ρ).

The purpose of the present paper is to prove a common generalization, Theorem 3 stated hereunder, to both the Leudesdorf and the Kimball-Webb congruences, i.e., a common generalization to Theorems 1 and 2.

Theorem 3. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences. Let m be an integer of maximal rank with respect to U(P, Q). Then, for all integers k, we have that

S_{m,k}(P, Q) = ∑_{t∈I_{m,k}} \frac{V_{t}}{U_{t}} is congruent to 0 (mod h_{m} · m^{2}/ gcd(m, 3)),

where I_{m,k} is the set of integers in the interval (kρ(m), (k + 1)ρ(m)) that are not multiples of any rank ρ(p) for all primes p dividing m, and where

h_{m} = \begin{cases}1/2, & if m = 2^{a}, a ≥ 1, and ν_{2}(P) = 1; \\ 2^{σ}, & if 2||m and 4 | P; \\ 2^{τ}, & if 2||m, P is odd and Q ≡ 1 (mod 4); \\ 8, & if 4||m, P is odd and Q ≡ 3 (mod 4); \\ 1, & otherwise, \end{cases}

with σ = ν_{2}(P) − 2 ≥ 0 and τ = ν_{2}(P^{2} − Q) − 1 ≥ 1, ν_{2}(P) and ν_{2}(P^{2} − Q) being respectively the 2-adic valuations of P and P^{2} − Q.

In particular, S_{m,k} ≡ 0 (mod m^{2}/ gcd(m, 3)) if m is not a power of 2 or if ν_{2}(P) ≠ 1.

Example 4. Say (P, Q) = (1, −1), i.e., U = F and V = L are the sequences of Fibonacci and Lucas numbers. We will see that 35 and 500 are two integers of maximal rank with respect to F. Thus, putting k = 0 in Theorem 3, we find that

• If m = 35, then ρ(35) = 40. Hence,

∑_{\begin{matrix}t=1 \\ 5 ∤ t, 8 ∤ t \end{matrix}}^{40} \frac{L_{t}}{F_{t}} ≡ 0 (mod 35^{2}),

where the above sum, S_{m,0}(1, −1), contains 40 − (8 + 5) + 1 = 28 terms.

• If m = 500 = 4 · 5^{3}, then

∑ \frac{L_{t}}{F_{t}} ≡ 0 (mod 8m^{2} = 2, 000, 000),

where the sum is over all t’s between 1 and ρ(m) = 6 · 5^{3} = 750 that are prime to 15, and, thus, contains 750 − (250 + 150) + 50 = 400 terms.

Section 2 of this paper is a short preliminary section where the relevant definitions, and in particular that of a general integer having maximal rank with respect to a Lucas sequence U(P, Q), followed by a few remarks and comments, are given. Section 3 contains the main theorems and their proofs. Theorem 12, generalizes the theorem of Kimball and Webb to prime powers. Theorem 14, which may be viewed as our chief result, is proved via induction on the number of distinct prime factors of an integer m of maximal rank and so Theorem 12 serves as a basis for that proof by induction. Theorem 14 is already a generalization of both Theorems 1 and 2. So we could have ended the paper there. However, it would not have been complete. We wanted a theorem that fully respected the definition we took of an integer of maximal rank. The remaining cases are thus treated in Section 4, but their proofs hinge heavily on the proof of Theorem 14 and are established through a series of lemmas, which, combined with Theorem 14, yield Theorem 3.

The proofs of the paper are all elementary, but assume familiarity with classical properties of Lucas sequences. We refer to Lucas’ original work [10] and Chapters 17 and 18 of [11], to [2], [14], to Chapter 4 of [15], and to Chapter 2 of [1], for properties of Lucas sequences used herein.

The letter p invariably denotes a prime number. If m is an integer, then ρ(m), or ρ_{U}(m), denotes its rank in U. The letter D stands for the discriminant P^{2} − 4Q of x^{2} − P x + Q. If t is a rational number, then ν_{p}(t) denotes its p-adic valuation. Alternately, as we did in Theorem 3, we write p^{a}||t to mean that p^{a} divides t, but p^{a+1} does not divide t. These divisions take place in the ring A_{p}. More generally, the congruences in Theorems 1, 2 and 3 and congruences that appear in this paper take place in the ring A_{m}, where A_{m} is the subring of the rationals which, when expressed in lowest terms, have a denominator prime to m. That is, s ≡ t (mod m) means that s and t are in A_{m} and that s − t ∈ mA_{m}. Note that A_{m} = A_{m^{2}} = A_{p_{1}···p_{r}}, if p_{1}, …, p_{r} are the prime factors of m. We will use the well-known fact [6] that ℤ/p^{a} is isomorphic to A_{p}/p^{a}, a ≥ 1, where the isomorphism is derived from the identity embedding of ℤ into A_{p}.

2 Preliminaries

Throughout the paper, we assume that U = U(P, Q) and V = V (P, Q) denote an arbitrary pair of Lucas sequences.

Recall that if m is an integer prime to Q, then m | U_{t} iff ρ(m) | t. Also, if p is a prime that does not divide Q, then ρ(p) | p − (D|p), where (D|p) is 0, if p | D; 1, if D is a nonzero square (mod p) and −1, otherwise.

We recall a few classical Lucas identities valid for all integers s and t.

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

It is easy to deduce from (6) and the relations Q^{t}V_{−t} = V_{t}, Q^{t}U_{−t} = −U_{t} that

2Q^{t}U_{s−t} = U_{s}V_{t} − U_{t}V_{s}.  (9)

Remark 5. Suppose p is an odd prime not dividing Q. If t is not a multiple of ρ(p), then from (8) we have that the square of the ratio V_{t}/U_{t} is well-defined and not congruent to D (mod p).

Our intention is to first generalize Theorem 2 to prime powers, possibly including the primes 2 and 3. Recall that the rank of a prime p is said to be maximal if it is p + 1, p or p − 1. We wish our generalized theorems to apply to all positive integers m having a certain maximal rank property.

Definition 6. (Maximal Rank) Let p be a prime not dividing Q and a be an integer ≥ 1. We say that the rank of p^{a} is maximal whenever ρ(p) is maximal and ρ(p^{a}) = p^{a−1}ρ(p). An integer m ≥ 1 prime to Q is said to have maximal rank whenever each prime power dividing m has maximal rank and the ranks of any two prime powers dividing m are coprime.

If m is a prime p, then Definition 6 only requires that ρ(p) be p or p ± 1. However, if m = p^{a}, with a ≥ 2, has maximal rank, then clearly we also must have p^{1}||U_{ρ(p)}. Note that if m has maximal rank with respect to U(P, Q), then any divisor n of m has maximal rank with respect to U(P, Q).

Remark 7. It may be useful to observe that if m is the product of prime powers which all have maximal rank with respect to some U(P, Q) and m is either odd, or m and P are both even, then m has maximal rank if and only if gcd (ρ(p), ρ(q)) = 1, for any two prime factors p and q of m.

Proof. Suppose gcd (ρ(p), ρ(q)) = 1. We only need to verify that ρ(p^{a}) and ρ(q^{b}) are coprime, where p^{a}||m and q^{b}||m. If p and q are odd, one of them, say q, must have rank equal to q, since p ± 1 and q ± 1 are both even. Thus, ρ(q^{b}) = q^{b}. So q ∤ ρ(p) and q ≠ p yields that gcd (ρ(p^{a}), ρ(q^{b})) = 1. If p is 2 and q is odd, then, assuming P is even, we have ρ(p) = 2 since U_{2} = P, and thence ρ(q) = q. Therefore, ρ(2^{a}) = 2^{a} and ρ(q^{b}) = q^{b}. The converse is immediate. ⊓ ⊔

The upcoming remark essentially says that if p has maximal rank, the condition p^{2} ∤ U_{ρ(p)} suffices for all p^{a}, a ≥ 1, to have maximal rank. Note that if U is the Fibonacci sequence, then the search for a Wall-Sun-Sun prime, i.e., a prime p such that p^{2} divides U_{ρ(p)}, has gathered attention, but to this date none is known to exist and there does not exist any below 2 × 10^{14} [12].

Remark 8. Let p ∤ Q be a prime of maximal rank such that p^{2} ∤ U_{ρ(p)}. Additionally, we assume P is even, if p is 2. Then p^{a} has maximal rank for all a ≥ 1.

Proof. By Theorem 9 of [1], the rank of p^{a} is equal to p^{a−1}ρ(p), if p is odd. Suppose p = 2. Since U_{1} = 1, U_{2} = P and P is even, we have ρ(2) = 2. By hypothesis, 4 ∤ U_{ρ(2)}, i.e., 4 ∤ P, and Q is odd. Therefore, 8 | D = P^{2} − 4Q. By identity (8), ν_{2}(V_{t}) = 1 for all integers t’s. Thus, the 2-adic valuation of U_{2t} = U_{t}V_{t} is one more than that of U_{t}. So by induction we obtain that ρ(2^{a}) = 2^{a−1}ρ(2) = 2^{a}. ⊓ ⊔

With the help of Lemma 15, we give the full list of integers of maximal rank with respect to the Fibonacci sequence.

Example 9. An integer m ≥ 1 has maximal rank with respect to the Fibonacci sequence F = U(1, −1) iff it has the form

2^{a} 5^{b} p^{c},

where p is a prime 3 (mod 4) of rank ρ(p) = p ± 1, not a Wall-Sun-Sun prime in case c ≥ 2, and where a ∈ {0, 1, 2}, b ≥ 0, c ≥ 0 with

• c = 0,  if a = 2;
• 3 ∤ ρ(p), if a = 1 and c ≥ 1;
• 5 ∤ ρ(p), if b ≥ 1 and c ≥ 1.

Artin’s conjecture states that an integer a, not a square, with |a| ≥ 2, is a primitive root modulo infinitely many primes. In fact, it has been conditionally proved that such primes have a positive density [5]. Similarly here, since Q is not a square, it is expected that a positive proportion of the primes 3 (mod 4) have maximal ranks in F. In fact, 3, 7, 11, 19, 23, 31 and 43 all have maximal ranks, 47 being the smallest prime 3 (mod 4) with rank less than p − 1. For all primes p that are 1 (mod 4), we have that p | U_{(p−1)/2} or p | U_{(p+1)/2}.

Definition 10. (I_{m,k} and S_{m,k}) Given an integer m ≥ 1 and an integer k, we define I_{m,k} as the set of integers that lie in the interval [kρ(m), (k + 1)ρ(m)] and are not a multiple of any ρ(p), for all primes p dividing m. Then S_{m,k} will denote the sum of all V_{t}/U_{t} in A_{m} as t varies through I_{m,k}. We write I_{m,k}(P, Q) or S_{m,k}(P, Q) if the dependence on (P, Q) needs to be specified.

In coining the two definitions 6 and 10, we had two constraints in our mind. In Leudesdorf’s Theorem 1, the sum involved is S_{m,0}(2, 1). That sum goes up to m, which is viewed as the rank of m in U_{t} = t. Thus, if we wanted a theorem that generalizes Theorem 1, then I_{m,0} had to go up to ρ(m). Actually, considering sums that go up to the least common multiple of the ranks of the prime powers dividing an integer m would also reduce to the right sums when U_{t} = t. However, generally these sums are not 0 (mod m^{2}).^{3} Also we wanted the arguments used in proving Theorem 2 to remain valid, which meant that S_{m,k} should have about m terms. These observations guided us in defining the notion of maximal rank.

Lemma 11. Let k be an integer. Let m be an integer ≥ 1 prime to Q. If m is odd, then all ratios V_{t}/U_{t} are distinct (mod m) as t varies through I_{m,k}. If m is even and 2||P, then all ratios V_{t}/(2U_{t}) are distinct (mod m) as t varies through I_{m,k}.

Proof. Assume first m is odd. If s and t are distinct integers in I_{m,k}, then U_{s−t} is not divisible by m. Thus, dividing (9) through by U_{s}U_{t}, we get that

\frac{V_{t}}{U_{t}} − \frac{V_{s}}{U_{s}} = 2Q^{t} \frac{U_{s−t}}{U_{s}U_{t}} .  (10)

Since the right-hand term of (10) is not 0 (mod m), all ratios V_{t}/U_{t} are pairwise incongruent modulo m as t varies through I_{m,k}. For the case m even, note that P = 2P′ with P′ odd. Since D = 4(P^{′2} − Q), 8 divides D. We have V_{t}^{2} − DU_{t}^{2} = 4Q^{t}, so each V_{t} is even and the ratios V_{t}/(2U_{t}) do belong to the ring A_{m} for t ∈ I_{m,k}. The reasoning is then similar to that of m odd. ⊓ ⊔

3 Main Theorems and Proofs.

Theorem 12. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences. Let p be a prime number. Suppose p^{a} has maximal rank with respect to U(P, Q), where P is even and not divisible by 4 in case p is 2. Then for all integers k

S_{p^{a},k} = ∑_{t∈I_{p^{a},k}} \frac{V_{t}}{U_{t}} is congruent to 0 (mod p^{c}),

where

c = \begin{cases}2a, & if p ≥ 5; \\ 2a − 1, & if p = 2 or 3. \end{cases}

Proof. Fix an integer k. Note that I_{p^{a},k} contains p^{a−1}ρ(p) − p^{a−1} = p^{a−1}(ρ(p) − 1) integers. By convention, all unmarked sums appearing in the proof are taken over the set I_{p^{a},k}, and thus contain p^{a−1}(ρ(p) − 1) terms. Denote (2k + 1)p^{a−1}ρ(p) by b. Since the rank of p^{a} is p^{a−1}ρ(p), we have that p^{a} divides U_{p^{a−1}ρ(p)} and that U_{b} is at least divisible by p^{a}. By (6),

2S_{p^{a},k} = ∑ (\frac{V_{t}}{U_{t}} + \frac{V_{b−t}}{U_{b−t}} ) = 2 ∑ \frac{U_{b}}{U_{t}U_{b−t}} .

3For instance, 3 and 7 have maximal ranks in the Fibonacci sequence and the least common multiple of their ranks is 8. But ∑_{t=1}^{8} L_{t}/F_{t}, (4 ∤ t), is 0 (mod 21), 6 (mod 9) and 14 (mod 49).

Suppose p is odd. Hence, it suffices to show that ∑ 2/(U_{t}U_{b−t}) is divisible by p^{d}, where d = a if p > 3, and d = a − 1 if p = 3. By (8) with t = b, gcd(U_{b}, V_{b}) divides 2Q^{⌊b/2⌋}, so that p does not divide V_{b}. Thus, it also suffices to show that

S_{1} := ∑ \frac{2V_{b}}{U_{t}U_{b−t}}

is divisible by p^{d}. Now, by (7), S_{1} is equal to

∑ \frac{V_{t}V_{b−t}}{U_{t}U_{b−t}} + Dp^{a−1}(ρ(p) − 1).

But

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

In the above final expression, the numerators of the terms in the first sum are all equal to 4U_{b}^{2} by (6). Since p^{a} divides U_{b}, we have that p^{d} divides S_{1}, if and only if, p^{d} divides

S_{2} := Dp^{a−1}(ρ(p) − 1) − S_{3},

where S_{3} := ∑(V_{t}/U_{t})^{2}.

If ρ(p) is p + 1, then S_{2} is congruent to −S_{3} (mod p^{a}). But since by Lemma 11 the p^{a} rational numbers V_{t}/U_{t} that appear in S_{3} are all distinct 0 (mod p^{a}), we have that

S_{3} ≡ ∑_{t=1}^{p^{a}} t^{2} = \frac{p^{a}(p^{a} + 1)(2p^{a} + 1)}{2 · 3} (mod p^{a}),

which yields that

S_{3} ≡ 0 (mod p^{d}).

If ρ(p) is p, then p divides D. Thus, again, S_{2} ≡ −S_{3} (mod p^{a}). Since p has odd rank, say by Theorem 10 in [1], no term of the V sequence is divisible by p. Thus, the p^{a} − p^{a−1} ratios V_{t}/U_{t} that appear in S_{3}, being all distinct (mod p^{a}), are all the invertible elements of the ring A_{p}/p^{a}. As they form a cyclic multiplicative group generated by, say, g, we have

S_{3} ≡ ∑_{k=0}^{φ(p^{a})−1} g^{2k} = \frac{g^{2φ(p^{a})} − 1}{g^{2} − 1} (mod p^{a}),

where φ denotes Euler’s totient function. For odd primes p, any primitive root (mod p^{a}) reduces to a primitive root (mod p). Therefore, the order of g (mod p) is p − 1 and, thus p | g^{2} − 1 iff p − 1 | 2, i.e., iff p = 3. But if p = 3 and a ≥ 2, then g being a primitive root (mod 9), the quantity g^{2} − 1 is divisible by 3, but not by 9. If p = 3 and a = 1, then d = 0. Therefore, for all cases, we have

S_{3} ≡ 0 (mod p^{d}).

If ρ(p) is p − 1, then the set I_{p^{a},k} is made up of p^{a−1} integer intervals of length p − 2. Indeed, integers in I_{p^{a},k} are not divisible by ρ(p), i.e., by p−1. As t varies through each such interval all V_{t}/U_{t} are distinct (mod p), and are not equal to any of the two square roots of D (mod p) by Remark 5. Thus, the summands (V_{t}/U_{t})^{2} in S_{3} take the value 0 once and every nonzero quadratic residue (mod p) twice, except D, on each interval of length p − 2 of I_{p^{a},k}. Thus, as t runs through I_{p^{a},k} and since all V_{t}/U_{t} are distinct (mod p^{a}), none of the summands (V_{t}/U_{t})^{2} of S_{3} is equal to any of the residues D, D + p, D + 2p, …, D + (p^{a−1} − 1)p (mod p^{a}). Thus,

S_{3} ≡ ∑_{i=1}^{p^{a}} i^{2} − 2 ∑_{j=1}^{p^{a−1}}(D + jp) ≡ 0 − 2p^{a−1}D (mod p^{d}).

Therefore, S_{2} = Dp^{a−1}(p − 2) − S_{3} ≡ −2Dp^{a−1} + 2p^{a−1}D = 0 (mod p^{d}).

Suppose p = 2. The symbols S_{1}, S_{2} and S_{3} refer to the same sums we had defined in the case where p was odd. Since P is even and U_{2} = P, ρ(2) = 2 and b = (2k + 1)2^{a}. As seen in proving Remark 8, ν_{2}(U_{2^{a}}) = a and so we also have ν_{2}(U_{b}) = a. Therefore, as S_{2^{a},k} = ∑ \frac{U_{b}}{U_{t}U_{b−t}}, we have

ν_{2}(S_{2^{a},k}) = a + ν_{2}( ∑ \frac{1}{U_{t}U_{b−t}} ) = a + ν_{2}( ∑ \frac{2V_{b}}{U_{t}U_{b−t}} ) − 2,

since, as shown in Remark 8, ν_{2}(V_{b}) = 1. Thus, we need to show that ν_{2}(S_{1}) ≥ a + 1. In fact, we will see that ν_{2}(S_{1}) = a + 1 so that ν_{2}(S_{2^{a},k}) is exactly 2a − 1 for all integers k. Because \frac{1}{2}(4U_{b}^{2}) is divisible by 2^{2a+1}, which is > 2^{a+1}, ν_{2}(S_{1}) = a + 1 iff ν_{2}(S_{2}) = a + 1. Since D = 4(P^{′2} − Q), where P = 2P′ and P′ is odd, 8 | D. Therefore, ν_{2}(S_{2}) is a + 1 iff ν_{2}(S_{3}) = a + 1. But S_{3} = 4S_{4}, where S_{4} = ∑ \frac{V_{t}^{2}}{4U_{t}^{2}} . The 2^{a−1} terms V_{t}/2U_{t} are all distinct (mod 2^{a}), by Lemma 11, and each such term is a unit of the ring A_{2}, by the proof of Remark 8. Therefore,

S_{4} ≡ ∑_{t=1}^{2^{a−1}}(2t − 1)^{2} (mod 2^{a}).

But ∑_{t=1}^{N}(2t − 1)^{2} = 4(N − 1)N(N + 1)/3 − N so 2^{a−1}||S_{4}. Since S_{3} = 4S_{4}, we have ν_{2}(S_{3}) = a + 1 as required. ⊓ ⊔

Remark 13. Under the hypotheses of Theorem 12, we have actually shown that the sums S_{2^{a},k} have 2-adic valuation exactly equal to 2a − 1, for all integers k.

We are ready to move on to our main result.

Theorem 14. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences. Let m be an integer of maximal rank with respect to U(P, Q). If m is even, then we make the additional hypothesis that P is even and not divisible by 4. Then for all integers k

S_{m,k}(P, Q) = ∑_{t∈I_{m,k}} \frac{V_{t}}{U_{t}} is congruent to 0 (mod m^{2}/d_{m}),

where I_{m,k} is the set of integers in the interval (kρ(m), (k + 1)ρ(m)) that are not multiples of any rank ρ(p) for all primes p dividing m, and where

d_{m} = \{ \begin{matrix}2, & if m = 2^{a}, a ≥ 1; \\ 3, & if 3 | m; \\ 1, & otherwise. \end{matrix}

Proof. We proceed by induction on ω(m), where ω denotes the distinct prime factors counting function. More precisely, our inductive hypothesis at level i, i ≥ 1, says that for all integers k, all integers m ≥ 1 with ω(m) = i and all Lucas sequences U = U(P, Q) with respect to which m satisfies the hypotheses of Theorem 14, the sum S_{m,k}(P, Q) is congruent to 0 (mod m^{2}/d_{m}).

The case i = 1 was established in Theorem 12, so we assume that i ≥ 2 and that the result holds for integers having i−1 distinct prime factors. To prove the inductive hypothesis at level i, we establish two properties (11) and (12) which together clearly suffice to prove the inductive step. The first property says that

if m = p^{a}n, then n^{2}/d_{n} divides S_{m,k},  (11)

where p is a prime that does not divide n and a ≥ 1. Note that (11) is sufficient to prove the inductive step if m is odd, but not if m is even, unless we know the theorem holds for even integers at level i = 2. Thus, in addition, we prove that

if m = 2^{a}q^{b}, then 2^{2a} divides S_{m,k},  (12)

where q is an odd prime, a and b ≥ 1.

We begin by establishing (11) inductively. To this end, we note that

S_{m,k} = S^{∗} − S^{∗∗},

where

S^{∗} = ∑_{j=0}^{ρ(p^{a})−1} ∑_{\begin{matrix}t=kρ(m)+jρ(n) \\ ρ(q) ∤ t if q|n \end{matrix}}^{kρ(m)+(j+1)ρ(n)} \frac{V_{t}}{U_{t}}  and  S^{∗∗} = ∑_{\begin{matrix}t=kρ(m) \\ ρ(p) | t \\ ρ(q) ∤ t, ∀q|n \end{matrix}}^{(k+1)ρ(m)} \frac{V_{t}}{U_{t}} ,  (13)

and the letter q stands for a prime. Moreover, we have

S^{∗} = ∑_{j=0}^{ρ(p^{a})−1} S_{n,j+kρ(p^{a})}.  (14)

Each inner sum S_{n,j+kρ(p^{a})} in S^{∗} is, by the inductive hypothesis, divisible by n^{2}/d_{n}, so we are left with showing that S^{∗∗} is also divisible by n^{2}/d_{n}. But

S^{∗∗} = ∑_{\begin{matrix}t=kρ(n)p^{a−1} \\ ρ(q) ∤ t, ∀q|n \end{matrix}}^{(k+1)ρ(n)p^{a−1}} \frac{V_{ρ(p)t}}{U_{ρ(p)t}} = U_{ρ(p)}^{−1} ∑_{j=kp^{a−1}}^{(k+1)p^{a−1}−1} S_{n,j}(V_{ρ(p)}, Q^{ρ(p)}).  (15)

In (15), the sum S_{n,j}(V_{ρ(p)}, Q^{ρ(p)}) is associated with the pair of Lucas sequences attached to the recursion x^{2} − V_{ρ(p)}x + Q^{ρ(p)}. Indeed, we have

V_{ρ(p)t}(P, Q) = V_{t}(P′, Q′) and U_{ρ(p)t}(P, Q) = U_{t}(P′, Q′) · U_{ρ(p)}(P, Q),  (16)

where P′ = V_{ρ(p)}(P, Q) and Q′ = Q^{ρ(p)}. Identities (16) may be derived from the Binet formulas for U_{t} and V_{t} whether the discriminant P^{2} − 4Q is zero or nonzero. For instance, suppose x^{2} − P x + Q = (x − α)^{2}. Then U_{t}(P, Q) = tα^{t−1} and denoting ρ(p) by ρ we have

U_{ρt}(P, Q) = ρtα^{ρt−1} = ρtα^{ρ(t−1)+(ρ−1)}
= ρα^{ρ−1} · t(α^{ρ})^{t−1}
= U_{ρ}(P, Q) · U_{t}(P′, Q′).

By the inductive hypothesis n^{2}/d_{n} divides each sum S_{n,j}(P′, Q′), for all j’s, provided we check, on the one hand, that n has maximal rank with respect to U′ = U(P′, Q′) and, on the other, in case n is even, that ν_{2}(P′) = 1.

Since m is prime to Q, n is prime to Q′. Let q be a prime factor of n, ρ(q) be its rank in U = U(P, Q) and ρ′(q) its rank in U′ = U(P′, Q′), where as above ρ(p) is the rank of p in U. By hypothesis, ρ(q) and ρ(p) are coprime so that q ∤ U_{ρ(p)}. Thus, as U_{ρ(p)t} = U_{ρ(p)} · U′_{t}, we have that q | U′_{t} iff q | U_{ρ(p)t} iff ρ(q) | ρ(p)t iff ρ(q) | t. Thus, ρ(q) = ρ′(q). We conclude that the rank of q in U′ is maximal. Similarly, since ρ(q^{s}) = q^{s−1}ρ(q) is also prime to ρ(p), the ranks of q^{s} in U and in U′ are identical for all s ≥ 2. Therefore, if q^{α}||m, then, as ρ(q^{α}) exists and is equal to q^{α−1}ρ(q), we have ρ′(q^{α}) = q^{α−1}ρ′(q). That is, q^{α} has maximal rank in U′. Moreover, distinct prime factors of n have coprime ranks in U′.

Suppose n is even. Then m is even. Hence, Q is odd and ν_{2}(P) = 1, which, as proved in Remark 8, implies that ν_{2}(V_{t}) = 1 for all integers t. But P′ = V_{ρ(p)}.

Thus, since each prime factor q of n is prime to U_{ρ(p)}, we deduce that S^{∗∗} is divisible by n^{2}/d_{n}. We have proved (11).

To prove (12), we assume i = 2 and ‘recycle’ the proof of (11). So given m = 2^{a}q^{b} we have, by (11), that 2^{2a−1}q^{2b}/d_{q} = m^{2}/(2d_{m}) divides S_{m,k}. Reexamining the proof of (11) with p = q, we will show that in fact 2^{2a} divides S_{m,k}. By Remark 13, each of the ρ(q^{b}) sums S_{2^{a},j+kρ(q^{b})} in (14) is divisible by 2^{2a−1}, but not by 2^{2a}. But, by (15), we see that S^{∗∗} is also the sum of q^{b−1} sums each of which is exactly divisible by 2^{2a−1}. Therefore, S_{m,k} is the sum of ρ(q^{b}) + q^{b−1} terms each divisible exactly by 2^{2a−1}. Thus, it suffices to check that ρ(q^{b}) + q^{b−1} is even. But ρ(2) = 2, and so ρ(q) must be odd. As the rank of q is maximal, it must be that ρ(q) = q. Hence, ρ(q^{b}) + q^{b−1} = q^{b−1}(q + 1). ⊓ ⊔

4 The Remaining Cases

Theorem 14 clearly contains Theorem 2, but it also implies Theorem 1. Indeed, for (P, Q) = (2, 1), we have U_{t} = t and V_{t} = 2, for all t’s. In particular, ν_{2}(P) = 1 and all integers m ≥ 1 have maximal rank. Say, for instance, that 3 | m. Then, by Theorem 14, ∑_{t∈I_{m,0}} 2/t ≡ 0 (mod m^{2}/3), which implies

∑_{\begin{matrix}t=1 \\ gcd(t,m)=1 \end{matrix}}^{m} 1/t ≡ 0 (mod m^{2}/ gcd(m, 6)),

as gcd(t, m) = 1 iff ρ(p) = p ∤ m for all primes p dividing m.

But Theorem 14 does not apply to even integers having maximal rank in U(P, Q), if either 4 | P, or P is odd. The next lemmas treat those missing cases, and, combined with Theorem 14, they yield Theorem 3 stated in the introduction.

The first lemma fully describes when powers of 2 have maximal rank.

Lemma 15. Assume Q is odd. Then 2^{a}, a ≥ 1, has maximal rank in U(P, Q) if and only if

a = 1,  if 4 | P, or if P is odd and Q ≡ 1 (mod 4);
a = 1 or 2, if P is odd and Q ≡ 3 (mod 4);
a ≥ 1,  if P ≡ 2 (mod 4).

Proof. Since U_{2} = P and U_{3} = P^{2} − Q, either P is even and ρ(2) = 2, or P is odd and ρ(2) = 3. Thus, 2^{a} has maximal rank for a = 1.

If 4 | P, or if P is odd and Q ≡ 1 (mod 4), then ρ(4) = ρ(2). By (8), if U_{t} is even, then V_{t} is even. Since U_{2t} = U_{t}V_{t}, we have ν_{2}(U_{2t}) ≥ 1 + ν_{2}(U_{t}). Therefore, since ρ(4) = ρ(2), ρ(2^{a}) < 2^{a−1}ρ(2) for all a ≥ 2.

If P is odd and Q ≡ 3 (mod 4), then ρ(2) = 3 and ρ(4) = 6. Thus, 4 has maximal rank. However, U_{6} = U_{2}U_{3}(P^{2} − 3Q) and 4 | P^{2} − 3Q, so 8 | U_{6}. Hence, ρ(8) = ρ(4) and ρ(2^{a}) < 2^{a−1}ρ(2), for all a ≥ 3.

The case P ≡ 2 (mod 4) was taken care of in Remark 8. ⊓ ⊔

Lemma 16. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences, where P is divisible by 4 and Q is odd. Let m be an even integer of maximal rank with respect to U(P, Q). Then for all integers k

S_{m,k}(P, Q) ≡ 0 (mod 2^{σ}m^{2}/ gcd(m, 3)),

where σ = ν_{2}(P) − 2.

Proof. By Lemma 15, m is not divisible by 4. So we write m = 2n with n odd. Since ρ(2) = 2, all odd prime factors p of m satisfy ρ(p) = p. As in proving Theorem 14, we carry an induction on i = ω(m), where the inductive hypothesis at level i assumes the lemma to hold for all integers m with ω(m) = i, all pairs (P′, Q′), 4 | P′ and Q′ odd, with respect to which m has maximal rank in U(P′, Q′) and all integers k. If i = 1, that is, if m = 2, then S_{2,k} = V_{2k+1}/U_{2k+1}. An easy induction using (3) yields that ν_{2}(V_{2t}) = 1 and ν_{2}(V_{2t+1}) = ν_{2}(P), for all integers t. Hence, 2^{ν_{2}(P)}||S_{2,k}. But 2^{ν_{2}(P)} = 2^{σ}m^{2}. Assume that i ≥ 2 and that the inductive hypothesis holds at level i − 1. We decompose S_{m,k} into the difference of S^{∗} and S^{∗∗} as we did in the proof of Theorem 14 by choosing a prime p that divides m. If p is 2, then, by Theorem 14, both the inner sums S_{n,j+2k}(P, Q) of S^{∗} in (14) and the inner sums S_{n,j}(P′, Q′) of S^{∗∗} in (15) are divisible by n^{2}/d_{n}, where d_{n} = gcd(n, 3).

But gcd(n, 3) = gcd(m, 3) so n^{2}/ gcd(m, 3) divides S_{m,k}. It remains to see that 2^{ν_{2}(P)} divides S_{m,k}. If p is odd, then put ℓ = m/p^{a}, where a = ν_{p}(m). The inner sums S_{ℓ,j+kρ(p)}(P, Q) of S^{∗} are now divisible by 2^{σ}ℓ^{2}/ gcd(ℓ, 3), and by 2^{ν_{2}(P)} in particular, by the inductive hypothesis. The inner sums S_{ℓ,j}(P′, Q′) are divisible by 2^{ν_{2}(P′)} by the inductive hypothesis, which is applicable since 4 | P′ and Q′ is odd. But P′ = V_{ρ(p)} = V_{p} and ν_{2}(V_{p}) = ν_{2}(P), since p is odd. Hence, S_{m,k} is divisible by 2^{σ}m^{2}/ gcd(m, 3). ⊓ ⊔

Lemma 17. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences, where P is odd and Q is congruent to 1 (mod 4). Let m be an even integer of maximal rank with respect to U(P, Q). Then for all integers k

S_{m,k}(P, Q) ≡ 0 (mod 2^{τ}m^{2}/ gcd(m, 3)),

where τ = ν_{2}(P^{2} − Q) − 1 ≥ 1.

Proof. One may carry a successful induction that closely follows that of the proof of Lemma 16. Note that 4 ∤ m and that ρ(2) = 3. If m = p^{a}ℓ, ℓ even, then by induction the sums S_{ℓ,j}(P′, Q′) in S^{∗∗} are divisible by 2^{τ}ℓ^{2}/ gcd(ℓ, 3). Indeed, 2 | V_{t} iff 3 | t. Thus, since P′ = V_{ρ(p)} and ρ(2) ∤ ρ(p), P′ is odd. Moreover, Q′ = Q^{ρ(p)} ≡ 1 (mod 4). If m = 2n, then, by Theorem 14 applied to the inner sums in both S^{∗} and S^{∗∗}, n^{2}/d_{n} divides S_{m,k}, where d_{n} was defined in Theorem 14.

For the base step of the induction, note that if ω(m) = 1, then m = 2. So I_{2,k} = {3k+1, 3k+2} and S_{2,k} = 2U_{6k+3}/U_{3k+1}U_{3k+2}. Therefore, we have ν_{2}(S_{2,k}) = ν_{2}(2U_{3}) = 2+τ. Indeed, U_{3(2k+1)} = U_{3} · U′_{2k+1}, where U′ = U(V_{3}, Q^{3}), and U′_{t} (mod 2) = 0, 1, 0, 1, 0, 1, ⋯ (t ≥ 0), since V_{3} is even. ⊓ ⊔

Lemma 18. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences, where P is odd and Q is congruent to 3 (mod 4). Let m be an even integer not divisible by 4 of maximal rank with respect to U(P, Q). Then for all integers k

S_{m,k}(P, Q) ≡ 0 (mod m^{2}/ gcd(m, 3)).

Proof. An induction very similar to those used in proving Lemmas 16 and 17 works fine. Note however that besides Theorem 14, Lemma 17 also comes into play. Indeed, if m = p^{a}ℓ, p an odd prime not dividing ℓ, then the sums S_{ℓ,j} in S^{∗∗} are associated with a Lucas sequence U(P′, Q′), where P′ is odd, but Q′ = Q^{ρ(p)} is congruent to 1 (mod 4), if ρ(p) is even. The base step of the induction corresponds to m = 2 and, as in the proof of Lemma 17, we have ν_{2}(S_{2,k}) = ν_{2}(2U_{3}). However, U_{3} = P^{2} − Q is even, but not divisible by 4. ⊓ ⊔

Lemma 19. Let U(P, Q) and V (P, Q) be a pair of Lucas sequences, where P is odd and Q is congruent to 3 (mod 4). Let m be an integer divisible by 4 of maximal rank with respect to U(P, Q). Then for all integers k

S_{m,k}(P, Q) ≡ 0 (mod 8m^{2}).^{4}

4Thus, 2^{7} divides S_{m,k}. Unless we refine further the hypotheses on P and Q, the exponent 7 is optimal.

For instance, S_{4,0}(1, −1) = \frac{128}{15}.

Proof. A proof by induction on i = ω(m) of the same model as in the three previous lemmas works fine. The rank of 4 is 6. Since the rank of 3 must be 2, 3 or 4, and none of these is prime to 6, 3 ∤ m. Writing m as 4n with n odd, we find that n^{2} divides S_{m,k} by Theorem 14. Thus, we are left with seeing that 2^{7} divides S_{m,k}. Write m as p^{a}ℓ, where p is a prime ≥ 5 and p ∤ ℓ. We have that 4 | ℓ and that the inner sums S_{ℓ,j+kρ(p^{a})} in S^{∗} are divisible by 8ℓ^{2} and by 2^{7} in particular, using the inductive hypothesis. How about the inner sums S_{ℓ,j}(P′, Q′) of S^{∗∗}? Note that ρ(2) is 3. So m being of maximal rank, 3 ∤ ρ(p). But 2 | V_{t} iff 3 | t. So P′ = V_{ρ(p)} is odd. In fact, as ρ(4) = 6, ρ(p) must also be odd, that is to say, ρ(p) = p. Thus, Q′ = Q^{ρ(p)} ≡ 3 (mod 4). The inductive hypothesis yields that S^{∗∗} is divisible by 2^{7}.

We have not checked the initial step of the induction, i.e., the case m = 4. Note that I_{4,k} = {6k + 1, 6k + 2, 6k + 4, 6k + 5}. Combining, on one hand, the first and fourth terms of S_{4,k}, and, on the other hand, the middle ones, yields

S_{4,k} = \frac{2U_{12k+6}}{U_{6k+1}U_{6k+5}} + \frac{2U_{12k+6}}{U_{6k+2}U_{6k+4}} .

Hence, ν_{2}(S_{4,k}) = ν_{2}(2U_{6}) + ν_{2}(U_{6k+2}U_{6k+4} + U_{6k+1}U_{6k+5}). But U_{6} = U_{2}U_{3}(P^{2} − 3Q) = P (P^{2} − Q)(P^{2} − 3Q), so that

ν_{2}(2U_{6}) = 2 + ν_{2}(P^{2} − 3Q) ≥ \{ \begin{matrix}5, if Q ≡ 3 (mod 8); \\ 4, if Q ≡ 7 (mod 8). \end{matrix}  (17)

Since ρ(8) = 6, we have U_{t+6} ≡ U_{7}U_{t} (mod 8) for all t ≥ 0. Indeed, the congruence holds for t = 0 and t = 1, and, by (3), it must hold for all t’s. Thus,

U_{6k+2}U_{6k+4} + U_{6k+1}U_{6k+5} ≡ U_{7}^{2k}(U_{2}U_{4} + U_{1}U_{5}) (mod 8).

A direct calculation gives U_{2}U_{4} + U_{1}U_{5} = 2P^{4} − 5P^{2}Q + Q^{2} ≡ 3(Q + 1) (mod 8). Therefore,

ν_{2}(U_{6k+2}U_{6k+4} + U_{6k+1}U_{6k+5}) ≥ \{ \begin{matrix}2, if Q ≡ 3 (mod 8); \\ 3, if Q ≡ 7 (mod 8), \end{matrix}

which, combined with (17), yields that ν_{2}(S_{4,k}) ≥ 7 for all integers k. ⊓ ⊔

5 Acknowledgments

We thank the two referees for time spent reading this paper and writing up comments and suggestions. One of the referees pointed out reference [13].

References

[1] Christian Ballot, Lucas sequences with cyclotomic root field, submitted preprint, 120 pages.

[2] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}, Ann. of Math., 15, (1913–14), 30–48, 49–70.

[3] S. Chowla, Leudesdorf’s generalization of Wolstenholme’s theorem, J. London Math. Soc., 9 (1934), 246.

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

[5] C. Hooley, On Artin’s conjecture, J. reine angew. Math. 225 (1967), 209–220.

[6] G. J. Janusz, Algebraic Number Fields, Academic Press, 1973.

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

[8] William Kimball and William Webb, Some generalizations of Wolstenholme’s theorem, in Applications of Fibonacci Numbers Vol. 8, Kluwer, 1999, pp. 213–218.

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

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

[11] Édouard Lucas, Théorie des Nombres, Librairie scientifique et technique Albert Blanchard, 1961.

[12] Richard J. McIntosh and Eric L. Roettger, A search for Fibonacci-Wieferich and Wolstenholme primes, Math. Comp., 76 (2007), 2087–2094.

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

[14] Paulo Ribenboim, The Fibonacci numbers and the Artic Ocean, Proceedings of the 2nd Gauss Symposium. Conference A: Mathematics and Theoretical Physics, de Gruyter, 1995, pp. 41–83.

[15] Hugh C. Williams, Édouard Lucas and Primality Testing, Wiley, 1998.

[16] Joseph Wolstenholme, On certain properties of prime numbers, Quarterly J. Pure Applied Math., 5 (1862), 35–39.

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

Received June 6 2012; revised version received October 8 2012. Published in Journal of Integer Sequences, October 8 2012. Minor typographical corrections, November 24 2013.

Return to Journal of Integer Sequences home page.