On the p-adic Valuations of Sums of Powers of Integers

Gombodorj Bayarmagnai and Sainjargal Delger Department of Mathematics National University of Mongolia Baga Toirog Ulaanbaatar 14200 Mongolia

                    bayarmagnai@num.edu.mn
                      sdelger96@gmail.com

Abstract In this paper we obtain a simple formula for the number of matching p-ary digits of certain terms of Lucas sequences for any odd prime p. Using this formula, we present a simple sufficient condition for the sequence (v_{p}(a_{1}^{n}+a_{2}^{n}+⋯+a_{k}^{n}))_{n≥0} to be unbounded, where a_{1}, a_{2}, …, a_{k} (k ≥ 2) are given integers and v_{p} is the p-adic valuation.

1 Introduction

The p-adic valuations of integer sequences have been objects of interest because of their surprising properties such as k-regularity (Allouche et al. [1], Bell [2], and Murru et al. [6]) and exponent lifting (Birkhoff et al. [3] and Sanna [9]). In the paper we focus on the p-adic valuations of sequences given by sums of powers of integers and differences of terms of Lucas sequences.

Given an integer k ≥ 2 and integers a_{1}, a_{2}, …, a_{k} satisfying |a_{i}| ≥ 2 for each 1 ≤ i ≤ k, let (s_{n})_{n≥1} be the sequence defined by

s_{n} = a_{1}^{n} + a_{2}^{n} + ⋯ + a_{k}^{n}

for each n ≥ 1. For k = 2, the sequence of the p-adic valuations (v_{p}(s_{n}))_{n≥1} is well known (Birkhoff et al. [3]) and in particular, the sequence is unbounded if p divides a term of (s_{n})_{n≥1}, where p is an odd prime and v_{p} is the p-adic valuation. But it is not true in general. The first purpose of this paper is to present a sufficient condition for the unboundedness of the sequence (v_{p}(s_{n}))_{n≥1}, especially for the case k ≥ 3.

Now, we formulate our main result:

Theorem 1. Let p be an odd prime dividing s_{ℓ} for some index ℓ such that ℓ < p. If

∑_{(a_{i},p)=1} q(a_{i})a_{i}^{ℓ} ≢ 0 (mod p)  (1)

then (v_{p}(s_{n}))_{n≥1} is unbounded, where q(a) = \frac{a^{p−1}−1}{p} is the Fermat quotient of p with base a.

Our next purpose is to study the rate of growth in the number of matching p-ary digits of certain terms of Lucas sequences. This will be useful in the proof Theorem 1. More precisely, throughout the paper, a Lucas sequence (U_{n})_{n≥0} is a sequence given by U_{0} = 0, U_{1} = 1, and

U_{n} = aU_{n−1} − bU_{n−2}, n = 2, 3, …,

where a, b are relatively prime integers. We require that (U_{n})_{n≥0} is nondegenerate, that is, b ≠ 0 and the ratio α/β of the two roots α, β of the characteristic polynomial x^{2} − ax + b is not a root of unity. It is well known that the Lucas quotient U_{τ}/p is an integer for any prime p not dividing 2b (Ribenboim [8]), where (\frac{·}{p}) is the Legendre symbol and τ = p − (\frac{a^{2}−4b}{p}). Then our next result is the following.

Theorem 2. Let (U_{n})_{n≥0} be a Lucas sequence, and let D denote the discriminant of its characteristic polynomial. For a prime p not dividing 2b we have

v_{p}(U_{τp^{ℓ}} − pU_{τp^{ℓ−1}}) = \begin{cases}2ℓ + δ + σ + v_{p}(τ), & if b^{2} ≠ 1; \\ 3ℓ + 3σ + v_{p}(D/3) + 1, & if b^{2} = 1, \end{cases}

for ℓ > δ, where δ and σ are the p-adic valuations of b^{p−1} − 1 and U_{τ}/p, respectively.

