Wie fast alle klassischen Themen der Algebra, wurde auch die Auflösbarkeit von Gruppen dadurch getrieben, die Frage nach der Lösbarkeit algebraischer Gleichungen durch Radikale zu beantworten.

Generationen von Mathematikern, darunter solche Berühmtheiten wie Galois, Jordan oder Abel, beschäftigten sich mit diesem Problem. Letztlich konnte die Galois-Theorie mit Hilfe der sog. Galois-Gruppen das Problem auf die Auflösbarkeit von Gruppen reduzieren, deren Theorie wir hier untersuchen werden. In diesem Zusammehang bietet es sich an, die Konstrukte Normalreihe und Kompositionsreihe näher zu untersuchen.

• Repetitorium: Homomorphie-Satz; erster und zweiter Isomorphiesatz; Permutationsgruppen, Symmetrische Gruppe; Alternierende Gruppe; Kleinsche Vierergruppe; gerade; ungerade; Ordnungen; Kommutatorgruppen der Permutationsgruppen, Auflösbarkeit von S_n; Definition des direkten Produkts; Homomorphismen;
• Normalreihen; Beispiele; Untergruppen abelscher Gruppen; Normalteiler von Gruppen; absteigende Gruppenkette von G; normale Kette; Faktorgruppen, Faktoren; zyklische bzw. abelsche Kette; Normalreihe von G nach N; äquivalente Normalreihen; Beispiele; Sätze;
• Verfeinerungssatz von Schreier; Lemma von Zassenhausen; Definition Verfeinerung; Je zwei Normalreihen einer Gruppe besitzen äquivalente Verfeinerungen; Butterfly-Lemma; dritter Isomorphiesatz; Beweis; Beispiel zum Verfeinerungssatz;
• Kompositionsreihen; nicht weiter verfeinert werden können, ohne Wiederholungen; maximaler Normalteiler; einfache Gruppe; M maximaler Normalteiler genau dann, wenn G/M einfach ist; Kompositionsreihe; Kompositionsfaktoren;
• Satz von Jordan-Hölder;
• Einfache Kommutatorgruppen; Kommutator von a und b; Produkt von Kommutatoren im Allgemeinen nicht wieder Kommutator; Erzeugendensymstem; kleinste Normalteiler; ablescher Faktorgruppe G/N; Höhere Kommutatorgruppen; i-te Kommutatorgruppe von G; Rechenregeln zu Kommutatorgruppen; Kommutatoren von Permutationsgruppen; symmetrische Gruppe S_n ist für n>4 nicht auflösbar;
• Auflösbare Gruppen; auflösbar; Jede Untergruppe einer auflösbaren Gruppe ist auflösbar;Jedes endliche direkte Produkt auflösbarer Gruppen ist auflösbar;Es sei N ein Normalteiler einer Gruppe G. Sind N und G/N auflösbar, so ist auch G auflösbar;Eine Gruppe ist genau dann auflösbar, wenn sie eine abelsche Normalreihe besitzt;
• Auflösbarkeit und Kompositionsreihen; Jede Verfeinerung einer abelschen Normalreihe ist abelsch;G ist genau dann auflösbar, wenn die Kompositionsfaktoren von G Primzahlordnung haben; Eine auflösbare Gruppe G besitzt genau dann eine Kompositionsreihe, wenn G endlich ist; Jede endliche p-Gruppe (p Primzahl) ist auflösbar; Alle Gruppen der Ordnung p^aq^b mit Primzahlen p, q und a, b aus IN sind auflösbar; Satz von Burnside; Satz von Feit-Thompson;

Ein Schmuckstück der elementaren Zahlentheorie ist die Theorie der quadratischen Reste, welche den hauptsächlichen Anlass zur Entwicklung der höheren Zahlentheorie gegeben hat. In diesem Dokument werden wir die Grundlagen dieser Theorie elementar vermitteln, d.h. es sind Kenntnisse über algebraische Konstrukte und zahlentheoretische Funktionen (wie die Eulersche -Funktion) für das Verstehen hilfreich.

Zunächst werden wir das so genannten Legendresymbol definieren und näher untersuchen. Im Anschluss daran beweisen wir einige grundlegende Sätze, wie z.B. das Eulersche Kriterium oder das Gaußsche Lemma.

Der Höhepunkt dieses Dokuments und der elementaren Zahlentheorie ist das quadratische Reziprozitätsgesetzt, welches Gauß in seiner Disquisitiones erstmals bewies. Gauß selbst hat acht Beweise des Reziprozitätsgesetzes für quadratische Reste angegeben, von denen sechs auf voneinander gänzlich verschiedenen Ideen fußen. Wir werden uns mit einem sehr anschaulichen Beweis begnügen.

Im Anschluss an diesen wunderbaren Beweis werden wir das Jacobisymbol und einige grundlegende Erkenntnisse, wie Rechenregeln, studieren.

