Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 462. (October 2008)

A. 462. Let p be an odd prime and let 1<a<p be an integer. Prove that p divides \sum_{k=0}^{p-2} {(-1)}^ka^{k^2} if and only if there exists an odd positive integer k for which ak is congruent to 1 modulo p.

(5 pont)

Deadline expired on December 15, 2008.


Solution. Let r be the order of the residue a modulo p,

(a) If r is odd, then


S=\sum_{k=0}^{p-2} {(-1)}^k a^{k^2} \equiv
\frac{p-1}{2r} \sum_{k=0}^{2r-1} {(-1)}^k a^{k^2} =
\frac{p-1}{2r} \left(
\sum_{k=0}^{r-1} (-1)^k a^{k^2} +
\sum_{k=0}^{r-1} (-1)^{k+r} a^{(k+r)^2} \right) =


= \frac{p-1}{2r} \left( \sum_{k=0}^{r-1} (-1)^k a^{k^2} +
(-1)^r\sum_{k=0}^{r-1} (-1)^k a^{k^2} \cdot (a^r)^{2k+r} \right)
\equiv

 \equiv \frac{p-1}{2r} \left( \sum_{k=0}^{r-1} (-1)^k a^{k^2} -
\sum_{k=0}^{r-1} (-1)^k a^{k^2} \right) = 0 \pmod{p}.

(b) If r is even, r=2s, then as\equiv-1 (mod p).

Let T = \sum_{k=0}^{p-2} (-1)^k a^{-k^2}. We will show that ST is not divisible by p.


ST =
\left( \sum_{k=0}^{p-2} (-1)^k a^{k^2} \right)
\left( \sum_{\ell=0}^{p-2} (-1)^\ell a^{-\ell^2} \right) =
\sum_{k=0}^{p-2} \sum_{l=0}^{p-2} (-1)^{k+\ell} a^{k^2-\ell^2} \equiv


\sum_{k=0}^{p-2} \sum_{m=0}^{p-2} (-1)^{m} a^{k^2-(m-k)^2} \equiv
\sum_{m=0}^{p-2} (-a^m)^{-m} \sum_{k=0}^{p-2} (a^{2m})^k
\pmod{p}

If r|2m, then a2m\equiv1 (mod p), and \sum_{k=0}^{p-2} (a^{2m})^k \equiv -1~(\mod p). In all other cases


\sum_{k=0}^{p-2} (a^{2m})^k \equiv
\left((a^{2m})^{p-1}-1\right)
\left(a^{2m}-1\right)^{-1}
\equiv 0 \pmod{p}.

If m/s is an even integer then m is even, -am\equiv-1 mod p), and (-am)-m\equiv((-1)2)m/2\equiv1 (mod p).

If m/s is an odd integer then am\equiv(as)m/s\equiv-1 (mod p) és (-am)-m\equiv1m\equiv1 (mod p).

As we have seen, we obtain nonzero residues only when s divides m, and this residue is -1in all such cases. Therefore,


ST \equiv \frac{p-1}{s}\cdot(-1) = -\frac{p-1}s \pmod{p}.

Since 0<\frac{p-1}{s}<p, this is not 0.


Statistics:

5 students sent a solution.
5 points:Nagy 235 János, Tomon István.
2 points:3 students.

Problems in Mathematics of KöMaL, October 2008