1

Is there any general expansion for 'a mod mn' ?
mod is modulo operation: http://en.wikipedia.org/wiki/Modulo_operation

Eg: we have 
(a + b ) mod n = ((a mod n) + (b mod n)) mod n
(a x b ) mod n = ((a mod n) x (b mod n)) mod n
Similarly, Is there any simplification/expansion for :
a mod (m x n) = ?

Thanks

Edit: Added example for clarification

Venkateshwar
  • 113
  • I think maybe you want to look at the Chinese remainder theorem. But it is possible that I haven't understood your question. And perhaps the wikipedia article is not the best source if you try to understand why this is relevant. It's past my bedtime, I'll have to leave this in the hands of people more awake than I am. – Harald Hanche-Olsen May 06 '13 at 21:59

1 Answers1

1

There is no really simple rule here. There is a not so simple one, which may not be what you want, but here we go: This rule assumes that $m$ and $n$ have no common factor, i.e., that $\gcd(m,n)=1$. In this case you can use the extended Euclidean algorithm (Bézout's identity) to find integers $u$ and $v$ so that $$mu+nv=1.$$ Now assume $$\begin{aligned}a&\equiv r\pmod{m},\\a&\equiv s\pmod{n}.\end{aligned}$$ So there are integers $p$, $q$ so that $a=pm+r$ and $a=qn+s$. Multiply the former equation by $n$ and the latter by $m$ to get $$\begin{aligned}am&\equiv rm\pmod{mn},\\an&\equiv sn\pmod{mn}.\end{aligned}$$ From this you get $$a=a\cdot 1=amu+anv\equiv rmu+snv\pmod{mn}$$ which is a connection between $a\bmod mn$ on one hand and $r=a\bmod m$ and $s=a\bmod n$ on the other.

This reduction is quite useful in applications such as RSA encryption, where you need to compute large powers modulo a product of two large primes. It is enough to compute the power modulo each factor and then combine the results.

Harald Hanche-Olsen
  • 31,960