Cryptography Reference
In-Depth Information
In the example given earlier (i.e.,
G
=
Z
6
,
+
and
H
=
{
0
,
2
,
4
}
), the
elements of
G
are partitioned into the following two left cosets of
H
:
1+
H
=3+
H
=
{
1
,
3
,
5
}
2+
H
=4+
H
=
{
2
,
4
,
6
}
The notion of a coset is important to prove Theorem 3.1 that is due to
Lagrange.
8
Theorem 3.1 (Lagrange's Theorem)
If
H
is a subgroup of
G
,then
|
H
|||
G
|
(i.e.,
the order of
H
divides the order of
G
).
Proof.
If
H
=
G
,then
|
H
|||
G
|
holds trivially. Consequently, we only consider the
case in which
H
⊂
G
.Forany
a
∈
G
\
H
,thecoset
a
∗
H
is a subset of
G
.The
following can be shown:
i) For any
a
=
a
,if
a/
a
∗
(
a
∗
∈
H
then (
a
∗
H
)
∩
H
)=
∅
;
ii)
.
For (i), suppose there exists a
b
|
a
∗
H
|
=
|
H
|
(
a
∗
∈
(
a
∗
H
)
∩
H
). Then there exist
c, c
∈
c
=
b
=
a
∗
c
. Applying various group axioms, we have
H
such that
a
∗
c
−
1
)=
b
c
−
1
=(
a
∗
c
)
c
−
1
=
a
∗
(
c
∗
c
−
1
)
a
∗
a
=
a
∗
e
=
a
∗
(
c
∗
∗
∗
∈
H
.
a
∗
This contradicts our assumption (that
a/
∈
H
).
holds trivially (by the definition of a coset). Suppose
that the inequality is rigorous. This is only possible if there are
b, c
For (ii),
|
a
∗
H
|≤|
H
|
∈
H
with
b
=
c
and
a
c
. Applying the inverse element of
a
on either side of the equation,
we get
b
=
c
, contradicting to
b
∗
b
=
a
∗
=
c
.
In summary,
G
is partitioned by
H
and the family of its mutually disjoint
cosets, each has the size
|
H
|
|
H
|||
G
|
, and hence
. This proves the theorem.
Quotient Groups
Let
G
be a (commutative) group and
H
G
a subgroup of
G
. The quotient group
of
G
modulo
H
, denoted by
G/H
, is the set of all cosets
a
⊆
∗
H
with
a
ranging over
G
, and with the identity element being
e
∗
H
. For example, for every positive integer
+
,theset
n
∈
N
{
0
,
±
n,
±
2
n,...
}
is a subgroup of
Z
under integer addition. The
quotient group
8
Joseph Louis Lagrange was a French mathematician who lived from 1736 to 1813.
