On a Congruence Modulo n^{3} Involving Two Consecutive Sums of Powers

Romeo Meštrović Maritime Faculty University of Montenegro 85330 Kotor Montenegro

                      romeo@ac.me

Abstract

For various positive integers k, the sums of kth powers of the first n positive integers, S_{k}(n) := 1^{k} +2^{k} +⋯+n^{k}, are some of the most popular sums in all of mathematics. In this note we prove a congruence modulo n^{3} involving two consecutive sums S_{2k}(n) and S_{2k+1}(n). This congruence allows us to establish an equivalent formulation of Giuga’s conjecture. Moreover, if k is even and n ≥ 5 is a prime such that n − 1 ∤ 2k − 2, then this congruence is satisfied modulo n^{4}. This suggests a conjecture about when a prime can be a Wolstenholme prime. We also propose several Giuga-Agoh-like conjectures. Further, we establish two congruences modulo n^{3} for two binomial-type sums involving sums of powers S_{2i}(n) with i = 0, 1, …, k. Finally, we obtain an extension of a result of Carlitz-von Staudt for odd power sums.

1 Introduction and basic results

The sum of powers of integers ∑_{i=1}^{n} i^{k} is a well-studied problem in mathematics (see, e.g., [9, 40]). Finding formulas for these sums has interested mathematicians for more than 300 years since the time of Jakob Bernoulli (1654–1705). Several methods were used to find the sum S_{k}(n) (see, for example, Vakil [49]). These lead to numerous recurrence relations. For a nice account of sums of powers, see Edwards [15]. For simplicity, here as always in the sequel, for all integers k ≥ 1 and n ≥ 2 we write

S_{k}(n) := ∑_{i=1}^{n−1} i^{k} = 1^{k} + 2^{k} + 3^{k} + ⋯ + (n − 1)^{k}.

The study of these sums led Jakob Bernoulli to develop numbers later named in his honor. Namely, the celebrated Bernoulli formula (sometimes called Faulhaber’s formula) gives the sum S_{k}(n) explicitly as (see, e.g., Beardon [4])

S_{k}(n) = \frac{1}{k + 1} ∑_{i=0}^{k} \binom{k + 1}{i}n^{k+1−i}B_{i},  (1)

where B_{i} (i = 0, 1, 2, …) are the Bernoulli numbers defined by the generating function

∑_{i=0}^{∞} B_{i} \frac{x^{i}}{i!} = \frac{x}{e^{x} − 1}.

It is easy to find the values B_{0} = 1, B_{1} = −\frac{1}{2}, B_{2} = \frac{1}{6}, B_{4} = −\frac{1}{30}, and B_{i} = 0 for odd i ≥ 3. Furthermore, (−1)^{i−1}B_{2i} > 0 for all i ≥ 1. These and many other properties can be found, for instance, in [23]. Several generalizations of the formula (1) were established by Z.-H. Sun ([46, Thm. 2.1] and [47]) and Z.-W. Sun [48].

By the well-known Pascal’s identity proven by Pascal in 1654 (see, e.g., [29]), we have

∑_{i=0}^{k−1} \binom{k}{i}S_{i}(n + 1) = (n + 1)^{k} − 1.  (2)

Recall also that the formula (2) is also presented in Bernoulli’s Ars Conjectandi [6], (also see [19, pp. 269–270]) published posthumously in 1713.

On the other hand, divisibility properties of the sums S_{k}(n) were investigated by many authors [13, 27, 30, 42]. For example, in 2003 Damianou and Schumer [13, Thm. 1, p. 221 and Thm. 2, p. 222] proved, respectively:

(1) if k is odd, then n divides S_{k}(n) if and only if n is incogruent to 2 modulo 4;

(2) if k is even, then n divides S_{k}(n) if and only if n is not divisible by any prime p such that p | D_{k}, where D_{k} is the denominator of the kth Bernoulli number B_{k}.

Denominators of Bernoulli numbers B_{k} (k = 0, 1, 2, …) are given as the sequence \underline{A027642} in [41] (cf. also its subsequence \underline{A002445} consisting of the terms with even indices k).

Motivated by the recurrence formula for S_{k}(n) recently obtained in [34, Corollary 1.7], in this note we prove the following basic result.

Theorem 1. Let k and n be positive integers. Then for each k ≥ 2

2S_{2k+1}(n) − (2k + 1)nS_{2k}(n) ≡ \begin{cases}0 (mod n^{3}), & if k is even or n is odd \\ & or n ≡ 0 (mod 4); \\ \frac{n^{3}}{2} (mod n^{3}), & if k is odd and n ≡ 2 (mod 4). \end{cases} (3)

Furthermore,

2S_{3}(n) − 3nS_{2}(n) ≡ \begin{cases}0 (mod n^{3}), & if n is odd; \\ \frac{n^{3}}{2} (mod n^{3}), & if n is even. \end{cases}  (4)

In particular, for all k ≥ 1 and n ≥ 1, we have

2S_{2k+1}(n) ≡ (2k + 1)nS_{2k}(n) (mod n^{2}),  (5)

and for all k ≥ 1 and n ≢ 2 (mod 4)

2S_{2k+1}(n) ≡ (2k + 1)nS_{2k}(n) (mod n^{3}).  (6)

Combining the congruence (5) and the “even case” (2) of a result of Damianou and Schumer [13, Thm. 1, p. 221 and Thm. 2, p. 222] mentioned above, we obtain the following “odd” extension of their result.

Corollary 2. If k is an odd positive integer and n a positive integer such that n is not divisible by any prime p such that p | D_{k−1}, where D_{k−1} is the denominator of the (k − 1)th Bernoulli number B_{k−1}, then n^{2} divides 2S_{k}(n).

Conversely, if k is an odd positive integer and n a positive integer relatively prime to k such that n^{2} divides 2S_{k}(n), then n is not divisible by any prime p such that p | D_{k−1}, where D_{k−1} is the denominator of the (k − 1)th Bernoulli number B_{k−1}.

