How to compute $(a+1)^b\pmod{n}$ using $a^b\pmod{n}$?

Question

As we know, we can compute $a^b \pmod{n}$ efficiently using Right-to-left binary method Modular exponentiation. Assume b is a prime number . Can we compute directly $(a+1)^b\pmod{n}$ using $a^b\pmod{n}$?

Answer 1

In general no, but yes in some special cases, e.g. if $\ n\mid \pm a^k\! +\! a\! +\! 1\,$ for small $\,k\,$ then

${\rm mod}\ n\!:\,\ \color{#c00}{a\!+\!1\,\equiv\, \pm a^k}\,\Rightarrow\, (\color{#c00}{a\!+\!1})^b \equiv (\color{#c00}{\pm a^k})^b\equiv (\pm1)^b (a^b)^k$

so you need only raise the known result $\,a^b\,$ to a small power $\,k\,$ to get the result.