Universit¨

at Karlsruhe (TH)

Fakult¨

at f¨

ur Mathematik

Das quadratische

Reziprozit¨

atsgesetz

f¨

ur Polynomringe

Zulassungsarbeit

von

Isolde Wallbaum

betreut von PD Dr. Stefan K¨

uhnlein

Mathematisches Institut II

Juli 2005

---

Vorwort

Quadratische Reziprozit¨

at geh¨

ort zum Gebiet der algebraischen Zahlentheo-

rie. Euler (1707-1783) war der erste, der vermutete, dass f¨

ur zwei verschiedene

ungerade Primzahlen p und q folgende Beziehung gilt:

Wenn eine der beiden Zahlen p-1 oder q-1 gerade ist, also p 1(mod 4)

2

2

oder q 1(mod 4), dann gilt: p ist genau dann quadratischer Rest modulo

q, wenn auch q quadratischer Rest modulo p ist.

Wenn aber beide Zahlen p-1 und q-1 ungerade sind, also p 3(mod 4)

2

2

und q 3(mod 4), dann gilt: p ist genau dann quadratischer Rest modulo

q, wenn q kein quadratischer Rest (oder quadratischer Nichtrest) modulo

p ist.

Es werden also Kongruenzen modulo verschiedener Primzahlen verglichen. Eu-

lers Vermutung wurde als erstes von Gauß (1777-1855) im Abschnitt 4 seiner

Disquisitiones Arithmeticae" bewiesen, und er gab insgesamt sieben Beweise

"

f¨

ur diesen Satz. Der Begriff der quadratischen Reziprozit¨

at wurde jedoch von

Legendre (1752-1833) gepr¨

agt, denn er hat das bekannteste quadratische Rezi-

prozit¨

atsgesetz formuliert, wof¨

ur es ca. 150 Beweise gibt. Legendre ging dabei

folgendermaßen vor: er definierte f¨

ur ungerade Primzahlen p und q ein Symbol

q

p-1

mit Werten in {-1, 1}. Unter der Voraussetzung, dass q q 2 (mod p)

p

p

gelte, verfasste er das quadratische Reziprozit¨

atsgesetz wie folgt:

Seien p, q N verschiedene ungerade Primzahlen. Dann gilt

p

q

p-1

= (-1) 2 · q-1

2 .

q

p

In dieser Arbeit beweisen wir obigen Satz mit der ¨

Anderung, dass p und q

irreduzible Elemente aus Polynomringen ¨

uber endlichen K¨

orpern sind.

In den ersten drei Kapiteln m¨

ochte ich den Leser auf den Beweis des quadra-

tischen Reziprozit¨

atsgesetzes in Polynomringen vorbereiten. Das Vorgehen im

Beweis (Abschnitt 3.4) lehnt sich eng an Helmut Hasse (1898-1979) an, der

sich jedoch nicht auf den quadratischen Fall beschr¨

ankt, sondern die allgemei-

ne G¨

ultigkeit des Reziprozit¨

atsgesetzes zeigt. Daf¨

ur definiert er das Legendre-

Symbol neu. Auf diese Verallgemeinerung bin ich im letzten Kapitel eingegan-

gen.

An dieser Stelle m¨

ochte ich mich besonders herzlich bei meinem Betreuer Herrn

PD Dr. Stefan K¨

uhnlein bedanken, der einen großen Teil zu meiner Freude an

dieser Arbeit beigetragen hat. Durch seine freundliche und unkomplizierte Art

und seine Bereitschaft, mich mit meinen Problemen jederzeit willkommen zu

heißen, um mir sehr geduldig und anschaulich all meine Fragen zu beantworten,

hat er mich immer wieder aufs Neue motiviert. Vielen Dank auch an meinen

1

---

lieben Studienkollegen Karsten Kremer, der mir ¨

uber die ganze Zeit hinweg

mit sehr hilfreichen Tipps, Erkl¨

arungen und wertvollen Korrekturvorschl¨

agen

zur Seite stand und mir damit fortw¨

ahrend half, Ordnung in meine Gedanken

und in diese Arbeit zu bringen. Schließlich gilt mein Dank meinen Eltern, die

durch ihre liebevolle und nat¨

urlich auch finanzielle Unterst¨

utzung in meinem

gesamten Studium das Entstehen dieser Arbeit erst erm¨

oglichten.

Hiermit versichere ich, vorliegende Arbeit selbst¨

andig und ausschließlich mit

den angegebenen Hilfsmitteln angefertigt zu haben.

Karlsruhe, den 12. Juli 2005

Isolde Wallbaum

2

---

Inhaltsverzeichnis

1

Polynomringe

4

1.1

Allgemeine Bezeichnungen .

4

1.2

Eigenschaften .

4

1.3

Ideale

.

9

2

K¨

orper

11

2.1

K¨

orpererweiterung

12

2.2

Endliche K¨

orper 14

3

Das quadratische Reziprozit¨

atsgesetz

20

3.1

Ganze Zahlen 20

3.2

Polynome ¨

uber endlichen K¨

orpern 20

3.2.1

Eulers Hilfssatz 21

3.3

Beispiele 22

3.3.1

Allgemeine lineare Polynome 22

3.3.2

Quadratische Polynome

23

3.4

Beweis 25

4

Das allgemeine Reziprozit¨

atsgesetz

29

4.1

Charaktere 29

4.2

Verallgemeinerung des Legendre-Symbols 31

Anhang

34

3

---

1

POLYNOMRINGE

1

Polynomringe

Zun¨

achst werden hier einige Eigenschaften von Polynomringen in einer Varia-

blen X genannt, wobei das Hauptaugenmerk auf K¨

orpern als den zugeh¨

origen

Koeffizientenbereichen liegt. Der Polynomring K[X] wird von Polynomen mit

Koeffizienten aus K gebildet. Man betrachte f K[X] und f (x) als die dem

Polynom zugeordnete Funktion, die einem Element x den Funktionswert f (x)

zuordnet. Nun ist es m¨

oglich, Elemente aus beliebigen K¨

orpern oder kommuta-

tiven Ringen K K in x einzusetzen, indem man die Variable X durch dieses

x ersetzt und den entstehenden Ausdruck f (x) als Element in K betrachtet.

Im dritten Abschnitt dieses Kapitels werden Ideale eingef¨

uhrt mit der Absicht,

sp¨

ater mit Polynomringen als Hauptidealringen zu arbeiten.

1.1

Allgemeine Bezeichnungen

Es seien R ein Ring, R[X] der Polynomring in einer Variablen X ¨

uber R und

f, g R[X]. Im Folgenden seien e = grad(f ), d = grad(g) und ai, bj R

jeweils die Koeffizienten von f bzw. g, wobei ae, bd = 0. Also:

e

f =

aiXi = aeXe + ... + a1X + a0

i=0

d

g =

bjXj = bdXd + ... + b1X + b0

j=0

1.2

Eigenschaften

F¨

ur Polynome f, g R[X] gilt

· grad(f + g) max(grad(f), grad(g)),

denn f¨

ur Koeffizienten ak und bk von f und g gilt ak + bk = 0 f¨

ur

k > max(grad(f ), grad(g)). Es gilt auch

· grad(f · g) grad(f) + grad(g),

denn

a

k+l=i

k ·bl = 0 f¨

ur i > grad(f )+grad(g). Das letzte Summenglied

von f · g kann also h¨ochstens die Summe beider Grade von f und g zum

Grad haben.

4

---

1

POLYNOMRINGE

Definition 1.1 Ein kommutativer nullteilerfreier Ring R = 0 mit Einselement

(neutrales Element der Multiplikation) heißt Integrit¨

atsring.

Satz 1.2 Wenn R ein Integrit¨

atsring ist, dann auch R[X].

Beweis:

1) Kommutativit¨

at:

Vor.: f¨

ur a, b R gilt a · b = b · a

z.z.: f¨

ur f, g R[X] gilt f · g = g · f

Es ist:

e

d

e

d

e

d

f · g =

aiXi ·

bjXj =

aibjXi+j =

bjaiXj+i

i=0

j=0

i=0 j=0

i=0 j=0

d

e

d

e

=

bjaiXj+i =

bjXj ·

aiXi

j=0 i=0

j=0

i=0

= g · f

2) Einselement:

Vor.: Es existiert die Eins f¨

ur jedes a in R mit a · 1R = a.

z.z.: Dann gibt es auch das Einselement f¨

ur alle Polynome f in R[X] mit

f · 1R[X] = f .

Wegen

R - R[X]

a

- a · X0 + 0 · X1 + ... (konstantes Polynom)

ist R R[X]. D.h. die 1R in R wird auf sich selbst in R[X] abgebildet.

Wir zeigen jetzt, dass 1R · f = f · 1R = f f¨ur alle f im Polynomring R[X]

gilt.

Sei also f =

e

a

i=0

iX i mit ai R. Dann ist

e

e

1R · f = 1R ·

aiXi =

1R · aiXi = f.

i=0

i=0

3) Nullteilerfreiheit:

Vor.: f¨

ur a, b R und a, b = 0 gilt a · b = 0

z.z.: f¨

ur f, g R[X] und f, g = 0 gilt f · g = 0

Seien f =

e

a

b

i=0

iX i und g =

d

j=0

j X j mit ae, bd = 0.

5

---

1

POLYNOMRINGE

e+d

k

f · g =

aibk-i Xk

k=0

i=0

= a0b0 + (a0b1 + a1b0)X + ... +

aebd

·Xe+d

=0, da R NT-frei nach Vor.

Falls R also nicht nur Ring, sondern sogar Integrit¨

atsring ist, so ist der Koef-

fizient des letzten Summenglieds (mit der h¨

ochsten Potenz) ae · bd = 0, woraus

folgt, dass grad(f · g) = grad(f ) + grad(g) ist.

Definition 1.3 Die Menge der Einheiten im Ring R ist

R× := {x R | y R : xy = 1}.

Dann ist y auch Einheit. Man nennt R× Einheitengruppe (bzw. multipli-

kative Gruppe) von R.

Definition 1.4 Sei R Integrit¨

atsring, p R und p = 0.

(i)

p heißt irreduzibel, falls f¨

ur jede Zerlegung p = xy mit x, y R gilt:

x R× oder y R×.

(ii) p heißt prim, wenn aus p|xy mit x, y R stets folgt: p|x oder p|y.

Satz 1.5 Sei R Integrit¨

atsring. Dann gilt, dass jedes prime Element f R

mit f = 0 auch irreduzibel ist.

Beweis:

Sei f prim und g, h R.

z.z.: Wenn f = g · h ist, dann folgt g R× oder h R×.

Angenommen, es ist f = gh. Dann gilt f |g oder f |h. Wenn f ein Teiler von g

ist, dann gibt es ein a R mit f a = g, woraus f = gh = f ah folgt, und das

bedeutet f (1-ah) = 0. Weil R Integrit¨atsring und somit nullteilerfrei ist, folgt

ah = 1, also ist h in der Einheitengruppe von R und damit ist f irreduzibel.

Bemerkung 1.6 Dasselbe funktioniert auch mit R[X]. Falls R (bzw. R[X])

ein Hauptidealring ist, dann gilt auch die R¨

uckrichtung, also wenn f irreduzibel

ist, dann ist f prim.1

1Beweis nachzulesen in [4], S. 46.

6

---

1

POLYNOMRINGE

Satz 1.7 Die Einheitengruppe eines Integrit¨

atsringes R ist die gleiche wie die

des Polynomringes R[X].

Beweis:

z.z.: R× = R[X]×

": Vor.: Zu jedem Element a in R× gibt es ein b in R× mit a · b = 1

"

R, wobei

a, b = 0 sind.

Wenn a in der Einheitengruppe von R enthalten ist, dann ist a auch

ein Element in R. Da R in R[X] enthalten ist, ist a auch ein Element

