K07 Endliche Körper

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.