modulo of series summation

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?

Update
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?

• You may find something helpful in this earlier question: math.stackexchange.com/questions/26722/calculating-ab-mod-c – Gerry Myerson Oct 9 '12 at 2:30
• 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. – Gerry Myerson Oct 9 '12 at 5:05
• 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? – Gerry Myerson Oct 10 '12 at 4:56
• Yes, I found some useful things from the link, thanks. – midishero Oct 10 '12 at 5:49
• So, the link tells you how to calculate powers in modular arithmetic. So what is it that you still have a question about? – 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],
If[EvenQ[exp],
temp = Mod[factor*PowerMod[q, exp, m], m];
sum = Mod[sum + temp, m];
exp--];
factor = Mod[Mod[1 + q, m]*factor, m];
q = Mod[q*q, m];
exp = Floor[ exp /2];
];

Return [Mod[sum + factor, m]]
]

Parameters:

• 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;
if(b&1){
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;
}
else{
sum = bigSsum( (a%m * a%m)%m,b/2, m  );
sum = ( sum + ( ( a%m  )*( sum  )  )%m  )%m;
}
return sum%m;
}

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.