MISA6zh

2022-11-17

Compute summation of modules expression?
In particular, what I want to look at is the sum
$\sum _{k=1}^{n}\left(pk\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}q\right)\right)$
where $p,q\in {\mathbb{Z}}_{\ge 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(modb) means taking the representative set $\left\{0,1,2,...,b-1\right\}$. For example, $7\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)=1$ is the only value we agree upon and $7\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)\ne -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.

Patrick Arnold

Expert

Step 1
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. We can calculate that the number of cycles are $⌊\frac{n}{q}⌋$. The remaining numbers are rqmodn.
We assume that for some integer ${m}_{1},{m}_{2}$, such that ${m}_{1}p\equiv k\phantom{\rule{thickmathspace}{0ex}}\left(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q\right)$ and ${m}_{2}p\equiv k\phantom{\rule{thickmathspace}{0ex}}\left(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q\right)$. By adding up the two equations we have $\left({m}_{1}-{m}_{2}\right)p\equiv 0\phantom{\rule{thickmathspace}{0ex}}\left(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q\right)$. We know, for every prime p,q, they are coprime. This means that only for $|{m}_{1}-{m}_{2}|\phantom{\rule{thickmathspace}{0ex}}|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\le r\le q$, thus for every set of numbers 1p,2p,...,qp, their modulo is $0,1,2,...,q-1$, the total sum of them is
$⌊\frac{n}{q}⌋\sum _{i=1}^{q-1}i=\frac{1}{2}⌊\frac{n}{q}⌋q\left(q-1\right)$
Step 2
Case 1: $p, 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 \left(q+a\right)=\alpha q+\alpha a\equiv \alpha a\phantom{\rule{thickmathspace}{0ex}}\left(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q\right)$. Thus the entire summation can be evaluated as follow:
$\sum _{k=1}^{n}pk\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q\equiv \frac{1}{2}⌊\frac{n}{q}⌋q\left(q-1\right)+\sum _{i=1}^{n-rq}ia\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q=\frac{1}{2}r\left({q}^{2}-q\right)+\sum _{i=1}^{n-rq}ia\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q$