d − 1 if q = 1 or q is even, 2(d − 1) if q ≥ 3 is odd

Problem 11546

(American Mathematical Monthly, Vol.118, January 2011)

Proposed by Kieren MacMillan (Canada) and Jonathan Sondow (USA).

Let d, k, and q be positive integers, with k odd. Find the highest power of 2 that divides

Sq(2^dk) =

2^dk

X

n=1

n^q.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

We will prove that if d ≥ 1 and k is odd then there exists an odd number Aq(2^dk) such that S_q(2^dk) = A_q(2^dk) ·

 2^d−1 if q = 1 or q is even, 2^2(d−1) if q ≥ 3 is odd . Therefore

ord2(Sq(2^dk)) =

 d − 1 if q = 1 or q is even, 2(d − 1) if q ≥ 3 is odd . We first note that for any integer m ≥ 1

Sq(2m) = m^q+

n

X

j=1

((m − j)^q+ (m + j)^q) = m^q+

n

X

j=1 q

X

r=0

q r



m^q−r((−j)^r+ j^r)

= m^q+ 2

bq/2c

X

r=0

 q 2r



m^q−2rS_2r(m) = m^q+ 2m^q+1+ 2

bq/2c

X

r=1

 q 2r



m^q−2rS_2r(m).

Our statement is true for q = 1 because S(2m) = m(2m + 1).

Now we assume q ≥ 2 and we proceed by induction on d. The statement is true for d = 1 because

S_q(2k) ≡

2k

X

n=1

n = k(2k + 1) ≡ 1 (mod 2).

Moreover, if q ≥ 2 is even then qd ≥ d + 1 and

Sq(2^d+1k) = (2^dk)^q+ 2(2^dk)^q+1+ 2

q/2

X

r=1

 q 2r



(2^dk)^q−2rA2r(2^dk)2^d−1≡ Aq(2^dk)2^d (mod 2^d+1)

where Aq(2^dk) is odd. On the other hand, if q ≥ 3 is odd then qd ≥ 2d + 1 and

Sq(2^d+1k) = (2^dk)^q+2(2^dk)^q+1+2

(q−1)/2

X

r=1

 q 2r



(2^dk)^q−2rA2r(2^dk)2^d−1≡ qkAq−1(2^dk) 2^2d (mod 2^2d+1)

where qkAq−1(2^dk) is odd.