Non-modular Power Residue Sums Given $a, b, k, n \in \mathbb{N}$, what techniques are available for computing sums of the form:
\begin{align}
\sum_{i = 1}^{n} (ai^{k} \ \text{mod} \ b ) ?
\end{align}
NB: Here, only the summands are reduced modulo $b$, not the overall summation. 
I'm specifically interested in the $k = 1$ case. For example, if $a = 2$, $b = 3$ and $k = 1$, I can prove that
\begin{align}
\sum_{i = 1}^{n} (2i \ \text{mod} \ 3) = 3 + 2 \left \lfloor \frac{n-1}{3} \right \rfloor + \left \lfloor \frac{n-2}{3} \right \rfloor 
\end{align}
by splitting the sum into sums over residue classes. In general, for prime $p$, one has
\begin{align}
\sum_{i =1}^{n} (ai \ \text{mod} \ p) = \binom{p}{2} + \sum_{k = 1}^{p-1} (k a \ \text{mod} \ p) \left \lfloor \frac{n-k}{p} \right \rfloor,
\end{align}
provided that $a$ and $p$ are coprime (otherwise the right side is identically $0$). Although this identity is nice, it is somewhat impractical if $p$ is large. Can the right-side be further simplified?
Edit 1: The formula above continues to hold in the case that $a$ and $b$ are coprime. What can be said about such sums if $a$ and $b$ are not coprime (and $b$ does not divide $a$)?
Edit 2: A slight modification of the formula above continues to hold in the case that $a$ and $b$ are not coprime. In this case, the constant is no longer $\binom{b}{2}$. What is the constant?
Edit 3: Using the comment below I can answer the question about the constant asked in Edit 2, although in this case $a$ and $b$ in the relation above must be replaced with $a/\gcd(a,b)$ and $b/\gcd(a,b)$, respectively, and both terms are multiplied by $\gcd(a,b)$. The constant is then $\gcd(a,b) \binom{b/\gcd(a,b)}{2}$.
Any help or hints are quite welcome!
 A: Applying the first transformation formula suggested in the comments with the above relation, we have the following identity.
Given $a, b \in \mathbb{N}$ with $d = \gcd(a,b)$, if $b \nmid a$, then for any $n \in \mathbb{N}$, 
\begin{align}  
S(n;a,b)  =  d \left( \binom{b / d}{2}   +  \sum_{k = 1}^{b / d-1} \left(   \frac{k a}{d}  \ \text{mod} \ \frac{b}{d} \right) \left \lfloor d \left( \frac{n - k}{b} \right) \right \rfloor \right).
\end{align}
The second transformation gives an equivalent, but slightly more involved, right side,
\begin{align}  
d \left( \left \lfloor \frac{n}{b} \right \rfloor + 1 \right)  \binom{b / d}{2}   + d  \sum_{k = 1}^{b / d-1} \left(   \tfrac{k a}{d}  \ \text{mod} \ \tfrac{b}{d} \right) \left(  \left \lfloor \frac{n}{b} \right \rfloor  \left \lfloor d \left( \frac{b  - k}{b} \right) \right \rfloor +  \left \lfloor d \left( \frac{n \ \text{mod} \ b - k}{b} \right) \right \rfloor \right).   
 \end{align}
NB: Applying the transformations repeatedly, I find
\begin{align}
S(n;a,b) = \left( d^{2} \left \lfloor \tfrac{n}{b} \right \rfloor + d \left \lfloor \tfrac{(n \ \text{mod} \ b)}{b/d} \right \rfloor \right) \binom{b/d}{2} + d S(n \ \text{mod} \ (b/d); a/b, b/d),
\end{align}
which thusfar gives me the best possible identity,
\begin{align}
S(n; a, b) & = d ( d  \lfloor \tfrac{n}{b} \rfloor      +   \left \lfloor \tfrac{(n \ \text{mod} \ b)}{b/d}  \right \rfloor + 1 ) \binom{b/d}{2}  + d \sum_{k =1}^{b/d - 1} (k \tfrac{a}{d} \ \text{mod} \ \tfrac{b}{d}) \left \lfloor  \tfrac{(n \ \text{mod} \ (b/d) ) - k}{b/d} \right \rfloor.
\end{align}
