This is one nice problem (in fact, all of them seem to be very nice, except maybe for the functional equation ). Let's solve it for $n=1$, and then we'll see why this is enough. We must compute $\sum_{k=1}^{p-1}\left(\frac{k^2}p-\frac 12-\left\lfloor\frac{k^2}p-\frac 12\right\rfloor\right)$, which is equal to $\sum_{k=1}^{p-1}\left(\frac{2k^2}p-\frac 12-\left\lfloor\frac{2k^2}p\right\rfloor+1\right)-\sum_{k=1}^{p-1}\left(\frac{k^2}p-\left\lfloor\frac{k^2}p\right\rfloor\right)\ (*)$, because of the identity $\left\lfloor x\right\rfloor+\left\lfloor x+\frac 12\right\rfloor=\left\lfloor 2x\right\rfloor$ applied to $x=\frac{k^2}p-\frac 12$. Now, $(*)$ is equal to $\sum_{k=1}^{p-1}\left(\left\{\frac{2k^2}p\right\}-\left\{\frac{k^2}p\right\}\right)+\frac{p-1}2$, which equals $\frac{p-1}2$ because $2$ is a quadratic residue $\pmod p$, so the residues $2k^2\pmod p$ are the same as the residues $k^2\pmod p$. The identity is proven for $n=1$. This is enough, because the residues $k^{2^n}\pmod p$ are the same as the residues $k^2\pmod p$, since $-1$ is not a quadratic residue $\pmod p$, meaning that the equation $x^4=1$ has $2$ solutions $\pmod p$, so there are $\frac{p-1}2$ fourth powers $\pmod p$, and we can apply induction: there are also $\frac{p-1}2$ $8$'th powers, and so on, and these are precisely the quadratic residues. It says $n\ge 0$ in the text, but if it's also true for $n=0$, it's certainly not interesting enough to work out . Edit: edited in response to prowler's post below

My solution is almost the same @ grobber I think you meant $[x]+[x+1/2] = [2x]$

$\left\lfloor x\right\rfloor+\left\lfloor\frac x2\right\rfloor=\left\lfloor 2x\right\rfloor$. What do I miss here?

Myth wrote: $\left\lfloor x\right\rfloor+\left\lfloor\frac x2\right\rfloor=\left\lfloor 2x\right\rfloor$. What do I miss here? Grobbers edit of his post due to prowler's post

I know, but for some uknown reasons I receive topic reply notifications with 40 minutes delay this evening!

grobber wrote: This is one nice problem (in fact, all of them seem to be very nice, except maybe for the functional equation ). Let's solve it for $n=1$, and then we'll see why this is enough. We must compute $\sum_{k=1}^{p-1}\left(\frac{k^{2}}p-\frac{1}{2}-\left\lfloor\frac{k^{2}}p-\frac{1}{2}\right\rfloor\right)$, which is equal to $\sum_{k=1}^{p-1}\left(\frac{2k^{2}}p-\frac{1}{2}-\left\lfloor\frac{2k^{2}}p\right\rfloor+1\right)-\sum_{k=1}^{p-1}\left(\frac{k^{2}}p-\left\lfloor\frac{k^{2}}p\right\rfloor\right)\ (*)$, because of the identity $\left\lfloor x\right\rfloor+\left\lfloor x+\frac{1}{2}\right\rfloor=\left\lfloor 2x\right\rfloor$ applied to $x=\frac{k^{2}}p-\frac{1}{2}$. Now, $(*)$ is equal to $\sum_{k=1}^{p-1}\left(\left\{\frac{2k^{2}}p\right\}-\left\{\frac{k^{2}}p\right\}\right)+\frac{p-1}2$, which equals $\frac{p-1}2$ because $2$ is a quadratic residue $\pmod p$, so the residues $2k^{2}\pmod p$ are the same as the residues $k^{2}\pmod p$. The identity is proven for $n=1$. This is enough, because the residues $k^{2^{n}}\pmod p$ are the same as the residues $k^{2}\pmod p$, since $-1$ is not a quadratic residue $\pmod p$, meaning that the equation $x^{4}=1$ has $2$ solutions $\pmod p$, so there are $\frac{p-1}2$ fourth powers $\pmod p$, and we can apply induction: there are also $\frac{p-1}2$ $8$'th powers, and so on, and these are precisely the quadratic residues. It says $n\ge 0$ in the text, but if it's also true for $n=0$, it's certainly not interesting enough to work out . Edit: edited in response to prowler's post below I wanna ask two questions : 1) Why $2$ is a quadratic residue $(mod p)$ ? 2) Why if $x^{4}\equiv 1 (mod p)$ has exactly $2$ solutions, then there are $\frac{p-1}{2}$ distinct fourth power in $mod p$ ? Isn't it possible that if $a$ and $b$ are distinct quadratic residues $mod p$, then $a^{2}\equiv b^{2}(mod p)$ ? (Of course $a \equiv b (mod p)$ is impossible, but $a+b \equiv 0 (mod p)$ is possible, for example $a = 1, b = 4, p = 5$) Maybe $p \equiv 7 (mod 8)$ has a role in both parts. Thanks..

1) Because $p\equiv 7(\mod p)$ and $\left( \frac{2}{p}\right) =(-1)^{\frac{p^{2}-1}{8}}$ 2) Suppose $a$ and $b$ are distinct quadratic residue $\mod p$ such that $a\equiv-b(\mod p)$ so $ab=-a^{2}(\mod p)$ but $ab$ and $a^{2}$ are quadratic residue $\mod p$ and $-1$ is not quadratic residue $\mod p$ Contadiction..

Just be legendre symbol $(\frac {k^{2^n}}{p})=(\frac {k}{p})^{2^n}=1$. Now consider the set $\{k^{2^n}\}$ mod ($p$). Suppose there are two same elements into that set, the $p|{a^{2^n}-{b^{2^n}}}$ also $p|a^{p-1}-b^{p-1}$ and that implies $p|a^2-b^2$ since $gcd(p-1,2^n)=2$. Now obviously $\{k^{2^n}\}$ mod ($p$)=$\{k^2\}$ mod ($p$). So it's enough do for $n=1$. Now we've to show $\sum_{k=1}^{p-1}\{\frac {k^2}{p}-\frac {1}{2}\}=\sum_{k=1}^{p-1}\{\frac {(ak)^2}{p}-\frac {1}{2}\}$. Since we've $\{k^2\}$ mod ($p$)=$\{(ak)^2\}$ mod ($p$) for all $a\in\mathbb N$. Now take such $a$ for which $\frac {(ak)^2}{p}>\frac {1}{2}$ for all $k<p$.Now just using $[x]+[x-\frac{1}{2}]=[2x-1]=[2x]-1$ (as we're taking $x=\frac {(ak)^2}{p}>\frac {1}{2}$) we're done.