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!

  • 4
    $\begingroup$ 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. $\endgroup$ – anon Aug 7 '11 at 3:29
  • $\begingroup$ Excellent comment. Thank you. $\endgroup$ – user02138 Aug 7 '11 at 3:31
  • 2
    $\begingroup$ I've removed Community Wiki mode from this post. $\endgroup$ – Zev Chonoles Aug 8 '11 at 4:42
  • $\begingroup$ Thanks, Zev! I appreciate it. $\endgroup$ – user02138 Aug 8 '11 at 4:47

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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.