MISA6zh

Answered

2022-11-17

Compute summation of modules expression?

In particular, what I want to look at is the sum

$\sum _{k=1}^{n}(pk\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}q))$

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 $\{0,1,2,...,b-1\}$. For example, $7\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)=1$ is the only value we agree upon and $7\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)\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.

In particular, what I want to look at is the sum

$\sum _{k=1}^{n}(pk\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}q))$

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 $\{0,1,2,...,b-1\}$. For example, $7\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)=1$ is the only value we agree upon and $7\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)\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.

Answer & Explanation

Patrick Arnold

Expert

2022-11-18Added 21 answers

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.

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.

Most Popular Questions