12CHAPTER Group Theory

12.1 Introduction
concepts of modern algebra. Groups
Group theory is one of the most important fundamental
found wide applications in physical
arise naturally in various mathematical situations. They have
crystal structure, configuration molecules
sciences and biological sciences particularly in the study of
and structure of human genes.
Hence, groups may
The struçture of a group is one of the simplest mathematical structures.
chapter, we
be considered as the starting point of the study of various algebraic structures. In this
shall define groups and study some of their basic properties.
12.2 Binary Operations
Let G be a nonempty set. Then G x G= ((a, b) : a e G, be G}.
Iff: G xG ’G, then fis said to be binary operation on G. Thus a binary operation on G is
a function that assign each ordered pairs of elements of G a unique element ofG.
The symbols +, ,0, *etc. are used to denote binary operations on a set. Thus + will be a
binary operation on G if and only if
a+be G for all a, b e G and a+ bis unique.
Similarly * will be a binary operation onGif and only if
a*be G for all a, be Gand a*b is unique.
This is said to be the closure property of the binary operation and the set Gis said to be
closed with respect to the binary operation. For example, addition (+) and multiplication (x) are
binary operations on the set N of natural numbers, for, the sum and product of two natural numbers
are also natural numbers. Therefore, Nis closed with respect to addition and multiplication ie.,
atbe N for alla, be N.
axbeN for all a, be N.
Note that subtraction is not a binary operation on N, for 5 - 9 =- 4 e Nwhereas 5 e N,
9e N. But subtraction is a binary operation on Z, the set of integers, positive and negative.
Abinary operation on a set G is sometimes called a composition in G. For finite set, a binary
operation on the set can be defined by means of a table, called the composite table. Let S be a set
with n distinct elements. To construct a table, the elements of S are arranged
horizontally in a row
called the initial row or 0-row ; these are again arranged vertically in a
column, called the nta
column or 0-column. The (i, j) th position in the tabBe is determined by the
row and the jth column. For example, let S = {a, b, c}. Define * on S intersection of the
by the following tabie.
 EORY 451

cb h h
Tabie 12.1
To determine the elements of S assigned to a *b, we look at the intersection of the row
labclled by aand the ciement headed by h. We see that a* bh. Note that b * a a
Algebraic Structure
A non-empty set together with one or more than one binary operations is called algebraic
structure. For example,
(N, +). (Z, +), (R, +, .)are all algebraic structures. Obviously addition and rnultiplication are
both binary operations on the set R of real numbers. Therefore, (R, +. ) is an algebraic
equipped with two operations. structure
Laws of Binary Operations
Associative law: A binary operation * on a set S is said to be associative or to satisfy associate
property, if and only if, for any elements a, b, ce S
a * (b * c) = (a * b) * c.
Commutative law: Abinary operation * on the elements of the set is commutative or to
commutative property, if and only if, for any two elements a and b e S, satisfy
a*h = h* a.
Example 1. The algebraic structure (Z, +), (Z, ), where the binary
and muitiplication on Z are both associative and commutative since additionoperations of addition
integers is both associative and commutative. and multiplication of
Example 2. Let M, (R) be the set of all 2 × 2 matrices over R i.e.,

M, (R) = :a, b, c, d, e R

Since addition and multiplication of 2× 2matrices over R is a2 x 2

that both + and. is a binary operation on M, (R). Hence (M, (R), +, .) is a matrix overR, it follows
that + is both associative and commutative and. is associative, but not algebraic structure. Note
commutative.
Example 3. The algebraic structure (Z, -) where - denotes the binary operation of
0n Z is neither associative nor commutative since subtraction
3-(4- 5) = 4 -6= (3 - 4) -5
and also 3-4 4-3
Adentity Element
An element ein a set S is called an identity elemnent with respect to the binary operation
Ior any element a in S if.
a *e = e*a= a
IHa*e= a, then e is called the right identity element for the operation * and if e * a=a,
ene is called the left identity element for the operation *,
Consider any element x of the set O of rational numbers with respect to the binary operation
addition. Obviously, Ois the identity element, since 0+x x+0=x, for everyxe Q.
every xSethe
Q.
identity element of Qfor the binary operation multiplication, since I.x = x.l =x, for
452 ATEXTBOOK OF DISCRETE