The theorem is analogous to the results of Lengyel [4, 5] for the sequences of Motzkin numbers, central binomial coefficients and Catalan numbers. Note that σ = 0 if p is a Lucas non-Wieferich prime. Assuming the ABC conjecture, Ribenboim [7] showed that there are infinitely many Lucas non-Wieferich primes.

2 The number of matching digits

In this section we prove Theorem 2. Before that we need some preliminary results stating properties of the subsequence (U_{τp^{ℓ}})_{ℓ≥0}. Finally, we see that the sequence defined by the last nonzero digits of U_{τp^{ℓ}} in base p is constant. This property is key in the proof of Theorem 1.

Lemma 3. If p is a prime not dividing 2b and n is a positive integer divisible by τ then

v_{p}(U_{np^{ℓ+1}}) = v_{p}(U_{np^{ℓ}}) + 1

for each positive integer ℓ.

Proof. Let ρ_{U}(p) be the rank of appearance of p in the sequence (U_{n})_{n≥0}. It is known that p | U_{n} if and only if ρ_{U}(p) | n (see for example, [8, (3.3), p. 12]). Thus τ is divisible by ρ_{U}(p) and hence the formula follows from [9, Corollary 1.6].

We read the p-ary digits of U_{τp^{ℓ}} from left to right and consider the number of matching p-ary digits of U_{τp^{ℓ}} and pU_{τp^{ℓ−1}}, i.e., v_{p}(U_{τp^{ℓ}} − pU_{τp^{ℓ−1}}). All the first ℓ + v_{p}(U_{τ}) digits of the two numbers are zero by Lemma 3, and moreover, the number of matching digits is determined by the p-adic valuation of the difference u_{ℓ} − u_{ℓ−1}, where u_{ℓ} is the p-free part of the term U_{τp^{ℓ}}, i.e.,

u_{ℓ} = p^{−v_{p}(U_{τp^{ℓ}})}U_{τp^{ℓ}}.

Lemma 4. For each odd k ≥ 1 we have

U_{kτp^{ℓ}}/U_{τp^{ℓ}} = D ∑_{i=1}^{(k−1)/2} b^{( \frac{k−1}{2} −i)τp^{ℓ}}U_{iτp^{ℓ}}^{2} + kb^{\frac{k−1}{2} τp^{ℓ}}.

Proof. It is well-known that for all integers n ≥ 0, it holds U_{n} = (α^{n} − β^{n})/(α − β). Hence we have U_{kτp^{ℓ}}/U_{τp^{ℓ}} = ∑_{i=0}^{k−1} α^{iτp^{ℓ}}β^{(k−1−i)τp^{ℓ}} for any integer k ≥ 1. For odd k the latter equals

∑_{i=1}^{(k−1)/2} b^{( \frac{k−1}{2} −i)τp^{ℓ}}(α^{iτp^{ℓ}} − β^{iτp^{ℓ}})^{2}+kb^{\frac{k−1}{2} τp^{ℓ}},

since b = αβ. Thus the lemma follows from this identity and D = (α − β)^{2}.

Lemma 5. For each positive integer ℓ there exists an integer t_{ℓ} such that

\frac{u_{ℓ+1}}{u_{ℓ}} = DU_{τp^{ℓ}}^{2}(pt_{ℓ} + \frac{p^{2} − 1}{24}b^{\frac{p−3}{2} τp^{ℓ}})+b^{\frac{p−1}{2} τp^{ℓ}}.

Proof. For any positive integer ℓ, by Lemma 4, we have

\frac{u_{ℓ+1}}{u_{ℓ}} = \frac{DU_{τp^{ℓ}}^{2}}{p} ( ∑_{k=1}^{(p−1)/2} b^{( \frac{p−1}{2} −k)τp^{ℓ}}(U_{kτp^{ℓ}}/U_{τp^{ℓ}})^{2})+b^{\frac{p−1}{2} τp^{ℓ}}.

