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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
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 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.

share|cite|improve this answer

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

 
discard

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.