Cryptography Reference
In-Depth Information
Beispiel
Ist
Z
18
Z
n
ϕ
(
ϕ
(
))
zyklisch, so gibt es genau
n
erzeugende Elemente, z. B. hat
genau
ϕ
(
ϕ
(
18
)) =
ϕ
(
6
)=
2 erzeugende Elemente (vgl. obiges B
ei
spiel). Und in
(
Z
p
,
+)
der additiven Gruppe
für eine Primzahl
p
ist jedes von 0 verschiedene
Element ein erzeugendes Element, da
ϕ
(
p
)=
p
−
1 gilt.
Bemerkung
Wir haben in diesem Kapitel Untergruppen einer Gruppe
(
·
)
G
,
betrachtet, die
a
n
von
einem
Element
a
. Wir können
allgemeiner auch Untergruppen betrachten, die von
endlich vielen a
1
,...,
a
n
∈
G
erzeugt werden:
a
=
{
∈
G
;
n
∈
Z
}
∈
G
erzeugt werden. Wir beschränken uns auf den Fall, dass
G
kommutativ ist. Dann
ist
a
ν
1
∈
Z
a
ν
n
;
a
1
,...,
a
n
:
=
···
ν
1
,...,
ν
n
ebenso eine Untergruppe von
G
- die von
a
1
,...,
a
n
erzeugte Untergruppe
von
G
. Man beachte, dass
a
1
,...,
a
n
die Menge aller Produkte aller Potenzen der
Elemente
a
1
,...,
a
n
∈
G
ist.
6.1.2 Der Satz von Lagrange
Lemma 6.2 legt den Verdacht nahe, dass die Ordnungen von Gruppenelementen
endlicher Gruppen Teiler der Gruppenordnung sind (vgl. auch das Beispiel auf
Seite 95). Tatsächlich gilt dies allgemeiner für jede Untergruppe einer endlichen
Gruppe. Das ist Inhalt des Satzes von Lagrange:
Satz 6.4
(Lagrange)
Ist U Untergruppe einer endlichen Gruppe G, so ist
|
U
|
ein Teiler von
|
G
|
, kurz
|
|||
|
U
G
;
insbesondere gilt o
(
a
)
| |
G
|
für jedes a
∈
G.
Beweis.
Wir begründen vorab, dass
{
aU
;
a
∈
G
}
eine Partition der (endlichen)
=
a
∈
G
aU
.
∈
= ∅
∈
Menge
G
ist: Für jedes
a
G
ist
aU
, und wegen 1
U
gilt
G
Es sei
au
=
bv
mit
u
,
v
∈
U
ein Element aus dem Durchschnitt
aU
∩
bU
zweier
. Dann liegen die Elemente
b
−
1
a
und
a
−
1
b
{
∈
}
Elemente
aU
und
bU
aus
aU
;
a
G
in
U
, folglich gilt
aU
⊆
bU
und
bU
⊆
aU
,d.h.
aU
=
bU
.
∈
Es ist
eine Partition der endlichen Menge
G
. Somit ist
G
disjunkte
Vereinigung endlich vieler Nebenklassen:
{
aU
;
a
G
}
G
=
a
1
U
∪···∪
a
r
U
.
∈{
}
|
|
=
|
|
→
→
Da für jedes
i
1, . . . ,
r
gilt
a
i
U
U
- es ist nämlich
ι
:
U
a
i
U
,
u
a
i
u
eine Bijektion -, folgt
|
G
|
=
r
|
U
|
.