We claim that (U_{kτp^{ℓ}}/U_{τp^{ℓ}})^{2} ≡ k^{2}b^{(k−1)τp^{ℓ}} (mod p^{2(ℓ+σ+1)}) for each 1 ≤ k ≤ (p − 1)/2. The claim follows easily from Lemma 4 if k is odd. For even k we have the identity

(U_{kτp^{ℓ}}/U_{kτp^{ℓ}/2})^{2} = DU_{kτp^{ℓ}/2}^{2} + 4b^{kτp^{ℓ}/2},

which, by induction on k, yields the claim. Thus we can conclude from the claim that

∑_{k=1}^{(p−1)/2} b^{( \frac{p−1}{2} −k)τp^{ℓ}}(U_{kτp^{ℓ}}/U_{τp^{ℓ}})^{2} ≡ \frac{p^{3} − p}{24}b^{\frac{p−3}{2} τp^{ℓ}} (mod p^{2(ℓ+σ+1)}),

completing the proof.

We are now ready to prove Theorem 2.

Proof of Theorem 2. The case b^{2} = 1: We claim that b^{\frac{p−1}{2} τ} = 1. If p is not a divisor of D then it is clear since τ is even. Suppose p is a divisor of D. Then τ = p which is odd. If b = −1 then D = a^{2} + 4 and hence p ≡ 1 (mod 4), implying the claim.

From Lemma 5 and the claim we obtain

\frac{u_{ℓ+1} − u_{ℓ}}{u_{ℓ}^{3}} = Dp^{2(ℓ+σ+1)}(pt_{ℓ} + \frac{p^{2} − 1}{24}b^{\frac{p−3}{2} τp^{ℓ}})

for some integer t_{ℓ}. Therefore

v_{p}(u_{ℓ+1} − u_{ℓ}) = 2(ℓ + σ + 1) + v_{p}(D/3)  (2)

for each positive integer ℓ.

The case b^{2} ≠ 1: We claim that b^{τ} is a square residue modulo p. If p is not a divisor of D then the claim is clear since τ is even. Suppose p is a divisor of D. Then τ = p and hence we have

b ≡ \frac{(α^{(τ+1)/2} + β^{(τ+1)/2})^{2}}{(α^{(τ−1)/2} + β^{(τ−1)/2})^{2}} (mod p),

since U_{τ} is divisible by p. Moreover, the right hand side is equal to (U_{τ+1}U_{\frac{τ−1}{2}} (U_{τ−1}U_{\frac{τ+1}{2}} )^{−1})^{2}, showing the claim.

By applying Lemma 3 and Lemma 4 we obtain

v_{p}(u_{ℓ+1} − u_{ℓ}) = v_{p}(b^{\frac{p−1}{2} τp^{ℓ}} − 1)

if ℓ > δ. Since v_{p}(b^{\frac{p−1}{2} τ} − 1) ≠ 0 by the above claim, we have v_{p}(u_{ℓ+1} − u_{ℓ}) = v_{p}(τ) + δ + ℓ when ℓ > δ, completing the proof of Theorem 2.

Example 6. The Fibonacci sequence (F_{n})_{n≥0} is a Lucas sequence with characteristic polynomial x^{2} − x − 1. Since τ = p ± 1 if p^{2} ≡ ±1 (mod 5) and τ = p if p = 5, we have

v_{p}(f_{ℓ+1} − f_{ℓ}) = \begin{cases}2ℓ + 1, & if p = 3; \\ 2ℓ + 3, & if p = 5; \\ 2ℓ + 2v_{p}(F_{τ}), & if p ≥ 7. \end{cases}

Here f_{ℓ} denotes the p-free part of the τp^{ℓ}-th Fibonacci number.

Let û_{ℓ} denote the last nonzero digit of U_{τp^{ℓ}} in base p. Theorem 2 implies that the sequence (û_{ℓ})_{ℓ≥0} is eventually constant since û_{ℓ} ≡ u_{ℓ} (mod p) for each positive integer ℓ.

