In particular, what I want to look at is the sum sum_{k=1}^n (pk(mod q)) where p, q in Z >= 1 can be assumed to be coprime but it would be best if solved in the fullest generality.

MISA6zh

MISA6zh

Answered question

2022-11-17

Compute summation of modules expression?
In particular, what I want to look at is the sum
k = 1 n ( p k ( mod q ) )
where p , q Z 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 ( mod 3 ) = 1 is the only value we agree upon and 7 ( mod 3 ) 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

Patrick Arnold

Beginner2022-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 r q < n. We can calculate that the number of cycles are n q . The remaining numbers are rqmodn.
We assume that for some integer m 1 , m 2 , such that m 1 p k ( mod q ) and m 2 p k ( mod q ). By adding up the two equations we have ( m 1 m 2 ) p 0 ( mod q ). We know, for every prime p,q, they are coprime. This means that only for | m 1 m 2 | | 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 r q, thus for every set of numbers 1p,2p,...,qp, their modulo is 0 , 1 , 2 , . . . , q 1, the total sum of them is
n q i = 1 q 1 i = 1 2 n q 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 α, α p = α ( q + a ) = α q + α a α a ( mod q ). Thus the entire summation can be evaluated as follow:
k = 1 n p k mod q 1 2 n q q ( q 1 ) + i = 1 n r q i a mod q = 1 2 r ( q 2 q ) + i = 1 n r q i a mod q
Feel free to leave a comment if there're mistakes.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?