Compute summation of modules expression? This question is an extension of the following question:
How can I calculate summations of modulus expressions?
In particular, what I want to look at is the sum $$\sum_{k=1}^n(pk\pmod{q})$$ where $p,q\in \mathbb{Z}_{\geq 1}$ can be assumed to be coprime but it would be best if solved in the fullest generality. In the above expression, $n$ is a variable, $p,q$ are fixed, and $a\pmod{b}$ means taking the representative set $\{0,1,2,...,b-1\}$. For example, $7\pmod{3}=1$ is the only value we agree upon and $7\pmod{3}\neq -2$.
The problem with this is that the list of representatives are permuted by $p$ and hence the methods presented in the initial link are no longer valid.
It would be nice if we can come up with a closed form, but a really tight upper bound of the expression also works.
 A: Let the sequence $1p, 2p, 3p, ... qp, ..., np$. This shows that there are some multiples of $qp$, or $1qp, 2qp, ..., rqp$. Thus we can assume $r$ be the largest number such that $rq<n$. We can calculate that the number of cycles are $\lfloor\frac {n} q\rfloor$. The remaining numbers are $rq\mod n$.
We assume that for some integer $m_1, m_2$, such that $m_1p\equiv k\;(\mod q)$ and $m_2p\equiv k\;(\mod q)$. By adding up the two equations we have $(m_1-m_2)p\equiv0\;(\mod q)$. We know, for every prime $p,q$, they are coprime. This means that only for $|m_1-m_2|\;\bigg|q$. This tells us that in the sets of number $0p, 1p,2p,3p,...qp$, the modulo of the numbers are always different.
As we take the modulo when $0\leq r\leq q$, thus for every set of numbers $1p, 2p, ..., qp$, their modulo is $0, 1, 2, ..., q-1$, the total sum of them is $$\lfloor \frac {n} q\rfloor\sum_{i=1}^{q-1}i=\frac 1 2\lfloor \frac {n} q\rfloor q(q-1)$$
Case 1: $p< q$, thus we can roughly calculate the modulo by hand.
Case 2: $p> q$, we can assume $p=q+a$ for some integer $a$, we can also know that most of the value of $a$ is even as mostly of the prime numbers are odd. Then, for some integer $\alpha$, $\alpha p=\alpha(q+a)=\alpha q+\alpha a\equiv\alpha a\;(\mod q)$. Thus the entire summation can be evaluated as follow:
$$\sum_{k=1}^n pk\mod q\equiv \frac 1 2\color{red}{\lfloor \frac {n} q\rfloor}\color{blue}{ q(q-1)}+\sum_{i=1}^{n-rq}ia\mod q=\frac 1 2\color{red}r\color{blue}{(q^2-q)}+\sum_{i=1}^{n-rq}ia\mod q$$
Feel free to leave a comment if there're mistakes.
