====================================
 Polynome über einer Veränderlichen
====================================

Def.: Ein Polynom über einer Variablen x ist ein Term
  mit +,∙, reelen Konstanten und dieser Variablen.
  
Bsp.: p(x) = x+(x²-5)-(x³-7)

Zwei Polynome sind _gleich_, wenn sie mit den üblichen 
Rechenregeln ineinander überführt werden können.
(z.B. Distributivgesetz, Assozitivgesetz, etc.)

Bsp.: x+(x²-5)-(x³-7) = x⁵-5x³-7x²+x-35 
 (Zwei verschiedene Repräsentanten der gleichen Äquivalenzklasse.)

Polynome lassen sich miteinander addieren und multiplizieren.

Def.: _Polynomfunktion_: Jedes Polynom p(x) definiert eine Abbildung fₚ:ℝ→ℝ
  mit fₚ(x)=p(x) durch Einsetzen und ausrechnen.
Bsp.: fₚ(7)=  14721

NB.: p und fₚ sind nicht dasselbe: p ist _ein_ Repräsentant der Äquivalenzklasse, während fₚ eine Funktion ist.
  Es gilt aber, dass aus fₚ=fₕ schon p=h folgt.
  In die Funktion können nur reele Zahlen eingesetzt werden, 
  aber ins Polynom könnte man auch eine Matrix oder Terme einsetzen.
  
Def.: Normalform & Grad eines Polynoms
  Jedes Polynom p(x) kann geschrieben werden in der Form 
    p(x)= aₙ∙x^n + a_(n-1)∙x^(n-1) + … + a₁∙x¹ + a₀
  mit n∈N und aₙ,…,a₀ Konstanten, aₙ≠0. 
  (Meist aᵢ∈ℝ, aber ℚ,ℂ,ℤₙ, etc. auch möglich)
  
  Die aᵢ heißen _Koeffizienten.
  
  n ist der Grad des Polynoms p, geschrieben grad(p)=n (engl. deg(p)).
  Konstante Polynome p(x)=a₀ mit a₀≠0 haben Grad 0.  
  Der Grad des Nullpolynoms p(x)=0 bleibt oft undefiniert oder wird als -1 definiert.
    
Berechnung der Normalform durch ausmultiplizieren und sortieren der Potenzen.

Lemma:
  grad(p∙q)=grad(p)+grad(q)      (falls p,q≠0)
  grad(p+q)≤max(grad(p),grad(q))

Bsp.:  
  a(x)=x²-3x+5, b(x)=4x+2
  grad(a)=2, grad(b)=1, 
  grad(a∙b)=grad(4x³-10x²+14x+10)=3
  grad(a+b)=grad(x²+x+7)=2
  
  c(x)=x²-3x+5, d(x)=-x²+4x+2
  grad(c)=2, grad(d)=2, 
  grad(c∙d)=grad(-x⁴+7x³-15x²+14x+10)=4
  grad(c+d)=grad(x+7)=1
  
Satz(Polynomdivision):
  Zwei Polynome a,b gegeben mit b≠0, dann
  gibt es eindeutige bestimmte Polynome q,r mit 
    a=q∙b+r 
  und grad(r) < grad(b) (oder r=0)
  
Beweis: 
  Existenz durch Algorithmus (bekannt aus der Schule)
  Eindeutigkeit: Angenommen a=t₁∙b+r₂ und a=t₂∙b+r₂
  mit grad(r₁)<grad(b) und grad(r₂)<grad(b)  
  Es gilt 0 = (a-a) = (t₁-t₂)∙b+(r₁-r₂) also auch 
  (t₁-t₂)∙b = r₂-r₁
  Falls (t₁-t₂)≠0 dann wäre aber wegen 
  grad(r₁)<grad(b) und grad(r₂)<grad(b)  
  auch grad((t₁-t₂)∙b) ≩ grad(r₂-r₁);
  dies wäre ein Widerspruch, also t₁=t₂ und r₁=r₂.
  □
Beispiel:
  a(x)=2x⁴+x³+x+3
  b(x)=x²+x-1
  
  2x⁴+ x³    +x+3 : x²+x-1 = 2x²-x+3
