i
i
main”—2013/4/10—15:19—page24—#36
i
i
i
i
i
i
24 Algebraische Strukturen
Sei n N.Fürjedezun teilerfremde Zahl k lassen sich mit dem erweiterten eukli-
dischen Algorithmus zwei ganze Zahlen
a, b bestimmen mit ak + bn = 1.Wennwir
modulo
n rechnen, dann gilt ak 1modn.Alsoista ein multiplikatives Inverses
von
k.Etwasgenauerbetrachtenwir(Z/nZ)
, die Elemente aus Z/nZ mit multipli-
kativen Inversen, im folgenden Satz.
Satz 1.30. Sei
n N. Dann gelten die folgenden Aussagen:
(a)
(Z/nZ)
={k + nZ |ggT(k, n) = 1}
(b) Die Zahl n ist genau dann eine Primzahl, wenn Z/nZ ein Körper ist.
(c) Sei
k Z. Die Multiplikation Z/nZ Z/nZ,x→ kx mit k ist genau dann bijektiv,
wenn
ggT(k, n) = 1 gilt.
Beweis. (a): Es gilt
k (Z/nZ)
genau dann, wenn wir 1 = k + mn schreiben
können. Nach Satz 1.29 ist dies genau dann der Fall, wenn
ggT(k, n) = 1.
(b): Der Ring
Z/nZ ist genau dann ein Körper, wenn alle von Null verschiedenen
Elemente invertierbar sind. Das bedeutet nach (a), dass alle natürlichen Zahlen von 1
bis
n 1 zu n teilerfremd sind. Dies wiederum ist gleichwertig zur Primzahleigen-
schaft.
(c): Für
ggT(k, n) = 1 ist k in (Z/nZ)
invertierbar, und die Multiplikation mit k
hat eine inverse Abbildung; sie ist damit bijektiv. Haben k und n einen gemeinsamen
Teiler
m 1,soistk ·(n/m) nZ und damit k · (n/m) 0 k · 0modn,aber
n/m ≡ 0modn.
1.5.2 Ideale in den ganzen Zahlen
Eine für die modulare Arithmetik wichtige Begriffsbildung aus der Algebra sind Idea-
le. Das Interesse an Idealen v on
Z erklärt sich durch den Umstand, dass sich Teilbar-
keit in
Z durch Teilmengenbeziehun gen von Idealen formulieren lässt. Es gilt
k | Z kZ
Aus dem folgenden Satz erhalten wir eine Umkehrung dieser Aussage: Jede Teilmen-
genbeziehung von Idealen in
Z lässt sich auch durch Teilbarkeit von Zahlen darstel-
len.
Satz 1.31. Sei
I ein Ideal von Z. Dann existiert genau ein n N mit I = nZ.DieZahln
ist hierbei der größte gemeinsame Teiler aller Zahlen aus I. Insbesondere gilt:
kZ +Z = ggT(k, ) Z
Beweis. Falls I ={0} gilt, erfüllt n = 0 die Behauptung. Sei nun I {0}.Füral-
le
a, b I finden wir p, q Z mit ggT(a, b) = ap + bq.Alsoistgenaudann
ggT(a, b) I,wenna, b I gilt. Hieraus folgt die Behauptung unter Beachtung,

Get Diskrete algebraische Methoden now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.