proving that addition modulo n is associative

Hello math helpers, I hope that I do not get accused of hijacking this thread but I think my question is relevant.

I am just starting to learn some elementary group theory and I am puzzled as to how one goes about proving that addition modulo n is associative. Strangely I have found a proof that shows the addition of congruence classes modulo n is associative and I understand that but I cannot seem to apply it to addition modulo n for integers.

Any help would be most appreciated.

Good old fashioned algebra

See the thing we need to remember that when dealing with modular arithmetic is that they are equivalence classes.

a~b (mod n) iff n|(a-b).

So you usually denote the equivalence class containing a as $\displaystyle [a]=\{x\in \mathbb{Z}|n|(x-a)\}= \{a+nk|k\in \mathbb{Z}\}$. So what we really need to do is check that the following sets are the same.

$\displaystyle ([a]+[b])+[c]=[a]+([b]+[c])$

$\displaystyle [(a+nk) + (b + nl)]+(c+nj)=[(a+b)+n(k+l)]+(c+nj)=$$\displaystyle (a+b+c)+n(k+l+j)=a+nk+[(b+c)+n(l+j)]=a+nk+[(b+nl) + (c+nj)]=$

The above quantity shows fwhen read from left to right that $\displaystyle ([a]+[b])+[c]\subset [a]+([b]+[c])$

And from right to left we get $\displaystyle ([a]+[b])+[c]\supset [a]+([b]+[c])$

so

$\displaystyle ([a]+[b])+[c]=[a]+([b]+[c])$

I think this is the proof you are looking for, but you notice the proof still comes down to the fact that addition in the integers is associative, this is because we have simply imposed an equivalence relation on the integers.

equivalence class containing a Vs class just containg a

Hi there Gamma

May I thank-you once again for your help, I appreciate it very much.

I see your point that using $\displaystyle [a]=\{x\in \mathbb{Z}|n|(x-a)\}= \{a+nk|k\in \mathbb{Z}\}$ to denote the congruence class containing $\displaystyle a$, you have shown, using the associativity property of addition, that addition of congruence classes is also associative. Forgive my ignorance but do we not need to show this for the sets containg just $\displaystyle a$,$\displaystyle b$ and $\displaystyle c$ or is this somehow automatically proved?

For example can I modify your proof somehow by using your previous definition of an interger using the division algorithm $\displaystyle a=r+nf$ say, to get

$\displaystyle (a+b)+c$ (mod n)=$\displaystyle (r+nf + s + ng)+(t+nh)$ (mod n)=??=$\displaystyle a+(b+c)$ (mod n).

Or do we just now somehow limit the set notation for the congruence class containing a to be the set just containing a, for example something like

$\displaystyle [a]=\{x\in \mathbb{Z}|n|(x-a),x-a=a\}= a$?

Any help as ever will be welcomed.

problems with notation for modulo n

Hi there math helpers.

As you can see I have been trying to follow this thread for a while now and am still struggling despite huge amounts of help from Gamma. I am reasonably familiar now I think with the concept of modulo n, addition modulo n, congruence classes etc.

I am trying to show that addition modulo n is associative, the usual way to write this is

$\displaystyle (a + b) + c (mod n) = a + (b + c) (mod n)$.

Now I think this notation is confusing. For example if I use some notation that Gamma used in one of his previous replies, that is $\displaystyle \phi(x)=x(mod n)$ then in words this means obviously to divide x by n and take the remainder. The expression $\displaystyle \phi(x+y)$ then means to add x and y and to then divide by n and take the remainder. So my question is can I write

$\displaystyle (a + b) + c (mod n) = a + (b + c) (mod n)$

as

$\displaystyle \phi( \phi(a+b) + c)=\phi( a + \phi(b+c))$

or should it be

$\displaystyle \phi((a+b) +c)=\phi(a + (b+c))$

??

If the last expression is correct then I can see that the proof of associativity is easy, if the first expression is the correct one then I am still struggling with this proof!

Any help would be greatly appreciated.