Elementare und algebraische Zahlentheorie/T1/Klausur mit Lösungen
Aufgabe | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Punkte | 3 | 3 | 2 | 5 | 4 | 4 | 3 | 6 | 2 | 3 | 5 | 4 | 9 | 5 | 3 | 4 | 65 |
Aufgabe (3 Punkte)
Definiere die folgenden (kursiv gedruckten) Begriffe.
- Ein Ideal in einem kommutativen Ring .
- Eine primitive Einheit in .
- Das Legendre-Symbol.
- Ein pythagoreisches Tripel.
- Eine Mersennesche Primzahl.
- Eine Carmichael-Zahl.
- Ein Ideal ist eine nichtleere Teilmenge , für die die beiden folgenden Bedingungen erfüllt sind:
- Für alle ist auch .
- Für alle und ist auch .
- Eine Einheit heißt primitiv, wenn sie die Einheitengruppe erzeugt.
- Für eine ungerade Primzahl und eine zu teilerfremde Zahl definiert man das Legendre-Symbol durch
- Ein pythagoreisches Tripel ist eine ganzzahlige Lösung der diophantischen Gleichung
- Eine Primzahl der Form heißt Mersennesche Primzahl.
- Eine natürliche Zahl , die nicht prim ist, und die die Eigenschaft besitzt, dass für jede zu teilerfremde ganze Zahl
gilt, heißt Carmichael-Zahl.
Aufgabe (3 Punkte)
Formuliere die folgenden Sätze.
- Das Lemma von Euklid für einen Hauptidealbereich.
- Der kleine Fermat.
- Der Primzahlsatz.
- Es sei ein Hauptidealbereich und . Es seien und teilerfremd und teile das Produkt . Dann teilt den Faktor .
- Für eine Primzahl und eine beliebige ganze Zahl gilt
- Es gilt die asymptotische Abschätzung
Das heißt
Aufgabe (2 Punkte)
Man gebe ein Beispiel für eine natürliche Zahl, die man als Summe von vier Quadraten darstellen kann, aber nicht als Summe von drei Quadraten.
Es ist
darstellbar mit vier Quadraten. Die einzigen Quadrate unterhalb von sind . Die trägt nicht zu einer minimalen Darstellung bei. Zweimal die ist schon zu groß, daher gibt es keine Darstellung als Summe von drei Quadraten.
Aufgabe (5 Punkte)
Finde unter den Zahlen diejenige Zahl mit der maximalen Anzahl an Teilern.
Wir betrachten direkt die Primfaktorzerlegungen
annehmen. Bei ist
welches Teiler besitzt, ist schon zu groß. Bei besitzt (wir führen nur ernsthafte Kandidaten auf)
Teiler,
hat Teiler,
hat Teiler,
Bei besitzt
Teiler,
hat Teiler,
ist zu groß,
hat Teiler. Bei besitzt
Teiler.
ist zu groß. Wegen
kann es nicht mehr Primfaktoren geben. Also besitzt unter allen Zahlen unterhalb von die maximale Anzahl an Teilern, nämlich .
Aufgabe (4 Punkte)
Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .
Wir multiplizieren die zweite Zahl mit der Einheit und erhalten . Damit ist
Im nächsten Schritt ist (wir können mit statt mit arbeiten)
bzw.
Weiter ist
und
sodass also Teilerfremdheit vorliegt.
Aufgabe (4 Punkte)
Beweise das Lemma von Euklid für einen Hauptidealbereich.
Da und teilerfremd sind, gibt es nach dem Lemma von Bezout Elemente mit . Die Voraussetzung, dass das Produkt teilt, schreiben wir als . Damit gilt
was zeigt, dass ein Vielfaches von ist.
Aufgabe (3 Punkte)
Beweise den Satz, dass für einen endlichen Körper das Produkt aller von verschiedener Elemente aus gleich ist.
Die Gleichung hat in einem Körper nur die Lösungen und , die allerdings gleich sein können. Das bedeutet, dass für immer ist. Damit kann man das Produkt aller Einheiten als
schreiben. Ist , so ist das Produkt . Ist hingegen , so fehlt in dem Produkt der zweite Faktor und das Produkt ist .
Aufgabe (6 (1+1+2+2) Punkte)
In dieser Aufgabe geht es um den Restklassenring .
a) Schreibe als Produktring
(im Sinne des chinesischen Restsatzes).
b) Wie viele Einheiten besitzt ?
c) Schreibe das Element in komponentenweiser Darstellung. Begründe, warum es sich um eine Einheit handelt und finde das Inverse in komponentenweiser Darstellung.
d) Berechne die Ordnung von in .
a) Es ist
daher ist
b) Nach der Formel für die eulersche -Funktion ist die Anzahl der Einheiten gleich
c) Die Reste von modulo und sind
Da jede Komponente teilerfremd zu den zugehörigen Modulozahlen sind, handelt sich es sich insgesamt um eine Einheit. Das Inverse ist
d) Zur Berechnung der Ordnung von modulo schreiben wir
Die Ordnung in der ersten und der dritten Komponente ist , die Ordnung in der zweiten Komponente ist wegen , gleich , da ja die Ordnung besitzt. Daher ist die Ordnung von gleich .
Aufgabe (2 Punkte)
Bestimme die Anzahl der hinteren Nullen in der Dezimalentwicklung von .
Die kommt in den Zahlen jeweils einmal vor und in nochmal zusätzlich mit einer weiteren Potenz. In kommt also der Primfaktor mit dem Exponenten vor. Wegen der geraden Zahlen kommt der Primfaktor öfters vor. In ist also die größte Zehnerpotenz und somit besitzt genau Nullen am Ende.
Aufgabe (3 Punkte)
Man gebe ein Polynom an, das nicht zu gehört, aber die Eigenschaft besitzt, dass für jede ganze Zahl gilt: .
Betrachte das Polynom
Die Koeffizienten liegen in , aber nicht in . Wenn man in dieses Polynom eine ganze Zahl einsetzt, so ist genau eine der Zahlen und gerade. Also ist ganzzahlig.
Aufgabe (5 (2+2+1) Punkte)
Es seien und sei .
a) Zeige, dass die beiden Polynome und Teiler des Polynoms sind.
b) Es sei . Ist stets ein Teiler von ?
c) Man gebe drei Primfaktoren von an.
a) Es ist
und daher ist (und ebenso ) ein Teiler von .
b) Dies ist nicht der Fall. Für
ist
Das Polynom hat keine reelle Nullstelle und ist deshalb kein Vielfaches von . Daher ist kein Teiler von .
c) Da Teiler von sind, ergibt sich aus Teil a), dass und Teiler von sind. Daher sind Primteiler von .
Aufgabe (4 Punkte)
Berechne mit Hilfe des quadratischen Reziprozitätsgesetzes und seiner Ergänzungssätze das Legendre-Symbol
und bestimme, ob ein Quadratrest modulo ist oder nicht ( ist eine Primzahl).
Wir berechnen Schritt für Schritt das Legendre-Symbol (wobei es sich in Zwischenschritten um das Jacobi-Symbol handeln könnte).
Also ist kein Quadratrest modulo
Aufgabe (9 Punkte)
Zeige, dass die diophantische Gleichung
keine ganzzahlige nichttriviale Lösung besitzt.
Es sei eine nichttriviale Lösung, d.h. alle Einträge sind . Wir können annehmen, dass alle Einträge sogar positiv sind. Wenn es eine solche Lösung gibt, dann gibt es auch eine nichttriviale Lösung mit minimalem positiven (unter allen nichttrivialen Lösungen). Wir zeigen, dass es dann eine Lösung mit kleinerem positiven gibt, was einen Widerspruch bedeutet.
Wegen der Minimalität ist primitiv, die Einträge sind also (sogar paarweise) teilerfremd. Wir können als ungerade annehmen. Es ist dann
ein primitives pythagoreisches Tripel. Daher gibt es nach Fakt teilerfremde natürliche Zahlen mit
und mit ungerade. Betrachtung der ersten Gleichung modulo zeigt, dass ungerade sein muss (und gerade). Die erste Gleichung
ist selbst ein primitives pythagoreisches Tripel. Es gibt als erneut teilerfremde natürliche Zahlen mit
( ist ungerade, gerade) mit ist ungerade. Somit sind paarweise teilerfremd. Aus
folgt
und aus der Teilerfremdheit der Faktoren folgt, dass die einzelnen Faktoren hier selbst Quadrate sind, also
Damit ist
eine neue nichttriviale Lösung der ursprünglichen Gleichung. Wegen
widerspricht dies der Minimalität von .
Aufgabe (5 Punkte)
Zeige, dass es unendlich viele Primzahlen gibt, die modulo den Rest besitzen.
Wir ziehen Fakt heran, wonach eine ungerade Primzahl genau dann den Rest modulo besitzt, wenn eine Quadratwurzel in ist. Nehmen wir an, dass es nur endlich viele Primzahlen von diesem Typ gibt. Wir betrachten das Polynom
Die Zahl
besitzt einen Primteiler , der von allen und von verschieden ist. Es ist
Doch dies bedeutet, dass eine Nullstelle modulo besitzt und somit ist ein Quadrat modulo , also hat den Rest modulo .
Aufgabe (3 Punkte)
Es sei . Zeige, dass das Produkt von aufeinanderfolgenden natürlichen Zahlen von geteilt wird.
Es ist
Da der Binomialkoeffizient eine ganze Zahl ist, folgt, dass das Produkt der aufeinanderfolgenden Zahlen von geteilt wird.
Aufgabe (4 Punkte)
Wir haben zu zeigen, dass für gilt: modulo . Es ist modulo nach dem kleinen Fermat. Damit ist modulo . Also ist ein Vielfaches von , sagen wir . Wegen modulo gilt dann modulo .