Calculating sum of geometric series (mod m)

Question

I have a series

S = i^(m) + i^(2m) + ...............  + i^(km)  (mod m)   

0 <= i < m, k may be very large (up to 100,000,000),  m <= 300000

I want to find the sum. I cannot apply the Geometric Progression (GP) formula because then result will have denominator and then I will have to find modular inverse which may not exist (if the denominator and m are not coprime).

So I made an alternate algorithm making an assumption that these powers will make a cycle of length much smaller than k (because it is a modular equation and so I would obtain something like 2,7,9,1,2,7,9,1....) and that cycle will repeat in the above series. So instead of iterating from 0 to k, I would just find the sum of numbers in a cycle and then calculate the number of cycles in the above series and multiply them. So I first found i^m (mod m) and then multiplied this number again and again taking modulo at each step until I reached the first element again.

But when I actually coded the algorithm, for some values of i, I got cycles which were of very large size. And hence took a large amount of time before terminating and hence my assumption is incorrect.

So is there any other pattern we can find out? (Basically I don't want to iterate over k.) So please give me an idea of an efficient algorithm to find the sum.

Answer 1

As you've noted, doing the calculation for an arbitrary modulus m is difficult because many values might not have a multiplicative inverse mod m. However, if you can solve it for a carefully selected set of alternate moduli, you can combine them to obtain a solution mod m.

Factor m into p_1, p_2, p_3 ... p_n such that each p_i is a power of a distinct prime

Since each p is a distinct prime power, they are pairwise coprime. If we can calculate the sum of the series with respect to each modulus p_i, we can use the Chinese Remainder Theorem to reassemble them into a solution mod m.

For each prime power modulus, there are two trivial special cases:

If i^m is congruent to 0 mod p_i, the sum is trivially 0.

If i^m is congruent to 1 mod p_i, then the sum is congruent to k mod p_i.

For other values, one can apply the usual formula for the sum of a geometric sequence:

S = sum(j=0 to k, (i^m)^j) = ((i^m)^(k+1) - 1) / (i^m - 1)

TODO: Prove that (i^m - 1) is coprime to p_i or find an alternate solution for when they have a nontrivial GCD. Hopefully the fact that p_i is a prime power and also a divisor of m will be of some use... If p_i is a divisor of i. the condition holds. If p_i is prime (as opposed to a prime power), then either the special case i^m = 1 applies, or (i^m - 1) has a multiplicative inverse.

If the geometric sum formula isn't usable for some p_i, you could rearrange the calculation so you only need to iterate from 1 to p_i instead of 1 to k, taking advantage of the fact that the terms repeat with a period no longer than p_i.

(Since your series doesn't contain a j=0 term, the value you want is actually S-1.)

This yields a set of congruences mod p_i, which satisfy the requirements of the CRT. The procedure for combining them into a solution mod m is described in the above link, so I won't repeat it here.

Answer 2

@Jim Lewis: I think that can be done only if m has non-repeated prime factors. eg-: if m=2*2*3*5*5 where 2 & 5 are repeated then CRT can't be used here.

Answer 3

@Jim and aditya -> hmmm... consider the number 199999.. this is a prime number...so u have to iterate 199999 times while finding the sum (sum(j=0 to k, (i^m)^j) u dont have to iterate till k, just till p_i).. isnt this what 'aditya' was doing in the first place - looping till he found a cycle.. and isnt this what you said was not acceptable? or have i missed smthn here?