The Groups Of Units In Zm, m>1

    Let m>1.  Think of the elements of Zm as {0, 1, ..., m-1} (the elements are actually equivalence classes, j=j+mZ, where j can be chosen from [0,m-1]).  The units of a ring, such as Zm, are the elements which are invertible for multiplication.  Thus a in Zm is a unit if and only if there is some b in Zm such that ba=1 (with multiplication mod m).  Thus, m divides (ba-1) and hence 1=ba+mx for some integer x.  Recall that gcd(a,m) is the least positive integer of the form ya+xm for some integers y and x.  Evidently, if a is a unit in Zm, 1 is the gcd (a,m) and hence a is relatively prime to m.  Conversely, if a is relatively prime to m, then 1=ya+xm for some integers y and x.  Then m divides 1-ya, and hence 1=y a in Zm.  Hence a is invertible in Zm.  In summary, for m>1, a is invertible in Zm if and only if a is relatively prime to m.

Theorem.  For m > 1, a homomorphism f from Zm to Zm is an automorphism if and only f(1)=a where a is relatively prime to m.  For m>1, the group of automorphisms is isomorphic to the group of units in Zm; in particular, if one has automorphisms f and g, then (fg)(1)=f(1)*g(1) (multiplication in Zm).

Proof.  Let a=f(1), a in [0,m-1].  Note that f(0)=0=0 a.  Also note that f(2)=f(1+1)=f(1)+f(1)=a+a=a+a= 2a = 2 a in Zm. Suppose that, for some n>1, f(n)=n a.  Then f(n+1)=f(n+1)=f(n)+f(1)=na+a=na+a=(n+1)a  = n+1 a.  Thus, by the principle of induction, f(n)=n a for all integers n>-1.

    Suppose that f is an automorphism.  Then f is onto and 1 = n a for some integer n in [0, m-1].  Then a is invertible in Zm and hence a is relatively prime to m.  Conversely, suppose that a is relatively prime to m.  Then a is invertible in Zm and there is some b in Zm such that b a = 1.  For any t in [0, m-1],

f(tb) =  (tb) a = t ( b a) = t 1 = t.

Thus f is onto Zm.  Since f is a function and Zm is finite, f being onto Zm forces f to be 1-1.  Thus f is an isomorphism from Zm to Zm and hence an automorphism.

    The mapping W(f)=f(1) is clearly 1-1 and onto from the Aut(G) to the units of Zm.  Note that, for automorphism f and g, the multiplication is the composition of functions, and thus (fg)(1)=f(g(1))=g(1)*f(1) (with the latter multiplication in Zm) by the first paragraph of this proof.  Since Zm has a commutative multiplication, g(1)*f(1)=f(1)*g(1).  Thus, W(fg)=W(f)*W(g) and W is a homomorphism (and hence an isomorphism).

QED

 

m

Units in Zm

 Isomorphic
Group ID		 Comment
1 { } The units do not form a group. Groups must be non-empty.
2 {1} <0> or Z1 The one-element group is unique up to isomorphism.
3 {2,3} Z2 When p is prime, the units in Zp always form a cyclic group of order p-1.
4 {1,3} Z2 Note that 3*3=1 mod 4.  Also there is a unique group of order 2.
5 {1,2,3,4} Z4 Note that 22=4, 23=3, and 24=1 mod 5.  See remark above at m=3.
6 {1,5} Z2 Note that 5*5=1 mod 6.
8 {1,3,5,7} (Z2)x(Z2) Note that 3*3=1, 5*5=1, and 7*7=1 mod 8.  Also, 3*5=7 mod 8.  This is the structure of the Klein group, the direct product of Z2 with itself.  Let f(0,0)=1, f(1,0)=3, f(0,1)=5, and f(1,1)=8.  Then f is an isomorphism from (Z2)x(Z2) to {1,3,5,7}.
9 {1,2,4,5,7,8} Z6 Note that 22=4,23=8,24=7,25=5,and 26=1 mod 9.
10 {1,3,7,9} Z4 Note that 32=9,33=7,and 34=1 mod 10.
12 {1,5,7,11} (Z2)x(Z2) Note that 52=1,72=1,112=1 mod 12.  Also, 5*7=11 mod 12.  See Z8 above for the isomorphism.
14 {1,3,5,9,11,13} Z6 3 generates this group.  32=9,33=13, 34=11, 35=5, and 36=1 mod 14.
15 {1,2,4,7,8,
11,13,14}		 (Z2)x(Z4) Here is an isomorphism.  f(1,0)=11, f(0,1)=2.  Note that 2 has order 4:  22=4,23=8,24=1.  Also, 11 has order 2:  112=1.

  • Of course, f(0,2)=4, f(0,3)=8 and f(0,0)=1.

  • 11*2=7.  Let f(1,1)=7.

  • 11*4=14.  Let f(1,2)=14.

  • 11*8=13.  Let f(1,3)=13.

