Is $(a\cdot b)\mod n= (a\mod n)\cdot(b\mod n)$?

74 Views Asked by At

Given $a,b,n\in \mathbb{N}$, it is always true that $(a⋅b)_\mod n= (a \mod n)⋅( b\mod n)$?

($a⋅b$ is the product of $a$ and $b$, and $x \mod p$ is the residue of $x$ from dividing it from $n$)

1

There are 1 best solutions below

0
On BEST ANSWER

No, $a \cdot b$ may well be greater than or equal to $n$ even if $a$ and $b$ are both less than $n$. For example, $(2 \cdot 2) \, \operatorname{mod} 3=4 \, \operatorname{mod} 3=1$, whereas $(2 \, \operatorname{mod} 3) \cdot (2 \, \operatorname{mod} 3)=2 \cdot 2=4$.

It is true, however, that $(a \cdot b) \, \operatorname{mod} n=[(a \, \operatorname{mod} n) \cdot (b \, \operatorname{mod} n)] \, \operatorname{mod} n$.