Lemma 7. The sequence (û_{ℓ})_{ℓ≥0} is constant.

Proof. For our purpose it suffices to show that v_{p}(u_{ℓ+1} − u_{ℓ}) ≥ 1 for any integer ℓ ≥ 0. If b^{2} = 1 then this follows from (1). In the proof of Theorem 2, we have seen that v_{p}(b^{\frac{p−1}{2} τ} −1) = δ + v_{p}(τ) ≥ 1 if b^{2} ≠ 1. Thus, by Lemma 3 and Lemma 5, we obtain

v_{p}(u_{ℓ+1} − u_{ℓ}) ≥ min(v_{p}(DU_{τp^{ℓ}}^{2}/3), v_{p}(b^{\frac{p−1}{2} τp^{ℓ}} − 1)) ≥ min(σ + 1, δ + v_{p}(τ)),

completing the proof.

3 On sums of powers of integers

We begin this section with a key lemma which is a version of the lifting the exponent (LTE) lemma and then use it to prove Theorem 1.

Let a_{1}, a_{2}, …, a_{k} be integers satisfying |a_{i}| ≥ 2 and p ∤ a_{i} for 1 ≤ i ≤ k. For each index i define a sequence q_{n}^{(i)} by the difference q_{n}^{(i)} = a_{i}^{n} − 1 for any integer n ≥ 0. Then the sequence of the quotients (q_{n}^{(i)}/q_{1}^{(i)})_{n≥0} is a Lucas sequence with characteristic polynomial x^{2} − (a_{i} + 1)x + a_{i}.

Lemma 8. Let p be an odd prime. If there exist integers c_{1}, c_{2}, …, c_{k} and ℓ ≥ 0 such that

c_{1}q_{(p−1)p^{ℓ}}^{(1)} + c_{2}q_{(p−1)p^{ℓ}}^{(2)} + ⋯ + c_{k}q_{(p−1)p^{ℓ}}^{(k)} ≡ 0 (mod p^{ℓ+χ+1})  (3)

then (3) holds for all ℓ ≥ 0, where χ is the minimum among all v_{p}(q_{p−1}^{(i)}).

Proof. Denote by χ_{i} (1 ≤ i ≤ k) the exponent v_{p}(q_{p−1}^{(i)}) which is clearly not zero. For the sequence (q_{n}^{(i)}/q_{1}^{(i)})_{n≥0}, we have τ_{i} = p if p | a_{i} − 1 and τ_{i} = p − 1 otherwise.

If τ_{i} = p − 1 then apply Lemma 7 to the sequence (q_{n}^{(i)}/q_{1}^{(i)})_{n≥0}. Then we obtain

(q_{(p−1)p^{n}}^{(i)}/q_{1}^{(i)})/p^{χ_{i}+n−v_{p}(q_{1}^{(i)})} ≡ (q_{p−1}^{(i)}/q_{1}^{(i)})/p^{χ_{i}−v_{p}(q_{1}^{(i)})} (mod p)

for any integer n ≥ 0. This yields that q_{(p−1)p^{n}}^{(i)}/p^{χ_{i}+n} ≡ q_{(p−1)p^{ℓ}}^{(i)}/p^{χ_{i}+ℓ} (mod p) for any n ≥ 0.

If τ_{i} = p then v_{p}(q_{(p−1)τ_{i}}^{(i)}) = 1 + χ_{i}. By applying Lemma 7 to the Lucas sequence

(q_{(p−1)n}^{(i)}/q_{p−1}^{(i)})_{n≥0} we similarly obtain

q_{(p−1)p^{n}}^{(i)}/p^{χ_{i}+n} ≡ q_{(p−1)p^{ℓ}}^{(i)}/p^{χ_{i}+ℓ} (mod p)