We need a nice lemma about this to prove that it is indeed an isomorphism (without doing lots of work).  See the lemma below.
16 {1,3,5,7,9,
11,13,15}		 (Z2)x(Z4) Here is an isomorphism.  f(1,0)=7; note that 72=1.  f(0,1)=3.  Note that 32=9,33=11, and 34=1.

  • f(0,2)=9, f(0,3)=11, and f(0,0)=1.

  • 7*3=5; let f(1,1)=5.

  • 7*9=15; let f(1,2)=15.

  • 7*11=13; let f(1,3)=13.
18 {1,5,7,11,
13,17}		 Z6 5 generates this group:  52=7, 53=17,54=13,55=11, and 56=1.
20 {1,3,7,9,11,
13,17,19}		 (Z2)x(Z4) Here is an isomorphism.  f(1,0)=11; note that 112=1.  f(0,1)=3.  Note that 32=9,33=7, and 34=1.

  • So, f(0,2)=9, f(0,3)=7 and f(0,0)=1.

  • 11*3=13.  Let f(1,1)=13.

  • 11*9=19.  Let f(1,2)=19.

  • 11*7=17.  Let f(1,2)=17.
21

{1,2,4,5,8,10,11,
13,16,17,19,20}

 (Z2)x(Z6) Let f(1,0)=13; note that 132=1.  Let f(0,1)=2.  Note that 22=4, 23=8, 24=16, 25=11, and 26=1.

  • Let f(0,2)=4, f(0,3)=8, f(0,4)=16, f(0,5)=11 and f(0,0)=1.

  • 13*2=5; let f(1,1)=5.

  • 13*4=10; let f(1,2)=10.

  • 13*8=20; let f(1,3)=20.

  • 13*16=19; let f(1,4)=19.

  • 13*11=17; let f(1,5)=17.
22 {1,3,5,7,9,13,
15,17,19,21}		 Z10 7 generates this group:  72=5, 73=13, 74=3, 75=21, 76=15, 77=17, 78=9, 79=19, and 710=1.
24 {1,5,7,11,13,
17,19,23}		 (Z2)x(Z2)x(Z2) Note that x2=1 for all units x in Z24.  Here is an isomorphism.  Let f(0,0,0)=1, f(1,0,0)=5, f(0,1,0)=7, and f(0,0,1)=13.

  • 5*7=11.  Let f(1,1,0)=11.

  • 5*13=17.  Let f(1,0,1)=17.

  • 7*13=19.  Let f(0,1,1)=19.

  • 5*7*13=23.  Let f(1,1,1)=23.
25 {1,2,3,4,6,7,
8,911,12,13,
14,16,17,18,19,
21,22,23,24}		 Z20 Note that 2 generates the group:  22=4, 23=8, 24=16, 25=7, 26=14, 27=3, 28=6, 29=12, 210=24, 211=23, 212=21, 213=17, 214=9, 215=18, 216=11, 217=22, 218=19, 219=13, and 220=1.
26 {1,3,5,7,9,
11,15,17,19,
21,23,25}		 Z12 Note that 7 generates the group:  72=23, 73=5, 74=9, 75=11, 76=25, 77=19, 78=3, 79=21,710=17, 711=15, and 712=1.
27 {1,2,4,5,7,8,
10,11,13,14,
16,17,19,20,
22,23,25,26}		 Z18 Note that 2 generates this group:  22=4, 23=8, 24=16, 25=5, 26=10, 27=20, 28=13, 29=26, 210=25, 211=23, 212=19, 213=11, 214=22, 215=17, 216=7, 217=14, and 218=1.
28 {1,3,5,9,11,
13,15,17,19,
23,25,27}		 (Z2)x(Z6) Let f(1,0)=15; note that 152=1.  Let f(0,1)=3.  Note that 32=9, 33=27, 34=25, 35=19, and 36=1.
  • Let f(0,2)=9, f(0,3)=27, f(0,4)=25, f(0,5)=19 and f(0,0)=1.
  • 15*3=17.  Let f(1,1)=17.
  • 15*9=23.  Let f(1,2)=23.
  • 15*27=13.  Let f(1,3)=13.
  • 15*25=11.  Let f(1,4)=11.
  • 15*19=5.  Let f(1,5)=5.
