Problem 11428
(American Mathematical Monthly, Vol.116, April 2009) Proposed by W. Blumberg (USA).
Letp a prime congruent to 3 mod 4, and let a and q be integers, such that p does not divide q.
Show that
p
X
k=1
(qk2+ a)/p = 2a + 1 +
p
X
k=1
(qk2− a − 1)/p .
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Let rp(n) be the remainder of the division of n by p then, since n = p⌊n/p⌋ + rp(n), the above equality is equivalent to
p
X
k=1
rp(qk2+ a) =
p
X
k=1
rp(qk2− a − 1).
Moreover
rp(qk2+ a) = rp(qk2) + rp(a) − p x(k) and rp(qk2− a − 1) = rp(qk2) − rp(a) − 1 + p y(k) with
x(k) = [rp(qk2) ≥ p − rp(a)] and y(k) = [rp(qk2) ≤ rp(a)]
where [Q] is equal to 1 if proposition Q is true and it is 0 otherwise.
Hence, since x(p) = 0 and y(p) = 1 then it suffices to show that
p−1
X
k=1
(x(k) + y(k)) = 2rp(a).
Note that rp(qk2) = j for some j ∈ {1, . . . , p − 1} iff k2 = jq−1 mod p (q is invertible mod p), that is iff jq−1 is a square mod p which means that
jq−1 p
= 1 where
· p
is the Legendre symbol.
Therefore the number of k ∈ {1, . . . , p − 1} such that rp(qk2) = j isjq−1
p
+ 1 (it gives 0 or 2).
Since p = 3 mod 4 then
−1 p
= (−1)(p−1)/2= −1, and it follows that
p−1
X
k=1
x(k) =
p−1
X
j=p−rp(a)
jq−1 p
+ 1
= rp(a) + q−1 p
rp(a) X
j=1
p − j p
= rp(a) − q−1 p
rp(a) X
j=1
j p
.
In a similar way
p−1
X
k=1
y(k) =
rp(a)
X
j=1
jq−1 p
+ 1
= rp(a) + q−1 p
rp(a) X
j=1
j p
.
Finally,
p−1
X
k=1
(x(k) + y(k)) = rp(a) − q−1 p
rp(a) X
j=1
j p
+ rp(a) + q−1 p
rp(a) X
j=1
j p
= 2rp(a).
