title: Calculating sum of geometric series (mod m)
body: <p>I have a series </p>
  
  <pre><code>S = i^(m) + i^(2m) + ...............  + i^(km)  (mod m)   
  
  0 &lt;= i &lt; m, k may be very large (up to 100,000,000),  m &lt;= 300000
  </code></pre>
  
  <p>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).</p>
  
  <p>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 <code>i^m (mod m)</code> and then multiplied this number again and again taking modulo at each step until I reached the first element again.</p>
  
  <p>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.</p>
  
  <p>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.</p>