i
i
main”—2013/4/10—15:19—page44—#56
i
i
i
i
i
i
44 Algebraische Strukturen
sind äquivalent zu x<x
und y>y
. Deshalb hat π genau
m
2

n
2
Fehlstellungen.
Dies zeigt:
sgn ν
1
) = (1)
m(m1)
2
n(n1)
2
= (1)
m1
2
n1
2
Damit haben wir (a) für positive Zahlen bewiesen, denn es gilt
n
m
1
=
n
m
.Zu
(b): Wegen
(n 1)/2 (n 1)/2mod2können wir n 1 annehmen. Nach
Lemma 1.13 gilt:
!
1
n
"
= sgn(x →−x mod n) =
x<y
x y
y x
= (1)
(
n
2
)
= (1)
n1
2
Die Eigenschaft (d) gilt nach Satz 1.14, da sgn ein Homomorphismus ist. Insbesondere
gilt damit das quadratische Reziprozitätsgesetz (a) für alle ungeraden teilerfremden
Zahlen
m, n Z. Zu (c): Ohne Einschränkung sei n 1. Aus dem bereits Gezeigten
folgt:
!
2
n
"
(d)
=
!
1
n
"!
n 2
n
"
(a)
=
!
1
n
"!
n
n 2
"
(b)
= (1)
n1
2
!
2
n 2
"
Die Behauptung erhalten wir daraus mit Induktion nach n. Zu (e): Nach dem chine-
sischen Restsatz existiert
r N mit r 1mod4und r m mod n.Damitgilt:
!
m
n
"
=
!
r
n
"
(a)
=
!
n
r
"
(d)
=
!
n
1
r
"!
n
2
r
"
(a)
=
!
r
n
1
"!
r
n
2
"
=
!
m
n
1
"!
m
n
2
"
Dies schließt den Beweis ab.
Der hier vorg estellte Beweis des quadratischen Reziprozitätsgesetzes stammt von
George Rousseau [72]. Das quadratische Reziprozitätsgesetz liefert den folgenden Al-
gorithmus zur Berechnung des Jacobi-Symbols:
/
*
Voraussetzung: m, n 1, n ungerade, ggT(m, n) = 1
*
/
function Jacobi(m,n)
begin
if
m = 1 then return 1;
if m 0mod2then return (1)
n
2
1
8
Jacobi(
m
2
,n)
else return (1)
m1
2
n1
2
Jacobi(n mod m, m)
end
Hierbei genügt es, bei den Zahlen
m und n im Exponenten von 1 jeweils die letzten
4 Bits zu betrachten, um festzustellen ob sich der Term zu 1 oder 1 auswertet.
Aufgaben
1.1. Zeig en Sie, dass in einem endlichen Monoid M jedes Linksinverse auch rechts-
invers ist, d. h., für alle
a, b M mit ba = 1 gilt ab = 1.
1.2. Zeigen Sie, dass die Aussage von Aufgabe 1.1. auf unendliche Monoide nicht
zutrifft.
i
i
main”—2013/4/10—15:19—page45—#57
i
i
i
i
i
i
Aufgaben 45
1.3 . Sei S eine Halbgruppe. Ein Element a S heißt quasi-invertierbar, falls es ein
b S gibt mit aba = a. Zeigen Sie, dass zu jedem quasi-invertierbaren Element
a S ein Element c S existiert mit aca = a und cac = c.
1.4. Sei
S eine endliche Halbgruppe mit n Elementen und seien a
1
,...,a
n
S
beliebig. Zeigen Sie, dass ein Index i ∈{1,...,n} und ein Element b S mit
a
1
···a
i
= a
1
···a
i
b existieren.
1.5. Geben Sie ein endliches Monoid
M und ein Untermonoid U von M an, so dass
|U| kein Teiler von |M| ist .
1. 6. Seien
X und Y nichtleere Mengen, sei S eine Halbgruppe, und sei ϕ : Y ×X
S
eine Abbild ung. Zeigen Sie, dass die Verknüpfung mit (x, s, y) (x
,s
,y
) =
(x, s · ϕ(y,x
) · s
,y
) auf der Menge X × S × Y eine Halbgruppe definiert, die
sogenannte Rees-Sandwich-Halbgruppe nach David Rees (geb. 1918).
1.7. Sei
G eine Halbgruppe. Zeigen Sie:
(a) Wenn ein Element
e G existiert mit:
Für alle
g G gilt eg = g (linksneutrales Element).
Für alle
g G existiert h G mit hg = e (linksinverse Elemente).
Dann ist
G eine Gruppe.
(b) Wenn ein Element
e G existiert mit:
Für alle
g G gilt ge = g (rechtsneutrales Element).
Für alle
g G existiert h G mit hg = e (linksinverse Elemente).
Dann braucht
G keine Gruppe zu sein.
(c) Wenn für alle
a, b G die Gleichungen a · x = b und y · a = b eindeutige
Lösungen
x,y G besitzen, dann ist G eine Gruppe.
1.8. Sei
G eine Gruppe und sei S G eine Teilmenge.
(a) Zeigen Sie, dass die folgenden Eigenschaften äquivalent sind:
(i)
S ist eine Untergruppe von G.
(ii)
S und für alle x, y S gilt xy
1
S.
(b) Sei
S endlich. Zeigen Sie, dass dann die folgenden Eigenschaften äqui valent sind.
(i)
S ist eine Untergruppe von G.
(ii)
S und für alle x, y S gilt xy S.
(c) Geben Sie eine Gruppe
G und eine unendliche Teilmenge S G an, welche keine
Untergruppe bildet aber die Eigenschaft
xy S für alle x,y S erfüllt.
1.9. Sei
M ein Monoid, so dass m
2
= 1 für alle m M gilt. Zeigen Sie, dass M eine
kommutative Gruppe ist.

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.