The paper is organized as follows. Some applications of Theorem 1 are presented in the following section. In Subsection 2.1 we give three particular cases of the congruence (3) of Theorem 1 (Corollary 3). One of these congruences immediately yields a reformulation of Giuga’s conjecture in terms of the divisibility of 2S_{n}(n) + n^{2} by n^{3} (Proposition 4).

In the next subsection we establish the fact that the congruence (6) holds modulo n^{4} whenever n ≥ 5 is a prime such that n − 1 ∤ 2k − 2 ((14) of Proposition 7). Motivated by some particular cases of this congruence and related computations in Mathematica 8, we propose several Giuga-Agoh-like conjectures. In particular, Conjecture 12 characterizes Wolstenholme primes as positive integers n such that S_{n−2}(n) ≡ 0 (mod n^{3}).

In Subsection 2.3 we establish two congruences modulo n^{3} for two binomial sums involving sums of powers S_{2i}(n) with i = 0, 1, …, k (Proposition 17).

Combining the congruence (5) of Theorem 1 with the Carlitz-von Staudt result for determining S_{2k}(n) (mod n) (Theorem 20), in the last subsection of Section 2, we extend this result modulo n^{2} for power sums S_{2k+1}(n) (Theorem 23).

Recall that Erdős-Moser Diophantine equation is the equation of the form

1^{k} + 2^{k} + ⋯ + (m − 2)^{k} + (m − 1)^{k} = m^{k}  (7)

where m ≥ 2 and k ≥ 2 are positive integers. Notice that (m, k) = (3, 1) is the only solution for k = 1. In letter to Leo Moser around 1950, Paul Erdős conjectured that such solutions of the above equation do not exist (see [39]). Using remarkably elementary methods, Moser [39] showed in 1953 that if (m, k) is a solution of (7) with m ≥ 2 and k ≥ 2, then m > 10^{10^{6}} and k is even. We believe that Theorem 23 can be useful for study some Erdős-Moser-like Diophantine equations with odd k (see Remark 26).

Proofs of all our results are given in Section 3.

2 Applications of Theorem 1

2.1 Variations of Giuga-Agoh’s conjecture

Taking k = (n − 1)/2 if n is odd, k = n/2 if n is even and k = (n − 2)/2 if n is even into (3) of Theorem 1 we obtain respectively the following three congruences.

Corollary 3. If n is an odd positive integer, then

2S_{n}(n) ≡ n^{2}S_{n−1}(n) (mod n^{3}).  (8)

If n is even, then

2S_{n+1}(n) − n(n + 1)S_{n}(n) ≡ \begin{cases}0 (mod n^{3}), & if n ≡ 0 (mod 4); \\ \frac{n^{3}}{2} (mod n^{3}), & if n ≡ 2 (mod 4) \end{cases}  (9)

and

2S_{n−1}(n) ≡ n(n − 1)S_{n−2}(n) (mod n^{3}).  (10)

In particular, for each even n we have

S_{n−1}(n) ≡ \begin{cases}0 (mod n), & if n ≡ 0 (mod 4); \\ \frac{n}{2} (mod n), & if n ≡ 2 (mod 4). \end{cases}  (11)

Notice that if n is any prime, then by Fermat’s little theorem we have S_{n−1}(n) ≡ −1 (mod n). In 1950 Giuga [18] conjectured that a positive integer n ≥ 2 is a prime if and only if S_{n−1}(n) ≡ −1 (mod n). This conjecture is related to the sequences \underline{A029875}, \underline{A007850}, \underline{A198391}, \underline{A199767}, \underline{A226365} and \underline{A029876} in [41]. The following proposition provides an equivalent formulation of Giuga’s conjecture.

Proposition 4. The following conjectures are equivalent:

(i) A positive integer n ≥ 3 is a prime if and only if

S_{n−1}(n) ≡ −1 (mod n).  (12)

(ii) A positive integer n ≥ 3 is a prime if and only if

2S_{n}(n) ≡ −n^{2} (mod n^{3}).  (13)

The above conjecture (ii) is related to the sequence \underline{A219540} in [41]. Since by the congruence (11), S_{n−1}(n) ≢ −1 (mod n) for each even n ≥ 4, without loss of generality Giuga’s conjecture may be restricted to the set of odd positive integers. In view of this fact and the fact that by (8), n^{2} | S_{n}(n) for each odd n, Proposition 4 yields the following equivalent formulation of Giuga’s conjecture.

Conjecture 5 (Giuga’s conjecture). An odd integer n ≥ 3 is a prime if and only if

\frac{2S_{n}(n)}{n^{2}} ≡ −1 (mod n).

Remark 6. It is known that S_{n−1}(n) ≡ −1 (mod n) if and only if for each prime divisor p of n, (p−1) | (n/p−1) and p | (n/p−1) (see [18], [7, Thm. 1]). Therefore, any counterexample to Giuga’s conjecture must be squarefree. Giuga [18] showed that there are no exceptions to the conjecture up to 10^{1000}. In 1985 Bedocchi [5] improved this bound to n > 10^{1700}. Finally, in 1996 Borwein et. al. raised the bound to n > 10^{13887}. Recently, Luca, Pomerance, and Shparlinski [28] proved that for any real number x, the number of counterexamples to Giuga’s conjecture G(x) := #{n < x : n is composite and S_{n−1}(n) ≡ −1 (mod n)} satisfies the estimate G(x) = o(\sqrt{x}) as x → ∞.

Independently, in 1990 Agoh [1] (published in 1995; see also [8] and the sequence \underline{A046094} in [41]) conjectured that a positive integer n ≥ 2 is a prime if and only if nB_{n−1} ≡ −1 (mod n). Note that the denominator of the number nB_{n−1} can be greater than 1, but since by the von Staudt-Clausen theorem (1840) (see, e.g., [22, Thm. 118]; cf. the equality (25) given below), the denominator of any Bernoulli number B_{2k} is squarefree, it follows that the denominator of nB_{n−1} is invertible modulo n. In 1996 it was reported by Agoh [7] that his conjecture is equivalent to Giuga’s conjecture, and hence the name “Giuga-Agoh conjecture” found in the literature. It was pointed out in [7] that this can be seen from the Bernoulli formula (1) after some analysis involving the von Staudt-Clausen theorem. The equivalence of both conjectures is proved in detail in 2002 by Kellner [24, Satz 3.1.3, Section 3.1, p. 97] (also see [25, Thm. 2.3]).