des Polynomrings R[X]. Dasselbe gilt f¨

ur b und nach Voraussetzung gilt

a · b = 1R = 1R[X], demzufolge gilt a R[X]×.

": Vor.: Zu jedem f R[X]× gibt es ein g R[X]× mit f · g = 1

"

R[X], wobei

f, g = 0 und grad(f ), grad(g) 0 gilt.

Aus f · g = 1R[X] folgt grad(f · g) = 0 = grad(f ) + grad(g) (weil R[X] ein

Integrit¨

atsring ist) und das gilt nur, wenn grad(f ) = grad(g) = 0 ist. Es

folgt, dass f und g in R liegen. Da nach Voraussetzung f ·g = 1R[X] = 1R

gilt, folgt f R×.

Definition 1.8 Ein Integrit¨

atsring R mit einer Abbildung : R\{0} - N

heißt ein euklidischer Ring, wenn gilt: Zu den Elementen f, g R, g = 0

gibt es stets Elemente q, r R mit

f = q · g + r wobei (r) < (g) oder r = 0.

Die Abbildung wird als Grad- oder Normabbildung des euklidischen Rings

bezeichnet.

Wir werden weiter unten zeigen, dass der Polynomring K[X] ¨

uber einem

K¨

orper K bez¨

uglich der Gradfunktion = grad euklidisch ist. Also inter-

essieren wir uns f¨

ur die Abbildung

:

K[X]\{0} - N

f

- grad(f)

und betrachten K[X] als Polynomring ¨

uber einem K¨

orper K.

Definition 1.9 Dem Nullpolynom 0 wird im Folgenden der Grad - zuge-

ordnet.

Mit dem folgenden Satz wird gezeigt, dass in Polynomringen ¨

uber einem K¨

orper

K eine Division mit Rest m¨

oglich ist. Das wird n¨

amlich sp¨

ater ben¨

otigt, um

zu zeigen, dass diese Ringe Hauptidealringe sind.

7

---

1

POLYNOMRINGE

Satz 1.10 Sei K K¨

orper. Dann ist der Polynomring K[X] euklidisch bez¨

uglich

der Gradfunktion = grad.

Beweis:

Da K K¨

orper ist (und damit auch Integrit¨

atsring) folgt, dass auch K[X] ein

Integrit¨

atsring ist (siehe Satz 1.2).

noch z.z.: F¨

ur f, g K[X] mit f = 0 gibt es Polynome k, r K[X] mit

g = kf + r und grad(r) < grad(f ).

Es folgt nun eine vollst¨

andige Induktion ¨

uber d unter der Voraussetzung, dass

obige Aussage f¨

ur alle g mit kleinerem Grad als d gilt.

Induktions-Anfang:

F¨

ur d = 0 ist grad(g) = 0 und somit g K.

Falls grad(f ) > 0 setze k = 0 und r = g.

Falls grad(f ) = 0 setze k = g und r = 0.

f

Induktions-Voraussetzung:

F¨

ur alle Grade von g bis zum Grad d - 1 gilt: zu f, g K[X] mit f = 0 gibt

es k, r K[X] mit g = kf + r und grad(r) < grad(f ).

Induktions-Schritt:

Seien

e

f =

aiXi = aeXe + ... + a1X + a0

i=0

und

d

g =

bjXj = bdXd + ... + b1X + b0.

j=0

Es gilt ae = 0 und grad(f ) = e. Falls grad(g) < grad(f ) sein sollte, dann kann

man k = 0 und r = f setzen. Wenn aber grad(g) grad(f ) ist, dann hat das

Polynom

g1 := g - bd · Xd-e · f

ae

einen kleineren Grad als grad(g) = d, denn

d

e

g1 =

bjXj - bd · Xd-e ·

aiXi

ae

j=0

i=0

d

e-1

=

bjXj - bdXd-e+e - bd · Xd-e ·

aiXi

ae

j=0

i=0

d-1

e-1

=

bjXj - bd · Xd-e ·

aiXi,

ae

j=0

i=0

8

---

1

POLYNOMRINGE

d.h. grad(g1) d-1, also grad(g1) < grad(g). Nach Induktions-Voraussetzung

gibt es jetzt f¨

ur g1 eine Zerlegung g1 = k1f + r1 mit grad(r) < e = grad(f )

und k1, r1 K[X]. Jetzt setzt man noch k = k1 + bd Xd-e und damit gilt

ae

g = kf + r.

1.3

Ideale

Definition 1.11 Sei R ein kommutativer Ring. I R heißt Ideal in R, wenn

gilt:

(i)

I ist eine additive Untergruppe von R;

(ii) wenn r R und a I, dann folgt, dass auch ra I ist.

F¨

ur a R nennt man Ra := {ra|r R} das von a erzeugte Hauptideal.

Satz 1.12 Seien R ein Ring und I ein Ideal. Dann ist R/I wieder ein Ring.

Beweis:

Die Abbildung

:

R - R/I

g

- ¯g

schickt ein g R auf seine Restklasse ¯g R/I. ¯g l¨asst sich folgendermaßen

schreiben: ¯

g = {a + g|a I}. Die Restklasse ¯

g beinhaltet sowohl g als auch

alle Elemente, die sich von g nur um ein Element aus I unterscheiden.

(R/I, +) ist bekanntlich abelsche Gruppe.

F¨

ur die Wohldefniniertheit der Multiplikation ist zu zeigen: f¨

ur ¯

g1, ¯

g2, ¯

h R/I

gilt: ¯

g1 = ¯

g2 ¯

g1 · ¯h = ¯

g2 · ¯h.

Seien g1 ¯

g1, g2 ¯

g2 mit ¯

g1 = ¯

g2. Es gibt also ein a I mit g2 = g1 + a.

Sei h ¯h. Weil g1 und g2 in derselben Restklasse sind, ist g2h dasselbe wie

g1h + ah. Da a im Ideal I enthalten ist, gilt auch ah I, woraus ¯

g1 · ¯h = ¯

g2 · ¯h

folgt. Analog gilt ¯

h · ¯

g1 = ¯

h · ¯

g2.

Es gilt auch die Assoziativit¨

at und das Distributivgesetz ¯

g(¯

h + ¯

f ) = ¯

g¯

h + ¯

g ¯

f .

Satz 1.13 Jedes Ideal in einem euklidischen Ring ist ein Hauptideal.

Beweis:

Sei I R Ideal und R euklidisch. z.z.: I ist ein Hauptideal.

1) Sei I = {0} = R · 0. Das ist ein Hauptideal.

9

---

1

POLYNOMRINGE

2) Sei I = 0.

W¨

ahle b I\{0} mit (b) minimal: (b) = min{(y) | y I\{0}} N

Bei beliebigem a I existieren q, r R mit a = q · b + r und r = 0 oder

(r) < (b) (nach Satz 1.10). Es gilt (r) = (a - qb) < (b). Wenn (b)

minimal ist, dann kann ein (r) nicht kleiner sein, also f¨

allt der Rest r

weg. Aus r = 0 folgt a = qb (wobei a I und q R). F¨ur ein q R gilt

qb Rb und damit auch a Rb. Da a I beliebig ist, folgt I Rb.

Aber es ist auch b I und nach Voraussetzung ist Rb I. Damit ist

Rb = I, und das ist ein Hauptideal.

Satz 1.14 Es seien K ein K¨

orper und I ein Ideal in K[X]. Dann ist in

K[X]/I jedes Ideal ein Hauptideal.

Beweis:

Sei J ein Ideal in K[X]/I.

z.z.: J ist Hauptideal.

Betrachte die Abbildung

:

K[X] - K[X]/I

a

- ¯a

und zeige: -1(J ) ist Ideal in K[X].

1. -1(J ) ist bekanntlich Untergruppe von K[X].

2. Sei x -1(J), y K[X]. Zeige: x · y -1(J).

(x · y) = (x) · (y) J, weil (x) J.

Nach Satz 1.10 ist K[X] euklidisch und nach Satz 1.13 somit Hauptidealring,

was bedeutet, dass -1(J ) K[X] Hauptideal ist. Also gibt es ein f K[X]

mit: -1(J ) = K[X] · f = (f ). Es wird (-1(J)) = J demnach von (f )

erzeugt. Es gilt n¨

amlich J = (-1(J )) = (K[X] · f ) = (K[X]) · (f ) =

K[X]/I · (f ).

10

---

2

KORPER

2

K¨

orper

Hier werden einige grundlegende Eigenschaften von K¨

orpern aufgef¨

uhrt, die

im n¨

achsten Kapitel f¨

ur die Konstruktion des endlichen K¨

orpers Fq ben¨otigt

werden.

Satz 2.1 Sei K ein K¨

orper und U eine endliche Untergruppe seiner Einhei-

tengruppe K×. Dann ist U zyklisch.

Beweis:

Sei a U mit maximaler Ordnung m. In der endlichen Untergruppe U der

Einheitengruppe K× soll also kein Element gr¨

oßere Ordnung als ord(a) haben.

Dann sei Um diejenige Untergruppe aller Elemente b aus U, deren Ordnung

m teilt, also Um = {b U : ord(b) |m}. In Um befinden sich h¨ochstens m

Elemente, denn das sind alles L¨

osungen der Gleichung Xm = 1.

Wenn man sich jetzt die von a erzeugte zyklische Gruppe a = {1, a1, a2, . . . ,

am-1} ansieht, bemerkt man, dass diese genau m verschiedene Elemente hat,

und zwar deswegen, weil die Ordnung dieses Erzeugenden a ja genau m ist.

Und weil a Um ist, Um h¨ochstens m Elemente hat, a aber genau m, folgt

a = Um. Somit ist Um zyklisch.

Wenn man jetzt noch Um = U zeigt, dann ist auch U zyklisch. Dazu wird

hier der Struktursatz f¨

ur endliche abelsche Gruppen2 benutzt, welcher besagt,

dass sich jede endliche abelsche Gruppe (also auch U ) als direktes Produkt

von zyklischen Gruppen in der Form U = Zn × Z × . . . × Z

schreiben l

1

n2

n

¨

asst,

k

wobei ni = #Zn und n

i

1|n2|n3| . . . |nk.

Angenommen Um = U. Dann gibt es ein Element y U welches nicht in Um

enthalten ist, somit teilt die Ordnung von y nicht m. Das kann aber nicht sein,

denn wenn es ein Element y U mit ord(y) = n gibt, dann muss n gleich ir-

gendeinem ni sein und das m¨

usste dann m = nk teilen, was einen Widerspruch

zur Annahme ergibt. Also ist U zyklisch.

Korollar 2.2 F¨

ur einen endlichen K¨

orper K gilt dann, dass auch K× zyklisch

ist. Daraus folgt, dass f¨

ur alle Elemente a K× gilt: a#K× = 1.

Satz 2.3 Sei K[X] Polynomring ¨

uber einem K¨

orper K und (f ) := f ·K[X] das

von f erzeugte Hauptideal. Wenn f irreduzibel ist, dann ist K[X]/(f ) K¨

orper.

Beweis:

Nach Bemerkung 1.6 ist dann f auch prim, also ist K[X] nullteilerfrei und

nach Satz 1.14 ein Hauptidealring.

2Beweis nachzulesen in [3], S. 540f.

11

---

2

KORPER

Nach Satz 1.12 ist bekannt, dass K[X]/(f ) ein Ring ist, also bleibt nur noch

die Existenz von Inversen zu zeigen.

Sei ¯

g K[X]/(f ) Restklasse, ¯

g = 0. Alle Elemente aus ¯

g lassen sich in der Form

g = k · f + r1 darstellen mit variablem k K[X] und festem r1 K[X]\(f ),

grad r1 < grad f .

Mit Hilfe der Abbildung

¯g :

K[X]/(f ) - K[X]/(f )

¯

h

- ¯g · ¯h

