# 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!

-
Call the sum $S_k(n;a,b)$. Convince yourself that $d|b\to(dm\mod b)=d(m \mod b/d)$. Then if $d=\gcd(a,b)$, we can factor $$S_k(n;a,b)=dS_k(n;a/d,b/d).$$ Furthermore, since $(m+b)^k\equiv m^k$, we can write $S_k(n+b;a,b)=S_k(n;a,b)+S_k(b;a,b)$. Generalizing, this gives $$S_k(n;a,b)=\left\lfloor\frac{n}{b}\right\rfloor S_k(b;a,b)+S_k(n\mod b;a,b).$$ Beyond these two reductions I can't say if you'll be able to find anything to explicitly simplify the formula for general $a,b,k,n$. For $a,b$ coprime, I can say $S_1(b;a,b)=b(b-1)/2$, and quadratic reciprocity might enable an explicit $S_2$ form. – anon Aug 7 '11 at 3:29
Excellent comment. Thank you. – user02138 Aug 7 '11 at 3:31
I've removed Community Wiki mode from this post. – Zev Chonoles Aug 8 '11 at 4:42
Thanks, Zev! I appreciate it. – user02138 Aug 8 '11 at 4:47

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}