Quite recently, Grau and Oller-Marcén [20, Corollary 4] proved that an integer n is a counterexample to Giuga’s conjecture if and only if it is both a Carmichael and a Giuga number (for definitions and more information on Carmichael numbers see Alford et al. [2] and Banks and Pomerance [3], and for Giuga numbers see Borwein et al. [7], Borwein and Wong [8], and Wong [50, Chapter 2]; also see the sequences \underline{A007850} and \underline{A002997} in [41]). Furthermore, several open problems concerning Giuga’s conjecture can be found in [8, E Open Problems].

2.2 The congruence (3) holds modulo n^{4} for a prime n ≥ 5

The following result shows that for each prime n ≥ 5 the first congruence of (3) also holds modulo n^{4}.

Proposition 7. Let p ≥ 5 be a prime and let k ≥ 2 be a positive integer such that p − 1 ∤ 2k − 2. Then

2S_{2k+1}(p) ≡ (2k + 1)pS_{2k}(p) (mod p^{4}).  (14)

Furthermore, if p − 1 ∤ 2k, then

S_{2k−1}(p) ≡ 0 (mod p^{2}).  (15)

As a consequence of Proposition 7, we obtain the following “supercongruence” which generalizes Lemma 2.4 in [32].

Corollary 8. Let p ≥ 5 be a prime and let k be a positive integer such that k ≤ (p^{4}−p^{3}−4)/2 and p − 1 ∤ 2k + 2. Then

2R_{2k−1}(p) ≡ (1 − 2k)pR_{2k}(p) (mod p^{4})  (16)

where

R_{s}(p) := ∑_{i=1}^{p−1} \frac{1}{i^{s}} , s = 1, 2, ….

Remark 9. Z.-H. Sun [45, Section 5, Thm. 5.1] in terms of Bernoulli numbers explicitly determined ∑_{i=1}^{p−1}(1/i^{k}) (mod p^{3}) for each prime p ≥ 5 and k = 1, 2, …, p − 1. In particular, substituting the second congruence of Theorem 5.1(a) in [45] (with 2k instead of even k) into (14), we immediately obtain the following “supercongruence”:

R_{2k−1}(p) ≡ \frac{k(1 − 2k)}{2} (\frac{B_{2p−2−2k}}{p − 1 − k} − 4\frac{B_{p−1−2k}}{p − 1 − 2k} ) p^{2} (mod p^{4})

for all primes p ≥ 7 and k = 1, …, (p − 5)/2.

By [45, (5.1) on p. 206],

S_{2k}(p) ≡ \frac{p}{3}(3B_{2k} + k(2k − 1)p^{2}B_{2k−2}) (mod p^{3}),  (17)

which, inserting into (14), gives

S_{2k+1}(p) ≡ \frac{2k + 1}{2}p^{2}B_{2k} (mod p^{4})  (18)

for all primes p ≥ 5 and positive integers k ≥ 2 such that p − 1 ∤ 2k − 2. Moreover, (14) with 2k = p − 1 ≥ 4 (i.e., p ≥ 5) directly gives

S_{p}(p) ≡ \frac{p^{2}}{2} S_{p−1}(p) (mod p^{4}).

Taking 2k + 1 = p into (18), we find that

S_{p}(p) ≡ \frac{p^{3}}{2} B_{p−1} (mod p^{4}),

which reducing modulo p^{3}, and using the congruence pB_{p−1} ≡ −1 (mod p), yields 2S_{p}(p) ≡ −p^{2} (mod p^{3}). This is actually the congruence (13) of Proposition 4 with a prime n = p ≥ 5.

Comparing the above two congruences gives S_{p−1}(p) ≡ pB_{p−1} (mod p^{2}) for each prime p ≥ 5. However, the congruence (17) with 2k = p − 1 implies that for all primes p ≥ 5

S_{p−1}(p) ≡ pB_{p−1} (mod p^{3}).

Remark 10. A computation shows that each of the congruences

S_{n}(n) ≡ \frac{n^{3}}{2} B_{n−1} (mod n^{4})

and

S_{n−1}(n) ≡ nB_{n−1} (mod n^{3})

is also satisfied for numerous odd composite positive integers n. However, we propose the following conjecture.

Conjecture 11. Each of the congruences

S_{n}(n) ≡ \frac{n^{3}}{2} B_{n−1} (mod n^{5}),

S_{n−1}(n) ≡ nB_{n−1} (mod n^{4})

is satisfied for none integer n ≥ 2.

Similarly, taking k = (p − 3)/2 into (18) for each prime p ≥ 5 we get

S_{p−2}(p) ≡ \frac{(p − 2)p^{2}}{2} B_{p−3} (mod p^{4}).  (19)

Therefore, p^{3} | S_{p−2}(p) if and only if the numerator of the Bernoulli number B_{p−3} is divisible by p, and such a prime is said to be Wolstenholme prime (see, e.g., [33, Section 7]). Numerators of Bernoulli numbers B_{k} (k = 0, 1, 2, …) are given as the sequence \underline{A027641} in [41] (cf. also its subsequence \underline{A000367} consisting of the terms with even indices k). The only two known such primes are 16843 and 2124679, and by a result of McIntosh and Roettger from [31], these primes are the only two Wolstenholme primes less than 10^{9}. Wolstenholme primes are given as the sequence \underline{A088164} which is a subsequence of irregular primes \underline{A000928} in [41] (cf. the sequence \underline{A177783}). In view of the above congruence, and our computation via Mathematica 8 up to n = 20000 we have the following two conjectures.

Conjecture 12. A positive integer n ≥ 2 is a Wolstenholme prime if and only if

S_{n−2}(n) ≡ 0 (mod n^{3}).

Conjecture 13. The congruence

S_{n−2}(n) ≡ 0 (mod n^{4})

is satisfied for none integer n ≥ 2.

Remark 14. Quite recently, inspired by Giuga’s conjecture, Grau, Luca, and Oller-Marcén [21] studied the odd positive integers n satisfying the congruence