wird jetzt gezeigt, dass es f¨

ur jedes Element ¯

g K[X]/(f ) \{0} ein Inverses

¯

h K[X]/(f ) \{0} gibt. Das ist genau dann der Fall, wenn ¯g Automor-

phismus ist.

¯g ist K-linear, denn es gilt ¯g(¯

a + ¯

b) = ¯

g(¯

a + ¯

b) = ¯

g · ¯a + ¯g · ¯b = g(¯a) + g(¯b)

und ¯g(¯

a) = ¯

g · · ¯a = · ¯

g · ¯a = · ¯g(¯a) (mit K).

Injektivit¨

at von ¯g:

Sei h K[X]. Zeige nun: ¯g(¯h) = 0 ¯h = 0.

¯g(¯

h) = 0 ¯h Kern(¯g). Also gilt ¯g(¯h) = ¯

g · ¯h = 0. Es folgt ¯h = 0, denn

nach Voraussetzung ist ¯

g = 0 und somit ist ¯g injektiv.

Dann ist ¯g surjektiv, somit ist 1 Bild(¯g) und es folgt, dass es eine Rest-

klasse ¯

h in K[X]/(f ) gibt mit ¯g(¯

h) = 1. Also gilt ¯

g · ¯h = 1, dann ist ¯

g Einheit

und hat ein Inverses, n¨

amlich ¯

h. Folglich ist K[X]/(f ) also ein K¨

orper.

2.1

K¨

orpererweiterung

Definition 2.4 Sei K L Teilk¨orper, also L/K K¨orpererweiterung. Ein Ele-

ment L heißt algebraisch ¨uber K, wenn ein Polynom m K[X] mit

m = 0 existiert, von dem eine Nullstelle in L darstellt, also m() = 0. Hat

m kleinstm¨

oglichen Grad, so nennt man m Minimalpolynom von . Man

nennt eine K¨

orpererweiterung L/K algebraisch, wenn jedes Element von L

¨

uber K algebraisch ist.

Falls es kein gibt mit obiger Eigenschaft, dann ist sie transzendent, was hier

allerdings nicht von Belang ist.

Sei Nullstelle vom Minimalpolynom m K[X] mit grad m = e. Wenn

man nun dieses zu K dazuadjungiert, erh¨

alt man den kleinsten Erweite-

rungsk¨

orper von K, welcher K und enth¨

alt, n¨

amlich K(). Hierin sind

nat¨

urlich auch die Potenzen i von enthalten mit i = 1, . . . , e - 1. Alle

i lassen sich als Basis von K() als K-Vektorraum auffassen und wenn sie

mit Skalaren i aus K multipliziert werden, dann bekommt man den ganzen

12

---

2

KORPER

K(), der modellhaft so aussieht:

e

K() = {

ii-1|i K} = K + K + . . . + e-1K

i=1

Wir wissen ¨

ubrigens, dass e K(), denn es ist ja

m() = e + ee-1 + . . . + 1 + 0 = 0, woraus folgt, dass

e = -ee-1 - . . . - 1 - 0 K. Alle mit h¨oherer Potenz als e - 1 lassen

sich also als Linearkombinationen von i darstellen.

K() ist isomorph zum K-Vektorraum Ke. Falls K endlich ist, hat Ke (#K)e

Elemente und somit auch K(). Zur Veranschaulichung folgt ein Beispiel:

Beispiel 2.5 Sei f Z/3Z[X], grad(f ) = 2 und f irreduzibel.

Z/3Z() =

2

i=1

ii-1|i Z/3Z

= {1 + 2 | 1, 1 Z/3Z}

Betrachte die Abbildung

:

Z/3Z() - (Z/3Z)2

1 + 2 - (1, 2).

(1, 2) {(¯0, ¯0), (¯0, ¯1), (¯0, ¯2), (¯1, ¯0), (¯1, ¯1), (¯1, ¯2), (¯2, ¯0), (¯2, ¯1), (¯2, ¯2)}; es gibt al-

so 9 Kombinationsm¨

oglichkeiten. Jedes Polynom wird eindeutig auf einen Vek-

tor abgebildet, es gibt 32 verschiedene Polynome, also auch 32 verschiedene

Bildvektoren. Somit ist der Erweiterungsk¨

orper Z/3Z() isomorph zum Z/3Z-

Vektorraum (Z/3Z)2, der 32 = 9 Elemente hat.

Satz 2.6 Der Restklassenk¨

orper K[X]/(f ) ist isomorph zu K().

Beweis:

Die Abbildung

:

K[X] - K()

g

- g()

ist surjektiv (denn (K[X]) = Bild =K()). Kern = K[X], denn nur die-

jenigen Polynome, welche als Nullstelle haben, werden auf die Null in K()

abgebildet. Zum Beispiel wird die 1 = 1 · X0 aus K[X] auf die 1 = 1 · 0 in

K() abgebildet und ist somit nicht im Kern von enthalten, also ist nicht

die Nullabbildung.

Da f () = 0, ist das von f erzeugte Hauptideal (f ) im Kern enthalten. Sei

nun g Kern und g /

(f). Dann gilt g {a|(a) = 0; a K[X]}. Die

einzigen Polynome, die anhand von auf die 0 abgebildet werden sind dieje-

nigen, die als Nullstelle haben, und das sind nur alle Vielfachen von f . Also

muss g ein Vielfaches von f sein (g (f )) und es gilt Kern (f ) und somit

Kern = (f ).

13

---

2

KORPER

Die Abbildung

~

:

K[X]/(f ) - K()

¯

g

- ¯g()

ist also auch injektiv, damit bijektiver Homomorphismus, also Isomorphismus.

Das heißt:

K[X]/(f )

= K()

Korollar 2.7 Somit besteht auch K[X]/(f ) aus (#K)grad f Elementen, wenn

K endlich ist.

2.2

Endliche K¨

orper

Satz 2.8 (kleiner Satz von Fermat) Sei p prim. F¨

ur alle a Fp gilt ap = a.

F¨

ur alle a = 0 gilt ap-1 = 1.

Beweis:

F¨

ur a, b Fp gilt (a + b)p = ap + bp, denn es ist

p

p

(a + b)p =

aibp-i

i

i=0

p

p

p

p

=

bp +

abp-1 + . . . +

ap-1b +

ap

0

1

p - 1

p

=1

=p=0 in Fp

=1

= ap + bp,

p

da

f¨

ur 1 < i < p durch p teilbar ist und somit in F

i

p verschwindet.

(a1 + a2 + . . . + ak)p = ap + ap + . . . + ap f

1

2

¨

ur alle a

k

i Fp.

Falls alle ai = 1, so ist

kp = (1 + 1 + . . . + 1)p = 1p + 1p + . . . + 1p = k,

also kp = k.

Weil Fp K¨orper ist, ist außer der Null jedes Element darin invertierbar, somit

gilt in Fp\{0} = F×:

p

ap-1 = ap · a-1 = a-1 · ap = a-1 · a = 1.

14

---

2

KORPER

Definition 2.9 Man nennt einem K¨

orper K algebraischen abgeschlos-

sen, wenn jedes Polynom f K[X] mit grad(f ) > 0 eine Nullstelle in K

hat. Das heißt, dass in K[X] jedes nicht-konstante Polynom in Linearfaktoren

zerf¨

allt.

Definition 2.10 Wenn f K[X] ist, nennt man den Zerf¨

allungsk¨

orper

von f den kleinsten Teilk¨

orper vom algebraischen Abschluss K, der K und alle

Nullstellen von f enth¨

alt.

Definition 2.11 Der Durchschnitt aller Teilk¨

orper eines K¨

orpers K ist der

kleinste in K enthaltene Teilk¨

orper und er wird Primk¨

orper genannt.

Im Folgenden sei Z/pZ = Fp als Primk¨orper eines endlichen K¨orpers F be-

zeichnet.

Definition 2.12 Sei R ein Integrit¨

atsring und : Z - R der kanonische

Ringhomomorphismus. Wenn p Z ein erzeugendes Element des Hauptideals

Kern ist, dann nennt man p die Charakteristik von R (in Zeichen: p =

char R).

Wir wollen jetzt zeigen, dass ein (endlicher) K¨

orper mit q Elementen genau

dann existiert, wenn q eine Primzahlpotenz ist, und dass dieser bis auf Iso-

morphie eindeutig bestimmt ist, denn sp¨

ater soll in Restklassenk¨

orpern von

Polynomringen ¨

uber solchen endlichen K¨

orpern gerechnet werden.

Satz 2.13 Jeder endliche K¨

orper hat die Ordnung pn f¨

ur eine Primzahl p und

n N.

Beweis:

Sei F endlicher K¨orper. Dann ist #F eine Primzahlpotenz.

Wenn F n¨amlich endlich ist, ist das auch sein Primk¨orper Fp und es gilt

char Fp = p = char F, denn die Charakteristik von K¨orper und seinen Teilk¨orpern

ist dieselbe. F kann als Fp-Vektorraum gesehen werden und dieser muss end-

liche Dimension haben, weil ja F als endlich vorausgesetzt wird. Mit einer

Basis 1, . . . , n l¨

asst sich dann jedes Element von F eindeutig schreiben als

a11 + . . . + ann, wobei ai Fp. Es hat F somit pn = q Elemente.

Satz 2.14 Wenn F und F zwei K¨orper mit Ordnung pn sind, dann sind sie

zueinander isomorph.

Beweis:

Die multiplikative Gruppe F× jedes endlichen K¨orpers ist zyklisch (siehe Korol-

lar 2.2). Das heißt, dass alle Elemente aus F× die Gleichung Xq-1 = 1 erf¨ullen,

denn jedes Element daraus ist Einheitswurzel. Aus F× = F\{0} folgt, dass

jedes der q Elemente aus dem endlichen K¨

orper F Nullstelle von f = Xq - X

ist. Xq - X hat maximal q Nullstellen und F hat q Elemente. Dann ist F

15

---

2

KORPER

Zerf¨

allungsk¨

orper von Xq - X.

Satz 2.15 F¨

ur jede Primzahlpotenz q = pn gibt es einen K¨

orper F mit pn

Elementen, welcher der Zerf¨

allungsk¨

orper des Polynoms f = Xq - X ¨uber

seinem Primk¨

orper Fp ist.

Beweis:

1.) Es sei F der Zerf¨allungsk¨orper von f ¨uber Fp. Wir zeigen: Er hat min-

destens pn Elemente.

Sei dazu Fp ein algebraischer Abschluss von Fp, hierin liegen s¨amtliche

Nullstellen aller nicht-konstanten Polynome aus Fp[X], auch diejenigen

von f = Xq - X. F enth¨alt alle Nullstellen von f .

Nun wird gezeigt, dass Xq-X lauter verschiedene Nullstellen hat, n¨amlich

q St¨

uck. Damit hat F mindestens q Elemente.

f zerf¨

allt ¨

uber F vollst¨andig in Linearfaktoren und l¨asst sich in der Form

Xq -X = X ·(X -0)·(X -1)·(X -2)·. . .·(X -q-2) wobei 0 = 1

darstellen.

Jetzt gilt es zu zeigen, dass alle i paarweise verschieden sind. Dann

hat Xq - X n¨amlich keine mehrfachen Nullstellen und somit ganz genau

pn = q St¨

uck.

Wenn f, g Fp[X] sind, dann ist formal abgeleitet (mit der Produktre-

gel) (f · g) = f g + g f .

Wenn das Polynom Xq - X eine doppelte Nullstelle in Fp h¨atte, dann

w¨

are Xq - X = (X - )2 · g mit g Fp[X].

Es folgt also (Xq - X) = 2(X - ) · g + (X - )2 · g = 0, wenn X =

gesetzt wird. Daraus folgt aber, dass nicht nur Nullstelle von Xq - X

ist, sondern auch von seiner Ableitung (Xq - X) . Es gilt aber auch:

(Xq - X) = qXq-1 - 1 = pnXpn-1 - 1 = -1, weil char Fp = p und

p · Fp = 0. Wenn aber (Xq - X) = -1 ist, dann ist keine Nullstelle

von (Xq - X) , was einen Widerspruch ergibt.

2.) Der Zerf¨