-(2x⁴+2x³-2x²)
      -x³+2x²+x+3
    -(-x³- x²+x)
          3x²  +3
        -(3x²+3x-3)
            -3x+6

Es gilt also a = (2x²-x+3)∙b + (-3x+6)
                  = q            = r
mit grad(r)=1<2=grad(b).

Teilbarkeit, ggT, erweiterte Euklidischer Algorithmus können ganz analog für Polynome definiert werden.

Def.(Nullstellen von Polynomen):
Eine Zahl α mit fₚ(α)=0 (bzw. p(α)=0), also α eine Nullstelle
der Polynomfunktion, heißt Nullstelle des Polynoms p.

Lemma:
  Ist α eine Nullstelle von p≠0, so gibt es q mit grad(q)=grad(p)-1
  und p(x)=(x-α)∙q(x).
Beweis:
  Schreibe mit Polynomdivision
    p(x)=q(x)∙(x-α)+r(x) 
  mit grad(x-α)=1. Wegen grad(r)=0 ist r ein konstantes Polynom,
  also r(x)=c für ein c. 
  Wegen 0=p(α)=q(α)∙(α-α)+c=c folgt c=0, also gilt r(x)=0
  und damit die Behauptung.
  □              
Satz:
  Ein Polynom p≠0 mit grad(p)=n hat höchstens n Nullstellen.
Beweis:
  Durch Induktion über n.
  Für n=0 ist p konstant. Wegen p≠0 gibt es keine Nullstelle.  
  Gelte die Behauptung für ein festes aber beliebiges n₀ und
  sei grad(p)=n₀+1.
  Wenn p keine Nullstelle hat, so folgt die Behauptung trivialerweise.
  Sonst sei α eine Nullstelle von p. Schreibe
    p(x)=q(x)∙(x-α) mit grad(q)=n₀
  Für jede Nullstelle β von p mit β≠α muss gelten q(β)=0.
  Also gibt es nach Induktionshypothese höchstens n₀ solche β,
  α ist eine weitere Nullstelle, also insgesamt höchstens n₀+1 Nullstellen.
  □
Beispiele:
  x²-2x+1 hat eine Nullstelle, nämlich 1 (doppelt)
  x²-1    hat zwei Nullstelle, nämlich 1, -1
  x²+1    hat keine Nullstellen in R (in C: i,-i)

Nullstellen können mehrfach vorkommen.

Fundamentalsatz der Algebra:
Jedes Polynom p mit p≠0 und grad(p)=n hat 
in den komplexen Zahlen n Nullstellen.
  
  
========================= 
Ende Vorlesung 24.05.2016  
  
=========================
 Algebraische Strukturen
=========================

Anstatt Teilbarkeit, ggT, etc. immer wieder zu Wiederholen
suchen wir nun verallgemeinerte Strukturen. Wenn ein Beweis auf 
einer verallgemeinerten, abstrakten Struktur möglich ist,
dann gilt dieser Beweis gleich auch für alle spezielleren Strukturen,
welche zu der verallgemeinerten Struktur passen.

Def.: Eine _Signatur_ ist eine Liste von natürlichen Zahlen,
  welche die Stelligkeiten von _Operationen_ angibt.
  Operationen mit Stelligkeit 0 sind Konstanten.
  
Def.: Eine Algebra (A,f₁,…,fₖ) zur Signatur σ=(m₁,…,mₖ) besteht aus
einer Menge A und Operationen  fᵢ mit Stelligkeit mᵢ, d.h.
fᵢ: A×…×A→A, auch geschrieben fᵢ:A^(mᵢ)→A,
d.h. eine Abbildung von mᵢ-vielen Argumenten aus A auf ein A.

Meist wird in der Sprechweise nicht mehr zwischen
der Menge D und der zugehörigen Algebra ⅅ=(D,f₁,…,fₖ) unterschieden.
Manchmal wird die Grundmenge D auch |ⅅ| geschrieben, oder als Trägermenge bezeichnet.