30 {1,7,11,13,
17,19,23,29}		 (Z2)x(Z4) Here is an isomorphism:  let f(0,0)=1, f(1,0)=11, and f(0,1)=7.  Note that 112=1; also 72=19, 73=13 and 74=1.

  • Let f(0,2)=19 and f(0,3)=13.

  • 11*7=17.  Let f(1,1)=17.

  • 11*19=29.  Let f(1,2)=29.

  • 11*13=23.  Let f(1,3)=23.
 

Homomorphism Lemma.  Let f be a function from a commutative group G into a group H.  Suppose that G is generated by a non-empty subset X of G.  Also suppose that the following two conditions hold for f:

  1. For all x in X, |x| is finite and |f(x)| is 0 or |f(x)| divides |x|.
  2. For any n>-1, let a1, ... an be distinct members of X.  Suppose that for any non-negative integer exponents k(1), ... k(n), with each k(j)<|xj|,  f((a1)k(1)(a2)k(2)....(an)k(n))=[f(a1)]k(1)*[f(a2)]k(2)*...[f(an)]k(n).

Then f is a homomorphism.

Proof.  Let x be in X (X is not empty).  Since x0=eG, f(x0)=[f(x)]0=eH.  Thus, f(eG)=eH.  Note also, that if x in X has order q, x xq-1=eG and thus xq-1=x-1.  For any non-negative integer k, k can be written as mq+r for some r in [0, q-1].  Then xk=xmqxr=(xq)m xr = (eG)m xr = eG xr =xr.  Likewise, for any negative integer k, xk=(xq-1)(-k)=x[(1-q)k].  Note that (1-q)k>-1 and hence the case of non-negative k applies:   xk=x[(1-q)k]=xr where r is in [0,q-1] and (1-q)k=mq+r for some m.

Let v and w be members of G.  Each is a product of members of X.  So for each there is some integer n>-1, some a1, a2, ..., an in X and integers k1, ..., kn such that each equals a product of the form


(a1)k(1)(a2)k(2)....(an)k(n)

Since G is commutative, the ai's with their respective exponents can be written in any order.  If ai=aj, combine those two factors as (ai)[k(i)+k(j)].  Continue to combine factors which have equal bases for the exponents, until the remaining bases in each exponential factor are all distinct.  By the previous paragraph, we can replace the exponent on each ai by an integer in [0,|ai|).  Do this as well.

    Thus we may write v and w as follows, with distinct bases from X among the factors for each of v and w, separately, and with exponents in [0,q-1) where q is the order of the base for that exponent:

v=(a1)k(1)(a2)k(2)....(an)k(n) and w=(b1)j(1)(b2)j(2)....(bm)j(m).

 

Case 0.  Suppose m=0, that w is the "empty" product (and hence equals eG).  Then vw=veG=v.  Hence, vw = (a1)k(1)(a2)k(2)....(an)k(n) , with distinct ai's from X and exponents in the ranges need to apply condition (2) of the lemma.  Hence

f(vw) = [f(a1)]k(1)*[f(a2)]k(2)*...[f(an)]k(n)
         = [f(a1)]k(1)*[f(a2)]k(2)*...[f(an)]k(n) eH
         = f(v)f(eG)
         = f(v)f(w).

Induction Step.  Assume that f(vw)=f(v)f(w), for all v in G and any w that can be written as a product of powers of m distinct members of X, with the exponents non-negative and less than the order of the base element for which the exponent serves.  Consider any v in G and any w in G such that w can be written as a product of powers of m+1 distinct members of X, with the exponents non-negative and less than the order of the base element for which the exponent serves.  For distinct bj's in X and appropriately restricted exponents,

