Problem 11118
(American Mathematical Monthly, Vol.111, December 2004) Proposed by V. Dimitrov (Bulgaria).
Let p be an odd prime, and let k be a positive integer. Prove that
k
X
j=0
k(p − 1) j(p − 1)
≡ 2 + p(1 − k) mod p2.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Let ω = e2πi/(p−1) then it is well known that
n r
p−1
:= X
j≡r mod (p−1)
n j
= 1
p− 1
p−2
X
s=0
ω−rs(1 + ωs)n.
In order to prove that
k(p − 1) 0
p−1
≡ 2 + p(1 − k) mod p2 we need the following preliminary results (the proofs are given later):
(a)k(p − 1) 0
p−1
= 2 + p(1 − k) mod p2 for 1 ≤ k ≤ p ;
(b)
p−2
X
r=0
(−1)r n
−r
p−1
=
p−2
X
r=0
(−1)rn r
p−1
= 0.
(c)p(p − 1) r
p−1
= (−1)r(p + 1) mod p2 for 1 ≤ r ≤ p − 2 ;
Finally, by (a), the proof can be completed by induction by showing that
n + p(p − 1) 0
p−1
≡n 0
p−1
mod p2.
n + p(p − 1) 0
p−1
= 1
p− 1
p−2
X
s=0
(1 + ωs)n+p(p−1)
= 1
p− 1
p−2
X
s=0
(1 + ωs)n
p(p−1)
X
t=0
p(p − 1) t
ωst
=
p(p−1)
X
t=0
p(p − 1) t
· 1 p− 1
p−2
X
s=0
ωst(1 + ωs)n
=
p(p−1)
X
t=0
p(p − 1) t
· n
−t
p−1
=
p−2
X
r=0
p(p − 1) r
p−1
· n
−r
p−1
≡ n 0
p−1
+ (p + 1)
p−2
X
r=0
(−1)r n
−r
p−1
mod p2 (by (a) and (c))
≡ n 0
p−1
mod p2 (by (b)).
Proof of (a). Since (p − 1)! = −1 mod p then, for any 1 ≤ j ≤ p there is an integer q such that (j(p − 1))! = (jp − j) · · · (jp − (p − 1)) · (j − 1)p · ((j − 2)p + p − 1) · · · 1 = (−1 + qp)pj−1. Hence there are integers q1, q2, q3, q such that
k(p − 1) j(p − 1)
= (−1 + q1p)pk−1
(−1 + q2p)pj−1· (−1 + q3p)pk−j−1 = (−1 + qp)p ≡ −p mod p2. Therefore
k(p − 1) 0
p−1
= 2 +
k−1
X
j=1
k(p − 1) j(p − 1)
≡ 2 +
k−1
X
j=1
(−p) ≡ 2 + p(1 − k) mod p2.
Proof of (b). Since p − 1 even then
p−2
X
r=0
(−1)rn r
p−1
=
p−2
X
r=0
(−1)r
⌊n/(p−1)⌋
X
q=0
n
(p − 1)q + r
=
⌊n/(p−1)⌋
X
q=0 p−2
X
r=0
(−1)(p−1)q+r
n
(p − 1)q + r
=
n
X
j=0
(−1)jn j
= 0.
Proof of (c). The case r = 0 follows from (a). Assume that 1 ≤ r ≤ p − 2. Since
p(p − 1) pr
≡p − 1 r
mod p2 and p(p − 1) j
= 0 mod p if p 6 |j then
p(p − 1) r
p−1
=
p−1
X
q=0
p(p − 1) q(p − 1) + r
=p(p − 1) pr
+ par≡p − 1 r
+ par mod p2
where aris the following integer
ar≡
p−1
X
q=0,q6=r
p− 1 q(p − 1) + r
p(p − 1) − 1 q(p − 1) + r − 1
.
By Lucas’ Theorem
ar≡
r−1
X
q=0
−1 r− q
p − 2 q
p− 1 r− 1 − q
+
p−1
X
q=r+1
−1 r− q
p − 2 q− 1
p− 1 p+ r − 1 − q
mod p
Since
p − 1 j
≡ (−1)j ,p − 2 j
≡ (−1)j(j + 1) ,
p−1
X
q=1
1
q ≡ 0 mod p then
ar ≡ (−1)r
r−1
X
q=0
q+ 1 r− q +
p−1
X
q=r+1
q r− q
!
≡ (−1)r
r−1
X
q=0
1 r− q+
p−1
X
q=0q6=r
q r− q
≡ (−1)r
r
X
q=1
1 q+
p−1
X
q=0q6=r
q− r r− q+ r
p−1
X
q=0q6=r
1 r− q
≡ (−1)r
r
X
q=1
1 q + 1
!
mod p
Therefore
p(p − 1) r
p−1
≡p − 1 r
+ p (−1)r
r
X
q=1
1 q+ 1
!!
mod p
mod p2.