Beispiele: 
  ({⊥,⊤},∧,∨,¬) hat Signatur (2,2,1)
  (ℕ,min,max)   hat Signatur (2,2)
  (ℝ,+,0)       hat Signatur (2,0)
  (ℝ,f₁(x,y)=0,f₂(x,y)=x²-y,f₃()=42) hat auch Signatur (2,2,0)
  
Achtung: Operationen dürfen nicht aus Menge herausführen! (Wertebreich=A)
              
Def.: Sei A Algebra mit (u.a.) einer 2-stelligen Operation ○ als Infix.
  Ein Element a∈A ist _links-neutral_,  falls für alle x∈A gilt a○x=x
  Ein Element a∈A ist _rechts-neutral_, falls für alle x∈A gilt x○a=x
  Ein Element a∈A heisst _neutral_ bezüglich ○, falls a sowohl
  links-neutral als auch rechts-neutral ist.  
  
Lemma: Falls es in Algebra A zu einer 2-stelligen Operation ○ ein 
  links-neutrales Element a und ein rechts-neutrales Element b, 
  dann muss a=b gelten.
Beweis:
  a○b=b, da a links-neutral  ist.
  a○b=a, da b rechts-neutral ist.
  Also folgt a=a○b=b.
  □
Korollar: Neutrale Elemente sind eindeutig, d.h. 
  falls a und b neutral, dann folgt a=b.
  
Beispiele:
  ⊤ ist neutral bezüglich ∧
  ⊥ ist neutral bezüglich ∨
  0 ist neutral bezüglich +
  1 ist neutral bezüglich ∙
  0 ist neutral bezüglich max in Algebra (ℕ,min,max) 
    aber min hat in dieser Algebra kein neutrales Element 

Beispiel:
  Verbände kann man alternativ auch als Algebren mit zwei zweistelligen Operation ⊓ (Infimum) und ⊔ (Supremum) definieren,
  welche den Gesetzen für Assoziativität, Kommutativität und Absorption genügen (in Vorlesung war Relation ⊑ grundlegend
  gewählt worden, doch eine Relation ist keine Operation).    
    
Def.: Eine zweistellige Operation ○ einer Algebra A heisst _assoziativ_, 
  falls für alle x,y,z∈A gilt x○(y○z)=(x○y)○z.
  
Für assoziative Operationen eignet sich die Infix-Notation, 
denn man kann einfach die Klammern weglassen und x○y○z schreiben.
(Wir setzen im Folgenden Klammern nur zur Verdeutlichung der Beweiskonstruktion.)

Def.(Halbgruppe):
  Eine algebraische Struktur mit einer zweistelligen assoziativen Operation ○ heisst _Halbgruppe_.

Def.(Monoid):
  Eine Halbgruppe mit einem neutralen Element e heisst _Monoid_.
  (oft auch "Halbgruppe mit Eins" genannt; da das neutrale Element oft mit 1 bezeichnet wird) 

Oft wird das neutrale Element in der Signatur aufgeführt, z.B. (ℤₙ,∙,1) mit Signatur (2,0),
man muss es aber auch nicht angeben, da es nach obigen Lemma ja eindeutig sein muss; man kann es also berechnen.
  
Def.: Ist M ein Monoid und a∈M so heisst x∈M _rechtsinvers_zu_a_ falls
  a○x=1. Analog: y∈M _Linksinverses_zu_a_ falls y○a=1.
  Ein z∈M heist _Inverses_zu_a_ falls z rechts- und linksinvers zu a ist. 
  
Lemma: Hat a ein Rechtsinverses x und ein Linksinverses y, so ist x=y.
Beweis: Es gilt x=1○x=(y○a)○x=y○(a○x)=y○1=y □

Aus dem Lemma folgt sofort, dass Inverse eindeutig sind, daher bezeichnet man das Inverse von a oft auch mit a^(-1).

