# Distribution of $\bmod$ on the $+$ operator

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

-

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

-
Thank you for your answer. Can you provide proof? – Khaled Oct 27 '12 at 10:56
I provided a proof. Hope you understand it. – user46090 Oct 27 '12 at 11:37
Thank you very much my friend. – Khaled Oct 28 '12 at 9:27