# Product Rule for the mod operator

If we multiply 2 number and take the mod with prime this is equivalent to first taking mod with the prime of individual number and then multiplying the result and again taking mod.

$$ab\bmod p = ((a\bmod p)(b\bmod p))\bmod p$$

does there exist any proof for this? Does it work for composite moduli too? Then I can use the Chinese remainder Theorem to calculate the result does there any other way apart from Chinese remainder Theorem to solve the problem?

It has nothing to do with prime moduli or CRT. Rather, it is true for all moduli $$\,m\,$$ as we prove as follows, where $$\ \bar x := x\bmod m =$$ remainder left after dividing $$x$$ by $$m$$.

Using $$\ x\equiv y\pmod m\color{#c00}\iff \bar x = \bar y,\,$$ and using  CPR = Congruence Product Rule

\begin{align} {\rm mod}\ m\!:\,\ a &\color{#c00}\equiv \bar a\\ b&\color{#c00}\equiv \bar b\\ \Rightarrow\,\ a\,b&\equiv \bar a\, \bar b\ \ \rm{ by}\ {\rm CPR }\\ \color{#c00}\Rightarrow\, ab\ {\rm mod}\ m &= \bar a \bar b\bmod m,\ \ {\rm i.e.}\ \ \overline{ab} = \overline{\bar a \bar b} \end{align}

Remark  Generally, as above, to prove an identity about mod as an operator it is usually easiest to first convert it into the more flexible congruence form, prove it using congruences, then at the end, convert back to operator form.

• I had a misconception thanks for clarifying – Prashant Bhanarkar Aug 12 '16 at 18:06

The remainder of the product equals the remainder of the product of the remainders....$p$ doesn't need to be prime.

$s\equiv q\pmod p$ is the same thing as saying. $s = mp+q$

$t = np+r\\ st = (nkp + nq + kr) p + qr\\ st \equiv qr \pmod p$

Sure, as long as you know $$c\equiv x \bmod p \implies c-x=py\implies c=py+x$$ It follows from FOIL, that you used in linear algebra for multiplying two binomials: $$a=pz+d\land b=pe+f\implies ab=(pz+d)(pe+f)=p(pze+ed+zf)+df$$ which then implies: $$ab\equiv df \bmod p$$