Beispiel: Sei A eine Menge und M die Menge aller Abbildungen f:A→A. 
Eine zweistellige Operation ○ auf M ist definiert durch (f○g)(x)=f(g(x)), also Komposition für f,g∈M.
Man kann nachrechnen, dass (M,○) eine Halbgruppe ist. Weiterhin ist die Identitätsfunktion id(x)=x 
das neutrale Element zu ○, d.h. (M,○,id) ist ein Monoid. 
Es gilt: Ist f∈M injektiv, so hat f ein Linksinverses. 
         Ist f∈M surjektiv, so hat f ein Rechtsinverses.
         Ist f∈M bijektiv, so hat f ein Inverses. 
Zum Beispiel:
  A=ℕ, M=ℕ→ℕ, f(x)=⌊x/2⌋ ist surjektiv aber nicht injektiv, g(x)=2x ist injektiv aber nicht surjektiv
  g ist Rechtsinverses zu f, f ist Linksinverses zu g.         
         
Def.(Unterstruktur):
  Für Algebra A=(A,f₁,…,fₙ) mit Signatur σ=(m₁,…,mₙ) dann ist eine
  Teilmenge U⊆A eine Unterstruktur von A, falls U unter den Operationen
  _abgeschlossen_ ist, d.h. 
  für alle i∈{1,…,n} und alle u₁,…,u_mₖ∈U gilt fᵢ(u₁,…,u_mᵢ)∈U.
  Man schreibt auch fᵢ|U für "fᵢ eingeschränkt auf U".
  (U,f₁|U,…,fₙ|U) ist dann insbesondere auch eine algebraische Struktur.
  
Beispiele: 
  ① (ℕ,+) ist Unterstruktur von (ℤ,+)
  ② ({2n|n∈ℕ},+) ist Unterstruktur von (ℕ,+),
  aber ({2n+1|n∈ℕ},+) ist keine Unterstruktur von (ℕ,+).

Def.(Homomorphismus):
  Für Algebren (A,f₁,…,fₙ) und (B,g₁,…,gₙ) mit gleicher Signatur σ=(m₁,…,mₙ) heisst eine 
  Funktion h:A→B _Homomorphismus_, wenn für alle a₁,…,a_mᵢ∈A gilt:
  h(fᵢ(a₁,…,a_mᵢ)) = gᵢ(h(a₁),…,h(a_mᵢ))
  Man sagt auch "h veträgt sich mit den Operationen der beiden Algebren".
  Falls A=B, so spricht man von einem _Endomorphismus_.
  
Beispiele:
  ③ Ist U Unterstruktur von A, so ist h:U→A definiert durch
  h(x)=x trivialerweise ein Homomorphismus.
  
  ④ h:ℤ → ℤₘ      (also ganze Zahlen modulo m)
    n ↦ n mod m
  ist Homomorphismus von (ℤ,+,∙) nach (ℤₘ,+ₘ,∙ₘ);
  wobei +ₘ,∙ₘ jeweils Addition/Multiplikation modulo m.
  
Def.(Isomorphismus):
  Ein bijektiver Homomorphismus von (A,f₁,…,fₙ) nach (B,g₁,…,gₙ) heisst
  _Isomorphismus_. Ist A=B so spricht man von einem _Automorphismus_.
  
  Existiert ein Isomorphismus von A und B, so bezeichnet man die beiden Algebren A und B als _isomorph_.
  
Lemma: Ist h:A→B ein Isomorphismus, so ist die Umkehrfunktion h⁻¹ wieder ein Homomorphismus.
Beweis=Übung

Beispiele:
  ⑤ h(n)= n↦-n ist Automorphismus für (ℤ,+,∙)
  ⑥ h(x)= e^x ist Isomorphismus von (ℝ,+) mach (ℝ⁺,∙), denn e^(a+b)=e^a∙e^b und log ist Umkehrfunktion
  ⑦ h: ℤ_(m₁∙…∙mₖ) → ℤₘ₁×…×ℤₘₖ mit m₁,…,mₖ paarweise teilerfremd, definiert durch h(n)↦(n mod m₁,…,n mod mₖ) ist Isomorphismus 
  zwischen (ℤ_(m₁∙…∙mₖ),+ mod m₁∙…∙mₖ,∙ mod m₁∙…∙mₖ) und 
  (ℤₘ₁×…×ℤₘₖ, + koponentenweise modulo mᵢ, ∙ koponentenweise modulo mᵢ); dies folgt aus dem Chinesischen Restsatz.
  
