My question is rather simple as I'm interested about modulus and multiplication, specifically whether it holds that $(a*b)\,mod\,n=(a\,mod\,n)*(b\,mod\,n)$?
$\endgroup$ 45 Answers
$\begingroup$Not quite, the correct rule is
$$(ab\bmod m)=((a\bmod m)(b\bmod m))\bmod m$$ because the product $(a\bmod m)(b\bmod m)$ can very well exceed $m$ (it actually lies in range $[0,(m-1)^2]$).
$\endgroup$ 4 $\begingroup$$\begin{array}{}a\pmod n\equiv \tilde a\iff a=np+\tilde a\\ b\pmod n\equiv \tilde b\iff b=nq+\tilde b\end{array}$
$ab=n(npq+q\tilde a+p\tilde b)+\tilde a\tilde b\implies ab\equiv \tilde a\tilde b\pmod{n}$
$\endgroup$ $\begingroup$Hint: $a=nr_1+s_1, b=nr_2+s_2$ where $r_1, r_2, s_1, s_2 \in \mathbb{Z}$ and $0\leq s_1< n, 0 \leq s_2 < n$. Then $$a\,\,(mod\,\, n)=?$$ $$b\,\,(mod \,\, n)=?$$ $$ab\,\, (mod\,\, n) = ?$$ Can you conclude from here?
$\endgroup$ $\begingroup$In modular arithmetic there are two equivalent expressions: $$a \bmod n = a_1 \iff a \equiv a_1 (\bmod n)$$ $$b \bmod n = b_1 \iff b \equiv b_1 (\bmod n)$$ $$(ab) \bmod n = c_1 \iff (ab) \equiv c_1 (\bmod n)$$ According to the multiplication property (see: here): $$(ab) \equiv (a_1b_1) \equiv c_1 (\bmod n)$$ For example: $a=5,b=8,n=3$: $$5 \equiv 2 (\bmod 3)$$ $$8 \equiv 2 (\bmod 3)$$ $$(5\cdot 8) \equiv (2\cdot2) \equiv 1 (\bmod 3)$$
$\endgroup$ 1 $\begingroup$The statement
for all integers $a$ and $b$, $(ab)\bmod n=(a\bmod n)(b\bmod n)$
only holds for $n=1$ or $n=2$. The case $n=1$ is trivial, as $a\bmod 1=0$ for every integer $a$. For $n=2$ it's easy as well, because $a\bmod 2=0$ if $a$ is even and $a\bmod 2=1$ if $a$ is odd (just check the four cases).
There is already a counterexample for $n=3$: indeed $$ (2\cdot2)\bmod 3=1 \qquad (2\bmod 3)(2\bmod 3)=4 $$ For general $n>2$ the counterexample is similar: take $a=b=n-1$; then $$ (ab)\bmod n=(n^2-2n+1)\bmod n=1 $$ whereas $$ (a\bmod n)(b\bmod n)=(n-1)^2=n^2-2n+1=n(n-2)+1>1 $$
$\endgroup$
