Rules for Modulus and Multiplication

Rules for Modulus and Multiplication
$\begingroup$

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

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

Your Answer

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

Alexander Ross
Author

Alexander Ross

Alexander Ross has covered the video game industry for a decade, writing deep dives on game design, esports tournaments, VR developments, and gaming culture.