S_{(n−1)/2}(n) ≡ 0 (mod n).

Grau et al. [21, Section 2, Proposition 2.1] observed that this congruence is satisfied for each odd prime n and for each odd positive integer n ≡ 3 (mod 4). Notice that if n = 4k + 3 with k ≥ 0, then the first part of the congruence (3) yields

2S_{(n−1)/2}(n) ≡ \frac{(n − 1)n}{2}S_{(n−3)/2}(n) (mod n^{3})

which by the congruence (14) holds modulo n^{4} for each prime n ≥ 7 such that n ≡ 3 (mod 4). Multiplying the above congruence by 2 and reducing the modulus, immediately gives

4S_{(n−1)/2}(n) ≡ −nS_{(n−3)/2}(n) (mod n^{2}).

The above congruence shows that S_{(n−1)/2}(n) ≡ 0 (mod n^{2}) for some n ≡ 3 (mod 4) if and only if S_{(n−3)/2}(n) ≡ 0 (mod n). Furthermore, reducing the congruence (18) with k = (p − 3)/4 where p ≥ 7 is a prime such that p ≡ 3 (mod 4) gives

S_{(p−1)/2}(p) ≡ −\frac{p^{2}}{4} B_{(p−3)/2} (mod p^{3}),  (20)

whence it follows that for such a prime p, S_{(p−1)/2}(p) ≡ 0 (mod p^{2}).

On the other hand, if n ≡ 1 (mod 4), that is n = 4k + 1 with k ≥ 1, the first part of the congruence (3) yields

2S_{(n+1)/2}(n) ≡ \frac{(n + 1)n}{2}S_{(n−1)/2}(n) (mod n^{3})

which by the congruence (14) holds modulo n^{4} for each prime n ≡ 1 (mod 4). Multiplying the above congruence by 2 and reducing the modulus, immediately gives

4S_{(n+1)/2}(n) ≡ nS_{(n−1)/2}(n) (mod n^{2}).

The above congruence shows that S_{(n−1)/2}(n) ≡ 0 (mod n) for some n ≡ 1 (mod 4) if and only if S_{(n+1)/2}(n) ≡ 0 (mod n^{2}). For example, by [21, Proposition 2.3] (cf. Corollary 24 given below) both previous congruences are satisfied for every odd prime power n = p^{2s+1} with any prime p ≡ 1 (mod 4) and a positive integer s. Moreover, reducing the congruence (17) with k = (p − 1)/4 where p ≥ 5 is a prime such that p ≡ 1 (mod 4) gives

S_{(p−1)/2}(p) ≡ pB_{(p−1)/2} (mod p^{2}).  (21)

The congruence (21) shows that S_{(p−1)/2}(p) ≡ 0 (mod p^{2}) whenever p ≡ 1 (mod 4) is an irregular prime for which B_{(p−1)/2} ≡ 0 (mod p). To see that the converse is not true, consider the composite number n = 3737 = 37 · 101 satisfying S_{(n−1)/2}(n) ≡ 0 (mod n^{2}) (this is the only such a composite number less than 16000).

Nevertheless, in view of the congruences (20) and using arguments similar to those preceding Conjecture 12 (including a computation up to n = 20000), we have the following conjecture.

Conjecture 15. An odd positive integer n ≥ 3 such that n ≡ 3 (mod 4) satisfies the congruence

S_{(n−1)/2}(n) ≡ 0 (mod n^{3})

if and only if n is an irregular prime for which B_{(n−3)/2} ≡ 0 (mod n).

We also propose the following conjecture.

Conjecture 16. The congruence

S_{(n−1)/2}(n) ≡ 0 (mod n^{3})

is satisfied for none odd positive integer n ≥ 5 such that n ≡ 1 (mod 4).

2.3 Two congruences modulo n^{3} involving power sums S_{k}(n)

Combining the congruences of Theorem 1 with Pascal’s identity, we can arrive to the following congruences.

Proposition 17. Let k and n be positive integers. Then

2 ∑_{i=0}^{k}(1 + n(k + 1 − i))\binom{2k + 2}{2i}S_{2i}(n) ≡ −2 (mod n^{3})  (22)

and

2 ∑_{i=0}^{k} (\binom{2k + 2}{2i} + n(k + 1)\binom{2k + 1}{2i}) S_{2i}(n) ≡ −2 (mod n^{3}).  (23)

Remark 18. Clearly, if n is odd, then both congruences (22) and (23) remain also valid after dividing by 2. However, a computation in Mathematica 8 for small values k and even n suggests that this would be true for each k and even n, and so we have

Conjecture 19. The congruence

∑_{i=0}^{k}(1 + n(k + 1 − i))\binom{2k + 2}{2i}S_{2i}(n) ≡ −1 (mod n^{3})

is satisfied for all k ≥ 1 and even n.

2.4 An extension of Carlitz-von Staudt result for odd power sums

The following congruence is known as a Carlitz-von Staudt’s result [10] in 1961 (for an easier proof see [37, Thm. 3]).

Theorem 20. ([10], [37, Thm. 3]) Let k and n > 1 be positive integers. Then

S_{k}(n) ≡ \begin{cases}0 (mod \frac{(n−1)n}{2}), & if k is odd; \\ − ∑_{(p−1)|k,p|n} \frac{n}{p} (mod n), & if k is even, \end{cases}  (24)

where the summation is taken over all primes p such that (p − 1) | k and p | n.

Remark 21. It is easy to show the first (“odd”) part of Theorem 20 (see, e.g., [37, Proof of Theorem 3] or [30, Proposition 1]) whose proof is a modification of Lengyel’s arguments in [27]. Recall also that the classical theorem of Faulhaber ([16]; also see [4, 14, 26]) states that every sum S_{2k−1}(n) (of odd power) can be expressed as a polynomial in the triangular number T_{n−1} := (n − 1)n/2 \underline{A000217} (cf. the sequences \underline{A079618} and \underline{A064538} in [41]). For even powers, it has been shown that the sum S_{2k}(n) is a polynomial in the triangular number T_{n−1} multiplied by a linear factor in n (see, e.g., [26]). Quite recently, Dzhumadil’daev and Yeliussizov [14] established an analog of Faulhaber’s theorem for a power sum of binomial coefficients. Remark 22. The second part of the congruence (24) in Theorem 20 can be proved using the famous von Staudt-Clausen theorem (given below) discovered without proof by Clausen [12] in 1840, and independently by von Staudt in 1840 [43]; for alternative proofs, see, e.g., Carlitz [10], Moree [35] or Moree [37, Thm. 3]. This also follows from Chowla’s proof of the von Staudt-Clausen theorem given in [11]. Namely, Chowla proved that the difference