allungsk¨

orper von Xq - X hat h¨ochstens pn Elemente.

Zeige dazu: die Menge dieser Nullstellen ist ein K¨

orper. Dies ist dann der

Zerf¨

allungsk¨

orper von Xq - X, der Fp enth¨alt.

Wenn p prim und R Integrit¨

atsring mit char R = p (also p · 1 = 0), dann

gilt f¨

ur a, b R und n N:

(a ± b)pn = apn ± bpn = aq ± bq

mit pn = q.

16

---

2

KORPER

Wenn a Nullstelle von Xq - X ist, dann ist aq - a = 0, also aq = a, weil

außer der Null jede Nullstelle davon Einheitswurzel ist (analog mit einer

Nullstelle b), daraus folgt dann aq ± bq = a ± b. Aus (a ± b)q = a ± b folgt

(a ± b)q - (a ± b) = 0, d.h. a ± b sind wieder Nullstellen von f = Xq - X.

Genauso folgt f¨

ur b = 0: ( a )q = aq = a und (a · b)q = aq · bq = a · b, denn

b

bq

b

wie oben gilt aq = a und bq = b. Also sind auch a und a · b Nullstellen

b

von Xq - X. Wir haben nun also herausgefunden, dass wenn a und b

Nullstellen von Xq - X sind (und davon gibt es q St¨uck), dann auch

a + b, a - b, a · b und a. Somit ist die Nullstellenmenge F tats¨achlich

b

Teilk¨

orper von Fp, welcher Fp enth¨alt (wegen 1 + . . . + 1 F ist Fp F),

somit Zerf¨

allungsk¨

orper von Xq - X mit ganz genau pn Elementen. Die-

ser K¨

orper wird im Folgenden Fq genannt.

Satz 2.16 Sei p Primzahl, f Fp[X] irreduzibel und normiert mit grad f = e

und Fp() eine Nullstelle von f . Dann hat f genau e Nullstellen, n¨amlich

, p, p2, . . . , pe-1 Fp(), und l¨asst sich somit folgendermaßen in Linear-

faktoren zerlegen:

f = (X - ) · (X - p) · (X - p2) · . . . · (X - pe-1)

Fp() ist daher der Zerf¨allungsk¨orper von f.

Beweis:

Sei Aut (Fp()) (erstmal nicht n¨aher bestimmt, einfach irgendein Auto-

morphismus auf Fp()). Jetzt wird gezeigt, dass auch () Nullstelle von f

ist, wenn Nullstelle von f ist.

ist auf Fp die Identit¨at, denn aufgrund der Homomorphie-Eigenschaft gilt

(1) = 1 und (1 + . . . + 1) = 1 + . . . + 1. Es gilt auch (0) = 0. Da f () = 0

ist, gilt auch (f ()) = 0.

Dann ist

e

e

e

0 = (0) = (f ()) =

aii =

(aii) =

ai(i)

i=0

i=0

i=0

e

=

ai()i = f (()),

i=0

also stellt auch () eine Nullstelle von f dar. Wenn aber () eine Nullstelle

von f ist, dann ist auch (()) eine Nullstelle von f usw. Und da #Fp() = pe

(wie in Abschnitt 2.1 gezeigt), gibt es h¨

ochstens so viele Automorphismen auf

Fp() wie verschiedene Nullstellen von f und das sind h¨ochstens e St¨uck, weil

der Automorphismus durch () eindeutig bestimmt ist.

17

---

2

KORPER

Wir w¨

ahlen jetzt die Abbildung

:

Fp() - Fp()

z

- zp

und m¨

ochten, dass () = p auch wieder eine Nullstelle von f ist. Das ist

dann der Fall, wenn ein Automorphismus ist. Das wird jetzt kurz gepr¨

uft.

Homomorphie-Eigenschaft:

(z + w) = (z + w)p = zp + wp

= (z) + (w)

(z · w)

= (z · w)p

= zp · wp

= (z) · (w)

Injektivit¨

at:

Angenommen, es sei (z) = (w). zp = wp zp - wp = 0 (z - w)p =

0 z = w. Fertig. Weil Fp() gleich viele Elemente hat wie Fp(), ist

surjektiv, sobald es injektiv ist.

Somit ist () = p Nullstelle von f , also auch (p)p = p2, also auch pe-1.

Dann l¨

asst sich f folgendermaßen schreiben:

e-1

f =

(X - pk) = (X - ) · (X - p) · (X - p2) · . . . · (X - pe-1)

k=0

Wenn man jetzt noch zeigt, dass die Nullstellen , p, p2, . . . , pe-1 paarweise

verschieden sind, dann ist sicher, dass gilt: # Aut(Fp()) = e = # NST von f .

Sei 0 i < k < e. Angenommen, es sind zwei der Nullstellen gleich, n¨amlich

pi = pk. Wenn man links und rechts die pi-te Wurzel zieht, bekommt man

= pk-i. Nenne nun k - i := j, es gilt 0 < j < e.

Dann gibt es ein g(X) = (X - ) · (X - p) · . . . · (X - pj-1) und es gilt:

(g(X)) = gp(X) = (X - )p · (X - p)p · . . . · (X - pj-1)p

= (X - p) · (X - p2) · . . . · (X - pj ) wegen Homomorphie

von

= g(X), denn pj = .

Damit ist (g(X)) = gp(X) = g(X) und es gilt dann f¨

ur jeden Koeffizienten c

von g: (c) = cp = c, denn

gp(X) = g(X) = cjXj + . . . + c1X + c0

= cpXjp + . . . + cpXp + cp

j

1

0

= cpXj + . . . + cpX + cp.

j

1

0

18

---

2

KORPER

Nach Satz 2.8 gilt in Fp Xp = X f¨ur alle X Fp, das Polynom Xp - X

hat h¨

ochstens p Nullstellen, also sind alle Nullstellen von Xp - X = 0 in

Fp enthalten. Damit folgt aus (c) = c, dass c Fp ist. Dann ist also auch

g Fp[X].

Nach Voraussetzung ist f irreduzibel und f () = 0 = g(), also teilt f das

Polynom g. Das geht aber nur, wenn j e ist, und das ist ein Widerspruch zu

oben. Somit f¨

allt f mit g zusammen und hat genau e verschiedene Nullstellen.

19

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

3

Das quadratische Reziprozit¨

atsgesetz

3.1

Ganze Zahlen

In Abschnitt 3.3.1 wird das Legendre-Symbol f¨

ur Zahlen verwendet, es sei

hierf¨

ur folgendermaßen definiert:

Definition 3.1 Sei p prim und a Z, wobei p kein Teiler von a sei. Dann ist

das Legendre-Symbol f¨

ur Zahlen definiert durch

a

1

falls es ein b Z gibt mit a b2(mod p)

=

p

-1 sonst.

Satz 3.2 Das

3

quadratische Reziprozit¨

atsgesetz f¨

ur Zahlen

besagt:

Wenn l und p zwei verschiedene ungerade Primzahlen sind, dann gilt

p

· l

p-1

= (-1) 2 · l-1

2 ,

l

p

l-1

wobei nach dem Euler′schen Kriterium gilt:

p

p 2 (mod l).

l

Beispiel 3.3 Sei p = 7. Die Quadrate in Z/7Z sind 1, 2 und 4. Dann ist das

Legendre-Symbol 4 = 1, denn 4 ist ein Quadrat in Z/7Z (4 22(mod 7)).

7

Es ist aber zum Beispiel

5

= -1, weil es kein b Z mit 5 b2(mod 7) gibt.

7

Sei nun l = 5. Die Quadrate in Z/5Z sind 1 und 4, also ist 7 = -1. Nach

5

Satz 3.2 ist dann

7

7-1

(-1) · (-1) =

· 5 = (-1) 2 ·5-1

2

= (-1)3·2 = 1.

5

7

3.2

Polynome ¨

uber endlichen K¨

orpern

Es stellt sich jetzt die Frage, wie das quadratische Reziprozit¨

atsgesetz in Poly-

nomringen ausgedr¨

uckt werden kann. Wie man gleich sieht, wird das Legendre-

Symbol analog obiger Definition formuliert, wobei es nach Euler in Polynom-

ringen jedoch auf andere Art berechnet wird. Damit ¨

andert sich auch die For-

mulierung des quadratischen Reziprozit¨

atsgesetzes.

3Beweis nachzulesen in [7] S. 35f.

20

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

3.2.1

Eulers Hilfssatz

Definition 3.4 Sei f Fq[X] irreduzibel und normiert, g Fq[X] und g kein

Vielfaches von f . Im endlichen K¨

orper Fq[X]/(f ) ist

g

1

falls es ein b F

=

q [X ] gibt mit

¯

g = ¯

b2 in Fq[X]/(f )

f

-1 sonst

als das Legendre-Symbol definiert.

Wir m¨

ussen hier q als ungerade voraussetzen, denn in char(Fq) = 2 w¨are

1 = -1. Sei also im Folgenden q = pn (n N) mit p 3 und p prim.

Satz 3.5 (Eulers Hilfssatz) Das Legendre-Symbol l¨

asst sich nach dem Eu-

ler′schen Kriterium folgendermaßen berechnen:

g

qe-1

g 2 (mod f ),

f

oder anders ausgedr¨

uckt:

g

qe-1

= ¯

g 2

in

Fq[X]/(f),

f

wobei g Fq[X], e = grad(f ) und f kein Teiler von g sei.

Beweis:

Die Einheitenguppe Fq[X]/(f )× von Fq[X]/(f ) ist zyklisch und hat die Ord-

nung qe - 1. Es gibt also einen Erzeuger ¯h Fq[X]/(f )× mit ord(¯h) = qe - 1.

Daher gilt f¨

ur jedes Element 0 = ¯

g Fq[X]/(f ), dass ¯

gqe-1 = 1 ist.

1) Sei ¯

g = ¯

b2.

qe-1

qe-1

Dann ist ¯

g 2

= (¯

b2) 2

= ¯

bqe-1 = 1 nach Satz 2.8.

2) Sei y N mit ¯

g = ¯

hy. Vorausgesetzt, es gibt kein b Fq[X] mit ¯g = ¯b2.

y

Dann muss y ungerade sein, denn sonst k¨

onnte man ¯

b := ¯

h 2 setzen und

qe-1

qe-1

w¨

are somit bei Fall 1) angelangt. Also ist ¯

g 2

= 1 (denn ¯

g 2

= ¯

hy· qe-1

2

,

doch y · qe-1 ist kein Vielfaches von qe - 1).

2

qe-1

qe-1

Jetzt bleibt noch zu zeigen: ¯

g 2

= 1 ¯

g 2

= -1.

qe-1

Aus ¯

gqe-1 = 1 folgt (¯

g 2 )2 = 1.

qe-1

Daraus folgt ¯

g 2

= ±1.

21

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

qe-1

Korollar 3.6 Aus dem Euler-Kriterium

g

g 2 (mod f) folgt:

f

F¨

ur alle g, h Fq[X] mit f | gh und e = grad(f ) gilt:

gh

g

=

· h

f

f

f

denn

g

· h

qe-1

qe-1

qe-1

gh

= ¯

g 2

· ¯h 2 = (gh) 2 =

.

f

f

f

Satz 3.7 (Quadratisches Reziprozit¨

atsgesetz) Seien f, g Fq[X] irredu-

zibel ¨

uber diesem K¨

orper, normiert und verschieden, grad(g) = d und grad(f ) =

e.

Dann gilt:

f

· g

qd-1

