2
$\begingroup$

We know that $(a*b) \pmod n \equiv (a \pmod n * b \pmod n) \pmod n$.

What other distributive attributes of the mod exist? Specifically when we have:

$(a + b + c) \pmod n \equiv ?$

1 Answers 1

2

Of course

$(a+b+c)\equiv(a\pmod n+b\pmod n+c\pmod n)\pmod n$

update:

Actually, we can prove the general case, which is $\left(\sum_{i=1}^na_i\right)\equiv\sum_{i=1}^n\left(a_i\pmod n\right)\pmod n$

And this can be proved using induction.

For the base case, we need to prove $(a_1+a_2)\equiv(a_1\pmod n+a_2\pmod n)\pmod n$

Move the right side to left then we need to prove $(a_1+a_2-a_1\pmod n-a_2\pmod n)\equiv0\pmod n$

Assume $a_1=d_1\cdot n+r_1$, $a_2=d_2\cdot n+r_2$, where $0\leq r_1, r_2 are the residue modulo $n$. It is obvious that $r_1=a_1\pmod n$ and $r_2=a_2\pmod n$.

As a result, $a_1-a_1\pmod n=d_1\cdot n$ and $a_2-a_2\pmod n=d_2\cdot n$. Therefore, it holds that $(a_1+a_2-a_1\pmod n-a_2\pmod n)=(d_1\cdot n+d_2\cdot n)\equiv0\pmod n$

So the base case is proved. And the induction step is trivial, \begin{eqnarray} \left(\sum_{i=1}^na_i\right)&=&\left(\sum_{i=1}^{n-1}a_i\right)+a_n\\ &\equiv&\left(\left(\sum_{i=1}^{n-1}a_i\right)\pmod n+a_n\pmod n\right)\pmod n\;\;(\textrm{by base case})\\ &\equiv&\left(\sum_{i=1}^{n-1}\left(a_i\pmod n\right)+a_n\pmod n\right)\pmod n\;\;(\textrm{by induction hypothesis})\\ &\equiv&\sum_{i=1}^n\left(a_i\pmod n\right)\pmod n \end{eqnarray}

  • 0
    Thank you very much my friend.2012-10-28