\frac{S_{2k}(n + 1)}{n} − B_{2k}

is an integer for all positive integers k and n. This together with the facts that S_{2k}(n + 1) ≡ S_{2k}(n) (mod n) and that by the von Staudt-Clausen theorem,

B_{2k} = A_{2k} − ∑_{{(p−1)|2k \atop p prime}} \frac{1}{p},  (25)

where A_{2k} is an integer, immediately gives the second part of the congruence (24). This theorem is related to the sequences \underline{A000146} in [41] (cf. \underline{A165908} and \underline{A027762} in [41]). Recall also that in many places, the von Staudt-Clausen theorem is stated in the following equivalent statement (see, e.g., [44, page 153]):

pB_{2k} ≡ \begin{cases}0 (mod p), & if p − 1 ∤ 2k; \\ −1 (mod p), & if p − 1 | 2k, \end{cases}

where p is a prime and k a positive integer.

Combining the congruence (5) in Theorem 1 with the second (“even”) part of the congruence (24), we immediately obtain an improvement of its first (“odd”) part as follows.

Theorem 23. Let Let k and n be positive integers. Then

2S_{2k+1}(n) ≡ −(2k + 1)n ∑_{(p−1)|2k,p|n} \frac{n}{p} (mod n^{2}),  (26)

where the summation is taken over all primes p such that p − 1 | k and p | n.

In particular, taking n = p^{s} and k = (p^{s} − 1)/4 into (26) where p is an odd prime p and s ≥ 1 such that p^{s} ≡ 1 (mod 4), we immediately obtain an analogue of Proposition 2.3 in a recent paper [21].

Corollary 24. Let p be an odd prime. Then

S_{(p^{s}+1)/2}(p^{s}) ≡ \begin{cases}0 (mod p^{2s}), & if p ≡ 1 (mod 4) and s ≥ 1 is odd; \\ −\frac{p^{2s−1}}{4} (mod p^{2s}), & if s ≥ 2 is even. \end{cases}

Finally, comparing (24), (25) and (26), we immediately obtain an “odd” extension of a result due to Kellner [25, Thm. 1.2] in 2004 (the congruence (27) given below).

Corollary 25. Let k and n be positive integers. Then

S_{2k}(n) ≡ nB_{2k} (mod n) (Kellner [20])  (27)

and

2S_{2k+1}(n) ≡ (2k + 1)n^{2}B_{2k} (mod n^{2}).  (28)

Remark 26. Notice also that Theorem 20 plays a key role in a recent study ([17, 35, 37, 38]) of the Erdős-Moser Diophantine equation given by (7). As noticed in Introduction, in 1953 Moser [39] showed that if (m, k) is a solution of the equation (7) with m ≥ 2 and k ≥ 2, then m > 10^{10^{6}} and k is even. Recently, using Theorem 20, Moree [37, Thm. 4] improved the bound on m to 1.485 · 10^{9321155}. That Theorem 20 can be used to reprove Moser’s result was first observed in 1996 by Moree [36], where it played a key role in the study of the more general equation

1^{k} + 2^{k} + ⋯ + (m − 2)^{k} + (m − 1)^{k} = am^{k}  (29)

where a is a given positive integer. Moree [36] generalized Erdős-Moser conjecture in the sense that the only solution of the “generalized” Erdős-Moser Diophantine equation (29) is the trivial solution 1 + 2 + ⋯ + 2a = a(2a + 1). Notice also that Moree [36, Proposition 9] proved that in any solution of the equation (29), m is odd. Nevertheless, motivated by the Moser’s technique [37, proof of Theorem 3] previously mentioned, to study (7), we believe that Theorem 23 would be applicable in investigations of some other Erdős-Moser type Diophantine equations with odd k.

3 Proofs of Theorem 1, Corollaries 2, 8, Propositions 4, 7 and 17

Proof of Theorem 1. If k ≥ 1 then by the binomial formula, for each i = 1, 2, …, n − 1 we have

\begin{matrix}2(i^{2k+1} + (n − i)^{2k+1}) − (2k + 1)n(i^{2k} + (n − i)^{2k}) \\ ≡ & 2 (i^{2k+1} − i^{2k+1}) + \binom{2k + 1}{1}ni^{2k} − \binom{2k + 1}{2}n^{2}i^{2k−1}) \\ − (2k + 1)n (i^{2k} + i^{2k} − \binom{2k}{1}ni^{2k−1}) (mod n^{3}) \\ = & 2(2k + 1)ni^{2k} − 2(2k + 1)kn^{2}i^{2k−1} − 2(2k + 1)ni^{2k} + 2(2k + 1)kn^{2}i^{2k−1} \\ = & 0 (mod n^{3}). \end{matrix}  (30)

If k ≥ 3 and n is odd then after summation of (30) over i = 1, 2, …, (n − 1)/2 we obtain

2 ∑_{i=1}^{n−1} i^{2k+1} − (2k + 1)n ∑_{i=1}^{n−1} i^{2k} ≡ 0 (mod n^{3}).  (31)

If k ≥ 2 and n is even then after summation of (30) over i = 1, 2, …, n/2 we get

2 ∑_{i=1}^{n−1} i^{2k+1} + 2 (\frac{n}{2})^{2k+1} − (2k + 1)n ∑_{i=1}^{n−1} i^{2k} − (2k + 1)n (\frac{n}{2})^{2k} ≡ 0 (mod n^{3}),

or equivalently,

2S_{2k+1} − (2k + 1)nS_{2k} ≡ \frac{kn^{2k+1}}{2^{2k−1}} = \frac{n^{3}}{2} · k · (\frac{n}{2})^{2k−2} (mod n^{3}).  (32)

