# Modular arithmetic with different moduli

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}$$

-

Unfortunately, for sufficiently large numbers $x$, the remainder of $x$ modulo $m$ has absolutely nothing to do with the remainder of $x$ modulo $n$ when $m$ and $n$ are relatively prime.

It may be possible to use some method to use the remainder modulo $2^{20}$ to accelerate the calculation of the remainder modulo $2^{96}$ (which would be the exact value) and then reduce that result modulo $2^{20} + 1$. For this particular calculation, I find it very unlikely that any such approach would be more efficient than computing it directly.

-
thanks for your answer, but do you think the nonexistence of any property for the modulus addition or subtraction is due to the nature of modular arithmetic or due to that we didn't find any relation yet? – Mohsen Afshin Dec 22 '12 at 15:48
The nature of -- in particular, I have the Chinese Remainder Theorem in mind, which says not only can $x$ have any possible pair of remainders modulo $m$ and $n$, but remainders happen uniformly in the sense that in any set of $mn$ consecutive integers, you will see each pair of possible residues exactly once. – Hurkyl Dec 22 '12 at 15:51