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!