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.

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.

share|improve this question
1  
Hint: is the multiplication inherited from some structure on which associativity is known? –  Jonathan Y. Sep 22 '13 at 20:47

2 Answers 2

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?$

share|improve this answer
    
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}.$$

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

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.