Non-modular Power Residue Sums

Question

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!

Answer 1

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}