Originally Posted by

**james121515** How would you go about proving that

$\displaystyle (a+b)\,\mbox{mod}\,n = a\,\mbox{mod}\,n + b\,\mbox{mod}\,n?$

We know by the D.A. that $\displaystyle a = nq + a',\, 0 \leq a' < n$

and $\displaystyle b = nq' + b',\,0 \leq b' < n$

These equations imply that

$\displaystyle a' = a\,\mbox{mod}\, n$

and $\displaystyle b' = b\,\mbox{mod}\,n$

Adding the first two gives:

$\displaystyle (a + b) = n(q + q') + (a' + b ')$

If I could show that $\displaystyle (a' + b') < n $, I would be done, right? Since that would imply that $\displaystyle a'+b'$ is the remainder upond dividing $\displaystyle a+ b $ by $\displaystyle n$. How how do we know that for sure?

Thanks for any help,

james