Cryptography Reference
In-Depth Information
Somit gibt es ein
y
∈
Z
mit
ab
−
1
=
ny
∈
n
Z
. Jeder gemeinsame Teiler von
a
(
)=
und
n
ist ein Teiler von 1, daher folgt ggT
a
,
n
1.
Ist ggT
1, so existieren nach dem Satz 4.10 zum euklidischen Algorithmus
ganze Zahlen
b
und
y
mit
ab
(
a
,
n
)=
+
=
ny
1, und es gilt
(
a
+
n
Z
)
·
(
b
+
n
Z
)=
ab
+
n
Z
=
1
+
n
Z
.
Somit ist
a
Z
∈
Z
n
invertierbar.
Nach diesem Satz gilt
=
a
+
n
Z
n
=
{
a
∈
Z
n
; ggT
(
a
,
n
)=
1
}
.
Beispiel
Wir geben die primen Restklassengruppen für einige kleine
n
an:
Z
2
=
{
Z
3
=
{
Z
4
=
{
Z
5
=
{
1
}
,
1, 2
}
,
1, 3
}
,
1, 2, 3, 4
}
,
Z
6
=
{
Z
7
=
{
Z
8
=
{
1, 5
}
,
1, 2, 3, 4, 5, 6
}
,
1, 3, 5, 7
}
.
Z
8
·
=
In
ist jedes Element zu sich selbst invers und es gilt etwa 3
5
7.
Wir ziehen einige wichtige Folgerungen. Die erste sollte aus der linearen Algebra
bekannt sein, sie wurde auch schon in Abschnitt 3.1 verwendet.
Korollar 4.17
Der Ring
(
Z
n
,
+
·
)
,
ist genau dann ein Körper, wenn n eine Primzahl ist.
=
Beweis.
Der Ring
0 invertier-
bar sind. Das ist nach Satz 4.16 gleichwertig dazu, dass alle Zahlen 1, . . . ,
n
Z
n
ist genau dann ein Körper, wenn alle Elemente
−
1z
u
n
teilerfremd sind; und das ist genau dann erfüllt, wenn
n
eine Primzahl ist.
4.3.2 Lineare Kongruenzgleichungen
In Satz 4.10 zum euklidischen Algorithmus wurde die Existenz einer Darstellung
des ggT zweier ganzer Zahlen
a
und
b
gezeigt:
∈
Z
(
)=
+
Es gibt
x
,
y
mit ggT
a
,
b
ax
by
.
Wir können nun die Frage nach der Eindeutigkeit einer solchen Darstellung klä-
ren.
Lemma 4.18
Es seien a und b ganze Zahlen und d
=
(
)
∈
Z
=
+
ggT
a
,
b
. Sind x
,
y
mit d
ax
by
gewählt, so gilt:
k
b
d
k
a
ax
+
by
für x
,
y
∈
Z
⇔∃
mit x
=
und y
=
d
=
k
∈
Z
x
+
y
−
d
.
