Congruences Involving Sums of Ratios of Lucas Sequences

Evis Ieronymou Department of Mathematics and Statistics University of Cyprus 1687 Nicosia Cyprus

                   ieronymou.evis@ucy.ac.cy

Abstract Given a pair (U_{t}) and (V_{t}) of Lucas sequences, we establish various congruences involving sums of ratios \frac{V_{t}}{U_{t}}. More precisely, let p be a prime divisor of the positive integer m. We establish congruences, modulo powers of p, for the sum ∑ \frac{V_{t}}{U_{t}}, where t runs from 1 to r(m), the rank of m, and r(q) ∤ t for all prime factors q of m.

1 Introduction

Wolstenholme’s classic congruence dating back to 1862 is the following:

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

where p ≥ 5 is a prime number. Kimball and Webb [4] found a generalization of the above congruence using Lucas sequences. In order to state it we need to recall some basic definitions and terminology: The pair of Lucas sequences (U_{t}) and (V_{t}) associated with a pair of coprime integers P and Q is given by the second-order linear recurrence

X_{n+2} = P X_{n+1} − QX_{n},

and initial conditions U_{0} = 0, U_{1} = 1, V_{0} = 2, V_{1} = P. We set D = P^{2} − 4Q. Given an integer m let r(m) denote, if it exists, the least positive integer such that m divides U_{r(m)} and call it the rank of appearance (or apparition) of m. For a prime p with gcd(p, 2Q) = 1 we know that r(p) divides p − (\frac{D}{p}), where (\frac{D}{p}) is the Legendre symbol. A prime is called

of maximal rank if r(p) = p − (\frac{D}{p}).

Kimball and Webb’s congruence is the following:

v_{p} ( ∑_{t=1}^{r(p)−1} \frac{V_{t}}{U_{t}} ) ≥ 2,

when p ≥ 5 is a prime of maximal rank. In the above inequality and in the rest of this note v_{p}(x) denotes the standard p-adic valuation of the rational number x, where p is a prime number. Note that for P = 2, Q = 1 we recover Wolstenholme’s congruence.

In turn, Ballot [2] generalized Kimball and Webb’s congruence in the following:

Proposition 1. Let (U_{t}) and (V_{t}) be a pair of Lucas sequences. If m is of maximal rank and gcd(m, 6Q)=1 then

v_{q} (∑_{t∈I_{m}} \frac{V_{t}}{U_{t}} ) ≥ 2v_{q}(m),

where q is a prime divisor of m and

I_{m} = \{n : 1 ≤ n ≤ r(m)\} − ⋃_{\begin{matrix}p is prime \\ p | m \end{matrix}} ℤ · r(p).

Remark 2. Ballot [2] proves more, most notably the condition that gcd(m, 6) = 1 is not there and a complete list of what happens in those cases is given. The reason we will assume that gcd(m, 6) = 1 in this note will be explained later in the introduction.

The notion of maximal rank for composite m was introduced in [2] and is the following: We say that m has maximal rank if for any two prime divisors p, q of m with a = v_{p}(m) and b = v_{q}(m) we have that (i) p is of maximal rank, (ii) r(p^{a}) = p^{a−1}r(p) and (iii) gcd(r(p^{a}), r(q^{b})) = 1 for p ≠ q.

This notion has the obvious nuisance that it excludes many m. For example, if m is of maximal rank then it can have at most one prime divisor outside the prime divisors of 2D and moreover all its prime divisors must themselves be of maximal rank. A natural thing to ask is whether we can say anything definite with a weaker notion. The aim of this note is to clarify the situation.

Our first main result tells us what happens for prime powers.

Theorem 3. Let (U_{t}) and (V_{t}) be a pair of Lucas sequences and let p be a prime with gcd(p, 6Q) = 1 and v_{p}(U_{r(p)}) = 1.

If p has maximal rank then

v_{p} ( ∑_{t∈I_{p^{a}}} \frac{V_{t}}{U_{t}} ) ≥ 2a.

If p does not have maximal rank then

v_{p} ( ∑_{t∈I_{p^{a}}} \frac{V_{t}}{U_{t}} ) = 2a − 1.

The new thing in the above theorem is the inclusion of the case when p does not have maximal rank. It is crucial in the consideration of integers with more than one prime divisor.

Example 4. We consider the Fibonacci and Lucas numbers, i.e., the pair of Lucas sequences associated to P = 1 and Q = −1.

• For m = 13^{3} we have r(13) = 7 and so

S ≡ 0 (mod 13^{5}), S ≢ 0 (mod 13^{6}),

where

