Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

452 ALGEBRAIC SYSTEMS [APP. B

(1) Proof thatis well-defined: We have([a])=f(a). Sincea∈S, we havef(a)∈f(S). Hence([a])∈f(S),

as required. Now suppose[a]=[b]. Thena∼band hencef(a)=f(b). Thus

([a])=f(a)=f(b)=([b])

That is,is well-defined.

(2) Proof thatis an isomorphism: Sincefis a homomorphism,

([a][b])=[ab]=f(ab)=f(a)f(b)=([a])([b])

Henceis a homomorphism. Suppose([a])=([b]).Thenf(a)=f(b), and soa∼b. Thus[a]=[b]and

is one-to-one. Lastly, lety∈f(S). Then,f(a)=yfor somea∈S. Hence([a])=f(a)=y. Thusis

ontof(S). Accordingly,is an isomorphism.

GROUPS

B.6.Consider the groupG={ 1 , 2 , 3 , 4 , 5 , 6 }under multiplication modulo 7.

(a) Find the multiplication table ofG.(b) Find 2−^1 ,3−^1 ,6−^1.

(c) Find the orders and subgroups generated by 2 and 3. (d)IsGcyclic?

(a) To finda∗binG, find the remainder when the productabis divided by 7.

For example, 5· 6 =30 which yields a remainder of 2 when divided by 7; hence 5∗ 6 =2inG. The multiplication

table ofGappears in Fig. B-6(a).

(b) Note first that 1 is the identity element ofG. Recall thata−^1 is that element ofGsuch thataa−^1 =1. Hence

2 −^1 =4, 3−^1 =5 and 6−^1 =6.

(c) We have 2^1 =2, 2^2 =4, but 2^3 =1. Hence| 2 |=3 andgp(2)={1, 2, 4}. We have 3^1 =3, 3^2 =2, 3^3 =6,

34 =4, 3^5 =5, 3^6 =1. Hence| 3 |=6 andgp(3)=G.

(d) Gis cyclic sinceG=gp( 3 ).

Fig. B-6

B.7.LetGbe a reduced residue system modulo 15, say,G={ 1 , 2 , 4 , 7 , 8 , 11 , 13 , 14 }(the set of integers

between 1 and 15 which are coprime to 15). ThenGis a group under multiplication modulo 15.

(a) Find the multiplication table ofG.(b) Find 2−^1 ,7−^1 ,11−^1.

(c) Find the orders and subgroups generated by 2, 7, and 11. (d)IsGcyclic?

(a) To finda∗binG, find the remainder when the productabis divided by 15. The multiplication table appears in

Fig. B-6(b).

(b) The integersrandsare inverses ifr∗s=1. Hence: 2−^1 =8, 7−^1 =13, 11−^1 =11.