Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Possible Duplicate:
calculating $a^b \!\mod c$

I have a number of form: $p^n + p$, where $p$ is a prime number and $n$ can be any large number, for example, say $10^{12}$.

What is the generic algorithm to compute $(p^n + p) \pmod k$, where $k$ is a huge number say $k=1000000007$.


share|cite|improve this question

marked as duplicate by hardmath, Ross Millikan, Noah Snyder, Chris Eagle, Norbert Oct 8 '12 at 9:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Since adding $p$ modulo $k$ is about as easy as any operation can be, perhaps the generic question is about exponentiating $p^n$ modulo $k$, a topic dealt with in previous questions. – hardmath Oct 2 '12 at 13:32
Possible duplicate: calculating $a^b$ mod $c$. Also two more times since then, Modular exponentiation? and how to calculate $f^x$ using fast binary exponentiation? – hardmath Oct 2 '12 at 15:11
up vote 1 down vote accepted

As you already know (a+b)mod n = ((a mod n) + (b mod n)) mod n . So I guess addition here is not a problem.

The real question seems to be on $p^n$ mod k where n is large. For that, have a look at Modular Exponentiation on wikipedia.

share|cite|improve this answer
thank you , i will check it out. – JCH Oct 2 '12 at 16:56

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