Lemma: Ein Isomorphismus bildet neutrale Elemente auf neutrale Elemente ab; sowie Inverse auf Inverse.
Beweis: Sei h:A→B ein Isomorphismus. Zeige b○h(e)=b für alle b∈B und e∈A neutral in A. 
Es gilt b○h(e)=h(h⁻¹(b))○h(e)=h(h⁻¹(b)○e)=h(h⁻¹(b))=b.Analog gilt h(e)○b=h(e)○h(h⁻¹(b))=h(e○h⁻¹(b))=h(h⁻¹(b))=b.□
Beweis für Inverse=Übung
  
Prinzip: Sind A,B isomorph, so haben A und B dieselben (vernünftig formulierten) Eigenschaften; d.h. Gesetze lassen sich übertragen.



Gruppen
=======

Def.(Gruppe):
Eine _Gruppe_ ist ein Monoid, in dem jedes Element ein Inverses besitzt.
(Inverses von x wird meist mit x⁻¹ (multiplikativ) oder -x (additiv) bezeichnet.)


Beispiele:
  ① (ℤ,+) neutrales Element ist 0 und Inverses von a ist -a
  ② (ℝ\{0},∙) mit 1 als neutralem Element, x⁻¹=1/x
  
Satz: Sei M ein Monoid, die Menge aller Elemente, welche ein Inverses besitzen, bilden als Unterstruktur eine Gruppe. 
  (Bemerkenswerterweise führt die Operation also nicht aus der Menge heraus!)
Beweis: G≝{m|∃x∈M.m○x=x○m=1}
  G ist Untermonoid von M, da für alle m₁,m₂∈G mit Inversen m₁⁻¹ und m₂⁻¹, dann ist auch m₁○m₂∈G, denn (m₂⁻¹○m₁⁻¹) ist das Inverse:
  (m₂⁻¹○m₁⁻¹)○m₁○m₂=m₂⁻¹○(m₁⁻¹○m₁)○m₂=m₂⁻¹○1○m₂=m₂⁻¹○m₂=1.
  Weiterhin ist 1∈G wegen 1○1=1.
  □
  
=============================  
  ENDE VORLESUNG 31.05.2016
=============================
Beispiele:  
  ③ Bijektive Funktionen (Permutationen) einer Menge bilden immer eine Gruppe: 
  Alle Funktionen einer Mengen bilden ein Monoid, alle invertierbaren Funktionen einer Menge bilden damit 
  ein Untermonoid und damit eine Gruppe (da ja alle verbleibenden Funktionen invertierbar sind).
  (Permutationen auf n Elementen wird auch "Symmetrische Gruppe Sₙ" genannt.)
  ④ (ℤₚ\{0},∙ₚ) für p prim ist eine Gruppe, 
  und auch  ℤₙ*=({d<m | ggT(d,m)=1}, ∙ₘ). 
  Begründung für Erstes: Abschluß und 1 ist klar; Inverses zu x∈ℤₚ existiert: finde mit 
  erweitertem Euklidischem Algorithmus s,t mit s∙x+t∙p=1=ggT(x,p) dann ist (s mod p) das Inverse zu x.
  
Def.: Ein Gruppe (G,∙) heisst _abelsch_ oder _kommutativ_, falls für alle Gruppenelemente x,y∈G gilt x∙y=y∙x.

Bsp.: ④ ist abelsch, aber ③ ist nicht abelsch

Satz: Für jede Gruppe G und x,y,a,b,c ∈ G gilt:
  ① (x⁻¹)⁻¹=x
  ② (aⁱ)⁻¹= (a⁻¹)ⁱ
  ③ a∙c=b∙c ⇒ a=b
  ④ c∙a=c∙b ⇒ a=b
  ⑤ a∙x=b   ⇔ x=a⁻¹∙b
  ⑥ x∙a=b   ⇔ x=b∙a⁻¹
  