It is easily seen that for the set Nof natural numbers there is no
MATHEMAAT
identity element for
but 1is an identity element with respect to multiplication.
Theorem 12.1. The identity element (if it exists) of any algebraic structure is
adit.
unique.
Proof. Let, if possible, e and e betwo identity elements of the algebraic structure (S.
e' e S
e*e' = e'.
Now e is an identity element
e* e ' e .
Again e is an identity element
But e* e'=e and e * e'=e e - e'.

Thus the identity element is unique.

Inverse Element
Consider a set S having the identity element e with respects to the binary
corresponding to each element ae S there exists an element b e S such that a*h=h operation *.
Then b is said to be the inverse of aand is usually denoted by a'. We say a is invertihl,
Consider the set R of real numbers which has 0 as the identity element with respect to t
binary operation addition. Then, for any a e R, we see that
(- a) + a = a+ (- a) = 0.
Thus, for any a of the real number set, (- a) is itsinverse. This is called the additive inver.
Similarly, for the set Q of rational numbers, 1 is the identity element for the binary operatics
of multiplication. Then, for any a e Qwe see that
a.(1/a) = (l/a).a= 1.
Thus, for any a (non-zero ) of the rational number set, its reciprocal is its inverse. This is called
the multiplicative inverse.
Note that the inverse of the identity element is the identity element itself.
Theorem 12.2. For an associative algebraic structure, the inverse of every invertible element
is unique.
Proof. Let (S, *) be an associative structure with identity element e. Let x be an invertible
clement of S. If possible, let y, z be two inverses of x. We then have
x * y = e=y *x ... (1)
and x *z = e=z * x. ... (2)
Now (y*x) * z = e * z from (1)
= z (e is the identity)
So that (y*x) * z = z
and y* (* * z) = y*e from (2)
= y (e is the identity)
Thus . . (4)
y* ( * z) = y
Since the composition * is associative, we have
(y * x) * z = y* (x * z).
Then from (3) and (4), we have y = z, showing that the inverse of every invertible element
unique.
Note. It may be noted that while an identity element is the same for all element x in S.
inverse of an element x is determined by the given element x.
From the composite table, one can conclude
()Closure property : If all the entries in the table are elements of S, then S is closed i
GROUP THEORY
453

(2 Commutative law : If every row of the table coincides with the corresponding column,
on S.
then * is commutative
ii)Jdentity element : If the row headed by an element a, of S coincides with the top row,
element.
then a, is the identity
(iv) Inverses : If the identity element e is placed in the table at the intersection of the row
band b-l =a.
beaded by a and the column headed by b, then a=
Exámple 4. Show that the binary operation * defined on (R, *) where x *y= max (x, y) is
associative.

Solution. (r * y) * z = max (x, y) *z

= max (max (x, y), z) = max (x,y, z)
Again x* (y * z) = x * max (y, z)
max (x, max (y, z))
= max (x, y, z)
Hence (x * y) * z = x * (y * z)
Thus, * is associative.
*y=x is not
Example 5. Show that the binary operation * defined on (R, *) where x
associative.
Solution. (x * y) * z = x)* z
= (xF=
Again x* (y * z) = x * y²
=

Since xz # **, ( * y) * z#x * (y * 2)

Thus, * is not associative.
Example 6. Prepare the composition table for multiplication on
the element in the set
multiplication satisfies the closure
A ={1, w, w}, where w is the cube root of unity. Show that
element. Write down the multiplicative
property, associative law, commutative law and Iis the inverse
inverse of each element.
various elements and
Solution. Since w is acube root of unity, w= 1. We can operate on
prepare the table as below.
X 1

1 1
1

From the table we can conclude that

closure property is satisfied.
()Closure property : Since all the entries in the table are in A so
A is a set
(ii) Associative law : Since multiplication is associative on complex numbers and
of complex numbers, so multiplication is associative on A.
and 3rd columns
(iii) Commutative law : Since 1st, 2nd and 3rd rows coincide with 1s, 2nd
respectively, so multiplication is commutative on S.
identity
(iv) Identity element : Since row headed by 1is same as the initial row, I is the
element.
(V) Inverses : Clearly 1-! = l: wl= ²; (w)=w
454 TEXTBOOK OF DISCRETE MATHEMATICS
A

Example 7. Let the binary operation * be defined on S = {a, b, c, d by means of composis

Table 11.2.
(a) Compute c * d, b *b, (a *b) * c and [(a * c) * e)] * a from the table.
(b) is * commutative ? why? C d

Solution. (a) c*d = b. b *b=c a C bd

C a
(a * b) * c = b*c= a
C a
and [(a * c) * e * a= (c * e) * a a* a-a
ldb e d
(b) No, since b *e=cand e * b = b and hence b * ete * b.
d|b a d e
Example 8. Let Z be the set of integers, show that the operation * on Table 11.2
Z, defined by a *b =a+b+ 1for all a, b e Zsatisfies the closure property,
associative law and the commutative law. Find the identity element. What is the inverse of an
integer a?
Solution. Since Zis closed for addition, as we have
atbe Z for all a, b e Z
’ atb+1e Z
’a* be Z
So * is a binary operation on Z.
Again, a *b = a+ b+ 1
= b+ a+1 (by commutative law of addition on Z)
= b* a for all a, be Z
Hence * is commutative.
Again, (a* b) *c = (a+b+ 1) * c
= (at b+ 1) +c+1=(a +b+c) + 2
and a* (6* c) = a* (6 +c +1)
= a+ (b+c+ 1)+ 1 =(a +b+ c) + 2
Thus (a * b) *c = a * (b * c) for all a, b, c e Z
Hence, * is associative.
Now, if eis the identity element in Z for *, then for all a eZ
a*eFa ’ a t e t l = a
’e=-1e Z
So, -1 is the identity element for * in Z.
Let the integer a have its inverse b. Then,
a* b=-1 ’ a+ b+ l=-1
’b=-(2 + a)
’ So, the inverse of a is - (2 + a).
12.3. Group
Let (G, *) be an algebraic structure, where * is a binary operation, then (G, *) is called a group
under this operation if the following conditions are satisfied.
1. Closure law: The binary * is a closed operation i.e., a * b e G for all a, be G.
2. Associative law: The binary operation * is an associative operation i.e., a * (6 * c) =
(a * b) * c for all a, b, c e G.
GROUP THEORY 455

2 Jdentity element:There exists an identity element i.e., for some e e G,e *a-a "e=a, a e G.
[Link] element: For each a in G. there exists an element a' (the inverse of a) in G such
that a* a'=a a =e.
Many books do not mention the first property as this is a consequence of the definition of
binary operation.

AgroupGis said to be Abelian if the commutative law holds ie., a *b= h *a for alla. b
e G.
Agroup with addition binary operation is known as additive group and that with muitiplication
hinary operation is known as multiplicative group.
Example 9.
) The set Rof real numbers, for the binary operation of addition, is agroup, with 0as identity
element and (-a) as the inverse of a. The same is true of the set Z of integers or the set Q
of all rational numbers or the set C of complex numbers.
(i)The set R* of non-zero real numbers, for the binary operation of multiplication, is group
with 1as identity element, and l/a as the inverse of a. The same is true of the set Qof
non-zero rational numbers or the set C* of non-zero complex numbers.
(i) The set Z' of positive integers with operation +is not a [Link] is no identity element
for + in Z*. The set Z with operation multiplication is not a group. There is an identity
element 1, but no inverse of 3.
Example 10. Prove that the fourth roots of unity 1, -1, i -iform an abelian mltiplicative
group.
Solution. Let G = (1, -1, i, -i}. We form the composite table as
1 -1
1 1 -1 i -i
-1-1 1 i
i i -i -1 1
-i 1 -1
Table 1.3
Closure Property : Since all the entries in the table are the elements of G and hence Gis
closed with respect to multiplication.
Associative Law : a(bc) = (ab) c for all values of a, b, c in G.
For example 1[(- 1) )=-i- [1l(-1)] i
Commutative Law : ab = ba for all a, b in G.
From the composition table it is clear that elements in each row are the same as elements in
the corresponding column so that ab = ba.
Identity element : 1 e G is identity element as 1.a = a.l = a. It can be seen from the first
row and first column of the table.
Inverses : As 1.1 =i. (-i)= (-).(-) = 1, the inverses of I, -1, i, -i are 1, - - i, i
respectively and all those belong to G. Hence it follows that Gis an abelian multiplicative group.
Example 11. Show that the set of allpositive rational numbers forms an abelian group under
the composition defined bya *b = (ab)/2
Solution. Let Q* denote the set of all positive rational numbers. We have to show that
(Q,) is a group under the composition a * b= (ab)2.
Closure Property : Since for every element a, b eQ, (ab)2 isalso in Q", therefore Q* is
closed with respect to operation .
456 ATEXTBOOK OF
DISCRETE
Associative Law : For a, b e Q', we have
(a * b) *c=(ab/2)) *c (ab/2) c/2 =a/2 (bc/2))= a * (bc/2) =
MATHEMtir
Commutative Law : For a, be Q, we have
a* (b * c
a*b = (ab)y2 = (ba)2 = b * a
Identity Element : Let e be the identity element in Q", such that e*asos=u* e
Now e*a = a’ (ea)/2 = a’ (a2) (e - 2) - 0
’e= 2, since ae Q*’a> 0
But 2 e Q and we have 2 * a= (2a)/2 = a= a* 2 for all a eQ
Inverses : Let a be any element of Q. If the number bis to be the inverse of a,
have then wer
b *a = e=2’ (ba)/2 = 2 ’b= 4/a e 0*
We have (4/a) * a = 4a/2a = 2 = a* (4/a)
Therefore, 4/a is the inverse of a. Thus each element of Q* is invertible.
Hence (Qt, *) is an abelian group.
Example 12. Show that the set {1, 2, 3, 4, 5} is not a group under addition and
modulo 6. multiplica:
Solution. Let G = (1, 2, 3, 4, 5}. The operation addition modulo 6 is denoted by +,. W..
operate to on the elements in G and prepare the composition table as
In the system (G, t)
2 +, 5 = 1. For 2 +5 =7=1 x6+ 1
It% 4 = 5. For 1 + 4 = 5
3 t, 5 = 2. For 3+ 5= 8= 1 x6+ 2 etc.
Hence the composition table is
t6 1 2 3
1 3 4
2 3 4
3 4 5 0 1 2
4 5 0 1 2 3
0 1 2 3 4

Since all the entries in the composition table do not belong to G, in particular 0 0
Hence G is not closed w.r.t. +s. Consequently (G, t) is not a group.
(i) The operation multiplication modulo 6 is denoted by x
In the system (G, X%).
2 x 5 = 4. For 2 x 5 = 10= ] x6 +4
3x4 =0. For 3x 4 = 12 =2 x6+ 0.
Hence the composition table is:
2 3 4
1 2 3 4 5
2 2 4 2 4
3 3 0 3 0 3
4 4 2 0 4 2
5 4 3 2
GROUP THEORY
457

composition table, it is clear that all the entries in the composition table do not belong
Fromthe
particular 0 e G. Hence Gis not closed w.r.t.
o G. inConsequently (G, x) is not a group.

Example 13. Show that

the matrices

form a multiplicative abelian group.

01 -1 0
Solution. Let A =

f0+1 0+0
0+0 0+I

--
AB =

Similarly AC = C, AD = D, BB = A etc.
Hence we find the composition table as
X A BC D
AA BC D
B BA D C
CC DA B
D D C B A

() Closure property : We can see that all entries in the composition table are the elements of
and hence Gis closed wrt. matrix multiplication.
(üi) Associative law : Multiplication is associative in G. Since associative law holds in case
of matrix multiplication, i.e.,
(AB) C = A (BC).
(i)Commutative law:The entries in the first, second, third and fourth columns of the
Composition table coincide with the corresponding entries in the first, second, third and fourth row.
This shows that G is commutative.
(iv) Existence of ldentity : From the composition table it follows that
AA = A, AB= B, AC = C, AD = D
Thus there exists an identity element Ain G.
)Existence of Inverse : From the composition table it can be seen that
AA = A, BB A, CC=A, DD = A
Thus every element is its own inverse.

G, .) is anee the set of four matrices form a multiplicative group which is commutative as well i.e.,
abelian group.
Example 14. Let G={(a, b) | a, be R, a +0}. Define a binary operation on G by
(a, b) *(c, d) =(uc, be t d)
Ior all (a, b), (c, d) eG. Show that (G, *) is a
group.
458 TEXTBOOK OF DISCRETE MATHEMATIoa
A

Solution.
Closure Property : Let (a, b) and (c, d) be any two members of G. Then a z 0 andcsn
Therefore, ac + 0. Consequently (a, b) * (c, d) = (ac, bc + d) is also a member of G. Hence C:
closed with respect to the given composition.
Associative law : Let (a, b). (c, d) and (e, f) be any three members of S. Then
[(a, b)*(c, d)] *(e.) =(ac, be + d)* (e, )
= (ac] e. [bc +d]e +)
=(ace, bce + de +f).
Also (a. b) * [(c, d) * (e,)] = (a, b) x (ce, de t )
= (a [ce], b [ce] + de +)
= (ace, bce t de +).
Hence the given composition * is associative.
Identity element : Suppose (x, v) is an element of Gsuch that (x, ) * (a, b) = (a, b)
(a, b) e G
Then (xa, va + b) =(a, b), Hence xa = aand ya + b= b.
These give x = 1and y = 0. Now (1, 0) e G
Therefore, (1, 0) is the identity element
Inverse element : Let (a, b) be any member of G. Let (x, v) be a member of G such that
(x. v) x (a, b) = (1, 0), then (x, y) be the inverse of (a, b).
Then (xa, va + b) =(1, 0). Hence xa = 1, yatb=0.
These give x = l/a, y=- bla.
Since a 0, therefore, xand y are real numbers.
Also x = +0. Thus is the inverse of (a, b).
a

Hence G is a group.
Note. In the above group, we have
(a, b) * (c, d) = (ac, bc + d)
and (c, d) * (a, b) = (ca, da + b).
Thus, in general,(a, b) *(c, d) z (c, d) *(a, b) i.e., the composition is not commutative and
hence the group is not abelian.
Example 15. Let be the set of positive rational numbers which can be expresed in the
form 243', where a and bare integers. Prove that the algebraic structure (2, .) is agroup where .
ismultiplication operator.
Solution.

Closure property: Let 9, =203, 4, = 23 e Qwhere a, b, c, d, e Z, the set integers.

Here g, g, = (203b)-(2¢3) = 2a t [Link] t d e 0
Since a + c, bt d e Z. Therefore Q is closed with respect multiplication operator.
Associative law: Let ,=243, q, = 234,g, = 2e Q
We have 9,42 43) = 243b-(23d. 2*3Y
= 243b. (2c tezdt/)
24 t (e t e). gb t (d+)
2atc) +e. gb+ (d +)
 GROUP THEORY
