Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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}

share|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
add comment

Your Answer

 
discard

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.