Consider sum:
\begin{equation}
S\_q(n) = \sum\_{x=1}^{n}\Big\{ \frac{x^q}{n} \Big\} 
\end{equation}
where $\{x\}$ is fractional part of $x$. It's easy to see that $S\_{1}(n) = \frac{1}{2}(n-1)$, but already $S\_{2}(n)$ looks more complicated. I have some observations about the $S\_q(n),\; q > 1$. It is likely that they are false, since I have no proof, but it is still interesting to ask about it here.


**Observation 1:**
If an integer $n = p\_{1}^{q\_1}\ldots p\_{m}^{q\_m}$, where $p\_i$ are prime numbers of the form $4k+1$, then
holds:
\begin{equation}\label{eq1}
S\_{2}(n) = \frac{1}{2}\Big(n- p\_{1}^{\big\lfloor \frac{q\_1}{2} \big\rfloor}\ldots p\_{m}^{\big\lfloor \frac{q\_m}{2} \big\rfloor}\Big)
\end{equation}


**Observation 2:**
If an integer $n = p\_{1}^{q\_1}\ldots p\_{m}^{q\_m}$, where $p\_i$ are prime numbers, then for odd $q > 1$ holds:
\begin{equation}\label{eq2}
S\_{q}(n) = \frac{1}{2}\Big(n- p\_{1}^{\big\lfloor 
\frac{1}{2}\big\lfloor q\_1 - \frac{2q\_1}{q} \big\rfloor + \frac{q\_1}{2}
\big\rfloor}\ldots p\_{m}^{\big\lfloor 
\frac{1}{2}\big\lfloor q\_m - \frac{2q\_m}{q} \big\rfloor + \frac{q\_m}{2}
\big\rfloor}\Big)
\end{equation}


I couldn't find any pattern for $S\_{2q}(n)$ in general, only some special cases:


\begin{equation}
S\_{2}(2^k) = \frac{1}{2}(2^k - a\_{k+1}) = \frac{1}{2}(2^k-b\_{k})
\end{equation} where $a\_k$ is the sequence [A060482](https://oeis.org/A060482), $k>1$ and $b\_k$ is the sequence [A136252](https://oeis.org/A136252), $k > 0$.


\begin{equation}
S\_{2}(3^k) = \frac{1}{2}\Big(3^k - \frac{a\_{k+2}}{3}\Big)
\end{equation} where $a\_k$ is the sequence [A060647](https://oeis.org/A060647), $k>0$


\begin{equation}
S\_{2}(4^k) = \frac{1}{2}(4^k - a\_{k+1})
\end{equation} where $a\_k$ is the sequence [A068156](https://oeis.org/A068156), $k>0$


\begin{equation}
S\_{4}(2^k) = \frac{1}{2}\Big(2^k - a\_{\big\lfloor \frac{k-1}{4} \big\rfloor + 1}\Big)
\end{equation} where $a\_k$ is the sequence [A000225](https://oeis.org/A000225), $k > 0$


**Question:**


Are the formulas in observations 1,2 correct? If the formulas are correct, is there any general pattern for $S\_{2q}(n)$?


*The [code](https://pastebin.com/k8ytVbsE) for numerical validation of certain small values*



Formulas for $\sum_{x=1}^{n}\Big\{\frac{x^q}{n}\Big\}$
I have a solution when $-1$ is a power of $q$ mod $n$ (which generalizes your observations) and when $n$ is prime and $q$ is 2.


We'll show that if there is a $z$ such that $z^q\equiv -1 \mod n$ where $n=\prod\_i p\_i^{q\_i}$ then:
$$S\_q(n)= \frac{1}{2} ( n - \prod\_i p\_i^{q\_i-\lceil{ q\_i/q }\rceil}) $$


In particular, this is a generalization of both your observations 1 and 2 since $-1$ is a quadratic residue for primes $1 \mod 4$ and for odd $q$, $(-1)^q=-1$.


Let $z$ satisfy $z^q\equiv -1 \mod n$. Let $m\_k$ be the number of integers $i$ from $0$ to $n-1$ such that $i^q\equiv k \mod n$.


Note that since $gcd(z^k,n)=gcd(-1,n)=1$ that $gcd(z,n)=1$, so multiplying by $z$ permutes the residues $\mod n$. Therefore,
$$\sum\_{i=0}^{n-1} \frac{i\cdot m\_i}{n}=\sum\_{x=1}^n \{\frac{x^q}{n} \}
=\sum\_{x=1}^n \{\frac{(zx)^q}{n} \}
=\sum\_{x=1}^n \{\frac{n-x^q}{n} \}
=\sum\_{i=1}^{n} \frac{(n-i)\cdot m\_i}{n} $$
Thus,
$$2S\_q(n)=\sum\_{i=0}^{n-1} \frac{i\cdot m\_i}{n}+\sum\_{i=1}^{n} \frac{(n-i)\cdot m\_i}{n}
=\sum\_{i=1}^{n-1} m\_i=n-m\_0$$
We can calculate that $x^q\equiv 0 \mod n$ iff for all $i$, $p\_i^{q\_i}$ divides $x^q$ iff $\prod\_i p\_i^{\lceil{q\_i/q}\rceil}$ divides $x$. Thus, $m\_0 = n/\prod\_i p\_i^{\lceil{q\_i/q}\rceil}$. Putting this together gives the desired $S\_q(n)$.


For general $q$,$n$ I suspect the answer is expressible using algebraic number theory. For $q=2$, $n=p$ prime, and $p \equiv 3 \mod 4$. For $p>3$, the Class Number formula simplifies to:
$$h(-p)=-\frac{1}{p}\sum\_{i=0}^{p-1} i (\frac{i}{p} )$$
Thus, you can express $S\_2(p)$ for $p\equiv 3 \mod 4$ and $p>3$ in terms of the Class number for imaginary quadractic field of discriminant $-p$:
$$S\_2(p)=\frac{p-1}{2}-h(-p)$$


