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<n$. We can calculate that the number of cycles are $\lfloor \frac{n}{q}\rfloor $. 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}}(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q)$ and ${m}_{2}p\equiv k\phantom{\rule{thickmathspace}{0ex}}(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q)$. By adding up the two equations we have $({m}_{1}-{m}_{2})p\equiv 0\phantom{\rule{thickmathspace}{0ex}}(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q)$. We know, for every prime p,q, they are coprime. This means that only for $|{m}_{1}-{m}_{2}|\phantom{\rule{thickmathspace}{0ex}}{\textstyle |}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

$\lfloor \frac{n}{q}\rfloor \sum _{i=1}^{q-1}i=\frac{1}{2}\lfloor \frac{n}{q}\rfloor q(q-1)$

Step 2

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\phantom{\rule{thickmathspace}{0ex}}(\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q)$. 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}{\lfloor \frac{n}{q}\rfloor}{q(q-1)}+\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}{({q}^{2}-q)}+\sum _{i=1}^{n-rq}ia\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q$

Feel free to leave a comment if there're mistakes.

###### Did you like this example?

Subscribe for all access