Im Einzelnen werden behandelt:

• Grundlegende (naive) Definitionen der Meng der natürlichen und ganzen Zahlen, Restklassen, Restklassenring, Menge von Äquivalenzklassen, Kongruenz, Einheitengruppe, Eulersche phi-Funktion, Wert der Eulerschen phi-Funktion für Primzahlpotenzen - Beweis.
• Definition quadratischer Rest, Beispiel, quadratischer Nichtrest, Wieviele Restklassen besitzen Quadratwurzeln? Antwort für p-Restklassen und allgemein, Erzeuger, zyklsiche Gruppen, Notwendigkeit der Zyklizität, kgV.
• Problemreduktion auf teilerfremde Faktoren speziell auf Primfaktorzerlegung einer vorgegebenen Zahl im Modul m; a ist quadratischer Rest genau dann, wenn a quadratischer Rest modulo jeder teilerfremden Zahl die a teilt bzw. modulo jeder Primzahlpotenz von a.
• Quadratische Reste modulo Primzahlpotenzen, ungerade und gerade Primzahlpotenzen, Beispiele, Beweise.
• Kriterium von Euler und das Legendre-Restsymbol, Legendre-Symbol, Definition, Beispiele, Beweis, notwendiges aber nicht hinreichendes Kriterium für Primzahlen, Folgerungen, Rechenregeln für Legendre-Symbole.
• Das Gaußsche Lemma, Menge der absolut kleinsten Reste, bijektive Abbildung, ausführlicher Beweis des Gaußschen Lemmas, Anzahl der negativen Zahlen unter den absolut kleinsten Resten modulo p, Anwendung des Gaußschen Lemmas, Beispiel, Beweis des zweiten Ergänzungssatzes, Gaußklammer.
• Das quadratische Reziprozitätsgesetzt; jedes Legendresymbol kann durch drei Typen gelöst werden, erste und zweite Ergänzungssatz, dritte Typ entspricht dem quadr. Reziprozitätsgesetz, Herleitung, p und q nicht beide von der Form 4k+3 bzw. beide die Form 4k+3, Erläuterung, Anwendung des qudartischen Reziprozitätsgesetzes, Beispiele.
• Geometrischer Beweis des quadratischen Reziprozitätsgesetzes mit Hilfe des Gaußschen Lemmas, Zerlegung eines Rechtecks in einen Streifen und zwei Dreiecken, Abzählung von (ganzzahligen) Gitterpunkten in der reellen Ebene, Skizze.
• Jacobi-Restsymbol, Jacobi-Symbol, Rechenregeln, Reziprozitätsgesetz für Jacobi-Symbole, Zusammenhang mit Legendre-Symbol, Grundlegendes.

Der Begriff der Berechenbarkeit spielt neben dem der Komplexität in der klassischen theoretischen Informatik eine zentrale Rolle. Zunächst sollte man sich fragen, was das Adjektiv „berechenbar“ überhaupt bedeutet und worauf sich dieser Begriff bezieht. Intuitiv werden viele darunter wohl verstehen, dass etwas „sich errechnen lässt“ bzw. „vorhersehbar“ ist. Um jedoch etwas berechnen zu können benötigt man sicherlich ein Kochrezept, also einen Algorithmus bzw. eine Funktionsvorschrift. Schließlich müssen wir auch noch klären, was man alles berechnen kann, es wird sich nämlich zeigen, dass nicht alle Funktionen berechnenbar sind.

Sowohl Turing- als auch Registermaschinen sind Modelle von Maschinen. Sie nähern sich der Frage nach der Berechenbarkeit von der Seite der berechenbaren Automaten. Die jeweiligen Programme, welche auf diesen Maschinen laufen, müssen spezielle für das jeweilige Modell und die jeweilige Problemstellung zugeschnitten sein.

Einen hiervon differeten (aber äquivalenten) Zugang zur Frage der Berechenbarkeit besiert auf speziellen Funktionenklassen und darauf abgeschlossenen Operationen (Verknüpfungen). Mit den so genannte rekursiven Funktionen werden wir Lösungen von Problemen beschreiben und nicht, wie es bei den Maschinenmodellen üblich ist, die einzelnen Schritte des Rechenweges. Das Modell der rekursiven Funktionen versucht also nicht eine Maschine bzw. einen Automaten nachzubilden, sondern packt das Problem der Berechnbarkeit sozusagen bei der Wurzel, d.h. es nähert sich der Frage nach der Berechenbarkeit von Seite der Algorithmen.

Im Einzelnen werden behandelt:

• Definition "intuitiv berechenbar"; Heranführung an den Begriff "Berechenbarkeit"; Grundlegende Definitionen
• Nicht berechenbare Funktionen und deren Existenz; Beispiele und Beweis; Kardinalitätsargument;
• Primitiv rekursive Funktionen; Induktionsprinzip; Basis-Funktionen; Grund-Funktionen; Konstante Funktionen; Nachfolgerfunktion (suc); Projektion auf den i-ten Eintrag; Substitution, Komposition, primitive Rekursion; primitiv rekursive Funktionen abgeschlossen gegenüber den Operationen; Beweis; Algorithmen; berechenbar;
• Arithmetische Funktionen primitiv rekursiv dargestellt: Addition, Multiplikation, Potenzierung, modifizierte Subtraktion, Fakultät, Signum-Funktion, Maximum, Minimum, Identität; Abgeschlossen gegenüber Umordnung und Weglassen von Variablen; Fallunterscheidung;
• Primitiv rekursive Relationen: Prädikate, Und, Oder, Nicht, Kleinergleich, Größergleich, Gleichheit; Charakteristische Funktion
• Der unbeschränkte mue-Operator; echte Erweiterung der primitiv rekursiven Funktionen; alle berechenbaren Funktionen; Minimalisierung; beschränkte mue-Operator; Beispiele;
• Ackermannfunktion; wichtigsten Charakterisierungen; Eigenschaften; Beweise; streng monoton in beiden Argumenten; wächst stärker als jede primitiv rekursive Funktion.

Primzahltests sind wichtige Beispiele so genannter probabilistischer Algorithmen. Der Solovay-Strassen-Test war sogar einer der ersten seiner Art und wird am Ende dieses Dokuments behandelt.

Die in diesem Dokument behandelten Primzahltests, der Fermat-Test bzw. Miller-Rabin-Test, sind eng miteinander verknüpft. Der Miller-Rabin-Test kann als Fort- bzw. Weiterentwicklung des Fermat-Tests angsehen werden. Beide Algorithmen basieren auf dem wichtigen und einfach zu beweisenden (kleinen) Satz von Fermat. Allerdings treten beim Fermat-Test Anomalien in Form von Carmichael-Zahlen auf, welche der Miller-Rabin-Test erfolgreich versucht zu umgehen.

Auch der Solovay-Strassen-Test ist eng mit den beiden anderen untersuchten Primzahltests verwandt. Dies äußert sich auch im Zusammenhang zwischen den einzelnen Pseudoprimzahlarten.

Im Einzelnen werden behandelt:

• Grundsätzliches Vorgehen bei einem probabilistischen Primzahltest, Vorgehen bei einem negativen Testausgang um eine große Primzahl zu finden.
• Brute-Force-Mathode um eine Zahl zu testen, Zusammenhang mit der Komplexitätstheorie, AKS-Test, deterministischer polynomieller Primzahltest.
• Definition Zusammengesetzte Zahl, Primzahl, Primfaktorzerlegung, Primfaktoren, Hauptsatz der Zahlentheorie, es existieren unendlich viele Primzahlen, Primzahlsatz und Primzahlverteilung.
• Anforderungen an ein Kryptosystem; Komplexität; deterministisch; stochastisch unabhängige Wahl der Basis, Zeugen (witness), nicht Zeugen (liar), randomisierten bzw. probabilistischer Algorithmus.
• Der Fermat-Test, Lemma von Bézout, modulare Inverse, "kleiner" Satz von Fermat, Satz von Euler; a Einheit im Ring Z_n genau dann, wenn ggT(n,a)=1; Pseudoprimzahl, Beispiele, Einheitengruppe, Restklassenring, erzeugende Elemente, Eulersche phi-Funktion, Menge aller Basen bilden eine Untergruppe von (Z/nZ)^*, zusammengesetzte Zahl, Pseudoprimzahl für mind. die Hälfte aller Basen oder aber für alle Basen.
• Carmichael-Zahl, Satz von Korselt, Verteilung der Carmichael-Zahlen, "wahrscheinlich prim", Charakterisierung von Carmichael-Zahlen, mindestens Produkt drei verschiedener Primzahlen.
• Rabin-Miller-Test, Polynom T²-1 hat in einem endlichen Körper der Ordnung p die einzigen Nullstellen +1 und -1, Beweis bzw. Herleitung, triviale Wurzeln bzw. nicht triviale Wurzeln, Beispiele, starke Pseudoprimzahl, höchstens für die Hälfte aller Basen b kann eine zusammengesetzte Zahl eine starke Pseudoprimzahl sein, Laufzeituntersuchungen, O-Notation.
• Quadratische Reste, quadratische Nichtreste, Anzahl der Quadratwurzeln, Legendre-Symbol, Jacobi-Symbol und quadratische Reste, Zusammenhang beider Symbole, Satz von Euler, Rechenrelgen des Jacobi- bzw. Legendre-Symbols, Eulersche Pseudoprimzahl, der Algorithmus.