Cryptography Reference
In-Depth Information
Beweis.
Wir wählen in
G
ein Element mit
o
(
b
)=
ε
(
G
)
und zeigen
ε
(
G
)=
|
G
|
.
ε
(
)
≤|
|
Nach dem Satz von Euler (Korollar 6.9 (a)) gilt
G
G
.
X
ε
(
G
)
−
Jedes Element
a
∈
G
ist Nullstelle des Polynoms
f
=
1
∈
K
[
X
]
.Da
ε
(
)=
dieses Polynom nach Satz 3.9 höchstens
G
deg
f
Nullstellen haben kan
n,
gilt andererseits auch
|
G
|≤
ε
(
G
)
,d.h.
|
G
|
=
ε
(
G
)
.
Z
p
ν
,
p
6.1.8 Die Gruppen
=
2
, sind zyklisch
Z
n
p
ν
,
p
=
=
Wir zeigen nun, dass
für jede ungerade Primzahlpotenz
n
2, zy-
klisch ist. Den Beweis bereiten wir mit einer Hilfsaussage vor.
Lemma 6.13
Für jede ungerade Primzahlpotenz p
ν
,
ν ≥
1
, gilt:
p
ν−
1
p
ν−
1
mod
p
ν
+
1
mod
p
ν
)
(
+
)
≡
(
(
+
)
≡
(
)
1
p
1
,
1
p
1
.
Beweis.
Wir zeigen die Behauptung mit vollständiger Induktion nach
ν
.
p
ν−
1
ν
=
ν ≥
(
+
)
=
Die Behauptung stimmt für
1 und sei richtig für ein
1, d. h.
1
p
kp
ν
mit
p
+
1
k
. Es folgt
p
j
p
j
=
0
p
ν
kp
ν
)
p
kp
ν
)
j
(
1
+
p
)
=(
1
+
=
(
p
−
1
kp
ν
+
1
k
2
p
2
ν
+
1
kp
ν
+
1
mod
p
ν
+
2
=
+
+
+
··· ≡
+
(
)
1
1
.
2
Die Aussage gilt also auch für
ν
+
1.
Damit können wir nun zeigen:
Satz 6.14
(Gauß)
Für jede ungerade Primzahlpotenz p
ν
Z
p
ν
ist die multiplikative Gruppe
eine zyklische
p
ν−
1
.
Gruppe der Ordnung
(
p
−
1
)
p
ν
Z
Beweis.
Wir kürzen
a
:
=
a
+
ab. Wegen Satz 6
.1
2 existiert ein
a
∈
Z
de
r
art,
Z
∈
Z
p
die Ordnung
p
1
hat. Aus
a
o
(
a
)
≡
mod
p
ν
)
folgt
a
o
(
a
)
≡
+
−
(
dass
a
p
1
1
(
mod
p
)
, und damit gilt
p
−
1
|
o
(
a
)
nach (iii) in Lemma 6.1. Es gelte etwa
a
r
(
)=
(
−
)
(
)=
−
o
a
r
p
1
. Dann gilt
o
p
1. Damit ist ein Element der Ordnung
Z
p
ν
ein Element der Ordnung
p
ν−
1
an.
Wegen der Kongruenz in Lemma 6.13 gilt 1
Z
p
ν
gefunden. Wir geben nun in
p
−
1in
p
p
ν−
1
+
=
1, wegen der Inkongruenz
p
p
ν−
2
p
ν−
1
nach (iii) in Lemma
in Lemma 6.13 gilt 1
+
=
1. Damit folgt
o
(
1
+
p
)=
1,
p
ν−
1
(
−
)=
6.1 (b). Wegen ggT
p
1 ergibt sich mit Aufgabe 6.2
p
ν
−
1
.
(
·
+
)=(
−
)
o
a
1
p
p
1
|
Z
p
ν
|
=
ϕ
(
Z
p
ν
=
Z
p
ν
p
ν
)=(
p
ν−
1
, also
Nun ist
p
−
1
)
a
·
1
+
p
. Daher ist
zyklisch.
