Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

Of course

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


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}

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.