Transcript
Algebra Aufgabe 1 Beweise den folgenden Satz: Ist R ein kommutativer Ring (nicht notwendig mit Eins!) mit mindestens zwei Elementen, der nur die trivialen Ideale {0} und R besitzt, so ist R entweder ein K¨orper oder es gibt eine Primzahl p dergestalt, dass R die folgenden beiden Eigenschaften hat: i) Die additive Gruppe von R ist isomorph zur Gruppe (Z/pZ, +). ii) Es gilt ab = 0 f¨ ur alle a, b ∈ R. Hinweis: Der Beweis ist (nat¨ urlich) auf verschiedene Arten durchf¨ uhrbar. Ein m¨oglicher Weg f¨ uhrt unter anderem u ¨ber die folgenden Stationen: 1. Zeige: Ist ab = 0 f¨ ur alle a, b ∈ R, so ist jede Untergruppe der additiven Gruppe von R ein Ideal in R. 2. Zeige: Eine zyklische Gruppe G mit neutralem Element e, f¨ ur die G 6= {e} gilt und die als Untergruppen nur {e} und G besitzt, ist isomorph zu einer Gruppe Z/pZ mit einer Primzahl p. 3. Wenn nicht gilt, dass ab = 0 f¨ ur alle a, b ∈ R ist, dann zeige, dass es ein u ∈ R und ein b ∈ R \ {0} mit ub = b gibt. Zeige weiter, dass u ein Einselement in R ist.
Aufgabe 2 p √ √ √ die positive reelle QuadratSei K = Q( 5) und L = K( 5 + 5). Dabei bezeichnet wurzel einer positiven reellen Zahl. p √ 1. Bestimme das Minimalpolynom f von 5 + 5 u ¨ber Q sowie alle Nullstellen von f in C. Zeige, dass [L : Q] = 4 gilt. 2. Bestimme alle Einbettungen σ : L → C. Dabei ist eine Einbettung ein injektiver Homomorphismus. p √ √ p 5+ 5 · 5 − 5 und folgere, dass L eine Galoiserweiterung von 3. Berechne Q ist. 4. Zeige: Die Galoisgruppe von L/Q ist zyklisch.
1
Zahlentheorie Aufgabe 1: 1. (Einstiegsaufgabe, unabh¨angig von den Teilaufgaben 2-4) Seien a, b, x, y ganze Zahlen mit ax + by = ggT(a, b). Zeigen Sie, dass ggT(x, y) = 1 gilt. 2. Zeigen Sie, dass f¨ ur ungerades a und n ≥ 3 gilt: a2
n−2
≡1
mod 2n .
3. Sie m ≥ 2 eine positive ganze Zahl. Definieren Sie den Begriff Primitivwurzel modulo m. 4. Zeigen Sie, dass 2 und 4 die einzigen Zweierpotenzen sind, modulo denen es Primitivwurzeln gibt.
Aufgabe 2: Sei p eine ungerade Primzahl. 1. Definieren Sie das Legendre Symbol ap und nennen Sie das Quadratische Reziprozit¨atsgesetz und die beiden Erg¨anzungss¨atze. Finden Sie eine dem zweiten Erg¨anzungssatz analoge Aussage f¨ ur −2 . p 2. Zeigen Sie: Wenn p 6≡ 5 mod 8 gilt, dann hat die Kongruenz x8 ≡ 16 mod p eine L¨osung. 3. Zeigen Sie, dass auch im Fall p ≡ 5 mod 8 die Kongruenz x8 ≡ 16 mod p l¨osbar ist. Gehen Sie in folgenden Schritten vor: (a) Begr¨ unden Sie, warum die Kongruenz y 2 ≡ −1 mod p l¨osbar ist und die Kongruenz z 4 ≡ −1 mod p nicht l¨osbar ist. (F¨ ur letzteres zeigen Sie, dass eine potentielle L¨osung z die Beziehung ordp z = 8 erf¨ ullen w¨ urde und f¨ uhren Sie dies zum Widerspruch.) 2 (b) Zeigen Sie, dass f¨ ur jede L¨osung y der Kongruenz y ≡ −1 mod p gilt: 2y = p 1. (c) Schließen Sie daraus, dass es ein x mit x2 ≡ 2y mod p gibt und zeigen Sie, dass dieses x die gew¨ unschte Kongruenz x8 ≡ 16 mod p erf¨ ullt.
2
Kryptographie Aufgabe 1 1. Erkl¨are das Sieb des Eratosthenes und den Rabin-Miller-Test. 2. Wie kann man praktisch große (etwa 100-stellige) Primzahlen erzeugen? Wie lautet eine mathematisch exakte Interpretation des Ergebnisses? 3. Sei nun n ∈ N gr¨oßer als 2 eine Zahl, die den Rabin-Miller-Test zur Basis 2 besteht. Beweise: n ist nicht durch 9, 15, 21, 35 oder 39 teilbar. 4. Beschreibe ein Kryptographieverfahren, welches auf der Konstruktion großer Primzahlen basiert. 5. Zeige n ist genau dann prim, wenn (Z/nZ)∗ zyklisch von Ordnung n − 1 ist. Hierzu d¨ urfen alle S¨atze aus der Vorlesung verwendet werden.
Aufgabe 2 1. Berichte u ¨ber endliche K¨orper: Definiere die Begriffe Charakteristik eines K¨orpers, K¨orpergrad und K¨orperhomomorphismus. Welche Charakteristiken k¨onnen bei endlichen K¨orpern auftreten? Formuliere S¨atze u ¨ ber Existenz, Eindeutigkeit und Konstruktion von endlichen K¨orpern und u ber Eigenschaften der multiplikativen Gruppe. ¨ 2. Sei nun K ein endlicher K¨orper der Charakteristik n und ϕ : K→K x 7→ xn . Zeige, dass ϕ ein bijektiver Homomorphismus von K nach K ist. 3. Zeige, dass ϕr h¨ochstens nr Fixpunkte hat. Wie viele Fixpunkte haben ϕ und ϕ2 ? 4. F¨ ur welche s > 0 ist ϕs die Identit¨at auf K ?
Aufgabe 3 Sei K = F2 und f = x127 + x + 1 ∈ K[x] sowie R = K[x]/(f ). Weiterhin setzen wir n = 2127 − 1. Wie Lucas bereits 1876 zeigen konnte, ist n prim. 127 ist u ¨ brigens auch prim, das ist aber offensichtlich.
3
1. Wie kann man xn+1 mod f mit vern¨ unftigem Aufwand ausrechnen? Die Rechnung soll hier nicht durchgef¨ uhrt werden, sondern nur so genau beschrieben werden, dass eine Durchf¨ uhrung reine Fleißarbeit ist. Das Ergebnis dieser Rechnung w¨are dann u ¨brigens x. Es kann bei Bedarf verwendet werden. (F¨ ur diese Rechnung hat mein Computer bei dilettantischer Programmierung 1,8 Sekunden gebraucht.) 2. Wie ist R∗ definiert? Zeige, dass R∗ h¨ochstens n Elemente hat. 3. Zeige: R ∼ = F2127 4. Zeige, dass es keinen K¨orper L mit F2 ( L ( F2127 gibt. 5. Zeige, dass f in K[x] irreduzibel ist. 6. Beschreibe ein Kryptographieverfahren, welches wesentlich auf der Konstruktion großer K¨orper wie etwa F2127 oder besser F21000 basiert.
Differentialgleichungen Aufgabe 1 L¨ose folgende Differentialgleichungen: 1. y 000 (x) − 3y 0 (x) + 2y(x) − xex = 0 2. u(t) ˙ + tu(t) − t2 u2 (t) = 0
Aufgabe 2 1. Beschreibe den Phasenraum und L¨osungskurven der gew¨ohnlichen Differentialgleichung f 00 (t) = −f (t) + sgn(f (t)), (1) wobei sgn(x) = 1 f¨ ur x > 0, = 0 f¨ ur x = 0, = −1 f¨ ur x < 0. 2. Zeige, daß die L¨osungen von (1) periodisch sind. H¨angt die Periode stetig von den Anfangsbedingungen ab?
4
Funktionentheorie Aufgabe 1 Zeigen Sie, dass der Hauptzweig des Logarithmus keine rationale Funktion ist.
Aufgabe 2 Zeigen Sie, dass durch f (z) =
∞ X
ein
3z
n=0
eine holomorphe Funktion in der oberen Halbebene Im(z) > 0 definiert ist.
Numerik Aufgabe 1 1. Die Funktion f (x) := e−x soll in den Punkten x1 = 0, x2 = 21 und x3 = 1 durch ein quadratisches Polynom p2 (f ) interpoliert werden. Man berechne p2 (f ) in der Lagrange- und Newton-Darstellung und leite eine m¨oglichst gute Absch¨atzung f¨ ur den maximalen Interpolationsfehler sup f (x) − p2 (f )(x) x∈[0,1]
her. 2. Sei wiederum f (x) := e−x . Zu jeder Zahl n ∈ N seien im Intervall [0, 1] n+1 paarwei(n) (n) se verschiedene St¨ utzstellen x1 , . . . , xn+1 gegeben. Weiter sei pn (f ) das zugeh¨ orige Interpolationspolynom vom Grad ≤ n. Zeigen Sie, dass die Folge pn (f ) n∈N f¨ ur n → ∞ auf [0, 1] gleichm¨aßig gegen f konvergiert.
Aufgabe 2 Gegeben sie die symmetrische tridiagonale a b A :=
n × n-Matrix b .. .. . . .. .. . . b b a
mit a, b ∈ R und n ≥ 3. 5
1. Man gebe hinreichende Bedingungen daf¨ ur an, dass A nichtsingul¨ar bzw. positiv definit ist. Hinweis: Es darf der Satz von Gerschgorin P angewandt werden. Dieser hat folgende Aussage: Ist A = (aijS) ∈ Rn×n und ri := nj=1,j6=i |aij | f¨ ur i = 1, . . . , n so liegt jeder n Eigenwert von A in i=1 Gi , wobei Gi := {z ∈ C : |z − aii | ≤ ri } f¨ ur i = 1, . . . , n. 2. Man gebe eine hinreichende Bedingung f¨ ur die Konvergenz des GSV zur L¨osung linearer Gleichungssysteme mit der Koeffizientenmatrix A an. 3. Wie sieht das Gauß’sche Eliminationsverfahren f¨ ur die Matrix A in einer nichtredundanten Version aus? Welchen Aufwand hat es als Funktion von n? Kann im Falle der Matrix A auf eine Pivotisierung verzichtet werden?
6
Stochastik Aufgabe Sei X : Ω → IN0 eine diskrete Zufallsvariable. Im folgenden betrachten wir Eigenschaften der erzeugenden Funktion, die durch MX (s) = EsX definiert ist. a) Zeigen Sie, dass EX = lim s↑1
d MX (s) = MX0 (1) ds
gilt und finden Sie eine analoge Darstellung f¨ ur die Varianz von X. b) Zeigen Sie, dass f¨ ur stochastisch unabh¨angige Zufallsvariable X und Y MX+Y (s) = MX (s)MY (s) gilt. c) Seinen (Xi ) stochastisch unabh¨angig verteilte Zufallsvariable auf IN0 , die von N unabh¨angig sind. Zeigen Sie die folgende Darstellung der erzeugenden Funktion f¨ ur die Summe MPN i=1
Xi
(s) = MN (MX1 (s))
und damit die Waldsche Identit¨at N X
E(
Xi ) = (EN )(EX1 ).
i=1
d) Ein radioaktives Pr¨aparat sendet pro Minute N Teilchen aus, wobei N Poissonverteilt mit Parameter λ ist. Die Wahrscheinlichkeit, dass ein Teilchen vom Meßger¨at registriert wird, sei θ. Wie ist die Anzahl der registrierten Teilchen verteilt. Wie ist ihr Erwartungswert und die Varianz?
Aufgabe a) Beweisen Sie die Tschebyschev Ungleichung, dass f¨ ur eine Zufallsvariable X mit endlicher Varianz f¨ ur jeder > 0 P (|X − EX| ≥ ) ≤ 1
V ar(X) 2
gilt. b) Formulieren Sie das schwache Gesetz der großen Zahlen und zeigen Sie wie es sich aus a) herleiten l¨aßt. c) Sei (Xi ) eine Folge unabh¨angig identisch verteilter Zufallsvariablen, X1 : Ω → IN0 mit Verteilung PX1 . Definiere durch n 1X ˆ Pn (B) = 1B (Xi ) n i=1
das empirische Maß von B ⊂ IN0 . Zeigen Sie, dass f¨ ur alle B ⊂ IN0 und n→∞ stoch Pˆn (B) → PX1 (B) gilt. d) L¨aßt sich aus b) auch n 1X stoch Xi → 0 n i=1
f¨ ur n → ∞ folgern, wenn die Xi unabh¨angig Cauchy verteilt sind, also die 1 Verteilung die Dichte π1 1+x 2 hat?
2
