K07 Endliche Körper
Ringe und (insbesondere endliche) Körper
K07_Körper.txt
—
Plain Text,
8 KB (8278 bytes)
Dateiinhalt
Persönliche Notizen zur Vorbereitung der LDS Vorlesung. Diese Notizen waren ursprünglich nicht zur Herausgabe gedacht und sind entsprechend mit Vorsicht zu genießen. Es wird dringend empfohlen, dass Buch zu verwenden: Angelika Steger: Diskrete Strukturen. Band 1: Kombinatorik, Graphentheorie, Algebra. 2. Auflage, Springer 2007, 978-3-540-46660-4 ============================================ Algebraische Strukturen (Buch Kapitel 5.4) ============================================ Definition: Ring Ein Ring ist eine algebraische Struktur R=(R,⊕,⊙) mit Signatur (2,2) und: R1) (R,⊕) ist kommutative Gruppe mit neutralem Element 0 R2) (R,⊙) ist ein Monoid mit neutralem Element 1 R3) a⊙(b⊕c) = (a⊙b)⊕(a⊙c) für alle a,b,c∈R (Distributivgesetz) (b⊕c)⊙a = (b⊙a)⊕(c⊙a) für alle a,b,c∈R (Distributivgesetz) Falls das Monoid kommutativ ist, so spricht man von einem kommutativen Ring. Beispiele für Ringe: ① (ℤ,+,∙) ② Ring der Polynome ℚ[x]: Alle Folgen (aᵢ)_i∈ℕ mit aᵢ∈ℚ, interpretiert als a₀+Σaᵢ∙xⁱ (Polynome in einer Variablen mit Koeffizienten aus ℚ) Definition: Körper Ein Körper (engl. field) ist eine algebraische Struktur K=(K,⊕,⊙) mit Signatur (2,2) und: K1) (K,⊕) ist kommutative Gruppe mit neutralem Element 0 K2) (K,⊙) ist kommutatives Monoid mit neutralem Element 1, welche als Unterstruktur die kommutative Gruppe (K\{0},⊙) besitzt K3) a⊙(b⊕c) = (a⊙b)⊕(a⊙c) für alle a,b,c∈K (Distributivgesetz) Bemerkung: Unterschied zwischen Ring und Körper ist die Existenz multiplikativer Inverse. Ring-Beispiele, welche keine Körper sind: ① Keine Inversen zu ∙ in (ℤ,+∙), da z.B. 3 kein multiplikatives Inverses besitzt (1/3∉ℤ). ② Jedes nicht-konstante Polynom wie etwa p(x)=x hat kein multiplikatives Inverses in ℚ[x]. (Allerdings bildet ℚ(x) einen Körper: der Körper der rationalen Ausdrücke in einer Variablen x: p(x)/q(x) mit p,q∈ℚ[x] und q≠0) Bemerkung: Anstatt ℚ kann man einen beliebigen Körper K verwenden. Abkürzende Notationen für n∈ℕ und x,y∈K: x+y ≝ x⊕y x∙y ≝ x⊙y (oft auch nur xy) x-y ≝ x+(-y) n∙x ≝ x+x+…+x (n-mal) -n∙x ≝ -(n∙x) xⁿ ≝ x∙x∙…∙x (n-mal) x⁽⁻ⁿ⁾ ≝ (xⁿ)⁻¹ = (x⁻¹)ⁿ (nach Lemma aus K06) HINWEIS: Potenzgesetze gelten damit noch nicht allgemein, nur als abkürzende Schreibweise eingeführt; ansonsten Beweis erforderlich! Spezialfälle: x⁰≝1, 0⊙x=0 In Körpern gelten die üblichen algebraischen Rechenregeln, z.B. Ausmultiplizieren, Ausklammern, etc. Beispiel: (x+y)∙(x-y) = (x+y)∙x - (x+y)∙y = x∙x+y∙x-x∙y-y∙y = x²+y² Lemma: In jedem Körper K gilt 1) a∙0=0 2) a∙b=0 ⇒ a=0 ∨ b=0 Beweis: 1) a∙0 =(0 neutral zu +)= a∙(0+0) =(Distributivgesetz)= a∙0+a∙0 Also auch a∙0+0 = a∙0+a∙0 und mit der Kürzungsregel für kommutative Gruppen (aus K06) folgt 0=a∙0, 2) Annahme a≠0 (sonst trivial). Dann gibt es a⁻¹ und es gilt b=(a⁻¹∙a)∙b=a⁻¹∙(a∙b)=a⁻¹∙0=0 □ Beispiele für Körper: ③ ℝ,ℚ,ℂ sind Körper mit den üblichen Operationen +,∙ ④ K={a,b} mit ⊕|a b ⊙|a b -+---- -+--- a|a b a|a a b|b a b|a b Es gilt 0=a, 1=b; Inverse: -a=a,-b=b,b⁻¹=b (Da a die Null ist, gibt es a⁻¹ nicht.) Assoziativ-, Kommutativ- und Distributivgesetz verbleiben als Übung. (Hinweis: Dieser Körper ist Isomorph zu ℤ₂) Bemerkung: Man kann Polynomringe über beliebige Körper erhalten: Z.B. gilt (x+1)(x+1)=x²+1 in ℤ₂[x], denn x²+x+x+1=x²+(1+1)∙x+1=x²+1 ⑤ Ein endlicher Körper mit 4 Elementen: ⊕|0 1 a b ⊙|0 1 a b -+-------- -+------- 0|0 1 a b 0|0 0 0 0 1|1 0 b a 1|0 1 a b a|a b 0 1 a|0 a b 1 b|b a 1 0 b|0 b 1 a Existenz von Inversen: -0=0, -1=1, -a=a, -b=b 1⁻¹=1, a⁻¹=b, b⁻¹=a Gesetze sind noch zu prüfen! Definition: Für einen beliebigen Körper K heißt p(x)∈K[x] _irreduzibel_, falls aus für alle q(x)∈K[x] q(x)|p(x) schon q=1 oder q=p folgt. Beispiel: x²+1 irreduzibel in ℝ[x]; aber nicht in ℤ₂[x], denn x²+1=(x+1)² in ℤ₂[x]; aber nicht in ℂ[x], denn x²+1=(x+i)∙(x-i); Lemma: Für ein irreduzibles p∈K[x] ist K[x]/p ein Körper. Dabei sind K[x]/p die "Polynome modulo p", d.h. zwei Polynome gelten als gleich, wenn sie sich nur um ein Vielfaches von p unterscheiden (also p|a-b bzw. a(x)=b(x) (mod p(x))). Addition und Multiplikation werden in K[x]/p einfach modulo p ausgeführt; additive Inverse bleiben unverändert; das multiplikative Inverse für q≠0 berechnet man mit Hilfe des erweiterten Euklidischen Algorithmus: dieser liefert s(x),t(x)∈K[x] mit 1=s(x)∙p(x)+t(x)∙q(x), denn es muss ggT(q,p)=1 gelten (ansonsten gilt q≡0 mod p falls p|q), damit ist t(x) das gesuchte Inverse. Beispiele: * ℝ[x]/(x²+1) ist ein Körper. In diesem gilt x²=-1, denn x²≡-1 mod x²+1. Alle Element von ℝ[x]/(x²+1) haben die Form α+β∙x für α,β∈ℝ. Rechenregeln: (α₁+β₁x)+(α₂+β₂x)=(α₁+α₂)+(β₁+β₂)x (α₁+β₁x)∙(α₂+β₂x)=(α₁∙α₂)+(α₁∙β₂+α₂∙β₁)x+(β₁∙β₂)x² ≡(α₁∙α₂-β₁∙β₂)+(α₁∙β₂+α₂∙β₁)x Tatsächlich ist ℝ[x]/(x²+1) ist ismorph zu ℂ * Der Körper aus ⑤ ist isomorph zu ℤ₂[x]/(x²+x+1), d.h. x²≡-x-1=x+1 (mod x²+x+1, mod 2), also a entspricht x und b entspricht 1+x Z.B. gilt a∙b=x(1+x)=x+x²=x+x+1=1 * ℚ[x]/(x²-3) ≃ {α+β√3|α,β∈ℚ} Division (α+β√3)⁻¹=(α²-3β³)(α-β√3) (mit erw.Eukl.Alg. oder direkt) Weitere Beispiele für endliche Körper * ℤₚ ist ein Körper für p prim (ganze Zahlen modulo p); damit existieren multiplikative Inverse, da alle teilerfremd zu p. Für n nicht prim ist ℤₙ kein Körper, denn wenn n=a∙b und a,b∉{1,n} dann hat a kein Inverses. Außerdem gilt in ℤₙ: a∙b=0, in einem Körper nicht gelten kann (siehe Lemma am Anfang). Beispiel: ℤ₃ +| 0 1 2 ∙| 0 1 2 -+------- -+------ 0| 0 1 2 0| 0 0 0 1| 1 2 0 1| 0 1 2 2| 2 0 1 2| 0 2 1 Definition: Charakteristik Für einen Körper K ist die Charakteristik von K, geschrieben char(K), definiert als ord(1) 1 in (K,⊕) falls <∞, sonst char(K)=0. Falls K ein endlicher Körper ist, so muss ord(1)≠∞ sein. Erinnerung: Die Ordnung von 1 in der Gruppe (K,⊕) ist die kleinste natürliche Zahl n mit n∙1=1+…+1(n-mal)=0. Beispiele: * char(ℚ)=chat(ℝ)=char(ℂ)=0 * char(ℤₚ)=p (für p prim) * char(ℤ₂[x]/(x²+x+1))=2 (da 1+1=0) Satz: Ist char(K)≠0, so bildet {t∙1|0≤t<char(K)} einen (Unter-)Körper welcher isomorph zu ℤ_char(K) ist. Deshalb muss die Charakteristik ≠0 immer eine Primzahl sein. Diesen Körper bezeichnet man als den Primkörper von K. Beispiel: Es gibt keinen Körper K mit char(K)=6, sonst wäre 6∙1=1+1+1+1+1+1=0 in K, aber 1+1≠0 und 1+1+1≠0. Aber (1+1)∙(1+1+1)=1∙1+1∙1+1∙1+1∙1+1∙1+1∙1=0. Dies widerspricht dem Lemma am Anfang, welches besagt das (1+1)=0 oder (1+1+1)=0 gelten muss, wenn das Produkt 0 ist. Beweisskizze: Allgemein ist für t∈ℤ_char(K) die Abbildung t↦t∙1 ein Isomorphismus. Jeder endliche Körper mit endlicher Charakteristik ist ein Vektorraum über seinem Primkörper ℤ_char(K), daher gilt |K|=char(K)ⁿ wobei n die Dimension des Vektorraums ist. Daraus folgt, dass die Kardinalität jedes _endlichen_ Körpers eine Primzahlpotenz sein muss. Satz: Zu jeder Primzahlpotenz q=pⁿ gibt es einen Körper mit dieser Kardinalität und dieser ist bis auf Isomorphie eindeutig bestimmt! Dieser eindeutige Körper wird als GF(q) bezeichnet. (GF: "Galois-Field" nach Évariste Galois, 1811–31). Endliche Körper spielen z.B. in der Codierungstheorie eine wichtige Rolle, siehe Buch von A.Steger für ein ausführliches Beispiel.
Artikelaktionen