Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|cite|improve this question
You may find something helpful in this earlier question: – 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

2 Answers 2

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.

share|cite|improve this answer

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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