Take the 2-minute tour ×
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.

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

share|improve this question

1 Answer 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.

share|improve this answer
    
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
1  
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

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.