Beweis:  
  ①: Es gilt x⁻¹∙x=e und x∙x⁻¹=e. Damit ist x ein Inverses von x⁻¹, aber das Inverse eindeutig sind, ist x das Inverse von x⁻¹.
  ②: Per Induktion über i: (a⁻¹)ⁱ∙aⁱ=(a⁻¹)⁽ⁱ⁻¹⁾∙(a⁻¹∙a)∙a⁽ⁱ⁻¹⁾= (a⁻¹)⁽ⁱ⁻¹⁾∙a⁽ⁱ⁻¹⁾=1
  ③: a∙c=b∙c ⇒ a∙c∙c⁻¹=b∙c∙c⁻¹ ⇒ a=b
  ④: analog zu ②
  ⑤: a∙x=b ⇒ a⁻¹∙a∙x=a⁻¹∙b ⇒ e∙x=a⁻¹∙b
     e∙x=a⁻¹∙b ⇒ x=a⁻¹∙b
  ⑥: analog zu ⑤
  □
    
Def.(Ordnung): 
  Sei a∈G, G eine Gruppe. Die _Ordnung_ von a, geschrieben ord(a),
  ist die kleinste Zahl k>0, so dass aᵏ=1;
  gibt es kein k, so setzen wir ord(a)=∞.

Bsp.: 
  * In (ℤ,+) gilt ord(1)=∞.
  * In ℤ₉* gilt ord(2)=6, da 2⁶=2∙2∙2∙2∙2∙2=64 und 64 mod 9 = 1
   
  
Lemma:
  Ist G eine endliche Gruppe, so hat jedes g∈G eine
  endliche Ordnung.
Beweis:
  Da die Gruppe endlich ist, muss es in der Folge 1,a,a²,a³,a⁴,a⁵,… irgendwann eine Wiederholung geben.
  O.b.d.A sei aⁱ=aʲ mit i<j∈ℕ. Es gilt (a⁻¹)ⁱ∙aⁱ=1 also auch 1=(a⁻¹)ⁱ∙aʲ = a⁽ʲ⁻ⁱ⁾. Damit ist ord(a)≤j-i.
  □
  
Lemma: 
  Ist aᵏ=1 für k>0, so gilt ord(a)|k.
Beweis:
  Wir schreiben k=q∙ord(a)+r mit 0≤r<ord(a).
  1=aᵏ=a^(q∙ord(a)+r)=a^(q∙ord(a))∙a^r==(a^ord(a))^q∙a^r=1∙a^r.
  Damit haben wir einen Widerspruch a^r=1 und r<ord(a), da per Definition die Ordnung ja die kleinest Potenz i ist, für die a^i=1 gilt.
  
Def.(Untergruppe):
  Eine Untergruppe U einer Gruppe G ist eine Unteralgebra, welche 
  ebenfalls eine Gruppe ist (d.h. jedes u∈U hat ein Inverses in U).
  
Bsp.: (ℕ,+) ist Unteralgebra von (ℤ,+), aber keine Untergruppe.

Lemma:
  Jede Unteralgebra U einer endlichen Gruppe G ist eine Untergruppe.
Beweis:
  Für ein b∈U muss bᵏ∈U für alle k∈ℕ gelten, da U als Unteralgebra bezüglich ∙ abgeschlossen sein muss.
  Nach dem vorangegangenen Lemma hat jedes Element einer endlichen Gruppe eine endliche Ordnung:
    1 = b^(ord(b)) = b^(ord(b)-1)∙b = b⁻¹∙b
  Also muss 1∈U und b⁻¹∈U gelten.  
  □

Lemma:
  Ist H eine Untergruppe von G, so definiert 
  { (a,b) | a⁻¹∙b∈H für a,b∈G } eine Äquivalenzrelation ~ auf G.
Beweis:
  Reflexivität: a~b ⇔ a⁻¹∙a∈H ⇔ 1∈H
  Symmetrie: a~b ⇔ a⁻¹∙b∈H ⇔ b⁻¹∙a∈H ⇔ b~a,
  da b⁻¹∙a das (eindeutige) Inverse von a⁻¹∙b in G bzw. H ist.
  Transitivität: Es sei a~b und b~c, d.h.
  a⁻¹∙b∈H und b⁻¹∙c∈H. Damit muss aber 
  (a⁻¹∙b)∙(b⁻¹∙c)∈H gelten, also auch b⁻¹∙c∈H wegen Assoziativität von ∙.
  □
  