w=(b1)j(1)(b2)j(2)....(bm+1)j(m+1).

Of course, v is a similar such product:

v=(a1)k(1)(a2)k(2)....(an)k(n).

Note that by the associative law,

vw=[(a1)k(1)(a2)k(2)....(an)k(n)(b1)j(1)][(b2)j(2)....(bm+1)j(m+1)].

The induction hypothesis applies to the right hand side of the equation above:

f(vw) = f([(a1)k(1)(a2)k(2)....(an)k(n)(b1)j(1)]) f([(b2)j(2)....(bm+1)j(m+1)]).

If b1 is distinct from each of the aj's, condition (2) of this lemma applies to the right hand side above:

f(vw) = {[f(a1)]k(1)*[f(a2)]k(2)*...[f(an)]k(n) [f(b1)]j(1) }{[f(b2)]j(2)*[f(b2)]j(2)*...[f(bm+1)]j(m+1)}
         = {[f(a1)]k(1)*[f(a2)]k(2)*...[f(an)]k(n) } {[f(b1)]j(1) [f(b2)]j(2)*[f(b2)]j(2)*...[f(bm+1)]j(m+1)}
            (by the associative law)
         = f(v)f(w) by condition (2) of this lemma.

Suppose there is some s such that b1=as.  Because G is commutative, the factors of

z=[(a1)k(1)(a2)k(2)....(an)k(n)(b1)j(1)]

can be rearranged with as and b1 together.  Then replace those two factors by (as)(k(s)+j(1)).  With m(s) as the order of as, replace the exponent k(s)+j(1) by t(s) in [0,m(s)) such that m(s) divides k(s)+j(1)-t(s).  Let dm(s)=k(s)+j(1)-t(s).  Thus, t(s)= k(s)+j(1)-dm(s).  Hence

z = [(a1)k(1)(a2)k(2)... (as-1)k(s-1) (as)t(s) (as+1)k(s+1)...(an)k(n)],

with the bases a1, ..., an all distinct members of X and the exponents meeting the requirements of condition (2) of the lemma.  By condition (2) above,

f(z) = {[f(a1)]k(1)*[f(a2)]k(2)*... [f(as-1)]k(s-1) [f(as)]t(s) [f(as+1)]k(s+1)......[f(an)]k(n) }.

Because the order of f(as) is 0 or it divides the order of as, which is labeled m(s) here, [f(as)](-dm(s))=eH.  Thus,

[f(as)]t(s) = [f(as)]k(s)+j(1)-dm(s) 
               = [f(as)]k(s) [ [f(as)]j(1) [ [f(as)]-dm(s) 
               = [f(as)]k(s) [ [f(as)]j(1) eH
               = [f(as)]k(s) [ [f(as)]j(1).

Because G is commutative, and condition (2) holds for the given factorization of v, the factors of f(z) can be rearranged so that

f(z) = {[f(a1)]k(1)*[f(a2)]k(2)*... [f(as-1)]k(s-1) [f(as)]k(s) [f(as+1)]k(s+1)......[f(an)]k(n) [f(b1)]j(1) }
      = {f(v) [f(b1)]j(1) }.

Hence,

f(vw) = f(z) f([(b2)j(2)....(bm+1)j(m+1)])
         = {f(v) [f(b1)]j(1) }* {[f(b2)]j(2)*[f(b2)]j(2)*...[f(bm+1)]j(m+1)},
           (by condition (2), which applies to given factorization with the bj's),
         = f(v) {  [f(b1)]j(1)  f(b2)]j(2)*[f(b2)]j(2)*...[f(bm+1)]j(m+1) },
            (by the associative law),
         = f(v) f(w), because condition (2) applies to the given factorization of w.

Thus, given the truth for m, we have the truth for m+1.  By the principle of induction, the truth holds for all m.  Recall from above, that any w in G can be written as a product of powers of elements of X with the product satisfying condition (2) of this lemma.  Thus, for all v and w in G, f(vw)=f(v)f(w).  That makes f a homomorphism from G into H.

QED