S = ∑_{\begin{matrix}t=1 \\ gcd(t,7)=1 \end{matrix}}^{7·13^{2}} \frac{L_{t}}{F_{t}} .

The second main result is concerned with integers with more than one prime divisor.

Theorem 5. Let m = p^{a} ∏_{i=1}^{τ} q_{i}^{a_{i}} be the prime factorization of m. Suppose that gcd(p, 6Q)=1 and v_{p}(U_{r(p)}) = 1. Let r = r(p) and r_{i} = r(q_{i}).

1. We have that

v_{p} (∑_{t∈I_{m}} \frac{V_{t}}{U_{t}} ) ≥ max(a, μ + ϵ),

where μ = max\{v_{p}(r_{i})\} and ϵ = (\frac{D}{p})^{2}.

2. Suppose that either max{v_{p}(r_{i}) : r ∤ r_{i}} = 0 or {r_{i} : r ∤ r_{i}} = ∅. Then

v_{p} (∑_{t∈I_{m}} \frac{V_{t}}{U_{t}} ) ≥ 2a − 1.

If moreover p has maximal rank and gcd(r, r_{i}) = 1 for all r_{i} with r ∤ r_{i} the above inequality is strict.

Note that we recover Ballot’s result stated at the beginning as a special case. Below we give examples not covered by that.

Example 6. We continue with the Fibonacci and Lucas numbers. In each case S = ∑_{I_{m}} \frac{L_{t}}{F_{t}}. • For m = 7^{4} · 11^{3} we have r(7) = 8, r(11) = 10 and so

S ≡ 0 (mod 7^{7} · 11^{5}).

• For m = 7 · 17^{2} we have r(7) = 8, r(17) = 9 and so

S ≡ 0 (mod 7^{2} · 17^{3}).

• For m = 7 · 97 we have r(7) = 8, r(97) = 7^{2} and so

S ≡ 0 (mod 7^{3} · 97).

• For m = 5 · 11^{2} we have r(5) = 5, r(11) = 10 and so

S ≡ 0 (mod 5^{2} · 11^{3}).

• For m = 79 · 859^{2} we have r(79) = r(859) = 78 and so

S ≡ 0 (mod 79^{2} · 859^{3}).

• For m = 37 · 73 we have r(37) = 19, r(73) = 37 and so

S ≡ 0 (mod 37^{2} · 73).

• For m = 19 · 73^{2} · 89^{3} · 97^{4} we have r(19) = 18, r(73) = 37, r(89) = 11, r(97) = 49 and so

S ≡ 0 (mod 19^{2} · 73^{3} · 89^{5} · 97^{7}).

Remark 7. Note that there is no claim for optimality in the congruences. It can be checked that when m ∈ {7 · 17^{2}, 5 · 11^{2}, 79 · 859^{2}, 37 · 73} the congruences above are indeed optimal for each prime dividing m. However when m = 7 · 97 the congruence is optimal modulo 97 but not modulo 7 as we actually have that v_{7}(S) = 4.

A few words about our assumptions and definitions. If we seek a nice generalization of Kimball and Webb’s result summing up to r(m) is more or less forced (cf. [2, pg. 7]). Now, if we want to say something about the sum modulo powers of prime divisors of m we want the individual terms to make sense modulo p for any prime p dividing m. That is why we exclude the multiples of r(p) in the definition of I_{m}. This, however, has hidden ramifications since integers we excluded because of q might alter the sum modulo powers of p in an unpredictable way and we have to keep track of the various interactions as we add more primes.

In this note we only impose the condition that v_{p}(U_{r(p)}) = 1 and see what happens. This is a reasonable condition: from considering prime powers we see that I_{m} does not see the difference between p and p^{v_{p}(U_{r(p)})}. Moreover, when v_{p}(U_{r(p)}) > 1 we can still use Lemma 10 to draw conclusions. With regards to our other assumptions, the exclusion of 3 is mostly a matter of aesthetics: the same arguments would go through but we would have to subtract 1 in various results when working modulo powers of 3 thus complicating the statement of the results. The exclusion of 2 is qualitatively different: not only the results would be more tedious to write but they would require different arguments to establish. Finally, we take gcd(p, Q) = 1 since otherwise r(p) does not exist.

This note is organized as follows. In Section 2 we recall some basic facts about Lucas sequences and set up two auxiliary lemmata. In Section 3 we take care of the case when m is a prime power by proving our first main result. In Section 4 we move on to the case when m has more than one prime divisor, and we prove our second main result.

The assertions about the ranks of appearance in the examples were checked using the computer algebra system magma.

2 Preliminaries