Bemerkung: a~b ⇔ Es gibt ein h∈H mit a∙h=b
  
Def.(Nebenklassen):
  Für eine Untergruppe H einer Gruppe G heisst 
    b∙H ≝ { b∙h | h∈H } 
  _linke_Nebenklasse_von_H_in_G_ mit der Form und analog _rechte_Nebenklasse_von_H_in_G_
    H∙b ≝ { h∙b | h∈H } 

Lemma:
  Die linken Nebenklassen sind Äquivalenzklassen zur Relation ~, denn a⁻¹∙b∈H ⇔ a∙H=b∙H:
Beweis:
  Es sei a~b, also a⁻¹∙b∈H. Wegen der  Gruppeneigenschaft von H gilt auch (a⁻¹∙b)⁻¹=b⁻¹∙a∈H.
  Sei nun x∈a∙H, dann gilt x=a∙h für ein h∈H.  
  Sei h'=(b⁻¹∙a)∙h. Es gilt h'∈H.
  x=a∙h=b∙b⁻¹∙a∙h=b∙h' also gilt x∈b∙H.
  Umgekeht sei nun a∙H=b∙H. Für jedes x=a∙h gibt es also ein h' mit x=b∙h'. 
  Aus a∙h = b∙h' folgt a⁻¹∙a∙h = h = a⁻¹∙b∙h' und damit bereits a⁻¹∙b∈H, denn a⁻¹∙b=h∙h'⁻¹.
  □
  
Lemma: 
  Ist G endlich, so haben alle Nebenklassen zu einer Untergruppe H die gleiche Kardinalität.
Beweis: 
  Angabe einer Bijektion 
  a∙H -f-> b∙H
  x ↦ b∙a⁻¹∙x 
  mit Umkehrfunktion y↦a∙b⁻¹∙y
  □
  
Korollar "Satz von Lagrange":
  Die Kardinalität einer Nebenklasse ist ein Teiler der Kardinalität der Gruppe;
  insbesondere gilt das die Kardinalität einer Untergruppe die Kardinalität der Gruppe teilt, wegen H=1∙H.
  
Lemma:  
  Ist a∈G und G endlich, so bildet
    H = {aⁱ| 0<i≤ord(a)}
  eine Untergruppe von G der Kardinalität ord(a).  
  (Man nennt diese auch die von a erzeugte zyklische Untergruppe.)
Beweis:
  aⁱ∙aʲ=aⁱ⁺ʲ=a^(i+j mod ord(a))
  (weil i+j=q∙ord(a)+(i+j mod ord(a)) und a^ord(a)=1)
  Inverses zu a: a^(ord(a)-1)=a⁻¹.
  □

Die zyklisch erzeugte Untergruppe von a ist isomorph zu (ℤ_ord(a),+)

Anwendung des Satzes von Lagrange ergibt:
  * Die Ordnung jedes Elements a ist ein Teiler von |G|
  * a^|G|=1, da |G| ein Vielfaches von ord(a) ist, also a^|G|=(a^ord(a))^q für ein q mit |G|=q∙ord(a)
  * Satz von Euler und kleiner Satz von Fermat

  
Def.(Ring):
  Ein Ring ist eine algebraische Struktur R=(R,⊕,⊙) mit Signatur (2,2) und:
    R1) (R,⊕) ist abelsche 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.


Def.(Körper):
  Ein Körper (engl. field) ist eine algebraische Struktur K=(K,⊕,⊙) mit Signatur (2,2) und:
    K1) (K,⊕) ist abelsche Gruppe mit neutralem Element 0
    K2) (K\{0},⊙) ist abelsche Gruppe mit neutralem Element 1
    K3) a⊙(b⊕c) = (a⊙b)⊕(a⊙c) für alle a,b,c∈K (Distributivgesetz)