Product Rule for mod operator: $ ab\bmod p = ((a\bmod p)(b\bmod p))\bmod p$

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 $\,n\,$ as we can easily prove as follows, using notation $\ \bar x := x\bmod n\, $ for the remainder left after dividing $\,x\,$ by $\,n.$

Applying the equivalence $\ x\equiv y\pmod{\! n}\!\color{#c00}\iff \bar x = \bar y,\, $ and $\,\small \rm\color{#0a0}{CPR} =$ Congruence Product Rule

$$\begin{align} {\rm mod}\ n\!:\,\ a \,&\color{#c00}\equiv\, \bar a\\ b\,&\color{#c00}\equiv\, \bar b\\ \smash{\overset{\rm\color{#0a0}{CPR}}\Longrightarrow}\,\ \ a\:\!b \,&\equiv\, \bar a\:\!\bar b\\ \color{#c00}\Longrightarrow\ a\:\!b\bmod n \,&=\, \bar a\:\! \bar b\bmod n,\ \ {\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, using $\color{#c00}\Longleftarrow$ in the equivalence, then prove it using congruences, then at the end, convert it back to operator form, using $\color{#c00}\Longrightarrow$ in the equivalence.

For a similar example consider equivalence of fractions, $\,\frac{a}b \equiv \frac{c}d\iff ad = bc.\,$ It would be quite cumbersome to do fraction arithmetic if we required that all fractions always be in normal (reduced) form, i.e. in least terms. Instead, it proves more convenient to have the flexibility to work with arbitrary equivalent fractions. For example, this allows us to state the fraction addition rule in very simple form by first choosing convenient reps having a common denominator.

See here for further discussion on $\!\bmod\!$ as a binary operator vs. equivalence relation.


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$