Lucas sequences are well-studied and satisfy many identities. For the convenience of the reader we collect some well-known properties of Lucas sequences we will be using in the following lemma. The interested reader can look at [1], [5] or [6] and references therein for details of the proofs and much more about Lucas sequences. We remind the reader of our assumption that gcd(P, Q) = 1.

Lemma 8. 1. If s, t are positive integers and s divides t then U_{s} divides U_{t}.

2. m divides U_{n} if and only if r(m) divides n.

3.

r(lcm(a, b)) = lcm(r(a), r(b)).

4. If gcd(n, 2Q) = 1 and r(n) does not divide either s or t then

\frac{V_{s}}{U_{s}} ≡ \frac{V_{t}}{U_{t}} (mod n) ⇔ s ≡ t (mod r(n)).

5. (Law of repetition) If p is an odd prime and p divides U_{n} then

v_{p}(U_{kn}) = v_{p}(U_{n}) + v_{p}(k).

6. If ℓ = v_{p}(U_{r(p)}) then r(p^{a}) = p^{max(a,ℓ)−ℓ}r(p).

Remark 9. For the sake of clarity, in order to make sense of the last two statements of the lemma when some U_{n} = 0 we use the conventions that v_{p}(0) = ∞ and ∞ − ∞ = 0. This has no relevance to the next two sections.

We now establish two auxiliary lemmata which we will be using in the next sections.

Lemma 10. Let p be an odd prime, s = r(p^{a}) and ν = v_{p}(U_{s}). Let J ⊂ ℤ be a finite set such that

(i) none of its elements is divisible by r(p), and

(ii) there is a k such that sending x to ks − x maps J to J.

Let ℓ = v_{p}(U_{ks}) and denote ks − x by x̂.

Then

v_{p} (∑_{t∈J} \frac{V_{t}}{U_{t}} ) = ℓ + v_{p} (∑_{t∈J} \frac{1}{U_{t}Ut̂}) ,

2V_{ks} ∑_{t∈J} \frac{1}{U_{t}Ut̂} ≡ D|J| − ∑_{t∈J} (\frac{V_{t}}{U_{t}} )^{2} (mod p^{2ℓ}).

Moreover, if J′ is the translation of J by s, i.e., J′ = J + s, then J′ satisfies the two assumptions (with the new k being k+2) and the value of ∑ \frac{1}{U_{t}Ut̂} is multiplied by \frac{4}{V_{s}^{2}} (mod p^{ν}).

Proof. The easy algebraic manipulations (which are based on well known-formulae for Lucas sequences) that establish the result can be found in [2] or [4]. For completeness and the convenience of the reader, we repeat the main points here. The first equality can be easily established by using the equality

\frac{V_{t}}{U_{t}} + \frac{Vt̂}{Ut̂} = 2\frac{U_{ks}}{U_{t}Ut̂}.

The congruence is established by noting that its left hand side equals

∑_{t∈J} \frac{V_{t}Vt̂}{U_{t}Ut̂} + D|J|,

and that we also have

∑_{t∈J} \frac{V_{t}Vt̂}{U_{t}Ut̂} = \frac{1}{2} ∑_{t∈J} \frac{(2U_{ks})^{2}}{(U_{t}Ut̂)^{2}} − ∑_{t∈J} (\frac{V_{t}}{U_{t}} )^{2} .

The only non-trivial part of the last sentence is the final assertion, which follows immediately from the fact that

2U_{s+t} ≡ U_{t}V_{s} (mod U_{s}).

Lemma 11. Let p ≥ 5 be a prime and r = r(p).

If p has maximal rank then

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

If p does not have maximal rank then

∑_{t=1}^{r−1} (\frac{V_{t}}{U_{t}} )^{2} ≢ D(r − 1) (mod p).

Proof. In the first case it is easy to calculate explicitly the set \{\frac{V_{t}}{U_{t}} : 1 ≤ t ≤ r − 1\} modulo p and establish the result (cf. [4, proof of Theorem]). For the second case, the result is established by hand for the cases r = 2, 3, 4. When r ≥ 5 we will use [3, Theorem 1.1] which states that if n ≥ 5 then

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

where w_{n} is the largest divisor of U_{n} relatively prime to U_{1}, …, U_{n−1}. Taking n = r in the above, and noting that from our assumptions \frac{(r^{2}−1)D}{6V_{r}} is not divisible by p we deduce that

v_{p} (∑_{t=1}^{r−1} \frac{V_{t}}{U_{t}} ) = v_{p}(U_{r}).

The result now follows from the two displayed formulas of Lemma 10 (taking s = r, k = 1 and J = {1, …, r − 1}).

3 The case of prime powers