459
24+ (c + e). z(b +d) +f
(Since addition is associative in Z)
= (24 tc. 3b* 2¢3
(243b. 2c3dy 2°3
(9, 9) 43
Identity element: Let q= 2"3° e Q, there exists an
identity element esuch that qe=q.
Now 243b e= 23b ’e=2"3° where 0 e Z.
since 243h-2030 = 2a +03b +0= 2a3b
Inverse Element: Let q = 23° e Q. Ifp is the inverse of g, then
we must have
4p = e
243b- p = 2030 .p= 2a3-b since
q'p = 243. 2 3b= 2a -azb-b = 2030 and -a, -b eZ
There (Q,) is a group.
Example 16. Prove that the set
{0, 1, 2, 3, 4}
is afinite abelian group of order 5 under addition modulo 5
as composition.
Solution. To test the nature of the system (G, t) where G= {0, 1, 2, 3,
4}
2+4 1 for 2+4 =6= 1x 5 + 1
3+ 4-2 for 3 + 4=7=|x 5 + 2
4+ 4=3 for 4+ 4 = 8 = 1 x 5+3 etc.
We have the following composition table :
ts 1 2 3 4
0 1 2 3 4
1 1 2 3 4
2 2 3 4 0 1
3 3 4 1 2
4 4 0 1 2 3
From the table, we see that (i) the given composition is binary (ii) Ois the identity element
(üi) every element has an inverse. Thus the inverses of 0, 1, 2, 3, 4 are 0, 4, 3, 2, 1
The composition is associative and commutative.
respectively.
Hence the given set is a finite abelian group of order 5 under addition modulo 5.
Order of an Element
Let (G, *) be a group and ae G. Then the order of an element a in a group G is the smalle
positive integer n such that a=e.
i.e. a * a * .. to n terms = e, e is the identity element.
If no such integer exists, we say a has infinite order. The order of an element a is denoted by
O
(a). The order of identity element e in a group is always one i.e. Oe) = 1
Example 21 (i) Let G= {1, 1, i, - i} be a multiplicative group. Find the order of every
element.
Solution. 1is the identity element in G.
() 1'=1 ’0(1)= 1.
(ii)(-1= 1, (-1)y 1for anypositive integer n<2
Hence O(-1)=2.
(iii) () =land (iy 1 for any positive integern <4.
Hence O (i) = 4.
(iv) (-i)* = l and(-iy1for any positive integer n <4.
Hence O(-i)=4.
GROUP T H E O R Y 463

Example 21 (i) Let G=[{0, 1,2, 3, 4}. + s] be a group. Find the order of every element.
Solution. Since O is the identity element, O(0) =1.
()'= 1
(1Ý =1+ gl=2
(1 =1 t;l +sl =2 + l =3
(1)= 1 ts1 + _lt sl =3 + l =4
(1)'= 1tsltsl tsl t,l=4+ ,l = 0(the identity element)
Therefore O (1) = 5
Now 2! =2,22 = 2 + 2 = 4, 2 =2 +,2 + 2 = 4 +,2=1
24 =2+ s2 + 2 + 2 =1+ 2 =3
25 =2+ s2 + s2t s2 t 2=3+2 =0(the identity element)
Therefore O (2) =5
Similarly, we can show that O(3) = 5 and O (4) = S.
Theorem 12.8. Let a be an element of a group (G, o) and e be its identity element. Then
() The order of an element a of a group is the same that of its inverse a - i.e. O(a) =0 (a ).
(ii) If O(a) =n then a =e if and only if n is a divisor of m.
(iüi) If O(a) =n,then a, a', a, .., a (=e) are distinct elements ofG.
(iv) If O(a) =n and pis prime to n, then O (aP) =n.
Proof : () Let O(a) =n and O(a)= m.
Then O (a) = n =e
(a) -1 = el
(aly = e [: el =e]
O(a') s n mSn ...(1)
Also O (a') = m + (aym=e
(am)! = e

an = el=e
O(a) s m ...2)
ns m
From (1) and (2), we have m=n, ie. O (a) =0(a).
Let O(a) be infinite. We assert that O (a') is infinite.
If not, let O (al) = m where m is a finite positive integer. Then (alym =e i.e. (a")l =e
a=e’0(a) [ m
i.e. a is of finite order which is a contradiction.
Therefore, O (a)' is infinite and O(a) = O(a).
(1) Let n be a divisor of m. Then there exists an integer q such that nq = m.
Now, am= g19 = (a9= e=e [: O(a)=n> =e]
Conversely, let O(a) = n. Then n is the least positive integer such that a =e.
Again mis an integer. By division algorithm, there exists integer q and r such that
m= ng t r where 0 <r< n.
Then e = n= gg +r= (aY. d =e. a' = a'.
Thus =e which is possible only when r= 0,
Since r <nand n is the least positive integer such that a" =e.
Iherefore, m = ng ’n is a divisor of m.
464 A
TEXTB0OK OF DISCRETE MATHEMATICS
(iii) Given Ofa) =n>=e (identity element), n be the least positive integer
If possible let a = a (|sr<s<n)
a. at= . a t
e= a
S- < n.
This is not possible. Hence our assumption
a= d is wrong i.e. d' # a
Therefore, a, a, ... a' are all distinct elements of G.
(iv) Given O(a) =n’ = e (identity element), n be the least positive integer.
Given that p is prime to n i.e. gcd (p. n) = 1.
Now (aPy = (ay = e= e.
Oa) s n.
Let O(aP) = m
m S n.

and (aPym =e apm = e

n [ pm and n/pm
n/m as gcd (n, p) = 1.
nS m.
Now n sn and n < n ’ n m.
. . O (aP) = n.
Example 22. Find the order of every element in the multiplicative group G = {a, ', a', a,
a, a = e}
Solution. The identity element of the given group is a = e.
ao =eo (a) =6
(a) = f =eo(a) =3
(a =a =co (a') = 2
(at =al2 = (ab =e=eo (a) = 3
(ayó = (ao) =e =eo (a) =6.
and (ay±e for any n <6
(ay' =a =eo(a)= 1.
Thus the orders of elements a, a, a', at, a, aÛ are 6, 3, 2, 3, 6, 1 respectively.
Example 23(). In a group (G, o), a is an element of order 30. Find the order of a.
Solution. Given o(a) - 30 so a0 =e, the identity element. Let o(a) =n. So, (ay -e i.e.
aSn =ewhere n is the least positive integer. Hence 30 is a divisor of Sn. .:. n=6. Hence o(a) =6.
Example 23(ii). In a group Gfor a, be G, o(a) = 5, bte and aba! = b'. Show that ofb)
is 31.
Solution. (ab a l = (ab a l(ab a) = ab(a 'a)bal=abebal
abbal = ab'al= alab a' (: abal b²)
= a ba2
(ab a ty = (ab a l (ab a l? = (a ba ') ( ba')
GROUP THEORY 465

= ab (a a) ba2 = ? be bu'=b² a2(: a=e)

= a(ab a)a'= a ba3
Similarly. (ab ay= dba and (ab aly6 a'b as
(ab a'yl6 = ebe (: ola) =5 i.e., a=e)
be (: el=e)

Thus (b2)l6 = b’ b2 =h
b.e = e ’ l=e
S0, o(b) = 31
12.4 Groupoid, Semigroup and Monoid
Let (S, *) be an algebraic structure in which S is a non-empty set and * is a binary operation
anS Thus S is closed with the operation *. Such a structure consisting of anon-empty set S and a
binary operation defined in S is called a groupoid.
An algebraic structure (S, *) is called a semigroup if the following cónditions are satisfied:
1. The binary operation * is a closed operation i.e., a * b e S for all a, b e S. (closure law).
2. The binary operation * is an associative operation i.e., a *(6 * c) = (a * b) *c for all a.,
b,c e S. associative law).
An algebraic structure (S, *) is called a monoid if the following conditions are satisfied:
1. The binary operation * is a closed operation. (closure law).
2. The binary operation * is an associative operation (associative law).
3. There exists an identity element, i.e., for some e e S, e *a=a*e=a for all a e S.
Thus a monoid is a semigroup (S, *) that has an identity element.
For example,
() IfN be a set of natural numbers, then (N, +) is groupoid because the set N is closed under
addition. But the set of odd integers is not a groupoid under addition operation since 3 +3=6 do
not belong to the set of odd integers and hence is not closed.
(i) If Zbe a set of all integers, then (2, +) and (Z, ) are semi group as these two operations
are closed and associative in Z.
(iii) N,the set of positive integers, and * is the operation of least common multiple (1.c.m) on
N, (N, *) is a semigroup, it is also commutative.
Solution. For a, b e N, define a * b= l.c.m (a, b). Clearly a * b e Nand for a, b, c, e N.
(a*b) *c= (l.c.m. (a, b)) *c
= L.c.m. [l.c.m. (a, b), c]
= l.c.m. [a, b, c]
= l.c.m. [a, l.c.m. (b, c)]
= a * (b * c).
Hence * is associative. Hence (N, *) is a semigroup. Clearly, a * b= l.c.m (a, b) = l.c.m (6, a)
b*afor all a. be N. Hence * is commutative.
The structure (Z, +) is a monoid with identity element 0 and (Z, ) is a monoid with l as the
Identity element. (P(S), U) is a monoid with Í as identity element.
We note that every group (G, *) is a semigroup. A semigroup (S, *) is commutative if * is
commutative i.e., a * b-b*a for all a, b e S. Asemi group (S, *) which is not commutative is
Called non-commutative. The set of integers (Z, +) and (Z, ) are commutative semigroups, where
ie binary operation on Z are usual addition and multiplication of integers.
The next three theorems give necessary and sufficient conditions for asemigroup to be a group.
468 ATEXTBOOK OF DISCRETE
Theorem 12,9, Asemigroup (S, )is a group if and only if MATHENMATICS
() ttere exists ee S such that e * a tor all a e Sand
() trall ae Sthere exists e S such that h *ae.
hooft Suyse (S, ") is asemigmup that satisties () and (), Then for be S, there
e S sunh that ebv ). exIsts
Now
ae*a (e * )*ac*(h* a)c*e
ani
a* (ce)*c* (e* b) c*be
abeh* a. Also a*ea(6* a) (a* b) *ag*.
Thus, «*eae* a. This shows that e is the identity elenent of S. Now since a
a, we haNe . Therefore. (S, *) is a group.
The oneNe can be proved from the detinition of a group.
Theorenn 12.10. Asemi group (S, *} is a group if and only if for a, be S cach of the
quatis * d and r *a has a solution in S for xand y.
Proof: If Sis a group, then by theorem 12.6, the equation a *xhand y * a
solutions in S. bhave
ConveNely. suppose the given equations have solutions in S. Let the
a solution e eS, Then e *aa. For any b eS, if t(depending on a and equation y* a a have
b) be the solution of the
quations a*=, then a* b.
Now, c * e (a* ) (e * a) *=a*t= b.
Consequently, e* b=b. for all beS eis aleft identity in S.
Next, a lett inverse of an element a e S is given by the solution y * a =e and the
belongs to S. solution
Hence, for each ae S, there exist a left inverse in S. Thus S is a group.
Theorem 12.11. A finite semi-group (S, *) is a group if and only
cancellation laws (i.e, a*c= b *c implies a= b ande*a=c *b implies a=ifb(S, *) satisfies the
for all a, b, ce S).
Proof: Let ($, *) be a finite semi-group satisfying cancellation law i.e.,
a*b= h* c=> b=c
and b* a = e * a b = c
Let S = a, a,.. a} where a,are alldistinct element of S.
Consider now the elements a, * a,, a, * ay, .....,. a,*a,
These elements belong to S and are distinct. If they are not distinct, let, a, * a, = a, * a,.
Then, by cancellation law, a,=a, which contradicts the fact a, * a,.
Then composite elements a, *a,, a, *a, . . a, *a,, being all distinct, they are the ngiven
clements of Sin some order. This shows that the equation a *x = b for a, be S has a solution in S.
Similarly, by forming the products a, * a, a, * aj .., a, * a, it can be shown that the
equation y *a=b for a, be S has a solution in S.
Thus (S, *} is a semi-group in which each of the equations a * x= b andy *a= b has a
solution in S for all a, b e S.
Hence by Theorem 12.9, {S, *} is a group.
 12.5 Subgroup
Let (G, *) be a group and His asubset of G. (H, *) is said to be subgroup of G if (H, *) is
also group by itself.
Now every set is a subset of itself. Therefore, if Gis a group, then Gitself is a subgroup of G.
Alsoife is the identity element of G. Then the subset of Gcontaining only identity element is also
asubgroup of G. These two subgroups (G, *) and ((e), *) of the group (G, ) are called improper
or trivial subgroups, others are called proper or nontrivial subgroups.
Example 24
() The multiplicative group {1, -1} is a subgroup of the multiplicative group {1, -1, i,-i}
() The additive group of even integers is a subgroup of the additive group of all integers.
(ii) The set Q* of all non-zero positive rational numbers is a subgroup of the multiplicative
group Q* of all non-zero rational numbers.
Important Theorems

Theorem 12.12. The identity element of a sub group is the same as that of the group.
Proof: Let H be the subgroup of the group G and e and e' be the identity elements ofG and
Hrespectively.
Now, if ae H, then ae G and ae = a, since e is the identity element of G.
Again a ¬ H, then ae' = a, since e is the identity element of H.
Thus ae - ae' which gives e =e
Theorem 12.13. The inverse of any element of a subgroup is the same as the inverse of the
same regarded as an element of the group.
Proof: Let H be the subgroup of the group G, and let e be the common identity element.
Let a e H. Suppose b is the inverse of a in H and c is the inverse in G. Then we have
ba - e and ca = e.
nce. in Gwe have ba = ca ’b=c
468 ATEXTBOOK OF DISCRETE MATHEMATICS

Note. Since the identity of H is the same as that of G, it is easy to see that the order of ax
element of H is the same as the order of that element regarded as a member of G.
The next two theorems provide simple tests that suffice to show that a subset of a group is a
subgroup.
Theorem 12.14. (two step subgroup test) Anon-empty subset Hof a group G is a subgroun
ofG if and only if
(i) ae H, beHa*beH
(i) a e H ’ a e H where a is the inverse of ain G.
Proof: The condition is necessary. Suppose His a subgroup of G. Then Hmust be closed with
respect to operation * i.e, ae H, be H’a*be H.
Let a e H and let a' be the inverse of a in G. Then the inverse of a in H is also a. Since H
itself is a group, therefore, each element of Hmust possess inverse. Therefore, a e H»ae H.
Thus the condition is necessary.
The Condition is Suficient
We observe that the binary operation * in Gis also a binary operation in H. Hence His closed
under the operation.
As the elements of His also the elements of G and the elements of G satisfy the associative
law for the binary operation, therefore, the elements ofH will also satisfy the associative law.
Now a eH r eH
From the condition (), we have a e H, a' e H’ aa e H =ee H which shows the
existence of identity element in H.
Thus al] the conditions are satisfied, H isa subgroup of G.
Theorem 12.15. The necessary and sufficient condition for a non-empty sub-set Hof a group
(G, *)to be a subgroup is
ae H, be H ’ a* b-l e H.
where bl is the inverse of b in G.
Proof: Let H be a sub-group and a e H, be H. Since H is a sub-group and b e H, b must
exist and will belong to H.
Now ae H, b-! e H’a*b-leH, by closure property.
Thus the condition is necessary.
To prove that this condition is als0 sufficient, we assume that
ae H, b e H ’ a* b-l e H.
We are to show that H is a sub-group of G.
By the given condition, we have
ae H, eH a* aleH
’ee H,
where e is the identity element. Hence H contains the identity elemente.
Again, we have ee H, ae H’e* a e H
’ a'e H,
where a is the inverse of a. Therefore, the inverse of each element in H exists in H.
Now, if be H, then b- e H.
Also ae H, b eH ’ a *(b-le H
’a*be H(closure property).
Now, HcGand the associative law holds good for G, as G is a group. Hence it is true 1
subgroup ot .
the elements of H. Thus all postulates for a group are satisfied for H. Hence H is a
GROUP THEORY 469

Example 25. Let Gbe the additive group of all integers and Hbe the subset of Gconsisting
positive integers. Then H is closed with respect to addition i.e., the composition in G. But H
of all of G since the identity 0 H.
notta
subgroup
js
Eyample 26. Let G - {.....3, 3,1, 3, 3, .. be the multiplicative group consisting
of allintegral powers
of3. Let H={1, 3, 3,... Then HcG and His closed with respect to
multiplication, But His not a subgroup of Gsince the inverse of 3ie., 3-! does not belong to H.
Example 27. Consider the group (Z, +). Let H= (3n :n e Z} show that His asubgroup of Z.
solution. It is a subgroup of Z since
() H is non-empty.
(ii) Let x, y e H. Then there exist p, qe Z such that x =3p, y = 3q.
Now xyl=3p - 3q=3 (p - ) where p- qeZ.
Thus xy e H
Hence H is a subgroup of Z.
Example 28. Let Gbe a group. For afixed element of G, let G, = {aeG:ax =[Link]
that G, is asubgroup of G for allx e G.
Solution. Since () ex =xe, e e G,. Therefore, G, ¢.
(i))a, b e G, ’ ax = xa and bx =xb.
Now (ab) x = abx,
= axb, (: bx= xb)
= xab, (:" ax = xa)
= x (ab).
This shows ab e G,. Hence G, satisfies the closure axiom.
(i) a e G,’ x =F xa.
’ a' (ax) al = al (xa) a!.
’ r ' axal =alxaa!,
’ exal=a'xe,

’a'e G,.
Thus the inverse of each element of G, is in G,.
Theorem 12.16. The intersection of any two sub-groups of a group (G, *) is again a sub-group
of (G, ").
Proof: Let H, and H, form any two sub-groups of (G, *).
We have H, n H, # ), since at least the identity element is common to both H, and H,
Let a e H, O H, and b e H, n H,.
Now ae H H, ’ a e H, and a e H,
be H, H, ’ be H, and be H,
Since H, and H, from sub-groups under the group (G, *), we have
ae H, be H, > a* bl e H,,
ae H,, be H, = a*ble H,
Finally, a * bl e H, a * b' e H, ’ a* b-l e H, o H,
 ATEXTBOOK OF DISCRETE
470 MATHEMATICS
Thus we see,
a*be H, o H,
ae H, H,, be H, O H
sub-group under (G, *)
Therefore, H, n H, forms a
not necessarily a subgroup.
Note: The union of two subgroups is
group of integers.
For example, let G be the additive
4, 6, ..... and
Then H, =(.....-6, -4, -2, 0, 2,
-3, 0, 3, 6, 9, 12.......
H, ={........12, -9, -6,
are both subgroups of G.
2, 3, 4, 6, .....
Now H, UH, = (....-4, -3, -2, 0,
Obviously H, UH, is not closed with respect
to addition as 2 e H, U H,,
H,. Therefore, H, U H, is not a subgroup
H, U
of G.
3e H, U H, but 2 +3 =5
Cosets
of Gand let a e G. Then the set aH -
Let G be amultiplicative group andHbe a subgroup a and is denoted by aH.
by
(ah : he H} is called the left coset ofH in G generated
Similarly the set Ha= (ha :he H} is called the right coset of Hin
G generated by a and is
Ha.
denoted by Ha. The element a is called a representative of aH and
It is evident that both aH and Ha are subsets of G.
Therefore, H itself is a right
If e be the identity element of G, then e e H and He = H=eH.
as well as a left coset.
In general aH Ha, but in the abelian group, each left coset coincides with the corresponding
right coset.
a is defined as
If the group operation be addition, then the right coset of H in G generated by
H+a = (h+a:he H}.
Similarly, the left coset a+ H=fa +h:h eH}.
Index of a subgroup in a group. If H is a subgroup of a group G, the number of distinct
right (left) cosets of H in G is called the index of H in G and is denoted by [G: H] or by i, (H).
Example 29. (I) Let Gbe te additive group of integers i.e.,
G= {... -3, -2. -1, 0, 1, 2, 3, ....
Let H be the subgroup of G obtained on multiplying each element of G by 3. Then
H={.., -9, -6, -3, 0, 3, 6, 9,..,.
Since the group G is abelian any right coset will be equal to the corresponding left coset. Let
us form the right cosets of H in G.
We have 0 e Gand
H+0= {.,-9, -6, -3, 0, 3, 6,9,....) = H
Again 1e G and H+ I ={., -8, -5, -2, 1, 4, 7, 10, .) =1+H
Then 2 ¬ G andH+ 2 ={.., -7, -4, -1, 2, 5, 8, 11, ...} = 2+ H
We see that the right cosets H, H+ 1and H + 2 are alldistinct and moreover these are disjoin
ie., have no element common.
Now 3 e G and H+3={..., -6, -3, 0, 3, 6, 9, 12, ...
We see that H + 3 =H.
Again 4 e Gand H+ 4 ={.-5, -2, 1, 4, 7, 10, 13,....}=H+1
Thus there exists three distinct and disjoint right cosets namely H, H + 1, H+2.
The union of all right cosets of H in G will be equal to G. ie.
G= HU(H + 1) U(H +2)
The index of Hin G is 3.
GROUPT H E U
471

Example 29 (ii) Let G= {1, a, a, a', a}(a= 1) be aa group and H={1, a} is asubgroup of
Find all the cosets of H.
multiplication.
Gunder

Solution. Right cosets of H in G

are
HI = {1, a} = H, Ha -{a, }
Ha = (a', a} = (a', 1} = H
Ha = {a', a} ={a,a} = Ha
So, there are two distinct right cosets of Hin G and G= HU Ha. Similarly, we can find the
G. The index of Hin Gis 2.
of Hin
left cosets
Example 29 (ii) Fiinnd the left cosets of H= {[0], [2]} in the group G=(Z, t)
Solution. Here G= {[0]. [1], [2),[3]} and H= {[01. (2]} be a sub-group of Gunder +, (addi
tion mod|4).
the left cosets of Hin Gare
{0} + H = ((0], [2]} =H
[1]+ H = (1], (3]}
[2]+ H ={(2], [4]} ={(2], [O]} = ([0], (2]} = H
[3] + H = {(3], [5]} = {(3], [1]} ={(1], [3} = (1] + H
[O] + H = [2]+ H= H and [1] + H= [3] + H
are the twodistinct left cosets of Hin Z, and G = HU[1]+ H
The index of HinG is 2.
Properties of Cosets
Let H be a subgroup of G, and a and b belong to G, Then,
1. ae aH
2. aH = H if and only if ae H
3. aH = bH or aHObH =
4. aH = bH if and only if a' b e H,
Analogous results hold for right cosets.
Proof 1. a= ae e aH, eis the identity element of G.
2. If e be the identity in G and so is in H, then
aH =H ’ ae E H
i.e., aH =H’ ae H . .(1)
Again, if a e H and h e H then
ae H’ ah e HhE H
aH c H
Also a e H’a H, Hbeing a sub-group of the group G, satisfies group axioms.
’a'he HYhe Hby closure lawin H
’a(a h) e H he Hby closure law in H
’he aH he H
.. Hc aH
So aHc H and HcaH ’ aH = H
Next ae H’ aH = H ... (2)
Hence aH = H ae H by (1) and (2).
3. Let H be a sub-group of a group G and let aH and bH be two of its left cosets. Assume
nat aH n bH and let c be the common element of the two cosets.
Then we may writec = ah and c = bh', for h, h' e H.
472 ATEXTBOOK OF DISCRETE
Therefore ah = bh', giving a = bh' h.
MATHEMATICS
Since H is asub-group, we have h' h e H.
Let 'hl h" so that a =bh".
Hence aH = (bh") H= b (h" H) = bH, since h" H = H.
Hence the two left cosets aH and bH are identical if aH o bHz .
Thus either aH obH = or aH = bH.
4. We have,
aH = bH ’ a aH = al bH
’ (a' a) H=(a b) H
’ eH = (a' b)H, ebeing the identity in G and so in H.
’ H= (a'b)H
aH =bH ’ abe H
Also, if al beH, then .. (1)
bH = e (bH) = (aa)(bH) = a(ab)H = aH
... (2)
A) and (2) follow that aH = bH al be H.
Normal Subgroup
A subgroup H of a group G is said to be a normal subgroup of G if Ha
and denoted by H 1G = aH for all ae G.
Clearly every subgroup of an Abelian group is a normal subgroup. Since every cyclic group
is abelian, so every subgroup of a cyclic group is normal. To verify that a subgroup is normal one
can use the following theorem.
Theorem 12.17. A subgroup H of a group G is normal if and only if g- hg e H for every
he H, g e G.
Proof: Let H be a normal subgroup of G. Let he H, ge G
Then Hg = gH (Definition of normal subgroup)
Now hg e Hg gH
SO
hg = gh, for some h, e H.
i.e., g'hg = h, e H.
Conversely let H be such that
g' hg e Hhe H, ge G.
Consider a e G For any he H, ar'hae H
Therefore, ha = a (a'ha) ¬ aH.
Consequently Ha c aH.
Let b = al
then b-l hb e H
But b-l hb = (al! haal = ahal
This gives aha e H
so that ah = (aha') a e Ha
which proves that aH c Ha.
Hence aH = HG
This theorem shows that, equivalertly a subgroup H of a group G can be defined to be a
normal subgroup if
g'hg eH¼h e H, ge G.
Order of a group. The number of elements in a group is called the order of the group.
 473
GROUP THEORY

of a group Gis denoted by o (G). Agroup of finite order called

order
is afinite group. By
The
ooncept of
cosets we prove a theorem due to Langrange which expresses a relationship
the
using
the order of
a finite group and the order of its subgroup.
betweeh

Lagrange's T h e o r e m

Cheorem 12.18. The order of each sub-group ofa finite group

G is a divisor of the order of
thegroup G.
group G of order n. We consider the left
Droof, Let H be any sub-group of order m of a finite
decomposition of Grelative to H.
different elements.
cOser

Ve first show that each coset a H consists of m

Let H ={h,, h,.., h.
of a H, all distinct.
Then a h,, a h,..., ah, are the m members
For, we have
ah,= a h, ’ h, =h, by cancellation law inG.
cosets will also be finite, say k. Hence the
Since G is a finite group, the number of distinct left
equal to the total number of elements of G.
Iotal number of elements of all cosets is k m which is .. (1)
n = mk.
Hence:
group G.
This shows that m, the order of H, is adivisor of n, the order of the
Note. The converse of Lagrange's theorem is not true.
Cor. 1. If G be a finite group of order n and n eG, then
a" = e.

Let o (a)= m which implies a =e.

of a is a sub-group of G and the
Now, the sub-set H of G consisting of all the integral powers
order ofH is m.
Then, by the above theorem, m is a divisor of n.
Let n = mk, then
a" = amk =(amyk = ek= e.
the possible subgroups can be of
If G be a group of order 15, then by Lagranges theorem,
order 1, 3, 5 or 15.
SOLVED EXAMPLES

prove that H is
Example 30. If His a subgroup of Gsuch that x' e Hfor everyx e G, then
anormal subgroup of G.
Solution. For anyge G, he H; (gh)² e H and g e H.
H,
Since His asubgroup, h-ge H and so (gh)² hlg?e H. This gives that gh gh h'ge
Le., ghgle H. Hence H is a normal subgroup of G.
Example 31. If G be an abelian group with identity e, then prove that all elements
x of G
Satisfying the equation x² =e form a sub-group H of G.
Solution. Let H ={x:=e}.
Now x =e’r=x.
Therefore, ifx e H, then x also belongs to H.
Furthermore e = e.
Hence the identity element of G also belongs to H.
Let x, ye H.
 DISCRETE

474
ATEXTBOOK OF
MATHEMATICCS
we have
Then, since G is abelian,

=ylr, asx=x andy=y

(p)!.

Therefore,
Hence xy e H and His a sub-group of G.
that the intersection of any two normal subgroups of a group is a nor.
Example 32. Prove
subgroup. of G. Then HOKis
be any two normal subgroups a
Solution. Let Gbe a group and H,K
subgroup of G. K
he H o K ’ h eH and h E
Let x e Gand he HaK. Then
Since H is a normalsubgroup of G.
xhre H e Gand he H ()
Also K is a normal subgroup of G
xhxe K r e Gandhe K (2)
From (1) and (2), we have
HOK’rhxe HOK
re G, he
Thus H nK is anormal subgroup of G.
subgroup of G
Example 33. If His a subgroup of index 2 in a group G, then His a normal
number of distinct right
Solution. Suppose H is a subgroup of index 2 in a group G so that
(or left)cosets of H in G is 2.
To prove that H is normal in G, it suffices to show that
Hx =xH re G.
Let x e Gbe arbitrary. Then x e H or x g H.
Ifx e H, then Hr= H=H and so Hr =xH
Ifx H, then index of His 2 says that right coset (left coset)decomposition contains only
two cosets
.:. G= He u Hr, G= eHuxH
Hence HU Hx =G= HUxH xH=G-H = Hx
’xH= Hx
In either case Hx=xH, meaning thereby H is normal in G.
12,6 Cyclic Group
A Group G is called a cyclic group if, for some a e G, every element of G is of the form ,
where n is some integer i.e.,
G= fa:ne Z}.The element ais then called a generator of G.
IfG is a cyclic group generated by a, it is denoted by G=<a>, If the composition of cyclie
group G is multiplication, the elements of G are in the form
G = <a >= {.a', a, a =e, a, a, a...
It the composition of cyclic group G is addition and a its generator, then G= (na :ne 2}
i.e. G=<a>={... -2a, - a, oa = e, a, 2a,..}
There may be more than one generator of a cyclic group. Every cyclic group has at least two
generators, generator and inverse of it.

Example 34 (). The multiplicative group of the cube roots of unity {l,w, w²} is acyclic group.
Solution. w = w. w = w, w= w, w = 2, w=1.
GROUP THEORY
475

=
And (w²)!= w², (w = w = w. w W,
(w =w. w²= =(w =1.
Thus cach element of the group can be expressed as some integral power of wand w. Hence
the group issa cyclic group with generators wand w.
Note the w is the inverse of w.
(i) The multiplicative group G= {1, -1, i, -i) is a cyclic group.
Solution. We can write G as G = {i, P, , .
Thus,G is a cyclic group and i is a generator.
Gcan also be written as G = (-i, (-i',(- ),(-i)}
Thus -i is also a generator of G.
Note that - iis the inverse ofi.
Example [Link] group (G, t6 )is a cyclic group where G = {0, 1, 2, 3, 4, 5}.
Solution. We see that
|!= 1, 12 =|t, l=2, 1' = 1+; 1'=3, 1' =1t, 1³= 1+, 3 =4, 15 = 1+, 1 =1
+,4=5, 16 = 0
Thus G= {1°, 12, 1, 14, 15, 16 = 0;
Hence G is a cyclic group and 1 is a generator.
Similarly, it can be shown that 5 is another generator.
Some Important Properties of Cyclic Grous
Theorem 12.19. Every cyclic group is an abelian group.
Solution. Let G be a cyclic group and let a be a generator of G so that
G = <a>= fa:ne Z}
g,
If g, and g, are any two elements ofG, there exist integers r ands such that g, = a and
=d. Then
gg, = da = s= = .d= g,81
So, G is abelian.
Note: 1. The symmetric group S, is not cyclic, since it is not abelian.
2. An abelian group is not necessarily a cyclic group. For example, Klein's 4-group
is abelian but it is not cyclic.
For example, consider the set G= fe, a, b, c} and let o be the binary operation defined on G
with the following composition table.
a b C
e a b

a c b

CC e

From the above table it follows that (G, o) is an abelian group of order 4 but not cyclic group as
<es= (e}, <a>= (e, a), <b> ={e, b}and <c>= (e, e) there does not exist any element
in Gwhich generates all the elements of G.
This group is known as Klein's 4-group and is denoted by K,. Every element except the identity
element is of order 2 [Link] element is its own inverse.
476 A TEXTBOOK OF DISCRETE MATHEMATICS

Theorem 12.20. If a is a generator of a cyclic group G, then a is also a generator of G.

Proof. Let G=<a> be a cyclic group generated by a. Let a' be any element of G, where .
is some integer. We can write d = (a). Since - r isalso some integer, therefore each element of
G, is generated by al. Thus al is also a generator of G.
Theorem 12.21. If a cyclic group Gisgenerated by an element a of order n, then a is a
generator of Gif and only if the greatest common divisor of mand n is Ii.e., if and only if mand
n are relative primes.
Proof. Suppose m is relatively prime to n. Consider the cyclic subgroup H = (a"} of G
generated by a". Obviously He Gsince each integral power of a" will also be an integral power
of a.
Since m is relatively prime to n, therefore, there exist two integers r and s such that
rm + sn = 1.
So amrtsn = al
’ m an =a
’ ( y =a; since a" = (a=e=e
So, each integral power of awill also be some integral power of a". Therefore, GcH. Hence
H=Gand a" is a generator of G.
Conversely, suppose a" is a generator of G. Let the greatest common divisor of mand n be d
and d # 1ie., d >1. Then mld and nld must be integers.
Now (a")yd = (ayid = emd= e, Obviously nld is a positive integer less than n itself. Thus o
(a) <n. Therefore a" can not be a generator of G because the order of a" is not equal to the order
of G. Hence d must be equal to 1. Thus m is prime to n.
Notes 1. The identity element of a cyclic group can not be the generator of the group.
2. If acyclic group has one generator, then it can not have more than two elements.
3. Every group of prime order p is cyclic group.
4. Number of generators in a cyclic group can be found by using Euler phi function. In a cyclic
group of order n, there are (n) generators.
Example 36. How many generators are there of the cyclic group G of order 8?
Solution. Let a be generator ofG. Then O(a) =8. We can write G= (a, a', a', a', , ao, a', a}
7 is prime to 8, therefore, a' is also a generator of G.
5is prime to 8, therefore, a is also a generator of G.
3 is prime to 8,therefore, a² is also a generator of G.
Thus there are only four generators of G i.e., a, a, a, a'
Example 37. Show that the group ({1, 2, 3, 4, 5, 6}, x) is cyclic. How many generators?
Solution. G be a given group. If there exists an element a e G such that o (a) = 6 i.e., equal
to the order of the group Gthen the group Gwill be a cyclic group and a will be a generator of G.
Note that o (3) = 6 because 3 =3, 32 = 3 x,3 =2, 33 = 32 x,3 =6, 34=6x,3 =4, 35 =4x,3
= 5, 36 x3 =5x,3=lie., the identity element.
So, G is cyclic and 3 is a generator of G. We can write
G = 3,32, 3, 34, 3$,36}.
Now 5 is prime to 6. Then 35 i.e., 5 is also generator of G. There are two generators 3 and 5.
Infinite Cyclic Group
An infinite cyclic group is a cyclic group generated by a such that all the powers of a are
distinct. Mathematically Va e G, a #e:m, ne G’ # a wheree is the identity element.
 477
G R O U PT H E O R Y

Example
38. The set of integers with respect to + ie. (Z, +) is an infinite cyclic group, a
I and -1.
being

10 = 0.1 =0, 1'= 1.1, 12-1+|-2.l 2,

gNeTAlor

Solution.

i-l+1 +1+=3- 3.1

l - ( - ) = - 1 . 12=(-2),1 -2. 1 - (-3) --3
Similarly.

and so on.
all the elements of z can be generated by 1.
Hence. I is the generator as
show that 1is also a generator.
Similarly. we can
exactly two generators.
Theerem: 12.22. If G is an infinite cyclhc group, then G has
order of ais infinite.
Proef: LetG-<a> be an infinite cyclic group. The
of Giie. G=<b>
Let bbe any other generator
a for some n e Z
Now beG and G = < a > ’ h =
And ae Gand G = < b > a = b "
for some m e Z

am=e
order of ais infinite, which is only
This shows O(a) s nm-1, that is O(a) is finite. Since the
possibie if
mn-1 =0 ’mn = l’m= 1/n > n # 1(since m
andn are integers)
Thus a and a are the exactly two generators of G.
order of its generator i.e. O(G)
Theorem: 12.23. The order of a cyclic group is equal to the
-Oa). where a is the generato.
Proof: Let G be a cyclic group and a be its generator.
Case L. When O(a) is finite
a=e. Now consider elements
Let O(a) =n. Then n is the lecast positive integer such that
generated by a
a. a'. a'. a" = e.
other element.
We will show that n elements are distinct and G does not contain any
more that n elements
First we will show that G contains n elements. Suppose G contains
G= (a, a, a', .., a =e, "}, mn.
By division algorithm.
m= nq tr, 0Sr<n, 4, r e

am= d for 0<r<n

and d is already coat in the set of n elemnents
a is also contained in these n elements
Hence Gcontains only n elements.
Now, we will show that these elements are distinct.
If possible, let d = for some r S.
Further, suppose r<sie. s-r 0
Now d= d. u!- d.a' e
:.0(a) Ss -rwbere s- r<n
0(a) <nThis not possible.
Hence out assumption -tis wrong Therefore, all nelexts is Gare distinet
.. O(G) =Oa)
 TEXTBOOK OF DISCRETE MATHEMATICs
A
478
infinite
Case II. Where O(a) is
Suppose that O (G) =
finite
There exists r and s such
that s -r>0
a a.a’e a
and a = d ’ .
.. O (a)ss-r. i.e. O(a) is finite
assumption is wrong.
which is a contradiction. Hence our
.. O(G) = infinite.
Sub-groupsof cyclic groups
cyclic.
Theorem 12.24: Every subgroup of a cyclic group is
Proof: Let H be a subgroup of G= <a>.
H.
Let m be the least positive integer such that a" e
We shall show that H is a cyclic group generated by a".
where n e Z.
Since HcG, any element of His of the form a
then n = m¡ + r, 0Sr<m.
Therefore, a = an9 + =a"9. a'

H. But a" e H (by

Since am eH, it follows that am9 eH and hence its inverse (am9) e
assumption) and a"m and all its integral power belong to H.
ThenaeH, 0sr<m.
But, since m is the least positive integer for which ame H, we conclude that r =0, Thus any
element aP of H is of the form (a")9.
Hence H=<a">, a cyclic group generated by a,
Corollay 1. If G bea cyclic group of order n generated by a then every subgroup of Gis
generated by an element of the form a" where m is a divisor ofn.
2. A cyclicgroup of prime order has no proper subgroup.
Let G be a finite cyclicof prime order p. Let H be a subgroup of G. By Lagrange's theorem
the order of subgroup is a divisor of the order of G. Hence O (H) = 1or O (H) =p as p is prime.
Hence G can have no proper subgroups.
12.7 Permutation Group
Let Abe afinite set. Then a functionf: A’ Ais said to be a permutation of Aif
(i) is one - one
(ii) fis onto
ie. Abijection from Ato itself is called a permutation of A.
The number of distinct elements in the finite set A is called the degree of
permutation.
Consider a set A= {a,, a, ....,.a,} and let f: A ’Abe a bijection function. Then evey
element of 4 has a unique image in A, no two distinct elements of Ahave the same image,
element of Ahas a unique pre-image, under f. Thus, the range of fis andevey
of the form
Ran () = fa). f(a,) ....fa,)
In the notation of relations the function }
fis given by
f= {(a,,f (a,), (a, f(a,), .. (a, f(a,)}
This is written in two line
notation as
ay......sssn
fla,)......f a,))
GROUP THEORY 479
Cloe 4is a finite set, its elements can be ordered as the first, the second, ... the nth.
Therefore, it is convenient to take Ato be a set of the form {1, 2, 3, ..., n} for some positive integer
ninstead of a, a,, az, .....a,}.
In general, a permutationfon the set {1, 2, 3, . . .n} can be written as
2 3 ...n

f(2)
Obviously, the order of the column in the symbol is immaterial so long as the corresponding
elements above and below in that column remain unchanged.
Equality of Two Permutations
Let fand g be two permutations on a set X. Then f=gif and only if
(i) degree off= degree of g (ii)f(«) = g () for all x in X.
Example 39. Let fand g be given by
(1 2 3 4) 3 21 4\
g=
(2 3 4 1) (4 3 2 1)
Here both fand g are of degree 4
Evidently f(l1) = 2 =g (1), f(2) =3 =g (2)
f3) = 4 g(3), f(4) = 1 =g (4)
Thusf(x) =g () for all x e {1, 2, 3, 4} which inmplies f= g.
Identity Permutation
If each element ofa permutation be replaced by itself. i.e., I(x)
=x xe X. Then it is called
the identitypermutation and is denoted by the symbol I. For
example,
ab c\
I= is an identity permutation.
abc)
Product of Permutations (or Composition of Permutation)
The product of two permutations fand g of same degree
first perform fand then perform g. is denoted by fo g or fg, meaning

(b b, b,...b,

Then
fog =
For, freplaces a, by b,
Jog replaces a, by Cz, a, by and then g replaces b, by c, so thatfog replaces a by c Simay
Cg.. a, by C
Clearly fog is also a permutation on S.
Snould be observed that the permutation g
0W offcoincides with the first row of g. This has been written in such a manner that the second
is most essential in order to findjo g
1 we want to write gof, then fshould be written in such a manner that the second row Or
must coincide with the first row 3
off.
480 ATEXTBOOK OF DISCRETE
Example 40. Find the product of two permutations and show that it is not
MATHEMATICS
commutative
(1 2 3 4) and g = g-[23 4)
32 14)
(2 14 3)
Sofution.

(1 2 3 4)
2 3 4 1)

(1 2 3 4) (3 2 14
3 2 1
(12 3
412)
We observe that fg gf.
This shows that the product of two permutations is not commutative.
But it can be shown that permutation multiplication is associative.
2 3) 12 3
Let P, = P,
2 3 23 1)

P,(P, P,) =

()C33-(
and (P, P) P, =
(CDJCD)G)
23
-23312)-23
P, (P, P,) = (P, P)P,
Inverse Permutation
Since a permutation is one-one onto map and hence it is inversible. i.e.. every permutattouy
on a set

P= {a, az...,.a}.
has a unique inverse permutation denoted by f-!,
Thus if f=

then
GROUP THEORY 481
Permutations
Total Number of
Lat X be a set consisting of n distinct elements. Then the elements of X can be permuted in
n! distinct ways. If S, be the set consisting of all permutations of degree n, then the set S. will have
ldistinct permutations of degree n. This set S, is called the symmetric set of permutations of
degree n.
Eor example, if 4= {1, 2, 3}, then S, = Po P- P» P, Pay Ps} where
(1 2 3 1 2 (1 2 3
P2
(1 2 3) |2 3 3 1 2)
2 3 1 2 3)
p=2 1) Ps =
|2 1 3
The multiplication table for the composition of permutations in S, is as given below:
Multiplication Table for S
Po Pi P2 P3 P4 Ps
Po Po P P2 P3 P4 Ps
Pi P P2 Po Ps P3 P4
P2 P Po Pi P4 Ps P3
P3 Ps P4 Ps Po P P2
P4 P4 Ps P3 P2 Po Pi
The table shows that Ps Ps P3 P4 P2 Po

)The multiplication of any two permutations of S, gives apermutation of S,. So, S, is closed
with respect to multiplication.
(i)) Associativity law holds for (p, P) PA -Ps P4 P, and p, (P, P) =PP Po
(iii) Identity element exists, P, when composed with any permutation gives that permutation.
(iv) Every permutation has its own inverse.
Hence S, is a group. It is a non-commutative group since pp, PP)» PP2 PP3
Let Abe a set of degree n. Let P,be the set of all permutations of degree n on 4. Then (P, *)
is a group, called a permutation group and the operation * is the composition (multiplication)n of
permutations.
Theorem 12.25. The set P, of all permutation on nsymbols is finite group of order n! with
respect to the binary composition of permutations. For n s2, P, is abelian and for n > 2 it is always
non-abelian.
The group (P,, *) is also called symmetric group of degree n and denoted by S,.
Cyclic Permutation
A permutation which replaces n objects cyclically is called a cyclic permutation of
degree
(length) n.
For example, consider the set A = (1 23 4} and the permutationfof Aas
1 2 3 4
2 3 4 1)
Here f(1l) = 2, f2) =3, f3) = 4, f4) = 1
Thus, inf, the elements 1. 2, 3, 4form a cycle in the sense that fmaps I ’2, 2
3> 4 and 4 -’ 1. ’ 3.
482 ATEXTBOOK OF DISCRETE
MATHEMATICS
This assignment of values could be presented schematically as follows

Thusf is a cyclic permutation which can also be written as

f= (12 34)
This means that each number is replaced by its successor on the right and the last number by
the first.
Any point of cycle may be taken as the starting point. For example,
(123 4)= (234 l) =(3 4 1 2) =(4 123)
Note that iffis a cyclic permutation with r elements then fcan be represented in r equivalent
ways.

Length of a Cycle
The number of elements permuted by a cycle is said to be its length. If a cycle permutes s
elements, we say that the length of the cycle is s or it is a s-cycle.
Let A = {1, 2, 3, 4, 5}, consider the permutations
1 2 3 4 23 4 5)
2 4 3 1 5 4 2 3)
1 2 3 4 5
1 3 4 5
Then f = (1 24) is of length 3 or 3- cycle
s=(25 3 4) is of length 4 or 4- cycle.
f=(1 2) is of length 2 or 2-cycle.
A cycle of length one means that the image of an element is the element itself.
Cycles of length one are generally omitted.
Product of Cycles
The product of two cycles is obtained by multiplying the permutations represented by them.
Let f= (13 2) andg= (1 4) are two cycle permutations on the set S= {1 2 3 4}

1 2 3 4)
fog
4 2 3 1)
1 2 3
4 =(13 2 4)
2 3 4 2 3
gof =
4 2 3 1 2 4,
(1 2 3 4
42-(432)
GROUP THEORY
483

Note that product of two cyclic permutations need not be a cyclic permutation consider
f=(1 2 5)
:and g = (2 1 4 5 6) be two cyclic permutation on a setA = (1 2 3456}
fog = (125)(2 1456)
(1 2 3 4 5 6 I 2 3 4 5 6
5 3 4 1 6)4 1 3 5 6 2
(1 2 3 4 5 6
1 63 5 4 2
is a permutation on A but not a cyclic permutation.
Inverse of a Cyclic Permutation
Inverse of a cyclic permutation is obtained by reversing the order of its elements.
Thus iff= (1 2 3 ...n -In) is a cyclic permutation of degree n, then
f = (n n-1... 3 2 1)is inverse off
ff= I =f-'f.
Every permutation of afinite set can be expressed as a cycle or as a product of disjoint cycles
(12 3 4 5 6)
a permutation of degree 6 on the set A = {1, 2, 3, 4, 5, 6} is written

as = (1 2) (3 4 6) (5)
The cycle (1 2) has length 2. The cycle (3 4 6) has length 3 and the cycle (5) has length 1 and
none of therm have a symbol common and hence they are disjoint cycles. (no common elements)
Order of Permutation
The order of permutation = lem of length of disjoint cycles. In the above example, the order
of permutation =lcm (2, 3, 1)= 6.
O() = 6

Transpositions
Acyclic permutation such as (a b) which interchanges the symbols leaving allother unchanged
is called a transposition. In other words, transposition is cycle of length two of the form (a b) i.e.,
it is a mapping which maps each object onto itself excepting two, each of which is mapped on the
other e.g. (12) is a transposition.
Every permutation can be resolved as a product of finite number of transpositions but the
decomposition is not unique. However, for a given permutation the number of transpositions is
always even or always odd.
The process consists of two steps:
(i) Express the permutation as a product of disjoint cycles.
(ii) Express each cycle as a product of transpositions.
Every cycle of length n can be expressed as a product of n-l transpositions.
Consider the 5-cycle f= (1 234 5). Them
(1234 5) =(1 2) (1 3) (1 4) (1 5)
Again f= (2 3 4 5 1) = (2 3) (2 4) (2 5) (2 1) etc.
Even and Odd Permutations
A permutation is said to be even or odd according as it can be expressed as a product of even
or odd number of transpositions.
 484 ATEXTBOOK OF DISCRETE
MATHEMATICS
SOLVED EXAMPLES
Example 41. If 4= (1234 5) and B = (2 3) (4 5), ind AB
Solution. We have AB = (1234 5) (2 3) (4 5)
(12 3 4 5)(1 2 3 4 5
|23 4 5 | 3 2 5 4,
(1 23 4 5)(2 3 4 5 1
|2 3 4 5 1)3 2 5 4 1)

= (1 35).

Example 42. Express the pernmutation (1 23 4 5 6) as a product of transpositions.

65 2 4 3 1)
Solution. First we express the given permutation as a product of disjoint cycles. Here 1 is
moved to 6 and then 6 to 1, giving the cycle (1, 6). Then 2 is moved to 5, which is moved to 3.
which is moved to 2, giving (2, 5, 3). This takes care of all the elements except 4 which is left
fixed. Thus
(1 23 4 5 6
6 5 2 4 3 1,
=(16) (253)
Multiplication of disjoint cycles is clearly commutative, so the order of the factors (1, 6)
(2, 5, 3) is not important.
(1 23 4 5 6
Example 43. Show that the permutation is odd, while the permutation
5 6 2 4 13)
1 23 4 5 6)
is even.
6 34 5 2 1)
(1 2 3 4 5 6
Solution. We have - (1 5)(2 6 3)
56 2 4 1 3)
= (1 5) (2 6) (2 3)
Thus the given permutation can be expressed as the product of an odd number of transpositions
and hence the permutation is an odd permutation.
(1 2 3 4 5 6
Again = (1 6) (234 5)
l63 4 5 21)
= (1 6) (2 3) (2 4) (2 5)
Since it is aproduct of an even number of transpositions, the permutation is an even permutation.
Example 44. Find the inverse of the permutation
(12 3 4 5)
|2 3 1 5 4)
Solution. Let the inverse of the given permutation be
1 23 4 5
 485
G R O U P T H E O R Y

3 4 5)
2 3 4 5)
(12
5 123 4 5)
(2 3 1
Then

123 4 5) (1 2 3 4 5
i.e., 2 3 4 5)
y= 5
.x=3, y= 1,z=2, u= 4,
(1 2 3 4 5
inverse is
Hence the required 3 12 5 4
Alternating Group
n!/2 with respect
The set A, of all even permutations of degree n forms a finite group of order
the
composition of permutation and is called alternative group and is denoted by A,
Theorem 12.26 Out of n! permutations of n symbols, n!/2 are even permutations and n!/2 are
odd permutations.

Let the number of even and odd

Proof. Let P, be the set of all permutations on n symbols.
nermutations in P, be s and 1. Then n! =s
+ 1.
number of distinct odd
Let e, e,» ...,e be s distinct even permutations and o,, o,, .... o, be t
permutations, then
P, =e e .., e O1 Og .. o,}
Let Ibe any proposition in P, then by closure property le, le,, ..., le,, lo,, lo,, ... lo, are all
o, are distinct.
distinct elements ofP, For if lo, = lo,, then o, =0, which contradicts that o, and
Now le,, le,, .......le, are odd permutations. Since there are t number of odd permutations,
elements
then s < t. Similarly, we can show that the even permutations lo,, lo,s ....... lo, are distinct
of P. Therefore t s s.
Thus t =s = n!/2.
Theorem 12.27 If 4, is the set of all even permutations of degree n, then A, is a finite group
of order n!/2 with respect to the composition of permutation.
Proof Let fand g be any two even permutations on n symbols.
Closure property : It is known that the product of two even permutations is an even
permutation. Therefore the set A, is closed with respect to the composition of permutation.
Associativity : It is known that the multiplication of permutations is an associative composition.
Existence of Identity : An identity permutation is an even permutation. If I is an identity
permutation then I e [Link] If=f=fIe A,.
Iis an identity element.
Existence of Inverse : Let fe A,. be any even permutation. Then fe P. Thus there exists
an inversef- in P, such that ff-l=ff= 1. Sincefis an even permutation so f is also an even
Permutation and hencef-l e A,. Hence every element of 4, has multiplicative inverse in 4,.
nence A, is a group of all even permutations of order n!/2.
Note that the set O, of all odd permutations does not form a group with respect to the
Omiposition
Set O,
of permutation. As the product of two odd permutations is an even permutation, the
is not closed.
Note: 1. Identity permutation is always an even permutation.
. Every transposition is an odd permutation.
O.A permutation can not be both even and odd.
*.Ihe product of two even permutations is an even permutation.
 486 ATEXTBOOK OF DISCRETE
f= (12 3) g=(3 45)
MATHEMATICS
then f. g =(1 234 5) is an even permutation.
5. The product of two odd permutations is an even permutation.
6. The product of an even permutation and an odd permutation is an odd permutation
f= (12 3) g =(1 234)
fin an even and g an odd permutation.
f =(12 3)(1 2 3 4) = (13 4 2)
f.g is an odd permutation.
7. The inverse of an even permutation is an even permutation and the inverse of an
.
permutation is an odd permutation.
8. Out of n! permutations of nsymbols, (1/2)n! are even permutations and (1/2) n! are
permutations.

12.8. Homomorphism and Isomorphism of Groups

Structure preserving maps between groups are called morphisms. So, to relate two grouns
requires notions about such maps, which is defined below.
Definition. Let (G, o) and (G', *) be two groups. A mapping f: G ’ Gis said to be a
homomorphism if
f(aob) = fa) * f(b), V a, be G.
(G, o) (G, *)

aob
Hfiaob)-f(a)*f(b)
f(b)

Ahomomorphism is said to be a monomorphism if it is one-to-one, i.e., f() -f«) =r

x' where x, x' e G.
Ahomomorphism is said to be an epimorphism if it is onto, i.e., every element of Gis an
image of some element x e G.
Ahomomorphism of a group (G, o) into itself is called an endomorphism, Le.,f: G’ Gis
said to be an endomorphism iff(a o b) =f (a) of(b), Vab, e G.
The image offis called the homomorphic image of fand is denoted by f(G).
For example,
Let G= (R, +) and G=(R*.). The mapping f: G G is defined by f(r) = 2¥. Then for a, b
e G, a+ beG we havef(a) = 2°, f(b) = 2 and f(a + b) = 2a+6,
Now,f (a+b) = 20+b = 20. 2b =f(a) .f (b)
So,fis a homomorphism.
Baste Properties on Homomorphisms
Theorem 12.28. Let (G, o) and (G, ") be two groups and f: G- G be a homomorphism.
()f(e) = e where e and e' are identity elements of G and G respectively
(i) f(a') = f(a)}, ae G.
(ii)if ae G thenf(a") = f(a)}", n being an integer
(iv) if a e G and o(a) is finite then of (a) is a divisor of o(a).
Proof:
(1) Here ae G ’ fa) e G'
f(a) * e f(a), as e' is the identity element of G.
 GROUP THEORY
487

= f(a o e), as e is the identity element of G.

= f(a) *f(e), as fis a homomorphism
f(a) * e' = f(a) *f(e), in G
e' = f(e), by left cancellation law in G'.
f(e) = e'.
(i) ae G ’ ae G. Then f(a) e G' andf(a) e G.
e' =f(e) =f(a oa)=f(a) *f(al) ...(1)
Also, e' = f(e) =f(aoa) =f(a') *f(a) ...(.2)
From (1) and (2), we get
f(a) *f(a') = f(a) *f(a) = e'
Hence f(a') is the inverse off (a) in G'.
flal) = S(a)},,Vae G.
(iii) Case 1 :n= 0
In this case the given statement reduces to () and hence it holds.
Case 2 : n is a positive integer
The given statement is true for n = 1. Let us assume that it is true for n= m, mn
being a positive
integer.
Then f(a") = f(a)}",
f(amt) = f(am o a)
= f(a") *f(a), since fis a homomorphism
= f(a)}" *f(a), by (1)
= (f(a)} mt1.
This show that if the given statement is true for m then
it is also true for m + 1. But we have
already seen that it is true for n = 1, so by the principle of
statement is true for any positive integer n. mathematical induction the given
Case 3 : n is a negative integer
Let n = - m where m is a positive integer.
f(a) = fam) =f {(alym
Sla)}, by Case 2
= [(a)}-", by (i)
=

fa)}-m=f(a)}".
f(a) = f(a)}", for any integer n.
(iv) Let a e G and o(a) = m, a finite number.
an = ’ f(am) =f(e) = e', by (i)
e

f(a)}m = e, by (iü)
’o(f(a) is a divisor of m=o (a).
Bxample 45. Show that the group (Zo, +} is a
homomorphic image of the group {Z, +}.
Solution. Here Z = the set of all integers and Z,= {[0].
e residue classes [|], (2], .. [8]} where [0], [1], ..., [8]
mnodulo 9.
Let us consider the
mapping
f:Z’ Z, defined byf(m) = [m] (mod 9).
Jis ahomomorphism, since
f(m + n) =[m + n]= [m] + [n]=f(m) +f(n), Vm, n Z.