= (-1) 2 ·qe-1

2

g

f

q-1

= (-1) 2 ·d·e

Korollar 3.8 Aus dem Euler′schen Kriterium folgt dieser (einzige) Erg¨

anzungs-

satz:

qe-1

= 2 ,

f

wobei F×.

q

Vor dem Beweis des quadratischen Reziprozit¨

atsgesetzes (in Abschnitt 3.4)

werden zur Veranschaulichung zwei Beispiele in Polynomringen ¨

uber endlichen

K¨

orpern gerechnet.

3.3

Beispiele

3.3.1

Allgemeine lineare Polynome

Es seien f = X - a und g = X - b mit a, b Fp und a = b. Die beiden

Polynome sind jeweils vom Grad eins und a und b sind ihre Nullstellen in Fp.

Es soll also gezeigt werden, dass hierf¨

ur das quadratische Reziprozit¨

atsgesetz

gilt, n¨

amlich

f

· g

p-1

= (-1) 2 .

g

f

Zuerst wird gezeigt, dass g genau dann ein Quadrat in Fp[X] ist, wenn (a - b)

in Fp ein Quadrat ist, es ist also zu zeigen: g = a-b .

f

p

22

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

": Vor.: a-b = 1, d.h. es gibt ein c mit a - b = c2 in F

"

p

p (alternativ:

a - b = l · p + c2 mit l, d Z).

z.z.: g = 1, es soll also k, h F

= k(X - a) + h2.

f

p[X ] geben mit X - b

g

f

W¨

ahle k = 1 und h = c (beides konstante Polynome in Fp[X]).

Es ist

X - b = X - a + c2

a - b = c2,

und das ist in Fp, fertig.

Das heißt, dass es mindestens ein k und ein h in Fp[X] gibt, so dass in

Fp gilt: g = kf + h2.

": Vor.: g = 1, es gibt also k, h F

"

f

p[X ] mit g = k · f + h2.

z.z.: a-b = 1, d.h. es gilt a-b = l·p+c2 bzw. gibt es ein c mit a-b = c2

p

in Fp.

n

m

Seien

h =

ci(X - a)i

und

k =

dj(X - a)j.

i=0

j=0

Also ist

g

= k · f + h2

X - b = (dm(X - a)m + . . . + d0)(X - a) + (cn(X - a)n + . . . + c0)2,

k

h

und das gilt in Fp[X].

Jetzt X = a einsetzen:

a - b = 0 + c2 und das gilt in Fp.

Ebenso gilt f

= b-a .

g

p

Es ist nach Korollar 3.6 f · g = b-a · a-b = (b-a)(a-b) = -(a-b)2 .

g

f

p

p

p

p

Außerdem gilt -(a-b)2

= -1 · (a-b)2 .

p

p

p

Das heißt also, wenn

-(a-b)2

= 1 gilt, dann ist -(a - b)2 ein Quadrat in F

p

p

und das ist genau dann der Fall, wenn die -1 ein Quadrat in Fp ist. Und das

gilt genau dann, wenn

-1 = 1 gilt. (analog in die andere Richtung)

p

Nach dem Euler′schen Kriterium ist

-1

p-1

= (-1) 2

p

p-1

= (-1) 2 ·1·1

in Fp

3.3.2

Quadratische Polynome

Nun wird ein konkretes Beispiel f¨

ur Polynome zweiten Grades aus F5[X] durch-

gerechnet. Dazu w¨

ahlen wir g = X2 + 2X - 1 und f = X2 + X + 2, beide sind

23

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

in F5[X] irreduzibel, normiert und verschieden. Es soll gezeigt werden:

g

· f

5-1

= (-1) 2 ·2·2

f

g

Zuerst konzentriert man sich auf g und um herauszufinden, ob das Legendre-

f

Symbol 1 oder -1 ergibt, muss man pr¨ufen, ob g modulo f quadratisch ist oder

nicht. Also:

g

1

falls g Quadrat in F

=

5[X ]/(f ) ist.

f

-1 sonst.

Es l¨

asst sich

g

so berechnen:

f

g

52-1

g 2 (modf ).

f

F5[X]/(f) beinhaltet alle Restklassen modulo f.

Der Erweiterungsk¨

orper F25 von F5 entsteht durch Adjunktion einer in Bezug

auf f geeigneten Nullstelle eines Minimalpolynoms mit demselben Grad

wie f (hier: grad(f ) = 2. Da f irreduzibel und normiert ist, k¨

onnten wir

auch eine Nullstelle von f dazuadjungieren, das macht die Sache aber recht

un¨

ubersichtlich und liefert letztendlich dasselbe Ergebnis.) Dieser K¨

orper hat

dann 5grad(f) = 52 Elemente und ist isomorph zu F5[X]/(f ), Polynome in

Abh¨

angigkeit von X werden Polynomen in Abh¨

angigkeit von zugeordnet.

Allerdings sollte ja f auf die Null abgebildet werden und das geht nur, wenn

man eine Nullstelle von f in f einsetzt. Und da in einer Abbildung mit allen

Polynomen aus F5[X]/(f ) dasselbe gemacht werden soll, sieht die Abbildung

dann so aus:

F

=

5[X ]/(f )

- F25 = F5()

¯

g

- g()

beliebige NST von f

Sei m ein irreduzibles Polynom zweiten Grades in F5[X], z.B. m = X2 - 3.

Unter der Voraussetzung, dass m in einem Erweiterungsk¨

orper eine Nullstelle

=

3 hat, adjungieren wir zu F5 dazu und erhalten somit ein Modell von

F25:

2

F25 =

ii-1|i F5

= {1 + 2|1, 2 F5} mit 2 = 3 = -2 in F5

i=1

Hierin befinden sich 52 Elemente (in Abh¨

angigkeit von ).

Die Quadrate sind die 12-ten Einheitswurzeln4 ( 25-1 = 12), in diesem Fall

2

QF

=

y2|y F× = F

25

25

25\{0}

= {1, -1, 2, -2, 2 + , 2 - , -2 + , -2 - , 1 + 2, 1 - 2,

-1 + 2, -1 - 2} .

4siehe auch Tabelle auf Seite 33.

24

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

Die Nullstellen 1 und 2 von f werden mit der quadratischen L¨

osungsformel

berechnet, es folgt also aus X2 + X + 2 = 0, dass

-7

1,2 = -1±

= 2 ± 3 3

2

(in F5 gerechnet!). W¨ahle = 2 + 3 3 mit =

3, also ist eine Nullstelle

von f in F25.

Jetzt bleibt noch g() auszurechnen und zu pr¨

ufen, ob das Ergebnis ein Qua-

drat ist.

g() = g(2 + 3) = 4 + 12 + 92 +4 + 6 - 1 = 34 + 18 = -1 - 2 QF25

=9·3

Das Legendre-Symbol

g

nimmt hier also den Wert 1 an.

f

Dasselbe macht man jetzt noch mit f :

g

Nullstellen von g:

X2 + 2X - 1 = 0

3

1,2 = -2±

= -1 2 3. Also ist = -1 - 2 Nullstelle

2

von g in F25.

f () = 2++2 = f (-1-2) = 1+4+ 42 -1-2+2 = 14+2 = -1 + 2

=4·3

QF25

f = 1 = g

g

f

g · f

52-1

52-1

= (1)·(1) = 1 = (-1) 2 · 52-1

2

= (-1)144 = (-1)48 = (-1) 2 ·2·2

f

g

Womit gezeigt ist, dass das quadratische Reziprozit¨

atsgesetz f¨

ur diesen spezi-

ellen Fall funktioniert.

3.4

Beweis

Vor dem Beweis des quadratischen Reziprozit¨

atsgesetzes in Polynomringen

¨

uber endlichen K¨

orpern (Satz 3.7) werden zur Erinnerung noch Definition und

S¨

atze vom Anfang des Kapitels wiederholt.

Wir ben¨

otigen hierf¨

ur das Legendre-Symbol, welches definiert ist als

g

1

falls es ein b gibt mit

¯

g = ¯

b2 in F

=

q [X ]/(f )

f

-1 sonst

und sich nach dem Euler′schen Kriterium folgendermaßen berechnen l¨

asst5:

g

qe-1

g 2 (modf )

f

5siehe Definition 3.4 und Satz 3.5

25

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

Wir interessieren uns hier also f¨

ur die quadratischen Restklassen in Fq[X]/(f ).

Es wird nun kurz auf die obige Definition des Legendre-Symbols eingegan-

gen, denn genau das muss berechnet werden, um zum quadratischen Rezi-

prozit¨

atsgesetz zu gelangen. Sei f Fq[X] ein irreduzibles normiertes Poly-

nom mit grad(f ) = e. Nun sehen wir uns den Restklassenring Fq[X]/(f ) an.

Nach Satz 2.3 und Korollar 2.7 ist bekannt, dass Fq[X]/(f ) endlicher K¨orper

mit qe Elementen ist und nach Korollar 2.2 ist seine multiplikative Gruppe

Fq[X]/(f)× zyklisch der Ordnung qe - 1. Es gilt also ¯aqe = ¯a f¨ur alle Restklas-

sen ¯

a Fq[X]/(f ). Die Einheitengruppe l¨asst sich folgendermaßen schreiben:

Fq[X]/(f)× =

¯

a Fq[X]/(f )|¯aqe-1 = 1 ,

wobei ¯

a Fq[X]/(f ).

Satz 3.7 (Quadratisches Reziprozit¨

atsgesetz) Seien f, g Fq[X] irredu-

zibel ¨

uber diesem K¨

orper, normiert und verschieden, grad(g) = d und grad(f ) =

e. Dann gilt:

f

· g

qd-1

= (-1) 2 ·qe-1

2

g

f

q-1

= (-1) 2 ·d·e

Beweis:

Nach Satz 2.6 ist Fq[X]/(f ) isomorph zu Fq() = Fqe und

:

F

=

q [X ]/(f )

- Fqe

¯

a

- a() beliebige NST von f

ist Isomorphismus. ist durch (f ) = 0 = f () wohldefiniert.

Um also herauszufinden, ob g modulo f quadratisch ist, kann man pr¨

ufen, ob

g() ein Quadrat in Fqe ist, anstatt in Fq[X]/(f ) mit ¯

g zu rechnen.

Das Polynom f kann in Fqe als Produkt seiner Linearfaktoren geschrieben

werden:

e-1

f (X) =

(X - qk) = (X - ) · (X - q) · (X - q2) · . . . · (X - qe-1),

k=0

denn wenn eine Nullstelle von f ist, dann auch qk , wobei nach Satz 2.16

0 k < grad(f ) = e gilt.

Anstatt jetzt das Legendre-Symbol

g

in F

f

q [X ]/(f ) zu betrachten, ersetzt

Hasse das irreduzible Polynom f durch einen seiner Linearfaktoren und sieht

sich das Symbol

g

in F

X-

qe [X ]/(X -) an. Nach dem Euler′schen Kriterium

ist das

g

qe-1

g

qe-1

g 2 (mod X - ) bzw.

= ¯

g 2

in Fqe.

X -

X -

26

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

g und X - sind beides Polynome in Fqe[X] mit Koeffizienten aus Fqe Fq.

Da grad(X - )=1, ist die Nullstelle Fqe, somit braucht man Fqe nicht zu

erweitern, denn Fqe[X]/(X - )

= F(qe)1.

Nun kann man auch das Symbol

g

als Kongruenz in F

f

qe [X ]/(X - ) schrei-

ben, n¨

amlich so:

g

qe-1

g 2 (mod X - )

f

qe-1

und zwar, weil das Euler′sche Kriterium, welches ja als

g

g 2 (mod f)

f

qe-1

definiert ist,

g

= g 2

+ k · f bedeutet. Weil aber X - in F

f

qe ein Teiler

qe-1

von f ist, kann das auch in der Form g = g 2 + k · j · (X - ) ausgedr¨uckt