In this section p is a prime with gcd(p, 6Q) = 1 and v_{p}(U_{r(p)}) = 1.

Note that the second assumption implies that

r(p^{a}) = p^{a−1}r(p) , v_{p}(U_{r(p^{a})}) = a.

Recall the definition

I_{m} = \{x : 1 ≤ x ≤ r(m)\} − ⋃_{\begin{matrix}q is prime \\ q | m \end{matrix}} ℤ · r(q).

Lemma 12. Let r = r(p). Then

v_{p} ( ∑_{t∈I_{p^{a}}} (\frac{V_{t}}{U_{t}} )^{2} − D|I_{p^{a}}|) is \begin{cases}≥ a, & if p has maximal rank; \\ = a − 1, & if not. \end{cases}

Proof. Let K := ker(ℤ/p^{a} → ℤ/p). Note that the elements of \{\frac{V_{t}}{U_{t}} : t ∈ I_{p}\} are pairwise distinct modulo p, the elements of \{\frac{V_{t}}{U_{t}} : t ∈ I_{p^{a}}\} are pairwise distinct modulo p^{a}, \frac{V_{t}}{U_{t}} ≡ \frac{V_{t+r}}{U_{t+r}} (mod p) and |I_{p^{a}}| = p^{a−1}|I_{p}|. Hence, working in ℤ/p^{a} the set \{\frac{V_{t}}{U_{t}} : t ∈ I_{p^{a}}\} is the disjoint union of the cosets K + \frac{V_{t}}{U_{t}} with t ∈ I_{p}. Since ∑_{x∈K} x = ∑_{x∈K} x^{2} = 0 ∈ ℤ/p^{a}, we therefore have that

∑_{t∈I_{p^{a}}} (\frac{V_{t}}{U_{t}} )^{2} ≡ p^{a−1} ∑_{t∈I_{p}} (\frac{V_{t}}{U_{t}} )^{2} (mod p^{a}).

The result now follows from Lemma 11.

Remark 13. It is clear that the same result holds if we replace I_{p^{a}} by I_{p^{a}} + l · r(p^{a}), where l is a positive integer.

Proof of Theorem 3: Combine Lemma 10 and Lemma 12. Remark 14. Looking at Lemma 10 and Lemma 12 it is easy to see what happens if we replace I_{p^{a}} by I_{p^{a}} + l · r(p^{a}) in Theorem 3: If p has maximal rank the result remains the same. If p does not have maximal rank then the result is the same when p does not divide 2l + 1 whereas the p-adic valuation is increased by at least one when p divides 2l + 1.

4 More than one prime divisor

In this section p is a prime with gcd(p, 6Q) = 1 and v_{p}(U_{r(p)}) = 1.

First we recall the following well-known fact, easily established by Binet’s formulae: Let U′, V′ denote the pair of Lucas sequences associated with P′ = V_{n}, Q′ = Q^{n}. Then

U_{nk} = U_{n}U′_{k} and V_{nk} = V′_{k}.  (1)

It is also straightforward to see that: (i) If r(p) divides n then r′(p) = p and v_{p}(U′_{p}) = 1, (ii) If r(p) does not divide n then r′(p) = \frac{r(p)}{d} and v_{p}(U′_{r′(p)}) = v_{p}(U_{r(p)}) + v_{p}(\frac{n}{d}) where d = gcd(r(p), n).

Next, we fix some notation. For a finite set J ⊂ ℤ denote

S(J) := ∑_{t∈J} \frac{V_{t}}{U_{t}} .

Trivially

S(X ∪ Y) = S(X) + S(Y) − S(X ∩ Y),

and so if three of the above terms have p-adic valuation at least ν then so does the fourth. We will use this with no further mention.

Recall that if X is a subset of ℤ we write

X + n = {x + n : x ∈ X} and n · X = {nx : x ∈ X}.

We also introduce the following:

L_{n:b_{1},..,b_{k}} := {x : 1 ≤ x ≤ n} − ⋃_{1≤i≤k} ℤ · b_{i}.

Whenever we use the notation above, we will always have that n is divisible by all the b_{i}’s. We list some identities which are elementary to establish

L_{nsb:b} = ⨆_{0≤t≤n−1} L_{sb:b} + tsb,  (2)

L_{n:b_{1},...,b_{k}} ∩ L_{n:b_{k+1},...,b_{k+t}} = L_{n:b_{1},...,b_{k+t}},  (3)
L_{n:b_{1},...,b_{k},c_{1}} ∪ L_{n:b_{1},...,b_{k},c_{2}} = L_{n:b_{1},...,b_{k},lcm(c_{1},c_{2})},  (4)
L_{n:b,c} ∪ (L_{n:b} ∩ L_{n:c}^{∗}) = L_{n:b},  (5)
L_{n:b} ∩ L_{n:c}^{∗} = c · L_{\frac{n}{c}: \frac{b}{gcd(b,c)}} ,  (6)

