Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
4  
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
2  
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

1 Answer 1

up vote 1 down vote accepted

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}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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