Since for even n

\frac{n^{3}}{2} · k · (\frac{n}{2})^{2k−2} ≡ \begin{cases}0 (mod n^{3}), & if k is even or n ≡ 0 (mod 4); \\ \frac{n^{3}}{2} (mod n^{3}), & if k is odd and n ≡ 2 (mod 4), \end{cases}

this together with (32) and (31) yields both congruences of (3) in Theorem 1. Finally, for k = 1 we have

2S_{3}(n) − 3nS_{2}(n) = \frac{n^{3}}{2} · (1 − n) ≡ \begin{cases}0 (mod n^{3}), & if n is odd; \\ \frac{n^{3}}{2} (mod n^{3}), & if n is even. \end{cases}

This completes the proof.

Proof of Corollary 2. Both assertions follow immediately from the congruence (5) and a result of Damianou and Schumer [13, Thm. 2, p. 222] which asserts that if k is even, then n divides S_{k}(n) if and only if n is not divisible by any prime p such that p | D_{k}, where D_{k} is the denominator of the kth Bernoulli number B_{k}.

Proof of Proposition 4. Proof of (i) ⇒ (ii). Suppose that Giuga’s conjecture is true. Then if n is an odd positive integer satisfying the congruence (13) of Proposition 4, using this and (8) of Corollary 3, we find that

n^{2}S_{n−1}(n) ≡ 2S_{n}(n) ≡ −n^{2} (mod n^{3}),

whence we have

S_{n−1}(n) ≡ −1 (mod n).

By Giuga’s conjecture, the above congruence implies that n is a prime.

If n ≥ 4 is an even positive integer, then the congruence (11) shows that S_{n−1}(n) ≢ −1 (mod n). We will show that for such a n, 2S_{n}(n) ≢ −n^{2} (mod n^{3}). Take n = 2^{s}(2l − 1), where s and l are positive integers. Since for i = 1, 2, … we have (2i)^{n} ≡ 0 (mod 2^{n}), this together with the inequality 2^{2^{s}} ≥ 2^{s+1} yields (2i)^{n} ≡ 0 (mod 2^{s+1}). Therefore, we obtain

2S_{n}(n) ≡ 2 ∑_{{1≤j≤n−1 \atop j odd}} j^{n} (mod 2^{s+1}).

By Euler’s theorem, for each odd j we have

j^{n} = j^{2^{s}(2l−1)} = (j^{2^{s}})^{2l−1} = (j^{φ(2^{s+1})})^{2l−1} ≡ 1 (mod 2^{s+1}) ≡ 1 (mod 2^{s}),

where φ(m) is Euler’s totient function. Substituting this into the above congruence, we get

2S_{n}(n) ≡ n = 2^{s}(2l − 1) ≢ 0 (mod 2^{s+1}).

Now, if we suppose that 2S_{n}(n) ≡ −n^{2} (mod n^{3}), then must be 2S_{n}(n) ≡ 0 (mod n^{2}), and so, 2S_{n}(n) ≡ 0 (mod 2^{2s})≡ 0 (mod 2^{s+1}). This contradicts the above congruence, and the implication (i) ⇒ (ii) is proved.

Proof of (ii) ⇒ (i). Now suppose that Conjecture (ii) of Proposition 4 is true. Then if n is an odd positive integer satisfying the congruence (12), multiplying this by n^{2} and using (8) of Corollary 3, we find that

2S_{n}(n) ≡ n^{2}S_{n−1}(n) ≡ −n^{2} (mod n^{3}),

which implies that

2S_{n}(n) ≡ −n^{2} (mod n^{3}).

By our Conjecture (ii), the above congruence implies that n is a prime.

If n ≥ 4 is an even positive integer, then we have previously shown that for such a n, 2S_{n}(n) ≢ −n^{2} (mod n^{3}) and S_{n−1}(n) ≢ −1 (mod n). This completes the proof of implication (ii) ⇒ (i).

Proof of Proposition 7. If we extend the congruence (30) modulo n^{4}, then in the same manner we obtain

\begin{matrix}2(i^{2k+1} + (n − i)^{2k+1}) − (2k + 1)n(i^{2k} + (n − i)^{2k}) \\ ≡ 2\binom{2k + 1}{3}n^{3}i^{2k−2} − (2k + 1)\binom{2k}{2}n^{3}i^{2k−2} (mod n^{4}), \end{matrix}

whence it follows that

2S_{2k+1}(n) − (2k + 1)nS_{2k}(n) ≡ \frac{k(1 − 4k^{2})}{3}n^{3}S_{2k−2}(n) (mod n^{4}).  (33)

If n = p is a prime such that p − 1 ∤ 2k − 2, then the well known congruence S_{2k−2}(p) ≡ 0 (mod p) (see, e.g., [46, the congruence (6.3)] or [29, Thm. 1]) and (33) yield the congruence (14). Finally, (15) immediately follows reducing (14) modulo p^{2} and using the previous fact that S_{2k}(p) ≡ 0 (mod p) whenever p − 1 ∤ 2k.

Remark 27. Applying a result of Damianou and Schumer [13, Thm. 2, p. 222] used in the proof of Corollary 2 to the congruence (33), it follows that

2S_{2k+1}(n) ≡ (2k + 1)nS_{2k}(n) (mod n^{4})

whenever n is not divisible by any prime p such that p | D_{2k−2}, where D_{2k−2} is the denominator of the (2k − 2)th Bernoulli number B_{2k−2}. The converse assertion is true if n is relatively prime to the integer k(1 − 4k^{2})/3.

Proof of Corollary 8. By Euler’s theorem [22], for all positive integers m and i such that 1 ≤ m < p^{4} − p^{3} and 1 ≤ i ≤ p − 1 we have 1/i^{m} ≡ i^{φ(p^{4})−m} (mod p^{4}), where φ(p^{4}) = p^{4} − p^{3} is the Euler’s totient function. Therefore, R_{m} ≡ S_{p^{4}−p^{3}−m} (mod p^{4}). Applying the last congruence for m = 2k −1 and m = 2k, and substituting this into (14) of Proposition 7 with p^{4} − p^{3} − 2k ≥ 4 instead of 2k, we immediately obtain

