Compute summation of modules expression?In particular, what I want to look at is the sum...
Compute summation of modules expression?
In particular, what I want to look at is the sum
where 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 . For example, is the only value we agree upon and .
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
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 . We can calculate that the number of cycles are . The remaining numbers are rqmodn.
We assume that for some integer , such that and . By adding up the two equations we have . We know, for every prime p,q, they are coprime. This means that only for . 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 , thus for every set of numbers 1p,2p,...,qp, their modulo is , the total sum of them is
Case 1: , thus we can roughly calculate the modulo by hand.
Case 2: , we can assume 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 , . Thus the entire summation can be evaluated as follow:
Feel free to leave a comment if there're mistakes.