for any integer n ≥ 0, since q_{(p−1)p}^{(i)}/p^{χ_{i}+1} ≡ q_{p−1}^{(i)}/p^{χ_{i}} (mod p). Consequently we have

q_{(p−1)p^{n}}^{(i)}/p^{χ+n} ≡ q_{(p−1)p^{ℓ}}^{(i)}/p^{χ+ℓ} (mod p)

for each index i. Substituting these congruences into

c_{1}q_{(p−1)p^{ℓ}}^{(1)}/p^{χ+ℓ} + ⋯ + c_{k}q_{(p−1)p^{ℓ}}^{(k)}/p^{χ+ℓ} ≡ 0 (mod p),

which is equivalent to (3), we complete the proof of the lemma.

Remark 9. Let p be an odd prime. For fixed integers a, b satisfying p ∤ ab and p | a − b, the classical LTE lemma states that v_{p}(a^{n} − b^{n}) = v_{p}(n) + v_{p}(a − b). Hence, for each index i, we have v_{p}(q_{(p−1)p^{ℓ}}^{(i)}) = ℓ + χ_{i}. Thus Lemma 8 does not follow from the LTE lemma since

q_{(p−1)p^{ℓ}}^{(i)}/p^{ℓ+χ} ≢ 0 (mod p) for some index i.

We are now ready to present a proof of Theorem 1.

Proof of Theorem 1. For each a_{i} which is prime to p we set c_{i} = a_{i}^{ℓ} and define a sequence (q_{n}^{(i)})_{n≥1} by q_{n}^{(i)} = a_{i}^{n} − 1 for each integer n ≥ 1. Then the assumption is clearly equivalent to the condition that

∑_{(a_{i},p)=1} c_{i}q_{p−1}^{(i)}/p ≢ 0 (mod p).  (4)

Under this condition we show the existence of an unbounded subsequence of (v_{p}(s_{n}))_{n≥1} by induction. We claim that there is an integer N ≥ 1 such that

v_{p}(s_{N}) > m and N ≡ ℓ (mod p − 1)

for a fixed integer m ≥ 0. Firstly, if m = 0 then we choose N = ℓ which is the base case of our induction. Assume the claim holds for an integer N such that m = v_{p}(s_{N}) > 0. We now show that there is an integer n such that v_{p}(s_{n}) > m and n ≡ ℓ (mod p − 1). For this purpose we consider the set S defined by

S = {s_{n_{t}} | n_{t} = N + φ(p^{m})t, t = 1, 2, …, p},

where φ denotes the Euler’s totient function. It follows from Euler’s theorem and the induction hypothesis that v_{p}(s_{n_{t}}) ≥ m for each t. Suppose each element of S is not divisible by p^{m+1}. Then, by Pigeonhole principle, there are two different elements s_{n_{j}} and s_{n_{j+t}} of S (t ≠ 0) which are congruent modulo p^{m+1}. Hence we obtain

∑_{(a_{i},p)=1} c_{i}q_{tφ(p^{m})}^{(i)}/p^{m} ≡ 0 (mod p)

since N ≡ ℓ (mod p − 1) and j, t are non-zero integers. Clearly, we have

q_{φ(p^{m})t}^{(i)}/p^{m} ≡ tq_{φ(p^{m})}^{(i)}/p^{m} (mod p)

for each index i. Therefore, using these congruences, it follows from Lemma 2 that

∑_{(a_{i},p)=1} c_{i}q_{φ(p)}^{(i)}/p ≡ 0 (mod p),

contradicting (4). Thus S contains an element s_{n_{t}} satisfying v_{p}(s_{n_{t}}) ≥ m+1. Clearly, n_{t} ≡ ℓ (mod p − 1) by the induction hypothesis. This completes the induction step.

Remark 10. Theorem 1 provides a sufficient but not necessary condition: consider the sequence (s_{n})_{n≥1} given by s_{n} = 1 + 2^{n} + 3^{n} for all n ≥ 0. Set p = 7. Then