2R_{2k−1}(p) ≡ (p^{4} − p^{3} − 2k + 1)pR_{2k}(p) ≡ (1 − 2k)pR_{2k}(p) (mod p^{4}),

as desired.

Proof of Proposition 17. As S_{0}(n) = n − 1 and S_{1}(n) = (n − 1)n/2, Pascal’s identity (2) yields

\begin{matrix}2(n^{2k+2} − 1) = 2 ∑_{i=0}^{2k+1} \binom{2k + 2}{i}S_{i}(n) \\ = 2(n − 1)(1 + (k + 1)n) + ∑_{i=1}^{k} (2\binom{2k + 2}{2i}S_{2i}(n) + 2\binom{2k + 2}{2i + 1}S_{2i+1}(n)) . \end{matrix}  (34)

If n is odd, then multiplying the congruence (6) of Theorem 1 by \binom{2k+2}{2i+1} and using the identity \binom{2k+2}{2i+1} = \frac{2k+2−2i}{2i+1} \binom{2k+2}{2i}, we find that

\begin{aligned}\binom{2k + 2}{2i + 1}2S_{2i+1}(n) & ≡ \frac{2k + 2 − 2i}{2i + 1}\binom{2k + 2}{2i}(2i + 1)nS_{2i}(n) (mod n^{3}) \\ & = (2k + 2 − 2i)\binom{2k + 2}{2i}nS_{2i}(n) (mod n^{3}) \end{aligned}  (35)

for each i = 1, …, k. Now substituting (35) into (34), we obtain

2(n − 1)(1 + (k + 1)n) + 2 ∑_{i=1}^{k}(1 + n(k + 1 − i))\binom{2k + 2}{2i}S_{2i}(n) ≡ −2 (mod n^{3}), (36)

which is obviously the same as (22).

If n is even, then since \binom{2k+2}{2i+1} is even (this is true by the identity \binom{2k+2}{2i+1} = \frac{2(k+1)}{2i+1} \binom{2k+1}{2i}), we have that \binom{2k+2}{2i+1} \frac{n^{3}}{2} ≡ 0 (mod n^{3}). This shows that (22) is satisfied for even n and each i = 1, …, k, and hence, proceeding in the same manner as in the previous case, we obtain (22).

Further, applying the identities 2i\binom{2k+2}{2i} = (2k + 2)\binom{2k+1}{2i−1} and \binom{2k+2}{2i} − \binom{2k+1}{2i−1} = \binom{2k+1}{2i}, the left hand side of (23) is equal to

2(1 + n(k + 1)) ∑_{i=0}^{k} \binom{2k + 2}{2i}S_{2i}(n) − n ∑_{i=0}^{k} 2i\binom{2k + 2}{2i}S_{2i}(n)

=2 ∑_{i=0}^{k} \binom{2k + 2}{2i}S_{2i}(n) + 2n(k + 1)(n − 1) + 2n(k + 1) ∑_{i=1}^{k} \binom{2k + 2}{2i}S_{2i}(n)

− 2n(k + 1) ∑_{i=1}^{k} \binom{2k + 1}{2i − 1}S_{2i}(n)

=2 ∑_{i=0}^{k} \binom{2k + 2}{2i}S_{2i}(n) + 2n(k + 1)(n − 1)

+ 2n(k + 1) ∑_{i=1}^{k} (\binom{2k + 2}{2i} − \binom{2k + 1}{2i − 1}) S_{2i}(n)

=2 ∑_{i=0}^{k} \binom{2k + 2}{2i}S_{2i}(n) + 2n(k + 1)(n − 1) + 2n(k + 1) ∑_{i=1}^{k} \binom{2k + 1}{2i}S_{2i}(n)
=2 ∑_{i=0}^{k} \binom{2k + 2}{2i}S_{2i}(n) + 2n(k + 1) ∑_{i=0}^{k} \binom{2k + 1}{2i}S_{2i}(n)
=2 ∑_{i=0}^{k} (\binom{2k + 2}{2i} + n(k + 1)\binom{2k + 1}{2i}) S_{2i}(n).

Comparing the above equality with (22) immediately gives (23).

References

[1] T. Agoh, On Giuga’s conjecture, Manuscripta Math. 87 (1995), 501–510.

[2] W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 139 (1994), 703–722.

[3] W. D. Banks and C. Pomerance, On Carmichael numbers in arithmetic progressions, J. Aust. Math. Soc. 88 (2010), 313–321.

[4] A. F. Beardon, Sums of powers of integers, Amer. Math. Monthly 103 (1996), 201–213.

[5] E. Bedocchi, Nota ad una congettura sui numeri primi, Riv. Mat. Univ. Parma 11 (1985), 229–236.

[6] J. Bernoulli, Ars Conjectandi, Basel, 1713.

[7] D. Borwein, J. M. Borwein, P. B. Borwein, and R. Girgensohn, Giuga’s conjecture on primality, Amer. Math. Monthly 103 (1996), 40–50.

[8] J. M. Borwein and E. Wong, A survey of results relating to Giuga’s conjecture on primality, in Proceedings of the 25th Anniversary Conference of the Centre de Récherches Mathématiques, CECM Preprint Series, 1995, 95-035: pp. 1–23. Available

at http://discerver.carma.newcastle.edu.au/101/.

[9] C. B. Boyer, Pascal’s formula for the sums of powers of the integers, Scripta Math. 9 (1943), 237–244.

[10] L. Carlitz, The Staudt-Clausen theorem, Math. Mag. 34 (1960/1961), 131–146.

[11] S. D. Chowla, A new proof of von Staudt’s theorem, J. Indian Math. Soc. 16 (1926), 145–146.

[12] T. Clausen, Lehrsatz aus einer Abhandlung über die Bernoullischen Zahlen, Astron. Nach. 17 (1840), 351–352.

[13] P. Damianou and P. Schumer, A theorem involving the denominators of Bernoulli numbers, Math. Mag. 76 (2003), 219–224.

[14] A. Dzhumadil’daev and D. Yeliussizov, Power sums of binomial coefficients, J. Integer Seq. 16 (2013), Article 13.1.4.

