# Multiplication group modulo n is well defined,associative

For positive integers N>1, the positive integers less than N and coprime to N form a multiplicative group modulo N.

How can I prove that the multiplication table for this group is well defined?

How can I prove that this group satisfies the associative group axiom? It's easy to prove the closure axiom and identity/inverse axiom, but I have no idea how to prove associativity.

-
Hint: is the multiplication inherited from some structure on which associativity is known? – Jonathan Y. Sep 22 '13 at 20:47

To check that an operation is well-defined, the usual issue is that you're defining the operation on representatives of equivalence classes, when the operation is actually supposed to be defined on the equivalence classes themselves. Here, this means that we need to check that if $(a+Nx)(b+Ny)=c+Nz$ for some $x,y,z$, then $(a+Nx')(b+Ny')=c+Nz'$ for any other $x',y',z'$. [why is this the right thing to check?]

Do you know about cosets? You should probably use those to deal with associativity. In any case, it's not too tedious to do the work manually. $((a+Nx)(b+Ny))(c+Nz)=\cdots?$

-
I don't understand. In this group, x=x'=y=y'=0. – alek_dv Sep 22 '13 at 21:02
@alek_dv: Ah, you are using a different definition than I am. In that case, I'm not sure what your concern is. In what way are you worried that this operation might not be well-defined? – Eric Stucky Sep 22 '13 at 21:25

Let $\overline a$ denote the class of the integer $a\in \mathbb Z$ modulo $N$. We are working in $$G=\{\overline a\in \mathbb Z/N\mathbb Z\,:\,\textrm{gcd}\,(a,n)=1\}.$$ You said that you proved the "closure" axiom so I assume you know that the product in $G$ is just $\overline a\cdot\overline b:=\overline{ab}$, where $ab$ denotes the product in $\mathbb Z$. Hence $$(\overline{a}\cdot\overline b)\cdot \overline c=\overline{ab}\cdot \overline c=\overline{(ab)c}\overset{\ast}{=}\overline{a(bc)}=\overline{a}\cdot\overline{bc}=\overline a\cdot(\overline b\cdot \overline c).$$ We used associativity in $\mathbb Z$ in $\ast$.

Added. Let us show $\overline a\cdot \overline b=\overline{ab}$ is well-defined. Let us change the representatives: $$\overline a=\overline{a'},\,\,\,\,\,\overline b=\overline{b'}.$$ This means $$a-a'=hN,\,\,\,\,\,b-b'=kN\,\,\,\,\,\textrm{some }h,k\in\mathbb Z.$$ We have to show that changing representatives does not change the result, i.e. our claim is: $\overline{a'}\cdot \overline{b'}=\overline{ab}$. So: $$\overline{a'}\cdot \overline{b'}=\overline{a'b'}=\overline{(a+hN)(b+kN)}=\overline{ab+N(ak+bh+hkN)}=\overline{ab}.$$

-
Thanks. This is the prove for associativity. Can you prove the multiplication table is well defined? – alek_dv Sep 22 '13 at 21:11