Das quadratische Reziprozitätsgesetz für Polynomringe

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:

gerade ist, also p ≡ 1(mod 4)

Wenn eine der beiden Zahlen p−1 oder q−1

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.

ungerade sind, also p ≡ 3(mod 4)

Wenn aber beide Zahlen p−1 und q−1

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 q ≡ q

p−1

mit Werten in {−1, 1}. Unter der Voraussetzung, dass

p p

gelte, verfasste er das quadratische Reziprozit¨ atsgesetz wie folgt:

Seien p, q ∈ N verschiedene ungerade Primzahlen. Dann gilt

p q

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  NA  

  3  

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 a i , b j ∈ R jeweils die Koeffizienten von f bzw. g, wobei a e , b d = 0. Also:

e f = i=0 d b j X j = b d X d + ... + b 1 X + b 0 g = 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 a k und b k von f und g gilt a k + b k = 0 f¨ ur k > max(grad(f ), grad(g)). Es gilt auch

• grad(f · g) ≤ grad(f ) + grad(g), k+l=i a k ·b l = 0 f¨ ur i > grad(f )+grad(g). Das letzte Summenglied denn von f · g kann also h¨ ochstens die Summe beider Grade von f und g zum Grad haben.

4

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 =

=

= g · f

2) Einselement:

Vor.: Es existiert die Eins f¨ ur jedes a in R mit a · 1 R = a. z.z.: Dann gibt es auch das Einselement f¨ ur alle Polynome f in R[X] mit

f · 1 R[X] = f .

Wegen

R −→ R[X]

a −→ a · X 0 + 0 · X 1 + ... (konstantes Polynom)

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

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

gilt.

e

i=0 a i X i mit a i ∈ R. Dann ist

Sei also f =

3) Nullteilerfreiheit:

Vor.: f¨ ur a, b ∈ R und a, b = 0 gilt a · b = 0

5

k

e+d

f · g = = a 0 b 0 + (a 0 b 1 + a 1 b 0 )X + ... +

Falls R also nicht nur Ring, sondern sogar Integrit¨ atsring ist, so ist der Koef- fizient des letzten Summenglieds (mit der h¨ ochsten Potenz) a e · b d = 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 1 Beweis nachzulesen in [4], S. 46.