[15] A. W. F. Edwards, A quick route to sums of powers, Amer. Math. Monthly 93 (1986), 451–455.

[16] J. Faulhaber, Academia Algebrae, Darinnen die miraculosische Inventiones zu den höchsten Cossen weiters continuirt und profitiert werden, Augspurg, bey Johann Ulrich Scönigs, 1631.

[17] Y. Gallot, P. Moree, and W. Zudilin, The Erdős-Moser equation 1^{k} + 2^{k} + ⋯ + (m − 2)^{k} + (m − 1)^{k} = m^{k} revisited using continued fractions, Math. Comp. 80 (2011), 1221–1237.

[18] G. Giuga, Su una presumibile proprietà caratteristica dei numeri primi, Ist. Lombardo Sci. Lett. Rend. A 83 (1950), 511–528.

[19] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Publishing Company, 1989.

[20] J. M. Grau and A. M. Oller-Marcén, Generalizing Giuga’s conjecture, preprint,

http://arXiv.org/abs/1103.3483, 2011.

[21] J. M. Grau, F. Luca, and A. M. Oller-Marcén, On a variant of Giuga numbers, Acta Math. Sin. (Engl. Ser.) 28 (2012), 653–660.

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

[23] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1982.

[24] B. C. Kellner, Über irreguläre Paare höherer Ordnungen, preprint,

    http://www.bernoulli.org/~bk/irrpairord.pdf, 2002.

[25] B. C. Kellner, The equivalence of Giuga’s and Agoh’s conjectures, preprint,

    http://arXiv.org/abs/math/0409259, 2004.

[26] D. E. Knuth, Johan Faulhaber and sums of powers, Math. Comp. 61 (1993), 277–294.

[27] T. Lengyel, On divisibility of some power sums, Integers 7 (2007), A# 41, 1–6.

[28] F. Luca, C. Pomerance, and I. Shparlinski, On Giuga numbers, Int. J. Mod. Math. 4 (2009), 13–18.

[29] K. MacMillan and J. Sondow, Proofs of power sum and binomial coefficient congruences via Pascal’s identity, Amer. Math. Monthly 118 (2011), 549–552.

[30] K. MacMillan and J. Sondow, Divisibility of power sums and the generalized Erdős-

    Moser equation, preprint, http://arXiv.org/abs/1010.2275, 2011.

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

[32] R. Meštrović, On the mod p^{7} determination of \binom{2p−1}{p−1}, Rocky Mountain J. Math. 44 (2014), 633–648.

[33] R. Meštrović, Wolstenholme’s theorem: Its generalizations and extensions in the last hundred and fifty years (1862–2012), preprint, http://arXiv.org/abs/1111.3057.

[34] R. Meštrović, Some identities in commutative rings with unity and their applications, submitted.

[35] P. Moree, On a theorem of Carlitz-von Staudt, C. R. Math. Rep. Acad. Sci. Canada 16 (1994), 166–170.

[36] P. Moree, Diophantine equations of Erdős-Moser type, Bull. Austral. Math. Soc. 53 (1996), 281–292.

[37] P. Moree, A top hat for Moser’s four mathemagical rabbits, Amer. Math. Monthly 118 (2011), 364–370.

[38] P. Moree, H. J. J. te Riele, and J. Urbanowicz, Divisibility properties of integers x, k satisfying 1^{k} + ⋯ + (x − 1)^{k} = x^{k}, Math. Comp. 63 (1994), 799–815.

[39] L. Moser, On the Diophantine equation 1^{n} + 2^{n} + ⋯ + (m − 1)^{n} = m^{n}, Scripta Math. 19 (1953), 84–88.

[40] H.J. Schultz, The sums of the kth powers of the first n integers, Amer. Math. Monthly 87 (1980), 478–481.

[41] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

cally at http://oeis.org.

[42] J. Sondow and K. MacMillan, Reducing the Erdős-Moser equation 1^{n} +2^{n} +⋯+k^{n} = (k + 1)^{n} modulo k and k^{2}, Integers 11 (2011), # A34, pages 8.

[43] K. G. C. von Staudt, Beweis eines Lehrsatzes die Bernoulli’schen Zahlen betreffend, J. Reine Angew. Math. 21 (1840), 372–374.

[44] Z.-H. Sun, Congruences for Bernoulli numbers and Bernoulli polynomials, Discrete Math. 163 (1997), 153–163.

[45] Z.-H. Sun, Congruences concerning Bernoulli numbers and Bernoulli polynomials, Discrete Appl. Math. 105 (2000), 193–223.

[46] Z.-H. Sun, Congruences involving Bernoulli polynomials, Discrete Math. 308 (2008), 71–112.

[47] Z.-H. Sun, Congruences involving Bernoulli and Euler numbers, J. Number Theory 128 (2008), 280–312.

[48] Z.-W. Sun, General congruences for Bernoulli polynomials, Discrete Math. 262 (2003), 253–276.

[49] R. Vakil, A Mathematical Mosaic: Patterns and Problem Solving, Brendan Kelly Pub., 1996.

[50] E. Wong, Computations on Normal Families of Primes, MSc Thesis, Simon Fraser University, 1997. Available at

http://discerver.carma.newcastle.edu.au/view/year/1997.html.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11A07, 11A51, 11B50, 11B65, 11B68. Keywords: sum of powers, Bernoulli number, Giuga’s conjecture, Carlitz-von Staudt result, von Staudt-Clausen theorem.

(Concerned with sequences \underline{A000146}, \underline{A000217}, \underline{A000367}, \underline{A000928}, \underline{A002445}, \underline{A002997}, \underline{A007850}, \underline{A027641}, \underline{A027642}, \underline{A027762}, \underline{A029875}, \underline{A029876}, \underline{A046094}, \underline{A064538}, \underline{A079618}, \underline{A088164}, \underline{A165908}, \underline{A177783}, \underline{A198391}, \underline{A199767}, \underline{A219540}, and \underline{A226365}.)

Received July 25 2013; revised versions received October 14 2013; October 22 2013; August 5 2014. Published in Journal of Integer Sequences, August 5 2014.

Return to Journal of Integer Sequences home page.