Cryptography Reference
In-Depth Information
Theorem 2.9
(Lagrange's theorem)
If G is a finite group and H a subgroup of G
then the order of H divides the order of G.
Proof
We have just noticed that
G
is the disjoint union of all the right cosets defined
by
H
. Now, observe that all the right cosets have the same number of elements
because if
Hx
and
Hy
are two different cosets (i.e.,
x
and
y
are not equivalent in the
equivalence relation defined by
H
) then the map from
Hx
to
Hy
that maps
hx
to
hy
is a bijection. Thus
G
is a disjoint union of sets which have
|
H
|
elements each (note
that
H
itself is a right coset, namely, the one corresponding to 1
∈
G
) and hence
|
H
|
divides
|
G
|
.
Corollary 2.1
If G is a finite group and x
∈
G then the order of x divides the order
of G. In particular, x
|
G
|
=
1
.
∈
Proof
The order of
x
G
is, aswe have seen, the order of the subgroup
x
generated
by
x
, so that the order of
x
divides
|
G
|
by Lagrange's theorem. Thus, if
i
is the
1 and hence
x
|
G
|
=
x
ti
x
i
t
order of
x
we have that
|
G
|=
ti
for some
t
≥
=
(
)
=
1
t
=
1.
Exercise 2.10
Prove that if
H
is a subgroup of
G
, then
G
is the disjoint union of
the left cosets
xH
, all of which are in bijective correspondence with
H
.
Exercise 2.11
Show that each subgroup of a cyclic group is also cyclic.
Exercise 2.12
Show that if
G
is a finite cyclic group and
d
||
G
|
, then there exists
exactly one subgroup of
G
of order
d
.
is defined
as the number of right cosets (or, equivalently, of left cosets) of
H
in
G
.If
G
is a
finite group and
K
If
H
is a subgroup of
G
, then the
index
of
H
in
G
, denoted
(
G
:
H
)
⊆
H
⊆
G
are subgroups, then it follows from the preceding
discussion that
(
G
:
K
)
=
(
G
:
H
)(
H
:
K
)
. It is also clear that
|
G
|=
(
G
:{
1
}
)
and
that
.
Suppose now that
G
is an abelian group and
H
a subgroup of
G
. Then it is easy to
see that the set of cosets, denoted
G
|
G
|=
(
G
:
H
)
|
H
|
/
H
, has the structure of a group with operation
given by
HxHy
=
Hxy
.
G
/
H
is then called the quotient group of
G
modulo
H
and its order satisfies
|
G
/
H
|=|
G
|
/
|
H
|
.
Remark 2.1
Quotient groups may be defined even if the group
G
is not abelian,
provided that
H
is a
normal
subgroup of
G
, which means that
xH
=
Hx
for every
x
G
, so that the left and the right cosets coincide. Of course, the subgroups of an
abelian group
G
are all normal.
∈
Let
f
:
G
→
H
be a homomorphism of groups. Then the
kernel
of
f
is defined
as Ker
f
={
x
∈
G
|
f
(
x
)
=
1
}⊆
G
and the
image
of
f
is Im
f
={
f
(
x
)
|
x
∈
G
H
.Ker
f
is a normal subgroup of
G
and Im
f
is a subgroup of
H
. Observe
that
f
is injective if and only if Ker
f
}⊆
={
1
}
(because
f
(
x
)
=
f
(
y
)
if and only if
xy
−
1
∈
Ker
f
) and that
f
is surjective if and only if Im
f
=
H
.
