2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I had a misconception thanks for clarifying $\endgroup$ – Prashant Bhanarkar Aug 12 '16 at 18:06
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.