where “⨆” stands for disjoint union and L_{n:c}^{∗} is the complement of L_{n:c} in L_{n:n}. We are now ready to prove our main result.

Proof of Theorem 5: Let

N = v_{p} (∑_{t∈I_{m}} \frac{V_{t}}{U_{t}} ) = v_{p}(S(I_{m})).

1. By Lemma 10 we have that N ≥ v_{p}(U_{r(m)}) = a + v_{p} (\frac{r(m)}{r(p^{a})}). Since

r(m) = lcm(p^{a−1}r, r(q_{i}^{a_{i}})),  (7)

the result then follows from the fact that v_{p}(r) = 1 when p divides D and v_{p}(r) = 0 when p does not divide D.

2. By Theorem 3, Remark 14 and formula (2) we have that

v_{p}(S(L_{nr:r})) ≥ 2v_{p}(n) + 1.  (8)

Write {1 ≤ i ≤ τ} = T ⨆ T′ where i ∈ T′ if and only if r divides r_{i}. Note that if T = ∅ then I_{m} = L_{r(m):r,r_{1},...,r_{τ}} = L_{r(m):r}, and we are done by what was said above. To treat the case when T ≠ ∅ we first establish the following.

Claim: Let c be the lcm of some of the r_{i} with i ∈ T. Then

v_{p}(S(L_{r(m):r,c})) ≥ 2a − 1.

Proof of claim: By equation (5) it suffices to show that

v_{p}(S(L_{r(m):r})) ≥ 2a − 1 and v_{p}(S(L_{r(m):r} ∩ L_{r(m):c}^{∗}) ≥ 2a − 1.

Using (8) and (7) we immediately get the first inequality. If r divides c then L_{r(m):r} equals L_{r(m):r,c} and we are done. Hence, we may assume that r does not divide c.

By (6) and (1) we have that

S(L_{r(m):r} ∩ L_{r(m):c}^{∗}) = \frac{1}{U_{c}} ∑_{t∈M} \frac{V′_{t}}{U′_{t}} , where M = L_{\frac{r(m)}{c}: \frac{r}{gcd(r,c)}}

and U′, V′ are defined as in the beginning of this section with n = c. Since v_{p}(r_{i}) = 0 when i ∈ T, we have that v_{p}(c) = 0. Hence, our assumptions imply that v_{p}(U′_{r′(p)}) = 1 and r′(p) = \frac{r}{gcd(r,c)}. Therefore, we deduce by (8) that v_{p}(S(L_{r(m):r} ∩ L_{r(m):c}^{∗}) ≥ 2γ + 1,

where γ = v_{p} (\frac{r(m)}{lcm(r,c)}). Since

v_{p} (\frac{r(m)}{lcm(r, c)}) = v_{p} (\frac{r(m)}{r}) ≥ a − 1,

the proof of the claim is complete. QED

It is now an easy induction using (3) and (4) to augment the claim to

v_{p}(S(L_{r(m):r,c,r_{i_{1}},...,r_{i_{k}}})) ≥ 2a − 1,

where i_{j} ∈ T.

Note that if p has maximal rank and gcd(r, r_{i}) = 1 for all i ∈ T then whenever we invoke Theorem 3 in the proof above the corresponding inequality is strict, and so in this case the result is that v_{p}(S(L_{r(m):r,c,r_{i_{1}},...,r_{i_{k}}})) > 2a − 1.

Finally, to finish the proof we need only note that by definition I_{m} = L_{r(m):r,r_{1},...,r_{τ}}, and that this set is unaltered if we omit all the r_{i}’s that are multiples of r.

Remark 15. Looking at the proof, it is not difficult to see that the same results hold if we replace I_{m} by I_{m} + l · r(m), where l is a positive integer.

References

[1] C. Ballot, Density of prime divisors of linear recurrences. Mem. Amer. Math. Soc. 115 (1995), no. 551.

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

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

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

[5] P. Ribenboim, The Book of Prime Number Records. Second edition. Springer-Verlag, 1989.

[6] E. Roettger, A cubic extension of the Lucas functions. Ph. D. thesis, University of Calgary, Canada, 2009.

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

Received June 5 2014; revised versions received July 18 2014; August 1 2014; August 8 2014. Published in Journal of Integer Sequences, August 12 2014.

Return to Journal of Integer Sequences home page.