How to calculate sum of this series modulo m fast?

Question

so I came across this problem where I need to calculate this:

1^k+(1+p)^k+(1+2*p)^k+.....+(1+n*p)^k % p

Where p is prime and k is some number strictly less than p.

p is less than 500 and n*p could range upto 10⁹

The only solution I could think is iterate from first to last term and calculate the modulo using exponentiation but that would be too costly I am looking for a faster algorithm.

Is it possible to do it faster?

Answer 1

For any integer m, (1+m*p)^k % p == 1.

Thus, computing

(1^k + (1+2*p)^k  + (1+3*p)^k + ... + (1+n*p)^k )% p

is the same as computing

(1 + 1 + 1 ... + 1) % p

Where there are n + 1 terms in the parentheses.

The answer is thus (n + 1)%p.