Elementare und algebraische Zahlentheorie/T1/Klausur mit Lösungen

Aus Wikiversity
Zur Navigation springen Zur Suche springen



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.

  1. Ein Ideal in einem kommutativen Ring .
  2. Eine primitive Einheit in .
  3. Das Legendre-Symbol.
  4. Ein pythagoreisches Tripel.
  5. Eine Mersennesche Primzahl.
  6. Eine Carmichael-Zahl.


Lösung

  1. Ein Ideal ist eine nichtleere Teilmenge , für die die beiden folgenden Bedingungen erfüllt sind:
    1. Für alle ist auch .
    2. Für alle und ist auch .
  2. Eine Einheit heißt primitiv, wenn sie die Einheitengruppe erzeugt.
  3. Für eine ungerade Primzahl und eine zu teilerfremde Zahl definiert man das Legendre-Symbol durch
  4. Ein pythagoreisches Tripel ist eine ganzzahlige Lösung der diophantischen Gleichung
  5. Eine Primzahl der Form heißt Mersennesche Primzahl.
  6. 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.

  1. Das Lemma von Euklid für einen Hauptidealbereich.
  2. Der kleine Fermat.
  3. Der Primzahlsatz.


Lösung

  1. Sei ein Hauptidealbereich und . Es seien und teilerfremd und teile das Produkt . Dann teilt den Faktor .
  2. Für eine Primzahl und eine beliebige ganze Zahl gilt
  3. 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.


Lösung

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.


Lösung

Wir betrachten direkt die Primfaktorzerlegungen

woraus direkt die Teileranzahl
ablesbar ist. Da klein sein soll, können wir direkt mit den ersten Primzahlen arbeiten und ferner

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 .


Lösung

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

so dass also Teilerfremdheit vorliegt.


Aufgabe (4 Punkte)

Beweise das Lemma von Euklid für einen Hauptidealbereich.


Lösung

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.


Lösung

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 .


Lösung

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 .


Lösung

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: .


Lösung

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)

Seien und sei .

a) Zeige, dass die beiden Polynome und Teiler des Polynoms sind.


b) Sei . Ist stets ein Teiler von ?


c) Man gebe drei Primfaktoren von an.


Lösung

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).


Lösung

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.


Lösung

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.


Lösung

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)

Sei . Zeige, dass das Produkt von aufeinanderfolgenden natürlichen Zahlen von geteilt wird.


Lösung

Es ist

Da der Binomialkoeffizient eine ganze Zahl ist, folgt, dass das Produkt der aufeinanderfolgenden Zahlen von geteilt wird.


Aufgabe (4 Punkte)

Zeige: Für eine Primzahl ist die Mersennesche Zahl quasiprim zur Basis .


Lösung

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 .