2
$\begingroup$

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?

  • 0
    You may find something helpful in this earlier question: http://math.stackexchange.com/questions/26722/calculating-ab-mod-c2012-10-09
  • 0
    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.2012-10-09
  • 0
    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?**2012-10-10
  • 0
    Yes, I found some useful things from the link, thanks.2012-10-10
  • 0
    So, the link tells you how to calculate powers in modular arithmetic. So what is it that you still have a question about?2012-10-10

4 Answers 4