Originally Posted by

**Gamma** I was thinking a little more about this question you have asked, and I was thinking it is probably more useful for you to prove essentially that this modulo reduction operation is a homomorphism under addition.

You probably have not gotten to this yet in your book, but the concept of a homomorphism will be important, so you might as well start to think about it now.

Consider the function $\displaystyle \phi:\mathbb{Z} \Rightarrow \mathbb{Z}_n,\phi(x)=x$ (mod n).

Now what you need to show is that it doesn't make a difference if you add two integers before you apply $\displaystyle \phi$ or after you apply $\displaystyle \phi$ to them separately. In symbols I mean:

$\displaystyle \phi(x)+\phi(y)=\phi(x+y)$

Simply apply the division algorithm to x and y to see that

$\displaystyle \phi(x)+\phi(y)=\phi(r+nk)+\phi(s+nl)=r+s$ (mod n)

$\displaystyle \phi(x+y)=\phi\left((r+nk)+(s+nl)\right)=\phi\left ((r+s) + n(k+l)\right)=r+s$ (mod n)

So now if you think about your question, associativity of addition under modular addition follows from the fact that addition is associative in $\displaystyle \mathbb{Z}$ and since this reduction mod n preserves addition, the associativity is inherited from $\displaystyle \mathbb{Z}$