Let $p$ be a prime number such that $p\equiv 1\pmod{4}$. Determine $\sum_{k=1}^{\frac{p-1}{2}}\left \lbrace \frac{k^2}{p} \right \rbrace$, where $\{x\}=x-[x]$.
Problem
Source: 5-th Hong Kong Mathematical Olympiad 2002
Tags: modular arithmetic, quadratics, number theory unsolved, number theory
10.01.2007 21:41
I think that sum $= \frac{p-1}4$. Lemma: if $p \equiv 1 \pmod 4$ then, for each $1 \le n \le \frac{p-1}2$ exists exactly one $1 \le m \le \frac{p-1}2$ such that $n^{2}+m^{2}\equiv 0 \pmod p$. Proof: it is known that $-1$ is a quadratic residue mod p. There exist only two numbers, a and -a, such that $a^{2}\equiv (-a)^{2}\equiv-1 \pmod p$. Then $m^{2}+n^{2}\equiv 0 \pmod p$ $\Leftrightarrow m^{2}m^{-2}+n^{2}m^{-2}\equiv 0 \pmod p$ $\Leftrightarrow (nm^{-1})^{2}\equiv-1 \pmod p$ $\Leftrightarrow nm^{-1}\equiv a \pmod p$ (or -a) $\Leftrightarrow n \equiv am \pmod p$ (or -am) But exactly one of am, -am lies between $1$ and $\frac{p-1}2$. If $m^{2}+n^{2}= kp$ then $\frac{m^{2}}p+\frac{n^{2}}p = k$, k is an integer. The sum of the fractional parts is an integer. But it cannot be 0 ($\frac{m^{2}}p$ is not an integer) and it's less than two. Therefore: $\{\frac{m^{2}}p\}+\{\frac{n^{2}}p\}= 1$. Now, we have $\frac{p-1}2$ fractions in our sum. If we match them, we get a sum with $\frac{p-1}4$ pairs, each of them is 1. The game is done.
11.01.2007 03:05
You are right, I think , thank you
12.05.2014 14:20
I remember a nice problem from Korea in which $p$ is a prime number and $p \equiv 1\pmod{4}$.The problem was to find the value of $\sum_{k=1}^{p-1}{([\frac{2k^2}{p}]-2[\frac{k^2}{p}])}$ .This problem uses exactly the same idea as the original problem.The answer is $\frac{p-1}{2}$