0
$\begingroup$

What is the cheapest and fastest way to find the remainder of the modular arithmetic $\pmod {n}$ when we have the reminder for $\pmod {n-1}$ or $\pmod {n+1}$ ?

As an example, if:

$$ 3^{60} \equiv 128433\pmod {2^{20}} $$

then

$$ 3^{60} \equiv ?\pmod {2^{20}+1} $$

1 Answers 1