THE 68th NMO SELECTION TESTS FOR THE BALKAN AND INTERNATIONAL MATHEMATICAL OLYMPIADS

Notice that $\{k^{2n}/p\}=r_k/p$, where $r_k$ is the remainder $k^{2n}$ leaves upon division by $p$. Clearly, the $r_k$ are quadratic residues modulo $p$. If $p$ is prime, and $p-1$ and $n$ are relatively prime, then the $r_k$, $k=1,\dots ,(p-1)/2$, are pairwise distinct, since the $k^{2n}$, $k=1,\dots ,(p-1)/2$, are pairwise distinct modulo $p$, by Fermat's little theorem. In this case, the $r_k$, $k=1,\dots ,(p-1)/2$, form the set $R$ of all $(p-1)/2$ quadratic residues modulo $p$ in the range $1$ through $p-1$. If, in addition, $p$ is congruent to $1(\mathrm{mod}4)$, then $-1$ is a quadratic residue modulo $p$, and the assignment $r\mapsto p-r$, $r\in R$, defines a permutation of $R$. In this case, ${\sum }_{r\in R}r={\sum }_{r\in R}(p-r)=p(p-1)/2-{\sum }_{r\in R}r$, so ${\sum }_{r\in R}r=p(p-1)/4$, and the arithmetic mean in question is $1/2$. Finally, since $n$ is odd, infinitely many primes congruent to $1(\mathrm{mod}4)$ are also congruent to $2(\mathrm{mod}n)$, by Dirichlet's theorem on arithmetic sequences of integers; for such a prime $p$, the numbers $p-1$ and $n$ are clearly relatively prime. This completes the proof.

---

Alternative solution.

It is sufficient to show that ${\sum }_{k=1}^{(p-1)/2}\{k^{2n}/p\}=(p-1)/4$ for every prime $p$ congruent to $1(\mathrm{mod}4)$. Let $p$ be a prime congruent to $1(\mathrm{mod}4)$, let $K=\{1,\dots ,(p-1)/2\}$, let $r_k$, $k\in K$, be the remainder $k^2$ leaves upon division by $p$, and let $$K^{-}=\{k:r_k<p/2\}\text{and}{K}^{+}=\{k:r_k>p/2\}.$$ It is easily seen that the $r_k$ are pairwise distinct, so they form the set of all quadratic residues modulo $p$. Since $p$ is congruent to $1(\mathrm{mod}p)$, $-1$ is a quadratic residue modulo $p$, so there is a bijection $f:K^{-}\to K^{+}$ such that $r_k+r_{f(k)}=p$ for all $k$ in $K^{-}$; in particular, $|K^{-}|=|K^{+}|=|K|/2=(p-1)/4$. Since $n$ is odd, it follows that $k^{2n}+f(k{)}^{2n}\equiv 0(\mathrm{mod}p)$ for all $k$ in $K^{-}$, so if $r_k^{\prime }$ is the remainder $k^{2n}$ leaves upon division by $p$, then $p-r_k^{\prime }$ is the remainder $f(k{)}^{2n}$ leaves upon division by $p$. Consequently, $$\begin{array}{rl}\sum _{k\in K}\{k^{2n}/p\}& =\sum _{k\in K^{-}}\{k^{2n}/p\}+\sum _{k\in K^{+}}\{k^{2n}/p\}=\sum _{k\in K^{-}}(\{k^{2n}/p\}+\{f(k{)}^{2n}/p\})\\ & =\sum _{k\in K^{-}}(r_k^{\prime }/p+(1-r_k^{\prime }/p))=|K^{-}|=(p-1)/4.\end{array}$$