Formulas for $\sum_{x=1}^{n}\Big\{\frac{x^q}{n}\Big\}$ 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, $k>1$ and $b_k$ is the sequence 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, $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, $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, $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 for numerical validation of certain small values
 A: 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)$$
