I have trouble with computing modulo.
First, I have a summation of series like this: $$1+3^2+3^4+\cdots+3^n$$ And this is the formula which can be used to compute the series: $$S=\frac{1-3^{n+2}}{1-3^2}=\frac{3^{n+2}-1}{8}$$ Then I want to compute $S \mod 1000000007$. But if $n$ is a large number, it's really hard for me to compute it. The only thing I know is $3^{n+2}-1$ divisible by 8 (n is an even number). Could anyone give me some good hint to solve this problem?

My intention is computing $$M=\frac{3^{n+2}-1}{8} \mod 1000000007$$ For example: If $n=4000$ I must split $3^{4000+2}$ into $3^{40}3^{40}...3^{40}3^2$ and compute modulo for each part to improve speed like this: $$(3^{40}\mod 1000000007)(3^{40}\mod 1000000007)...(3^{40}\mod 1000000007)3^2$$ But how can I compute M with the above idea.

Update more
It seems related to inverse modulo. I think the problem was solved like this $$I=\frac{(1000000007+1)}{8}=125000001$$ $$\frac{3^{n+2}-1}{8} \mod 1000000007=(3^{n+2}I-I)\mod 1000000007$$ Is it right?

  • $\begingroup$ You may find something helpful in this earlier question: math.stackexchange.com/questions/26722/calculating-ab-mod-c $\endgroup$ – Gerry Myerson Oct 9 '12 at 2:30
  • $\begingroup$ So, did you look at the link I gave? Questions about raising numbers to powers in modular arithmetic have been asked and answered repeatedly on this site --- it pays to see what's been written before. $\endgroup$ – Gerry Myerson Oct 9 '12 at 5:05
  • $\begingroup$ It is true that $8I\equiv1\pmod p$ (where $p=100\dots007$), so it's true that $(3^{n+2}-1)/8\equiv3^{n+2}I-I\pmod p$. I'm not sure how much that helps you. But did you look at the link I gave? $\endgroup$ – Gerry Myerson Oct 10 '12 at 4:56
  • $\begingroup$ Yes, I found some useful things from the link, thanks. $\endgroup$ – midishero Oct 10 '12 at 5:49
  • $\begingroup$ So, the link tells you how to calculate powers in modular arithmetic. So what is it that you still have a question about? $\endgroup$ – Gerry Myerson Oct 10 '12 at 6:41

The modulo value of a geometric sum

1 + a + a^2 + ... +a^n mod m

can be calculated based on the identity (if the highest exponent is odd)

1 + a + a^2 + ... +a^(2x+1) = (1 + a)(1 + a^2 + (a^2)^2 + ... + (a^2)^x)

A complete algorithm which can deal with odd and even highest exponents looks like this in Mathematica:

geometricSeriesMod[a_, n_, m_] := 
   Module[ {q = a, exp = n, factor = 1, sum = 0, temp},

   While[And[exp > 0, q != 0],
       temp = Mod[factor*PowerMod[q, exp, m], m];
       sum = Mod[sum + temp, m];
     factor = Mod[Mod[1 + q, m]*factor, m];
     q = Mod[q*q, m];
     exp = Floor[ exp /2];

   Return [Mod[sum + factor, m]]


  • a is the "ratio" of the series. It can be any integer (including zero and negative values).
  • n is the highest exponent of the series. Allowed are integers >= 0.
  • mis the integer modulus != 0

Note: The algorithm performs a Mod operation after every arithmetic operation. This is essential, if you transcribe this algorithm to a language with a limited word length for integers.


Note that $n$ needs to be even for the formula to hold.

Hint for the first part: Let $S=1+3^2+3^4+...+3^n$. What is $3^2 \cdot S$? Can you find $S-3^2S$?

For the second part, do you know what $n$ is, or do you need a general formula? Are you familiar with the Euler Theorem?


The modulo value of a geometric sum

1 + a + a^2 + ... +a^n mod m

for n=6;

(1 + a^2+ (a^2)^2) + a((1 + a^2+ (a^2)^2))

for n is odd

1 + a(1 + a + a^2 + ... +a^(n-1))

A complete algorithm which can deal with odd and even highest exponents looks with O(log(n))like this:

typedef long long ll;

ll bigSsum(ll a, ll b,ll m)
        if(b==0) return 0;
        ll sum;
               sum =bigSsum( (a%m * a%m)%m, ( b-1  )/2, m  );
               sum = ( sum + (( a%m  )*( sum  ) )%m )%m;
               sum = ( 1 + ( ( a%m  )*sum  )%m  )%m;
               sum = bigSsum( (a%m * a%m)%m,b/2, m  );
               sum = ( sum + ( ( a%m  )*( sum  )  )%m  )%m;
     return sum%m;

To calculate $$M=\frac{3^{4000+2}-1}{8} \mod 1000000007$$ First find $$a = 8^{-1} \mod 1000000007 = 125000001$$ and $$b = 3^{4002} \mod 1000000007 = 417856696$$ then you have $$M=(b-1)*a \mod 1000000007 = 927232093$$ Wikipedia has great articles on computing the modular inverse and Modular exponentiation . These methods take $O(log(m)^2)$ time and $O(log(n)^2)$ time to compute respectively, where you have used $m=1000000007$ and $n=4000$. In Mathematica, these methods are already built in and you can find the answer with:

Mod[(PowerMod[3, 4000 + 2, 1000000007] - 1)*ModularInverse[8,1000000007], 1000000007]

You can use the property of modulus,i.e., $$(a+b)\%m = (a\%m+b\%m)\%m$$

So to calculate $$S=1+3+3^2+3^3+...$$

you can use

$$S\%M = (1\%M + 3\%M +3^2\%M +......)\%M$$

This will speed the process and even save you from integer overflow.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.