f

werden, woraus obige Kongruenz folgt.

Das wiederum bedeutet, dass man die beiden Symbole gleichsetzen kann:

g

g

=

f

X -

Dann n¨

amlich konzentriert man sich einfach auf

g

und berechnet es nach

X-

dem Euler′schen Kriterium. Wie oben schon angedeutet, interessieren wir uns

f¨

ur g(). Im Folgenden wird in Fqe gerechnet:

g

qe-1

= g() 2

X-

qe-1

= g() q-1 · q-1

2

= g()(1+q+...+qe-1)· q-1

n

q-1

n

(Potenzgesetz)

=

g() · g()q · . . . · g()qe-1

q-1

n

=

g() · g(q) · . . . · g(qe-1)

Im letzten Schritt kann man die Potenz deshalb in die Klammer ziehen, weil

man unter Benutzung der binomischen Formel (Satz 2.8), welche in Charakte-

ristik p gilt zeigen kann, dass g()qk = g(qk):

qk

d

d

d

d

g()qk =

bii

=

bii qk =

(bi)qk (i)qk =

bii·qk = g(qk)

i=0

i=0

i=0

i=0

Wir haben jetzt also:

e-1

g

g

q-1

n

q-1

=

= g() · g(q) · . . . · g(qe-1)

=

g(qi) 2 ,

f

X -

i=0

wobei , q, . . . , qe-1 die Nullstellen von f sind.

27

---

3

DAS QUADRATISCHE REZIPROZITATSGESETZ

g sei jetzt auch ein irreduzibles normiertes Polynom aus Fq[X] und es sieht

zerlegt in seine Linearfaktoren in Fqd so aus:

d-1

g(X) =

(X - qj ) = (X - ) · (X - q) · (X - q2) · . . . · (X - qd-1)

j=0

Dann hat man

e-1

e-1 d-1

g

q-1

q-1

=

g(qi) 2 =

(qi - qj ) 2

f

i=0

i=0 j=0

Bei Vertauschung von f mit g ¨

andert sich die rechte Seite nur um den Faktor

(-1)e·d· q-1

2 :

e-1 d-1

d-1 e-1

g

· f

q-1

q-1

=

(qi - qj ) 2 ·

(qj - qi) 2

f

g

i=0 j=0

j=0 i=0

q-1

e-1 d-1

d-1 e-1

2

=

(qi - qj ) ·

(qj - qi)

i=0 j=0

j=0 i=0

q-1

e-1 d-1

2

=

(-1)e·d

(qi - qj )2

i=0 j=0

e-1 d-1

= (-1)e·d· q-1

2

(qi - qj )q-1

i=0 j=0

=1

Daraus folgt das quadratische Reziprozit¨

atsgesetz:

g

· f = (-1)e·d·q-12

wobei e = grad(f ) und d = grad(g)

f

g

28

---

4

DAS ALLGEMEINE REZIPROZITATSGESETZ

4

Das allgemeine Reziprozit¨

atsgesetz

4.1

Charaktere

F¨

ur den Beweis des quadratischen Reziprozit¨

atsgesetzes war bisher nur die

Zahl n = 2 von Interesse. Nun wird auf den folgenden Seiten dargestellt, wie

Hasse den Beweis des Reziprozit¨

atsgesetzes f¨

ur allgemeine nat¨

urliche Zahlen

n durchf¨

uhrt. Das Verfahren ist genau dasselbe, wie es in Abschnitt 3.4 schon

formuliert wurde, deshalb gehen wir hier auch nur kurz darauf ein.

Zun¨

achst werden Charaktere und die durch sie gebildeten Gruppen eingef¨

uhrt,

um sp¨

ater das Legendre-Symbol neu zu definieren. Die allgemeinere Definition

des Legendre-Symbols ist n¨

amlich die einzige bedeutende ¨

Anderung f¨

ur das

allgemeine Beweisverfahren.

Definition 4.1 Sei G eine Gruppe und K ein K¨

orper. Ein Homomorphismus

: G - K×

heißt ein (K-wertiger) Charakter von G in K.

Es gilt

(g1 · g2)

= (g1) · (g2)

(g1 · . . . · gn) = (g1) · . . . · (gn)

(gn)

= (g)n

(e)

= 1

(e neutr. El. von G)

(g-1)

= (g)-1

Wenn 1, 2 Charaktere sind, dann ist das Produkt 1 · 2 folgendermaßen

definiert:

(1 · 2)(g) = 1(g) · 2(g),

und das ist wieder ein Charakter, n¨

amlich 1 · 2 : G - K×. Sei ^

G =

Hom(G, K×) die Menge dieser Charaktere. Dann bildet ( ^

G, ·) eine abelsche

Gruppe, die Charaktergruppe genannt wird. Das neutrale Element ist hier

derjenige Charakter, der jedem Element g G die 1 aus K× zuordnet, also

(g) = 1.

Definition 4.2 Die Untergruppe ^

Gn ^

G der Charaktere mit der Eigenschaft

n = 1 nennt man die n-ten Charaktere.

Satz 4.3 Die Charaktergruppe ^

G = Hom(F×, F×) ist zyklisch mit der Ordnung

q

q

q - 1.

29

---

4

DAS ALLGEMEINE REZIPROZITATSGESETZ

Beweis:

F× ist zyklisch und wird von einem Element a erzeugt. Sei Hom(F×, F×).

q

q

q

Hom(F×, F×) ist mit der Multiplikation aus Definition 4.1 abelsche Gruppe,

q

q

neutrales Element ist die Abbildung (g) = 1 f¨

ur alle g F×. F

q

¨

ur b := ae ist

(b) = e(a), also ist durch (a) eindeutig bestimmt.

Betrachte die Abbildung

:

Hom(F×, F×) - F×

q

q

q

- (a).

ist nach Definition 4.1 Gruppenhomomorphismus. Er ist injektiv, denn da

durch (a) eindeutig bestimmt ist, und es gilt f¨

ur 1, 2 Hom(F×, F×) und

q

q

1 = 2, dass 1(a) = 2(a) ist.

Außerdem ist a Bild(), denn a = (id). F¨ur b := ae ist (mit der Multipli-

kation aus Definition 4.1) b = (ide). Damit sind dann auch alle Potenzen von

a im Bild() enthalten und Bild() = F×.

q

Also ist Isomorphismus. Es ist Hom(F×, F×) = id und # Hom(F×, F×) =

q

q

q

q

#F× = q - 1.

q

Korollar 4.4 Die Untergruppe der n-ten Charaktere ({, 2, . . . , n = 1}) hat

die Ordnung n und ist zyklisch, wird also von einem dieser n-ten Charakter

erzeugt.

Beispiel 4.5 Wir betrachten G = F× und K = F

q

q und interessieren uns f¨

ur

die Untergruppe der Quadrate. In ^

G = Hom(F×, F×) gibt es q - 1 Elemente,

q

q

q-1

darunter (g) = g 2

{-1, 1}. Die eine H¨alfte der Elemente aus F× wird

q

hier auf die 1, die andere H¨

alfte auf die -1 abgebildet. Die Quadrate sind

genau der Kern(). In Abschnitt 3.2 wurde das Legendre-Symbol als solcher

zweiter (oder quadratischer) Charakter definiert, ohne aber die Bezeichnung

Charakter" zu verwenden.

"

Beispiel 4.6 F× = 3 = {1 = 36, 2 = 32, 3 = 31, 4 = 34, 5 = 35, 6 = 33}.

7

Aus folgender Tabelle kann man alle n-ten Einheitswurzeln in F× entnehmen:

7

x F7 1 2

3

4

5

6

x2

1

4

2

2

4

1

x3

1

1

-1 1 -1 -1

x4

1

2

4

4

2

1

x5

1

4

5

2

3

-1

x6

1

1

1

1

1

1

Sei nun ein n-ter Charakter von F×, wobei n {1, 2, 3}. Dann ist durch

7

(3) eindeutig bestimmt.

Der erste (triviale) Charakter ist das Einselement, n¨

amlich (a) = 1 f¨

ur alle

a in F×. Es ist a7-1 = 1 (wobei sich jedes a als Potenz von 3 schreiben l

7

¨

asst).

30

---

4

DAS ALLGEMEINE REZIPROZITATSGESETZ

Zweite Charaktere sind diejenigen, f¨

ur die 2(3) = 1 gilt, also (a) {-1, 1}.

Daf¨

ur gibt es zwei M¨

oglichkeiten:

1.) 1(a) = 1 gilt wieder f¨

ur alle a F×.

7

2.) Es gilt 2(3) = -1, somit kann man alle Potenzen ausrechnen, n¨amlich

(1) = 6(3) = 1,

(2) = 2(3) = 1,

(4) = (2) · (2) = 1,

(5) = 5(3) = -1 und

(6) = 3(3) = -1.

F¨

ur die dritten Charaktere gilt 3(3) = 1, also (3) {1, 2, 4} (denn das sind

die dritten Einheitswurzeln). Die drei m¨

oglichen Charaktere sind also:

1.) (a) = 1 gilt f¨

ur alle a F×, siehe oben.

7

2.) (3) = 2: wir bestimmen wieder f¨

ur alle Elemente aus F×:

7

(1) = 1, (2) = 4, (4) = 2, (5) = 4 und (6) = 1.

3.) Falls (3) = 4, dann gilt:

(1) = 1, (2) = 2, (4) = 4, (5) = 2 und (6) = 1.

Es gibt also drei dritte Charaktere, welche die Untergruppe der dritten Charak-

tere bilden. Diese Untergruppe ist zyklisch und wird von mit (3) {2, 4}

erzeugt.

F¨

ur alle dritten Charaktere Hom(F×, F×) gilt 3 = 1 (3)3 = 1

7

7

7-1

3(3) 3 3 .

In Fq gibt es so viele verschiedene Untergruppen von n-ten Charakteren, wie

q - 1 Teiler hat, in diesem Beispiel sind das drei St¨uck.

4.2

Verallgemeinerung des Legendre-Symbols

Definition 4.7 Seien f und g in Fq[X] irreduzibel, normiert und verschieden

und g /

(f) sowie n ein Teiler von q-1. Sei Hom(Fq[X]/(f)×, Fq[X]/(f)×).

Das Legendre-Symbol ist definiert durch:

·

qe-1

=

:

¯

g -

¯

g

:= ¯

g n .

f

f

n

n

Das ist ein n-ter Charakter in Hom(Fq[X]/(f )×, Fq[X]/(f )×). Das Bild von

ist die Menge der n-ten Einheitswurzeln in Fq[X]/(f )×.

Hier sieht man, das das Legendre-Symbol genaugenommen in vereinfachter

Weise schon in Abschnitt 3.2 (Definition 3.4) als ein Charakter definiert wurde,

n¨

amlich als ein zweiter Charakter, der entweder den Wert 1 oder -1 annimmt.6

6vergleiche hierzu Satz 3.5

31

---

4

DAS ALLGEMEINE REZIPROZITATSGESETZ

Satz 4.8 Es gilt =

·

Hom(F

) und ist ein erzeugender

f

n

q [X ]/(f )×, F×

q

n-ter Charakter.

Beweis:

qe-1

Es ist erst zu zeigen, dass

g

= ¯

g n

f¨

ur alle g F

liegt.

f

n

q[X ] in F×

q

qe-1

Weil ¯

g n

eine n-te Einheitswurzel in Fq[X]/(f )× ist, ist es eine Nullstelle von

Xn - 1. Und da F× zyklisch ist und n ein Teiler von q - 1, sind alle Nullstellen

q

qe-1

von Xn - 1 schon in F× enthalten. Also ist ¯

g

q

n

eine n-te Einheitswurzel in

F×.

q

Es gilt f¨

ur g, h Fq[X] wegen der Homomorphie-Eigenschaft:

g