s_{4} ≡ 2^{4}(2^{p−1} − 1)/p + 3^{4}(3^{p−1} − 1)/p ≡ 0 (mod p),

but the subsequence (v_{p}(s_{4p^{n}}))_{n≥1} is unbounded since v_{p}(s_{4p^{n}}) = n + 2 for each n ≥ 0.

Corollary 11. Let p be a prime divisor of the sequence (s_{n})_{n≥1}. Assume that a_{1}, a_{2}, …, a_{k} and k are not divisibly by p and v_{p}(s_{ℓ}) = 1 for each s_{ℓ} such that 1 ≤ ℓ < p and p | s_{ℓ}. Then the sequence (v_{p}(s_{n}))_{n≥1} is bounded by 1 if and only if (1) does not hold.

Proof. If (v_{p}(s_{n}))_{n≥1} is bounded then Theorem 1 implies that (1) does not hold. Suppose (1) does not hold. For any integers n, j ≥ 1 we have

s_{n+φ(p)j} = ∑ a_{i}^{n}(pq(a_{i}) + 1)^{j}

and hence

s_{n+φ(p)j} ≡ s_{n} (mod p^{2}) ⟺ ∑_{i=1}^{k} a_{i}^{n}q(a_{i}) ≡ 0 (mod p).  (5)

If v_{p}(s_{n}) ≠ 0 then v_{p}(s_{ℓ}) ≠ 0, where ℓ is an integer satisfying n = ℓ+φ(p)j with 0 < ℓ < φ(p). Therefore (5) implies that v_{p}(s_{n}) = 1 and thus the sequence (v_{p}(s_{n}))_{n≥1} is bounded by 1.

Example 12. Let a_{1} = 6, a_{2} = 13, a_{3} = 97 and p = 19. Clearly, if ℓ < p and p | s_{ℓ} then ℓ = 2. Moreover, v_{p}(s_{2}) = 1 and the sum

a_{1}^{2}(a_{1}^{p−1} − 1)/p + a_{2}^{2}(a_{2}^{p−1} − 1)/p + a_{3}^{2}(a_{3}^{p−1} − 1)/p

is divisible by p. Thus, by Corollary 11, each term of the sequence (s_{n})_{n≥1} is not divisible by p^{2}.

4 Acknowledgment

The authors would like to thank the referee for carefully reading the paper. The research has received funding from the National University of Mongolia under grant agreement P2020-3943.

References

[1] J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992), 163–197.

[2] J. P. Bell, p-adic valuations and k-regular sequences, Discrete Math. 307 (2007), 3070– 3075.

[3] G. D. Birkhoff and H. S. Vandiver, On the integral divisors of a^{n} − b^{n}, Ann. of Math. 5 (1904), 173–180.

[4] T. Lengyel, Exact p-adic orders for differences of Motzkin numbers, Int. J. Number Theory 10 (2014), 653–667.

[5] T. Lengyel, On divisibility properties of some differences of the central binomial coefficients and catalan numbers, Integers 13 (2013), A10.

[6] N. Murru and C. Sanna, On the k-regularity of the k-adic valuation of Lucas sequences, J. Théor. Nombres Bordeaux 30 (2018), 227–237.

[7] P. Ribenboim, On square factors of terms of binary recurring sequences and the ABC conjecture, Publ. Math. Debrecen 59 (2001), 459–469.

[8] P. Ribenboim, My Numbers, My Friends, Springer-Verlag, 2002.

[9] C. Sanna, The p-adic valuation of Lucas sequences, Fibonacci Quart. 54 (2016), 118–124.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B50.

Keywords: sums of powers of integers, p-adic valuation, Lucas sequence.

Received July 11 2022; revised versions received August 5 2022; August 31 2022; September 13 2022. Published in Journal of Integer Sequences, October 7 2022.

Return to Journal of Integer Sequences home page.