How can I calculate summations of modulus expressions?

Question

I know that the following holds true: $$\sum_{k=1}^n k = {n (n + 1) \over 2} $$

Can modulus expressions be simplified in similar ways? For example:

$$\sum_{k=1}^n (k\bmod x) = ?? $$

To be clear, when I say modulus I mean "the non-negative integer that occurs as the remainder when dividing b by a", where b and a for my purposes are two integers, and x is some integer $x \leq k$.

Answer 1

I don't think people are understanding the question correctly, so please comment if this is what you were looking for:

$$\bigg[(1+\cdots +(x-1)+0)+(1+\cdots +(x-1)+0)+\cdots \bigg]+(1+\cdots+ (n\bmod x)) \\ =\left\lfloor \frac{n}{x}\right\rfloor\big(1+\cdots+(x-1)\big)+(1+\cdots +(n\bmod x)) \\ =\left\lfloor \frac{n}{x}\right\rfloor\frac{x(x-1)}{2}+\frac{(n\bmod x)(n\bmod x+1)}{2}$$

---

Example. Let's consider the case of $n=7$ and $x=3$: $$\begin{align}\sum_{k=1}^{7}(k\bmod 3)&=(1\bmod 3)+(2\bmod 3)+(3\bmod 3)+(4\bmod 3)+\cdots \\ &=\Big[(1+2+0)+(1+2+0)\Big]+(1) \\ &=2\cdot (1+2)+(1) \\ &=\left\lfloor \frac{7}{3}\right\rfloor(1+2)+(1)\end{align}$$

Answer 2

You can always just compute the answer without modulus and then take the modulus afterward, so I assume you're asking whether it's possible to do all the arithmetic under modulus. Consider if $x = 2$. Then you can't divide by $2$, and you know that either $k$ or $k+1$ is even but you don't know if they are divisible by $4$, so you don't know whether your answer $\mod x$ should be $1$ or $0$. So no, you can't just do the arithmetic $\mod x$ for arbitrary $x$ to compute the formula. I do believe you can do it for ODD $x$, if you compute the inverse of $2 \mod x$.

Answer 3

$\displaystyle {}\,\sum_{k=1}^n (k\bmod x)=\sum_{k=1}^n\left(k-x\left\lfloor\frac{k}{x}\right\rfloor\right)=\sum_{k=1}^nk-x\sum_{k=1}^n\left\lfloor\frac{k}{x}\right\rfloor$

$\displaystyle {}\qquad\qquad\qquad = \frac{n(n+1)}{2}-x\left\lfloor\frac{n}{x}\right\rfloor\left(n+1-\frac{x}{2}-\frac{x}{2}\left\lfloor\frac{n}{x}\right\rfloor\right)$

Example. Let's consider the case of $n=7$ and $x=3$: $$\sum_{k=1}^7 (k \bmod 3)=\frac{7(7+1)}{2}-3\left\lfloor\frac{7}{3}\right\rfloor\left(7+1-\frac{3}{2}-\frac{3}{2}\left\lfloor\frac{7}{3}\right\rfloor\right)=7$$