· h

gh

=

f

f

f

n

n

n

(analog zu Korollar 3.6) f¨

ur beliebige Potenzen n, die q - 1 teilen.

qe-1

Sei nun b ein Erzeuger von Fq[X]/(f )×, dann gilt ord(b n ) = n. Es ist also

qe -1

(b) = b n

eine primitive n-te Einheitswurzel in F×. Sei ein n-ter Charak-

q

ter. Da c := (b) ein Erzeuger von F× ist, l

q

¨

asst sich (b) als cj ausdr¨

ucken mit

k

j N. F¨ur a Fq[X]/(f ) ist dann (a) = (bk) = (b)

mit k N. Wie

oben gezeigt, ist (b) eine n-te Einheitswurzel in F×. Dann gilt

q

(a) = (cj)k = (b)jk = (bk)j = (a)j.

Also ist =

·

ein erzeugender n-ter Charakter.

f

n

Wegen

·

F

f

n

q l¨

asst sich die Multiplikation zweier Charaktere durchf¨

uhren,

und es gilt das allgemeine Reziprozit¨

atsgesetz

g

· f

= (-1)e·d·q-1

n

wobei e = grad(f ) und d = grad(g).

f

g

n

n

Der Beweis hierzu l¨

asst sich genauso durchf¨

uhren, wie der des quadratischen

Falls in Abschnitt 3.4.7

7siehe auch [1], S. 95ff.

32

---

2

2

2

2

-

2

2

-

2

1

2

-

-

2

2

4

1

-

2+

1+

-

-

-

-

-

-

2

-

1+

1

2

-

2+

-

-

-

2+

2+

-

2

1+

1

2

1

-

-

1+

-

l

s

2

2

2

-

-

2

-

1

22

-

1

22

1

3a

-

-

1

2

2

1+

2+

2+

1

-

-

-

1+

-

-

=

2

2

22

1

2

-

2

2

-

-

-

-

2

1+

2+

-

2+

1

2

2

it

-

-

-

1

-

1+

m

e

2

2

2

2

-

-

-

2

2

2

2

2

-

2

11

-

22

-

11

41

r

d

1+

-

-

2

2

1

2

1

-

-

-

nd.

2

-

1+

1

2+

1+

2+

2+

2

u

-

-

-

-

2

-

2+

1+

-

-

1

-

si

w

1

×

s

-

1

2

F 25

E

.

on

en

-

-

1

v

-

6

m

2

2+

-

2

2+

-

m

ger

o

k

2

2

2

2

-

2

2

1

2

2

2

-

-

2

21

-

-

2

-

-

-

24

r

zeu

2

-

2+

2+

-

1+

-

-

1

2

1

1+

-

1

-

-

1+

2+

1+

1

2+

-

2

2

-

-

-

-

E

r

age

e

F

h

2

2

2

2

2

-

2

1

2

2

2

-

in

2

-

-

-

-

-

2

-

11

24

2+

-

2

2

-

-

1

1+

2+

-

1+

1

e

-

1+

-

-

1

2

1

1+

2

-

2+

2+

-

-

-

-

oglic¨

m

ter

1

4

ak

-

12

6

2+

+

-

-

2

ar

-

-

h

2

12

)=2

C

-

-

2

12

4

a

