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.

Question

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.

Patrick Arnold · Accepted Answer

Step 1Let 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  &amp;lt;  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 2Case 1:   p  &amp;lt;  q, thus we can roughly calculate the modulo by hand.Case 2:   p  &amp;gt;  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      qFeel free to leave a comment if there&#039;re mistakes.