6

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 = 1 R = 1 R[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 = 1 R[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 = 1 R[X] = 1 R

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

γ :

−→ grad(f )

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

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 =

i=0

und d g =

j=0

Es gilt a e = 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

b d

g 1 := g − a e

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

d e b d

g 1 = = =

8

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

gibt es jetzt f¨ ur g 1 eine Zerlegung g 1 = k 1 f + r 1 mit grad(r) < e = grad(f )

und k 1 , r 1 ∈ K[X]. Jetzt setzt man noch k = k 1 + b d X d−e und damit gilt

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

κ :

schickt ein g ∈ R auf seine Restklasse ¯

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

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

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

g 2 , ¯

h ∈ R/I F¨ ur die Wohldefniniertheit der Multiplikation ist zu zeigen: f¨ ur ¯ g 1 , ¯

g 1 · ¯ g 2 · ¯ g 2 ⇒ ¯ gilt: ¯ g 1 = ¯ h = ¯ h.

Seien g 1 ∈ ¯ g 1 , g 2 ∈ ¯ g 2 . Es gibt also ein a ∈ I mit g 2 = g 1 + a. g 2 mit ¯ g 1 = ¯

Sei h ∈ ¯

h. Weil g 1 und g 2 in derselben Restklasse sind, ist g 2 h dasselbe wie

g 1 · ¯ g 2 · ¯ g 1 h + ah. Da a im Ideal I enthalten ist, gilt auch ah ∈ I, woraus ¯ h = ¯ h

folgt. Analog gilt ¯ g 1 = ¯ h · ¯ h · ¯ g 2 .

g( ¯ h + ¯ g ¯ g ¯

Es gilt auch die Assoziativit¨ at und das Distributivgesetz ¯

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

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 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 F q 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 U m diejenige Untergruppe aller Elemente b aus U, deren Ordnung m teilt, also U m = {b ∈ U : ord(b) |m}. In U m befinden sich h¨ ochstens m Elemente, denn das sind alles L¨ osungen der Gleichung X m = 1. Wenn man sich jetzt die von a erzeugte zyklische Gruppe a = {1, a 1 , a 2 , . . . , a m−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 ⊆ U m ist, U m h¨ ochstens m Elemente hat, a aber genau m, folgt a = U m . Somit ist U m zyklisch.

Wenn man jetzt noch U m = U zeigt, dann ist auch U zyklisch. Dazu wird hier der Struktursatz f¨ ur endliche abelsche Gruppen 2 benutzt, welcher besagt, dass sich jede endliche abelsche Gruppe (also auch U) als direktes Produkt von zyklischen Gruppen in der Form U = Z n 1 × Z n 2 × . . .× Z n k schreiben l¨ asst, wobei n i = #Z n i und n 1 |n 2 |n 3 | . . . |n k .

Angenommen U m = U. Dann gibt es ein Element y ∈ U welches nicht in U m 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 n i sein und das m¨ usste dann m = n k 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.

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

11

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

die Existenz von Inversen zu zeigen.

g ∈ K[X]/(f ) Restklasse, ¯ g = 0. Alle Elemente aus ¯ Sei ¯ g lassen sich in der Form

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

grad r 1 < grad f .

Mit Hilfe der Abbildung

K[X]/(f ) −→ K[X]/(f ) Λ ¯ g :

¯ g · ¯ −→ ¯ h h

\{0} ein Inverses

g ∈

wird jetzt gezeigt, dass es f¨ ur jedes Element ¯

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

phismus ist.

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

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

g · λ · ¯ a = λ · ¯ g · ¯ a = λ · Λ ¯ und Λ ¯ g (λ¯ a) = ¯

Injektivit¨ at von Λ ¯ g :

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

g ( ¯ h) = 0 ⇔ ¯ h ∈ Kern(Λ ¯ Λ ¯ g ). Also gilt Λ ¯

g = 0 und somit ist Λ ¯

nach Voraussetzung ist ¯

g surjektiv, somit ist 1 ∈ Bild(Λ ¯ Dann ist Λ ¯

klasse ¯ g ( ¯ h in K[X]/(f ) gibt mit Λ ¯ h) = 1. Also gilt ¯

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

K(α), der modellhaft so aussieht:

e λ i α i−1 |λ i ∈ K} = K + αK + . . . + α e−1 K K(α) = { i=1 ubrigens, dass α e ∈ K(α), denn es ist ja Wir wissen ¨ m(α) = α e + λ e α e−1 + . . . + λ 1 α + λ 0 = 0, woraus folgt, dass α e = −λ e α e−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 K e . Falls K endlich ist, hat K e (#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.

2 Z/3Z(α) = i=1 λ i α i−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 3 2 verschiedene Polynome, also auch 3 2 verschiedene Bildvektoren. Somit ist der Erweiterungsk¨ orper Z/3Z(α) isomorph zum Z/3Z- Vektorraum (Z/3Z) 2 , der 3 2 = 9 Elemente hat.

Satz 2.6 Der Restklassenk¨ orper K[X]/(f ) ist isomorph zu K(α).

Beweis:

Die Abbildung K[X] −→ K(α)

ϕ :

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 · X 0 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

Die Abbildung

K[X]/(f ) −→ K(α)

˜ ϕ :

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 ∈ F p gilt a p = a. F¨ ur alle a = 0 gilt a p−1 = 1.

Beweis:

F¨ ur a, b ∈ F p gilt (a + b) p = a p + b p , denn es ist

p p

(a + b) p = = =1 =1 = a p + b p ,

p

da ⇒ (a 1 + a 2 + . . . + a k ) p = a p Falls alle a i = 1, so ist k p = (1 + 1 + . . . + 1) p = 1 p + 1 p + . . . + 1 p = k,

also k p = k.

Weil F p K¨ orper ist, ist außer der Null jedes Element darin invertierbar, somit gilt in F p \{0} = F × p :

a p−1 = a p · a −1 = a −1 · a p = a −1 · a = 1.

14

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 = F p 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 p n 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 F p und es gilt char F p = p = char F, denn die Charakteristik von K¨ orper und seinen Teilk¨ orpern ist dieselbe. F kann als F p -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 a 1 ω 1 + . . . + a n ω n , wobei a i ∈ F p . Es hat F somit p n = q Elemente.

Satz 2.14 Wenn F und F zwei K¨ orper mit Ordnung p n 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 X q−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 = X q − X ist. X q − X hat maximal q Nullstellen und F hat q Elemente. Dann ist F

15

Zerf¨ allungsk¨ orper von X q − X.

Satz 2.15 F¨ ur jede Primzahlpotenz q = p n gibt es einen K¨ orper F mit p n Elementen, welcher der Zerf¨ allungsk¨ orper des Polynoms f = X q − X ¨ uber seinem Primk¨ orper F p ist.

Beweis:

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

Sei dazu F p ein algebraischer Abschluss von F p , hierin liegen s¨ amtliche Nullstellen aller nicht-konstanten Polynome aus F p [X], auch diejenigen von f = X q − X. F enth¨ alt alle Nullstellen von f . Nun wird gezeigt, dass X q −X lauter verschiedene Nullstellen hat, n¨ amlich q St¨ uck. Damit hat F mindestens q Elemente. uber F vollst¨ andig in Linearfaktoren und l¨ asst sich in der Form f zerf¨ allt ¨

X q −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 X q − X n¨ amlich keine mehrfachen Nullstellen und somit ganz genau p n = q St¨ uck.

Wenn f, g ∈ F p [X] sind, dann ist formal abgeleitet (mit der Produktre- gel) (f · g) = f g + g f .

Wenn das Polynom X q − X eine doppelte Nullstelle λ in F p h¨ atte, dann w¨ are X q − X = (X − λ) 2 · g mit g ∈ F p [X]. Es folgt also (X q − X) = 2(X − λ) · g + (X − λ) 2 · g = 0, wenn X = λ gesetzt wird. Daraus folgt aber, dass λ nicht nur Nullstelle von X q − X ist, sondern auch von seiner Ableitung (X q − X) . Es gilt aber auch: (X q − X) = qX q−1 − 1 = p n X p n −1 − 1 = −1, weil char F p = p und p · F p = 0. Wenn aber (X q − X) = −1 ist, dann ist λ keine Nullstelle von (X q − X) , was einen Widerspruch ergibt.

2.) Der Zerf¨ allungsk¨ orper von X q − X hat h¨ ochstens p n Elemente.

Zeige dazu: die Menge dieser Nullstellen ist ein K¨ orper. Dies ist dann der Zerf¨ allungsk¨ orper von X q − X, der F p 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) p n = a p n ± b p n = a q ± b q

mit p n = q.

16

Wenn a Nullstelle von X q − X ist, dann ist a q − a = 0, also a q = a, weil außer der Null jede Nullstelle davon Einheitswurzel ist (analog mit einer Nullstelle b), daraus folgt dann a q ± b q = a ± b. Aus (a ± b) q = a ± b folgt (a ± b) q − (a ± b) = 0, d.h. a ± b sind wieder Nullstellen von f = X q − X. ) q = a q und (a · b) q = a q · b q = a · b, denn Genauso folgt f¨ ur b = 0: ( a b q = a

wie oben gilt a q = a und b q = b. Also sind auch a b von X q − X. Wir haben nun also herausgefunden, dass wenn a und b Nullstellen von X q − 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 Teilk¨ orper von F p , welcher F p enth¨ alt (wegen 1 + . . . + 1 ∈ F ist F p ∈ F), somit Zerf¨ allungsk¨ orper von X q − X mit ganz genau p n Elementen. Die- ser K¨ orper wird im Folgenden F q genannt.

Satz 2.16 Sei p Primzahl, f ∈ F p [X] irreduzibel und normiert mit grad f = e und α ∈ F p (α) eine Nullstelle von f . Dann hat f genau e Nullstellen, n¨ amlich α, α p , α p 2 , . . . , α p e−1 ∈ F p (α), und l¨ asst sich somit folgendermaßen in Linear- faktoren zerlegen:

f = (X − α) · (X − α p ) · (X − α p 2 ) · . . . · (X − α p e−1 ) F p (α) ist daher der Zerf¨ allungsk¨ orper von f .

Beweis:

Sei ϕ ∈ Aut (F p (α)) (erstmal nicht n¨ aher bestimmt, einfach irgendein Auto- morphismus auf F p (α)). Jetzt wird gezeigt, dass auch ϕ(α) Nullstelle von f ist, wenn α Nullstelle von f ist.

ϕ ist auf F p 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 (α)) = ϕ

= 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 #F p (α) = p e (wie in Abschnitt 2.1 gezeigt), gibt es h¨ ochstens so viele Automorphismen auf F p (α) wie verschiedene Nullstellen von f und das sind h¨ ochstens e St¨ uck, weil der Automorphismus ϕ durch ϕ(α) eindeutig bestimmt ist.

17

Wir w¨ ahlen jetzt die Abbildung F p (α) −→ F p (α) ϕ :

−→ z p z 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 = z p + w p = ϕ(z) + ϕ(w) ϕ(z · w) = (z · w) p = z p · w p = ϕ(z) · ϕ(w)

Injektivit¨ at:

Angenommen, es sei ϕ(z) = ϕ(w). ⇒ z p = w p ⇒ z p − w p = 0 ⇒ (z − w) p =

0 ⇒ z = w. Fertig. Weil F p (α) gleich viele Elemente hat wie F p (α), ist ϕ

surjektiv, sobald es injektiv ist.

Somit ist ϕ(α) = α p Nullstelle von f , also auch (α p ) p = α p 2 , also auch α p e−1 . Dann l¨ asst sich f folgendermaßen schreiben: e−1 (X − α p k ) = (X − α) · (X − α p ) · (X − α p 2 ) · . . . · (X − α p e−1 ) f = k=0 Wenn man jetzt noch zeigt, dass die Nullstellen α, α p , α p 2 , . . . , α p e−1 paarweise verschieden sind, dann ist sicher, dass gilt: # Aut(F p (α)) = e = # NST von f . Sei 0 ≤ i < k < e. Angenommen, es sind zwei der Nullstellen gleich, n¨ amlich α p i = α p k . Wenn man links und rechts die p i -te Wurzel zieht, bekommt man α = α p k−i . Nenne nun k − i := j, es gilt 0 < j < e. Dann gibt es ein g(X) = (X − α) · (X − α p ) · . . . · (X − α p j−1 ) und es gilt: ϕ(g(X)) = g p (X) = (X − α) p · (X − α p ) p · . . . · (X − α p j−1 ) p = (X − α p ) · (X − α p 2 ) · . . . · (X − α p j ) wegen Homomorphie von ϕ = g(X), denn α p j = α.

Damit ist ϕ(g(X)) = g p (X) = g(X) und es gilt dann f¨ ur jeden Koeffizienten c von g: ϕ(c) = c p = c, denn g p (X) = g(X) = c j X j + . . . + c 1 X + c 0 = c p j X jp + . . . + c p 1 X p + c p

18

Nach Satz 2.8 gilt in F p X p = X f¨ ur alle X ∈ F p , das Polynom X p − X hat h¨ ochstens p Nullstellen, also sind alle Nullstellen von X p − X = 0 in F p enthalten. Damit folgt aus ϕ(c) = c, dass c ∈ F p ist. Dann ist also auch g ∈ F p [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

1 falls es ein b ∈ Z gibt mit a ≡ b 2 (mod p)

a

Satz 3.2 Das quadratische Reziprozit¨ atsgesetz f¨ ur Zahlen 3 besagt: Wenn l und p zwei verschiedene ungerade Primzahlen sind, dann gilt

wobei nach dem Euler’schen Kriterium gilt: Beispiel 3.3 Sei p = 7. Die Quadrate in Z/7Z sind 1, 2 und 4. Dann ist das

4 = 1, denn 4 ist ein Quadrat in Z/7Z (4 ≡ 2 2 (mod 7)).

Legendre-Symbol Es ist aber zum Beispiel Sei nun l = 5. Die Quadrate in Z/5Z sind 1 und 4, also ist Satz 3.2 ist dann

(−1) · (−1) =

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. 3 Beweis nachzulesen in [7] S. 35f.

20

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

3.2.1 Eulers Hilfssatz

Definition 3.4 Sei f ∈ F q [X] irreduzibel und normiert, g ∈ F q [X] und g kein

Vielfaches von f . Im endlichen K¨ orper F q [X]/(f ) ist

g = ¯ b 2 in F q [X]/(f )

1 falls es ein b ∈ F q [X] gibt mit ¯

als das Legendre-Symbol definiert.

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

1 = −1. Sei also im Folgenden q = p n (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:

oder anders ausgedr¨ uckt:

g

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

Beweis:

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

h ∈ F q [X]/(f ) × mit ord( ¯ nung q e − 1. Es gibt also einen Erzeuger ¯

h) = q e − 1.

Daher gilt f¨ ur jedes Element 0 = ¯ g ∈ F q [X]/(f ), dass ¯

g = ¯ b 2 .

1) Sei ¯

q e −1 q e −1 = ¯ b q e −1 = 1 nach Satz 2.8. = ( ¯ b 2 )

Dann ist ¯

2) Sei y ∈ N mit ¯ Dann muss y ungerade sein, denn sonst k¨ onnte man ¯ b := ¯ w¨ are somit bei Fall 1) angelangt. Also ist ¯

doch y · q e −1

Jetzt bleibt noch zu zeigen: ¯ g q e −1 = 1 folgt (¯ g Aus ¯

Daraus folgt ¯

21

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

≡ g f F¨ ur alle g, h ∈ F q [X] mit f | gh und e = grad(f ) gilt:

denn

Satz 3.7 (Quadratisches Reziprozit¨ atsgesetz) Seien f, g ∈ F q [X] irredu-

zibel ¨ uber diesem K¨ orper, normiert und verschieden, grad(g) = d und grad(f ) = e.

Dann gilt:

Korollar 3.8 Aus dem Euler’schen Kriterium folgt dieser (einzige) Erg¨ anzungs- satz:

ε q e −1

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 ∈ F p und a = b. Die beiden Polynome sind jeweils vom Grad eins und a und b sind ihre Nullstellen in F p . Es soll also gezeigt werden, dass hierf¨ ur das quadratische Reziprozit¨ atsgesetz gilt, n¨ amlich

Zuerst wird gezeigt, dass g genau dann ein Quadrat in F p [X] ist, wenn (a − b) g a−b in F p ein Quadrat ist, es ist also zu zeigen: = .

22

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

” g f W¨ ahle k = 1 und h = c (beides konstante Polynome in F p [X]). Es ist X − b = X − a + c 2 ⇔ a − b = c 2 , und das ist in F p , fertig. Das heißt, dass es mindestens ein k und ein h in F p [X] gibt, so dass in F p gilt: g = kf + h 2 . g ⇒“: Vor.: = 1, es gibt also k, h ∈ F p [X] mit g = k · f + h 2 .

” = 1, d.h. es gilt a−b = l·p+c 2 bzw. gibt es ein c mit a−b = c 2 in F p .

n m

Seien h = Also ist = k · f + h 2 g X − b = (d m (X − a) m + . . . + d 0 )(X − a) + (c n (X − a) n + . . . + c 0 ) 2 ,

k h und das gilt in F p [X]. Jetzt X = a einsetzen: a − b = 0 + c 2 und das gilt in F p .

f b−a

Ebenso gilt Es ist nach Korollar 3.6 Außerdem gilt = 1 gilt, dann ist −(a − b) 2 ein Quadrat in F p Das heißt also, wenn p und das ist genau dann der Fall, wenn die −1 ein Quadrat in F p ist. Und das −1 gilt genau dann, wenn p Nach dem Euler’schen Kriterium ist

−1

p−1

3.3.2 Quadratische Polynome

Nun wird ein konkretes Beispiel f¨ ur Polynome zweiten Grades aus F 5 [X] durch- gerechnet. Dazu w¨ ahlen wir g = X 2 + 2X − 1 und f = X 2 + X + 2, beide sind

23

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

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

Zuerst konzentriert man sich auf f Symbol 1 oder −1 ergibt, muss man pr¨ ufen, ob g modulo f quadratisch ist oder nicht. Also:

1 falls g Quadrat in F 5 [X]/(f ) ist.

g

g Es l¨ asst sich F 5 [X]/(f ) beinhaltet alle Restklassen modulo f . Der Erweiterungsk¨ orper F 25 von F 5 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 5 grad(f ) = 5 2 Elemente und ist isomorph zu F 5 [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 F 5 [X]/(f ) dasselbe gemacht werden soll, sieht die Abbildung dann so aus:

∼ = F 5 [X]/(f ) −→ F 25 = F 5 (ω) −→ g(α) ¯ g α beliebige NST von f Sei m ein irreduzibles Polynom zweiten Grades in F 5 [X], z.B. m = X 2 − 3. Unter der Voraussetzung, dass m in einem Erweiterungsk¨ orper eine Nullstelle √

3 hat, adjungieren wir ω zu F 5 dazu und erhalten somit ein Modell von

ω = F 25 :

2

F 25 =

= {λ 1 + λ 2 ω|λ 1 , λ 2 ∈ F 5 } mit ω 2 = 3 = −2 in F 5 Hierin befinden sich 5 2 Elemente (in Abh¨ angigkeit von ω). Die Quadrate sind die 12-ten Einheitswurzeln 4 ( 25−1

y 2 |y ∈ F ×

25 = F 25 \{0}

Q F 25 = = {1, −1, 2, −2, 2 + ω, 2 − ω, −2 + ω, −2 − ω, 1 + 2ω, 1 − 2ω, −1 + 2ω, −1 − 2ω} .

4 siehe auch Tabelle auf Seite 33.

24

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

Die Nullstellen α 1 und α 2 von f werden mit der quadratischen L¨ osungsformel √ √ −7 berechnet, es folgt also aus X 2 + X + 2 = 0, dass α 1,2 = −1±

√ (in F 5 gerechnet!). W¨ ahle α = 2 + 3

von f in F 25 .

Jetzt bleibt noch g(α) auszurechnen und zu pr¨ ufen, ob das Ergebnis ein Qua-

drat ist.

+4 + 6ω − 1 = 34 + 18ω = −1 − 2ω ∈ Q F 25 g(α) = g(2 + 3ω) = 4 + 12ω + 9ω 2

g

Das Legendre-Symbol

Dasselbe macht man jetzt noch mit

Nullstellen von g:

X 2 + 2X − 1 = 0 ⇔ β 1,2 = −2±

2 von g in F 25 .

−1−2ω+2 = 14+2ω = −1 + 2ω f (β) = β 2 +β+2 = f (−1−2ω) = 1+4ω+ 4ω 2

∈Q F 25

⇒

5 2 −1 · 5 2 −1 5 2 −1 g f

⇒

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 = ¯ b 2 in F q [X]/(f )

und sich nach dem Euler’schen Kriterium folgendermaßen berechnen l¨ asst 5 :

5 siehe Definition 3.4 und Satz 3.5

25

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

Wir interessieren uns hier also f¨ ur die quadratischen Restklassen in F q [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 ∈ F q [X] ein irreduzibles normiertes Poly- nom mit grad(f ) = e. Nun sehen wir uns den Restklassenring F q [X]/(f ) an. Nach Satz 2.3 und Korollar 2.7 ist bekannt, dass F q [X]/(f ) endlicher K¨ orper mit q e Elementen ist und nach Korollar 2.2 ist seine multiplikative Gruppe F q [X]/(f ) × zyklisch der Ordnung q e − 1. Es gilt also ¯ a q e = ¯ a f¨ ur alle Restklas- a ∈ F q [X]/(f ). Die Einheitengruppe l¨ asst sich folgendermaßen schreiben: sen ¯ F q [X]/(f ) × = a ∈ F q [X]/(f )|¯ a q e −1 = 1 a ∈ F q [X]/(f ).

wobei ¯ Satz 3.7 (Quadratisches Reziprozit¨ atsgesetz) Seien f, g ∈ F q [X] irredu- zibel ¨ uber diesem K¨ orper, normiert und verschieden, grad(g) = d und grad(f ) = e. Dann gilt:

Beweis:

Nach Satz 2.6 ist F q [X]/(f ) isomorph zu F q (α) = F q e und ∼ = Φ : F q [X]/(f ) −→ F q e

¯ a 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 F q e ist, anstatt in F q [X]/(f ) mit ¯ g zu rechnen.

Das Polynom f kann in F q e als Produkt seiner Linearfaktoren geschrieben werden:

e−1 (X − α q k ) = (X − α) · (X − α q ) · (X − α q 2 ) · . . . · (X − α q e−1 ), f (X) = k=0 denn wenn α eine Nullstelle von f ist, dann auch α q k , wobei nach Satz 2.16

0 ≤ k < grad(f ) = e gilt.

g in F q [X]/(f ) zu betrachten, ersetzt Anstatt jetzt das Legendre-Symbol f Hasse das irreduzible Polynom f durch einen seiner Linearfaktoren und sieht g in F q e [X]/(X −α) an. Nach dem Euler’schen Kriterium sich das Symbol X−α ist das

26

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

g und X − α sind beides Polynome in F q e [X] mit Koeffizienten aus F q e ⊃ F q . Da grad(X − α)=1, ist die Nullstelle α ∈ F q e , somit braucht man F q e nicht zu erweitern, denn F q e [X]/(X − α) ∼ = F (q e ) 1 . g als Kongruenz in F q e [X]/(X − α) schrei-

Nun kann man auch das Symbol ben, n¨ amlich so: und zwar, weil das Euler’sche Kriterium, welches ja als g definiert ist, von f ist, kann das auch in der Form f werden, woraus obige Kongruenz folgt. Das wiederum bedeutet, dass man die beiden Symbole gleichsetzen kann:

Dann n¨ amlich konzentriert man sich einfach auf X−α dem Euler’schen Kriterium. Wie oben schon angedeutet, interessieren wir uns f¨ ur g(α). Im Folgenden wird in F q e gerechnet: g q e −1

(Potenzgesetz)

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(α) q k = g(α q k ): d q k b i α i q k

g(α) q k = Wir haben jetzt also: q−1 e−1

wobei α, α q , . . . , α q e−1 die Nullstellen von f sind.

27

3 DAS QUADRATISCHE REZIPROZITATSGESETZ

g sei jetzt auch ein irreduzibles normiertes Polynom aus F q [X] und es sieht zerlegt in seine Linearfaktoren in F q d so aus:

d−1

(X − β q j ) = (X − β) · (X − β q ) · (X − β q 2 ) · . . . · (X − β q d−1 ) g(X) = j=0

Dann hat man

d−1

e−1 e−1 g

Bei Vertauschung von f mit g ¨ andert sich die rechte Seite nur um den Faktor (−1) e·d· q−1

2 :

d−1 d−1 e−1 e−1

Daraus folgt das quadratische Reziprozit¨ atsgesetz:

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

χ(g 1 · g 2 ) = χ(g 1 ) · χ(g 2 )

⇒ χ(g 1 · . . . · g n ) = χ(g 1 ) · . . . · χ(g n )

⇒ χ(g n )

= χ(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 ˆ G n ⊂ ˆ

χ n = 1 nennt man die n-ten Charaktere.

G = Hom(F × q , F × Satz 4.3 Die Charaktergruppe ˆ

q − 1.

29

4 DAS ALLGEMEINE REZIPROZITATSGESETZ

Beweis:

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

Hom(F × q , F × q ) ist mit der Multiplikation aus Definition 4.1 abelsche Gruppe, neutrales Element ist die Abbildung χ(g) = 1 f¨ ur alle g ∈ F × q . F¨ ur b := a e ist χ(b) = χ e (a), also ist χ durch χ(a) eindeutig bestimmt.

Betrachte die Abbildung

Hom(F × q , F × q ) −→ F × α :

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 × q , F × χ 1 = χ 2 , dass χ 1 (a) = χ 2 (a) ist.

Außerdem ist a ∈ Bild(α), denn a = α(id). F¨ ur b := a e ist (mit der Multipli- kation aus Definition 4.1) b = α(id e ). Damit sind dann auch alle Potenzen von a im Bild(α) enthalten und Bild(α) = F × q .

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

#F × q = q − 1.

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 × q und K = F q und interessieren uns f¨ ur

die Untergruppe der Quadrate. In ˆ ∈ {−1, 1}. Die eine H¨ alfte der Elemente aus F × darunter χ(g) = g 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 ×

7 = 3 = {1 = 3 6 , 2 = 3 2 , 3 = 3 1 , 4 = 3 4 , 5 = 3 5 , 6 = 3 3 }.

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

7 entnehmen:

χ(3) eindeutig bestimmt.

Der erste (triviale) Charakter χ ist das Einselement, n¨ amlich χ(a) = 1 f¨ ur alle a in F ×

7 . Es ist a 7−1 = 1 (wobei sich jedes a als Potenz von 3 schreiben l¨ 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 ×

7 , siehe oben.

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 × 7 , F ×

7 ) gilt χ 3 = 1 ⇔ χ(3) 3 = 1 ⇔

χ 3 (3) ∈ ∈3 3 .

In F q 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 F q [X] irreduzibel, normiert und verschieden ∈ (f ) sowie n ein Teiler von q−1. Sei χ ∈ Hom(F q [X]/(f ) × , F q [X]/(f ) × ). und g / Das Legendre-Symbol ist definiert durch:

· χ = Das ist ein n-ter Charakter in Hom(F q [X]/(f ) × , F q [X]/(f ) × ). Das Bild von χ ist die Menge der n-ten Einheitswurzeln in F q [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 6 vergleiche hierzu Satz 3.5

31

4 DAS ALLGEMEINE REZIPROZITATSGESETZ

∈ Hom(F q [X]/(f ) × , F × f n n-ter Charakter.

g

Beweis:

q e −1

Es ist erst zu zeigen, dass eine n-te Einheitswurzel in F q [X]/(f ) × ist, ist es eine Nullstelle von Weil ¯ g n X n − 1. Und da F × q zyklisch ist und n ein Teiler von q − 1, sind alle Nullstellen q e −1 von X n − 1 schon in F × q enthalten. Also ist ¯ g eine n-te Einheitswurzel in F × q .

Es gilt f¨ ur g, h ∈ F q [X] wegen der Homomorphie-Eigenschaft:

(analog zu Korollar 3.6) f¨ ur beliebige Potenzen n, die q − 1 teilen.

q e −1

Sei nun b ein Erzeuger von F q [X]/(f ) × , dann gilt ord(b χ(b) = b ter. Da c := χ(b) ein Erzeuger von F × j ∈ N. F¨ ur a ∈ F q [X]/(f ) ist dann χ (a) = χ (b k ) = oben gezeigt, ist χ (b) eine n-te Einheitswurzel in F ×

χ (a) = (c j ) k = χ(b) jk = χ(b k ) j = χ(a) j .

· Also ist χ = ein erzeugender n-ter Charakter. f n

· ∈ F q l¨ asst sich die Multiplikation zweier Charaktere durchf¨ uhren, Wegen f n und es gilt das allgemeine Reziprozit¨ atsgesetz

Der Beweis hierzu l¨ asst sich genauso durchf¨ uhren, wie der des quadratischen Falls in Abschnitt 3.4. 7 7 siehe auch [1], S. 95ff.

32

√ F ×

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.

g wird hier nicht im endlichen K¨ orper F p n , sondern Das Legendre-Symbol f in F p = Z/pZ berechnet. Als erstes muss das irreduzible Polynom aus F p [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 F p ). 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 F p [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 F p ), 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

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

using namespace std;

#include

struct polynom{

int grad;

double *koeff;

};

struct polynomfeld{

int anzahl;

int ausgangsgrad;

int prim;

polynom *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)

{ polynomfeld rueckgabe;

rueckgabe.anzahl=n;

rueckgabe.ausgangsgrad=m;

rueckgabe.prim=p;

rueckgabe.polynome=new polynom [n]; for(int i=0;i

}

void freepolynom(polynom freigabe) { delete [] freigabe.koeff;

}

35

void freepolynomfeld(polynomfeld freigabe) { for(int i=0;i

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 "<>eingabe.koeff[i]; cout<

} 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^"<

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<

36

else if(test==0||i==ausgabe.grad) { if(ausgabe.koeff[i]!=0)os<

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

} os<

return os;

}

ostream & operator <<(ostream & os, polynomfeld ausgabe) { for(int i=0;i

return os;

}

void setkoeff(polynomfeld eingang) { int k=0;

int schreib;

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

for(int j=0;j

37

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

38

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

} 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

{ return -1;

} for(int j=0;j

} 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

40

for(int k=0;k

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

}

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<

polynom A=createpolynom(n);

cin>>A; //*** Operator f¨ ur die Eingabe eines cout<<"Das erste Polynom lautet: "; // Polynoms wird aufgerufen *** cout<>prim;

polynomfeld B=restklassen(A,prim); //*** erstellt die Restklassen // von f *** cout<

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

polynomfeld C=quadrat(B); //*** erstellt die Quadrate

41

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

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

cout<

polynom G=createpolynom(m); cin>>G;

cout<

cout<<"Das zweite Polynom lautet: "; cout<

ergebnis=vergleichen(Rest,C); //*** ergebnis ist in {+1,-1} *** } else { cout<<"0, ";

ergebnis=0;

} cout<

if(ergebnis==1) { cout<<"Dieser Rest ist in der Menge der Quadrate von f "<

freepolynom(Rest);

freepolynomfeld(B);

freepolynomfeld(C);

freepolynomfeld(D);

return 0;

}

42

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