rd(

-ter

o

1

3

n

-

t

2

2+

mi

2

2

2

2

e

r

t

e

2

2

-

2

2

a

-

-

1

-

2

-

2

-

24

W

-

2

2

1+

-

-

1

-

-

-

2+

2

1+

-

2+

-

2

1

-

2+

1

2

1+

-

-

2+

-

1

-

-

1+

te

l

s

en

a

2

2

2

2

2

2

2

-

2

1

2

-

c

h

-

2

-

22

-

-

2

-

-

-

-

-

11

24

l

em

u

-

2+

1

2+

1+

2

1+

2

2+

1+

2

1

1

E

a

2+

1

-

2

-

1+

-

-

-

-

-

-

t

.

nn

+

-

3

alle

da

c

hne

s

s

a

22

12

21

1

4

d

e

re

-

-

g

,

e

l

c

he

ier

w

2

2

2

2

F 25

2

2

2

2

h

-

-

2

1

-

-

-

2

-

-

-

4

-

-

2

-

t

1

1

2

1+

2+

2

-

1+

2

1+

2+

1

2+

in

-

-

-

-

-

-

1+

-

2

-

1

2+

2

s

i

eh

e

l

i

s

t

e

t

,

2

2

2

2

1

2

-

22

fg

ad

-

-

1

2+

-

-

-

2

1

u

1

-

2+

1+

1+

2

-

1

a

Gr

-

-

Man

.

×

2

2

a

F 25

om

2

-

2

1

2

2

n

v

22

-

2

-

-

-

-

o

2

1

2+

2+

1+

i

n

s

1+

-

1

-

-

-

v

en

e

l

n

om

2

2

2

2

2

11

-

2

2

-

2

2

41

+

-

2

-

22

11

c

h

2+

-

-

-

-

1

-

-

-

1+

2

2

-

2

a

olyn

1+

2

1

2+

-

-

1

-

2+

-

-

-

1

2

-

2+

-

1+

2

P

11

1

i

t

swurz

Vielf

len

2

1

ie

nhe

2

d

z

ib

-

-

2

-

-

Ei

u

h

2

2

1

22

-

2

-

r

e

d

-

-

s

ic

-

t

e

n

ir

1

2

n

2

-

2

-

111

888

len

e

s

-

-

o

h

22

1

alle

ein

-

2

2

1

8

er

-

-

-

2

d

i

ed

sin

×

w

F 25

d

llstelle

2

3

4

5

6

7

8

9

a

a

a

a

a

a

a

a

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

or

a

Hier

Nu

Ab

---

ANHANG

Anhang

Berechnung in C++

Als Anhang habe ich die Berechnung des Legendre-Symbols in C++ umge-

setzt. Beim Implementieren der verschiedenen Algorithmen hat mir mein Tutor

Holger Bremer geholfen.

Das Legendre-Symbol

g

wird hier nicht im endlichen K¨

orper F

f

pn , sondern

in Fp = Z/pZ berechnet. Als erstes muss das irreduzible Polynom aus Fp[X],

welches wir bisher immer f genannt haben, eingegeben werden. Auf Irreduzi-

bilit¨

at kann dieses Programm nicht pr¨

ufen. Nach der Eingabe von f und der

Primzahl p bestimmt das Programm alle Restklassen von f und gibt sie auf

dem Bildschirm aus. Die Restklassen werden hier allerdings nicht als Mengen

kenntlich, sondern sind lediglich durch Polynome ausgedr¨

uckt (mit kleinerem

Grad als f und Koeffizienten in Fp). In Folgenden werden jeweils die Quadrate

aller vorher bestimmten Restklassen ausgerechnet (und auch auf dem Bild-

schirm ausgegeben). Danach wird der Anwender dazu aufgefordert, das zweite

irreduzible Polynom (in dieser Arbeit mit g bezeichnet) einzugeben. Wenn das

geschehen ist, so wird g durch f geteilt und der Rest als Polynom in Fp[X]

ausgegeben. Dann vergleicht das Programm diesen Rest mit den vorher be-

rechneten Quadraten und gibt das Ergebnis 1 aus, falls er in der Menge der

Quadrate enthalten ist, ansonsten wird -1 ausgegeben.

Um eine bessere ¨

Ubersicht zu gew¨

ahrleisten, werden zun¨

achst zwei Struktu-

ren festgelegt, auf die im gesamten Programm immer wieder zugegriffen wird.

Die erste Struktur legt einen Typ mit den Eigenschaften eines Polynoms fest,

der durch den Grad und seine Koeffizienten bestimmt ist. Um sp¨

ater verschie-

dene Polynome in einer Menge zusammenzufassen, dient die zweite Struktur

polynomfeld. Wir ben¨

otigen sie beispielsweise f¨

ur die Berechnung der Rest-

klassen eines Polynoms. Die folgenden beiden Funktionen freepolynom und

freepolynomfeld dienen dazu, sp¨

ater den belegten Speicher wieder freizu-

geben. Dann werden Operatoren eingef¨

uhrt, und zwar jeweils f¨

ur die Eingabe

und Ausgabe eines Polynoms und f¨

ur die Ausgabe einer Menge von Polynomen.

Wie man an der L¨

ange des ersten Ausgabeoperators erkennen kann, gestaltet

sich die Wiedergabe eines Polynoms auf dem Bildschirm recht aufwendig, hier-

zu habe ich im Quelltext einige Kommentare eingef¨

ugt.

Die Funktion setkoeff erzeugt die Koeffizienten modulo der eingegebenen

Primzahl p (also in Fp), was zum Beispiel beim Berechnen der Restklassen

und deren Quadrate verwendet wird. Im Folgenden werden in den Funktionen

restklassen und quadrat alle Restklassen bzw. das Quadrat eines Polynoms

berechnet. Es folgt eine gleichnamige Funktion, die von mehreren Polynomen

34

---

ANHANG

jeweils die Quadrate berechnet, also die vorherige Funktion quadrat benutzt.

Dann wird eine Funktion teilen erstellt, die ein Polynom A durch ein Polynom

B teilt. Es folgt eine Funktion vergleichen, die ein Polynom mit mehreren

Polynomen vergleichen kann. Die folgende Funktion reduzieren dient dazu,

bei der Ausgabe der Quadrate jedes Quadrat nur einmal auf dem Bildschirm

wiederzugeben. Es folgt nun das Hauptprogramm, welches all die im Vorfeld

definierten Funktionen in der Weise ausf¨

uhrt, wie schon oben (im zweiten Ab-

schnitt dieses Kapitels) beschrieben wurde.

#include <iostream>

using namespace std;

#include<math.h>

struct polynom{

int grad;

double *koeff;

};

struct polynomfeld{

int anzahl;

//*** Anzahl der Polynome ***

int ausgangsgrad;

//*** maximaler Grad ***

int prim;

//*** Primzahl p f¨

ur Z/pZ ***

polynom *polynome;

//*** in diesem Feld stehen Polynome ***

};

polynom createpolynom(int n)

//*** macht ein Polynom vom Grad n ***

{

polynom rueckgabe;

rueckgabe.grad=n;

rueckgabe.koeff=new double [n+1];

return rueckgabe;

}

polynomfeld createpolynomfeld(int n,int m,int p)

{

//*** macht ein Feld mit vielen Polynomen ***

polynomfeld rueckgabe;

rueckgabe.anzahl=n;

//*** n ist die Anzahl der Polynome ***

rueckgabe.ausgangsgrad=m;

//*** m ist der maximale Grad ***

rueckgabe.prim=p;

//*** l=p ist die Primzahl ***

rueckgabe.polynome=new polynom [n];

for(int i=0;i<n;i++) rueckgabe.polynome[i]=createpolynom(m);

return rueckgabe;

}

void freepolynom(polynom freigabe)

{

delete [] freigabe.koeff;

}

35

---

ANHANG

void freepolynomfeld(polynomfeld freigabe)

{

for(int i=0;i<freigabe.anzahl;i++)

freepolynom(freigabe.polynome[i]);

delete [] freigabe.polynome;

}

istream & operator >>(istream & is, polynom & eingabe)

{

for(int i=eingabe.grad;i>=0;i--)

//*** Koeffizienten a werden von

{

// a_n bis a_0 eingegeben, also

// von vorn nach hinten ***

cout<<"Bitte den "<<i<<"ten Koeffizenten ein: ";

is>>eingabe.koeff[i];

cout<<endl;

}

return is;

}

ostream & operator <<(ostream &os, polynom ausgabe)

{

int test=0;

//*** "test" ist eine Hilfs-

for(int i=ausgabe.grad;i>=0;i--)

// variable und wird erst

{

// dann auf Eins gesetzt,

if(i==ausgabe.grad&&i!=1&&i!=0)

// wenn der erste von Null

// verschiedene Koeffiezient

{

// ausgegeben worden ist. ***

if(ausgabe.koeff[i]==1) os<<"x^"<<i;

else if(ausgabe.koeff[i]!=0) os<<ausgabe.koeff[i]<<"x^"<<i;

}

else if(i==1)

{

if(test==1)

{

if(ausgabe.koeff[i]==1)os<<"+x";

else if(ausgabe.koeff[i]!=0)os<<"+"<<ausgabe.koeff[i]<<"x";

}

else if(test==0||i==ausgabe.grad)

//*** falls das eintritt,

{

// dann kam vorher noch kein

// Summand vor ***

if(ausgabe.koeff[i]==1)os<<"x";

else if(ausgabe.koeff[i]!=0)os<<ausgabe.koeff[i]<<"x";

}

}

else if(i==0)

//*** f¨

ur den letzten Summanden a_0 ***

{

if(test==1)

{

if(ausgabe.koeff[i]!=0)os<<"+"<<ausgabe.koeff[i];

}

36

---

ANHANG

else if(test==0||i==ausgabe.grad)

{

if(ausgabe.koeff[i]!=0)os<<ausgabe.koeff[i];

}

}

else

{

if(test==1)

{

if(ausgabe.koeff[i]==1) os<<"+x^"<<i;

else if(ausgabe.koeff[i]!=0)

{

os<<"+"<<ausgabe.koeff[i]<<"x^"<<i;

}

}

else if(test==0||i==ausgabe.grad)

{

if(ausgabe.koeff[i]==1) os<<"x^"<<i;

else if(ausgabe.koeff[i]!=0)

{

os<<ausgabe.koeff[i]<<"x^"<<i;

}

}

}

if(ausgabe.koeff[i]!=0)test=1;

}

os<<endl;

return os;

}

ostream & operator <<(ostream & os, polynomfeld ausgabe)

{

for(int i=0;i<ausgabe.anzahl;i++)

os<<ausgabe.polynome[i];

os<<endl;

return os;

}

void setkoeff(polynomfeld eingang)

//*** Hier werden die Koeffizienten

{

// der Polynome erzeugt ***

int k=0;

int schreib;

for(int i=0;i<=eingang.ausgangsgrad;i++)

{

schreib=0;

for(int j=0;j<eingang.anzahl;schreib++)

{

if(schreib%eingang.prim==0)schreib=0;

for(k=0;k<pow((double)(eingang.prim),(double)(i));k++)

{

37

---

ANHANG

eingang.polynome[j].koeff[i]=schreib;

j++;

}

}

}

}

polynomfeld restklassen(polynom eingang, int prim)

{

int anzahl=(int)pow((double)prim,(double)(eingang.grad));

//*** Anzahl der Restklassen ist p^grad(f) ***

polynomfeld ausgabefeld=createpolynomfeld(anzahl,eingang.grad-1,prim);

setkoeff(ausgabefeld);

return ausgabefeld;

}

polynom quadrat(polynom ein,int prim)

{

//*** erzeugt das Quadrat eines Polynoms ***

polynomfeld speicher=createpolynomfeld(ein.grad+1,ein.grad,0);

for(int i=0;i<=ein.grad;i++)

{

for(int j=0;j<=ein.grad;j++)

{

speicher.polynome[i].koeff[j]=ein.koeff[i]*ein.koeff[j];

} //*** multipliziert jeden Koeffizienten mit dem gesamten Polynom ***

}

polynom rueckgabe=createpolynom(ein.grad*2);

for(int i=0; i<=rueckgabe.grad;i++)

{

rueckgabe.koeff[i]=0;

}

for(int i=0; i<=ein.grad;i++)

{

for(int j=i; j<=ein.grad+i;j++)

{

rueckgabe.koeff[j]+=speicher.polynome[i].koeff[j-i];

}

}

for(int i=0; i<=rueckgabe.grad;i++)

//*** Koeffizienten anpassen ***

{

rueckgabe.koeff[i]=(int)rueckgabe.koeff[i]%prim;

}

freepolynomfeld(speicher);

return rueckgabe;

}

polynomfeld quadrat(polynomfeld ein)

{

polynomfeld rueck=createpolynomfeld(ein.anzahl,ein.ausgangsgrad*2,0);

for(int i=0; i<rueck.anzahl;i++)

{

38

---

ANHANG

rueck.polynome[i]=quadrat(ein.polynome[i],ein.prim);

}

return rueck;

}

polynom teilen(polynom A, polynom B, int prim)

{

//*** Polynomdivision A:B ***

int z=1,z2=0;

if(A.grad<B.grad)

{

return A;

}

polynom C=createpolynom(A.grad-B.grad);

C.koeff[C.grad]=A.koeff[A.grad]/B.koeff[B.grad];

for(int i=A.grad;i>=B.grad;i=A.grad,z2++)

{

z=1;

while((int)A.koeff[A.grad]%(int)B.koeff[B.grad]!=0)

{

A.koeff[A.grad]+=prim;

}

C.koeff[C.grad-z2]=((int)(A.koeff[A.grad]/B.koeff[B.grad]))%prim;

A.grad=A.grad-1;

for(int j=A.grad;j>=0;j--)

{

if(B.grad-z<0)

{

break;

}

else

{

A.koeff[j]-=C.koeff[C.grad-z2]*B.koeff[B.grad-z];

z++;

}

}

}

freepolynom(C);

for(int i=0;i<=A.grad;i++)

{

while(A.koeff[i]<0)

{

A.koeff[i]+=prim;

}

A.koeff[i]=(int)A.koeff[i]%prim;

}

return A;

}

int vergleichen(polynom eingangsp, polynomfeld eingang)

{

int ergebnis;

if(eingangsp.grad>eingang.ausgangsgrad)

39

---

ANHANG

{

return -1;

}

for(int j=0;j<eingang.anzahl;j++)

{

for(int i=0;i<=eingang.ausgangsgrad;i++)

{

if(i<=eingangsp.grad)

{

if(eingangsp.koeff[i]==eingang.polynome[j].koeff[i])

{

ergebnis=1;

}

else

{

ergebnis=-1;

break;

}

}

else

{

if(eingang.polynome[j].koeff[i]==0)

{

ergebnis=1;

}

else

{

ergebnis=-1;

break;

}

}

}

if(ergebnis==1)

{

return ergebnis;

}

}

return -1;

}

polynomfeld reduzieren(polynomfeld ein)

{

int zaehler=0;

int test=1;

polynomfeld aus=createpolynomfeld(ein.anzahl,ein.ausgangsgrad,ein.prim);

for(int i=0; i<=ein.ausgangsgrad;i++)

{

aus.polynome[0].koeff[i]=ein.polynome[0].koeff[i];

}

zaehler=1;

for(int j=0;j<ein.anzahl;j++)

{

test=0;

40

---

ANHANG

for(int k=0;k<zaehler;k++)

{

for(int i=0; i<=ein.ausgangsgrad;i++)

{

if(aus.polynome[k].koeff[i]!=ein.polynome[j].koeff[i])

{

test++;

break;

}

}

}

if(test==zaehler)

{

for(int i=0; i<=ein.ausgangsgrad;i++)

{

aus.polynome[zaehler].koeff[i]=ein.polynome[j].koeff[i];

}

zaehler++;

}

}

polynomfeld aus2=createpolynomfeld(zaehler,aus.ausgangsgrad,aus.prim);

for(int i=0;i<zaehler;i++)

{

for(int j=0;j<=aus2.ausgangsgrad;j++)

{

aus2.polynome[i].koeff[j]=aus.polynome[i].koeff[j];

}

}

freepolynomfeld(aus);

return aus2;

}

int main()

{

int n,m,prim;

int summe=0;

int ergebnis;

cout<<"Bitte den Grad des ersten Polynoms f eingeben: ";

//*** grad(f) ***

cin>>n;

cout<<endl;

polynom A=createpolynom(n);

cin>>A;

//*** Operator f¨

ur die Eingabe eines

cout<<"Das erste Polynom lautet: ";

// Polynoms wird aufgerufen ***

cout<<A<<endl<<endl;

cout<<"Bitte die Primzahl p eingeben, modulo der in Z/pZ ";

cout<<"gerechnet werden soll: ";

cin>>prim;

polynomfeld B=restklassen(A,prim);

//*** erstellt die Restklassen

// von f ***

cout<<endl;

cout<<"Die Restklassen von f lauten:"<<endl;

cout<<B;

polynomfeld C=quadrat(B);

//*** erstellt die Quadrate

41

---

ANHANG

cout<<endl;

// der Restklassen ***

cout<<"Die Quadrate dieser Restklassen lauten:"<<endl;

polynomfeld D=reduzieren(C);

cout<<D;

cout<<"Bitte den Grad des zweiten Polynoms g eingeben: ";

cin>>m;

cout<<endl;

polynom G=createpolynom(m);

cin>>G;

cout<<endl;

cout<<"Das zweite Polynom lautet: ";

cout<<G<<endl<<endl;

polynom Rest=teilen(G,A,prim);

//*** teilt g durch f ***

cout<<"Der Rest lautet: ";

for (int i=0;i<=Rest.grad;i++)

{

summe=(int)(summe+Rest.koeff[i]);

}

if(summe!=0)

{

cout<<Rest;

ergebnis=vergleichen(Rest,C);

//*** ergebnis ist in {+1,-1} ***

}

else

{

cout<<"0, ";

ergebnis=0;

}

cout<<endl;

if(ergebnis==1)

{

cout<<"Dieser Rest ist in der Menge der Quadrate von f "<<endl;

cout<<"enthalten, also nimmt das Legendre-Symbol den Wert ";

cout<<ergebnis<<" an."<<endl;

}

else if(ergebnis==0)

{

cout<<"das zweite Polynom g war ein Vielfaches von f."<<endl;

}

else

{

cout<<"Dieser Rest ist nicht in der Menge der Quadrate von f "<<endl;

cout<<"enthalten, also nimmt das Legendre-Symbol den Wert ";

cout<<ergebnis<<" an."<<endl;

}

freepolynom(A);

//*** L¨

oschen der belegten Speicher ***

freepolynom(G);

freepolynom(Rest);

freepolynomfeld(B);

freepolynomfeld(C);

freepolynomfeld(D);

return 0;

}

42

---

QUELLENVERZEICHNIS

Quellenverzeichnis

Prim¨

arliteratur

[1] Hasse, Helmut: Zahlentheorie. Berlin 1969 (Akademie), S. 95ff.

Sekund¨

arliteratur

[2] Artin, Emil: Galoissche Theorie. Thun/Frankfurt am Main 1988 (Harri

Deutsch).

[3] Artin, Michael: Algebra. Basel/Boston/Berlin 1993 (Birkh¨

auser).

[4] Bosch, Siegfried: Algebra. Berlin/Heidelberg 2004 (Springer).

[5] Cigler, Johann: K¨

orper, Ringe, Gleichungen. Ulm 1995 (Spektrum).

[6] Jacobson, Nathan: Basic Algebra 1. San Francisco 1974 .

[7] Koch, Helmut: Einf¨

uhrung in die klassische Mathematik 1. Vom quadra-

tischen Reziprozit¨

atsgesetz bis zum Uniformisierungssatz, Berlin 1986 (Sprin-

ger).

[8] Koch, Helmut: Zahlentheorie. Algebraische Zahlen und Funktionen, Braun-

schweig/Wiesbaden 1997 (Vieweg).

[9] Lang, Serge: Algebra. New York 1965 (Addison-Wesley).

[10] Lemmermeyer, Franz: Reciprocity Laws. From Euler to Eisenstein, Ber-

lin/Heidelberg 2000 (Springer).

[11] Van der Waerden: Algebra. Volume 1, New York 2003 (Springer).

43

---