# Elementare und algebraische Zahlentheorie/3/Klausur mit Lösungen
### Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.
* Ein euklidischer Bereich $R$.
* Eine vollkommene Zahl.
* Das Minimalpolynom eines Elementes $x\in L$ in einer endlichen Körpererweiterung $K\subseteq L$.
* Ein quadratischer Zahlbereich.
* Die Norm zu einem Ideal ${\mathfrak {a}}\neq 0$ in einem quadratischen Zahlbereich $R$.
* Die Diskriminante einer binären quadratischen Form.
Lösung
* Ein euklidischer Bereich ist ein Integritätsbereich $R$, für den eine Abbildung $\delta :R\setminus \{0\}\to \mathbb {N}$ existiert, die die folgende Eigenschaft erfüllt: Für Elemente $a,b$ mit $b\neq 0$ gibt es $q,r\in R$ mit
    $a=qb+r{\text{ und }}r=0{\text{ oder }}\delta (r)<\delta (b).$
* Eine natürliche Zahl $n$ heißt vollkommen, wenn sie mit der Summe all ihrer von $n$ verschiedenen Teiler übereinstimmt.
* Das Minimalpolynom von $x\in L$ (über $K$) ist das normierte Polynom $P\in K[X]$ von minimalem Grad mit $P(x)=0$.
* Ein quadratischer Zahlbereich ist der Ring der ganzen Zahlen in einem Erweiterungskörper von $\mathbb {Q}$ vom Grad $2$.
* Die (endliche) Anzahl des Restklassenringes $A_{D}/{\mathfrak {a}}$ heißt die Norm von ${\mathfrak {a}}$.
* Zu einer binären quadratischen Form nennt man die Diskriminante der Form.
    $aX^{2}+bXY+cY^{2}$
    $b^{2}-4ac$

### Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.
* Der Charakterisierungssatz für Einheiten modulo $n$.
* Das Bertrandsche Postulat.
* Der Satz über die Norm eines Hauptideals in einem quadratischen Zahlbereich $R$.
Lösung
* Genau dann ist $a\in \mathbb {Z}$ eine Einheit modulo $n$ (d.h. $a$ repräsentiert eine Einheit in $\mathbb {Z} /(n)$), wenn $a$ und $n$ teilerfremd sind.
* Für jede positive natürliche Zahl $n$ gibt es eine Primzahl zwischen $n+1$ und $2n$.
* Es sei $A_{D}$ ein quadratischer Zahlbereich und sei $f\neq 0$ ein Element. Setze ${\mathfrak {a}}=(f)$. Dann gilt $N({\mathfrak {a}})=\mid \!N(f)\!\mid$.

### Aufgabe (4 Punkte)

Zeige, dass ein euklidischer Bereich ein Hauptidealbereich ist.
Lösung
Es sei $I$ ein von $0$ verschiedenes Ideal. Betrachte die nichtleere Menge
    ${\left\{\delta (a)\mid a\in I,\,a\neq 0\right\}}.$
Diese Menge hat ein Minimum $m$, das von einem Element $b\in I,\,b\neq 0$, herrührt, sagen wir $m=\delta (b)$. Wir behaupten, dass $I=(b)$ ist. Dabei ist die Inklusion „$\supseteq$“ klar. Zum Beweis der Inklusion „$\subseteq$“ sei $a\in I$ gegeben. Aufgrund der Definition eines euklidischen Bereiches gilt $a=qb+r$ mit $r=0$ oder $\delta (r)<\delta (b)$. Wegen $r\in I$ und der Minimalität von $\delta (b)$ kann der zweite Fall nicht eintreten. Also ist $r=0$ und $a$ ist ein Vielfaches von $b$.

### Aufgabe (2 Punkte)

Bestimme die Primfaktorzerlegung von $10!$.
Lösung
Es ist
    $10!=10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=2\cdot 5\cdot 3^{2}\cdot 2^{3}\cdot 7\cdot 2\cdot 3\cdot 5\cdot 2^{2}\cdot 3\cdot 2=2^{8}\cdot 3^{4}\cdot 5^{2}\cdot 7\,.$

### Aufgabe (3 (1.5+1.5) Punkte)

(a) Bestimme für die Zahlen $3$, $11$ und $13$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
    $\mathbb {Z} /(3)\times \mathbb {Z} /(11)\times \mathbb {Z} /(13)$
die Restetupel $(1,0,0),\,(0,1,0)$ und $(0,0,1)$ repräsentieren.
(b) Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen
    $x=2\!\!\mod 3,\,\,\,\,x=5\!\!\mod 11{\text{ und }}x=6\!\!\mod 13.$
Lösung
a) $(1,0,0)$: Wir betrachten die Vielfachen von $11\cdot 13=143$, diese haben modulo $11$ und modulo $13$ den Rest $0$. Unter diesen Vielfachen muss also die Lösung liegen. $143$ hat modulo $3$ den Rest $2$, somit hat $286$ modulo $3$ den Rest $1$. Also repräsentiert $286$ das Restetupel $(1,0,0)$.
$(0,1,0)$: Hier betrachtet man die Vielfachen von $39$, und $39$ hat modulo $11$ den Rest $6$ und $2\cdot 39=78$ hat modulo $11$ den Rest $1$, also repräsentiert $78$ das Restetupel $(0,1,0)$.
$(0,0,1)$: Hier betrachtet man die Vielfachen von $33$, und $33$ hat modulo $13$ den Rest $7$ und $2\cdot 33=66$ hat modulo $13$ den Rest $1$, also repräsentiert $66$ das Restetupel $(0,0,1)$.
b) Man schreibt (in $\mathbb {Z} /(3)\times \mathbb {Z} /(11)\times \mathbb {Z} /(13)$)
    $(2,5,6)=2(1,0,0)+5(0,1,0)+6(0,0,1)\,.$
Die Lösung ist dann
    ${\begin{aligned}2\cdot 286+5\cdot 78+6\cdot 66&=572+390+396\\&=1358.\end{aligned}}$
Die minimale Lösung ist dann $1358-3\cdot 429=71$.

### Aufgabe (4 (1+1+1+1) Punkte)

Bestimme die Anzahl der primitiven Elemente in folgenden Körpern:
a) $\mathbb {Z} /(73)$,
b) ${\mathbb {F} }_{125}$,
c) ${\mathbb {F} }_{64}$,
d) $\mathbb {Z} /(113)$.
Lösung
Da die Einheitengruppe eines Körpers mit $n$ Elementen zyklisch ist, geht es um die Anzahl der Erzeuger von $\mathbb {Z} /(n-1)$, die mit der eulerschen $\varphi$-Funktion berechnet werden kann.
a) Es ist
    $72=2^{3}\cdot 3^{2}\,,$
die Anzahl der primitiven Elemente ist somit
    $4\cdot 2\cdot 3=24\,.$
b) Es ist
    $124=2^{2}\cdot 31\,,$
die Anzahl der primitiven Elemente ist somit
    $2\cdot 30=60\,.$
c) Es ist
    $63=3^{2}\cdot 7\,,$
die Anzahl der primitiven Elemente ist somit
    $2\cdot 3\cdot 6=36\,.$
d) Es ist
    $112=2^{4}\cdot 7\,,$
die Anzahl der primitiven Elemente ist somit
    $8\cdot 6=48\,.$

### Aufgabe (7 Punkte)

Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von $a$ und der andere ein Fassungsvermögen von $b$ Litern, wobei $a$ und $b$ teilerfremd seien. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.
Lösung
Ohne Einschränkung sei $a\leq b$. Wir bezeichnen die Inhalte in den Eimern zu einem bestimmten Zeitpunkt in Paarschreibweise mit $(u,v)$, wobei $u$ zwischen $0$ und $a$ und $v$ zwischen $0$ und $b$ liegt. Es sei $r$ der Rest von $-b$ bei Division durch $a$. Wir behaupten, dass wenn man die Belegung $(u,0)$ durch die erlaubten Schritte erzielen kann, dass man dann auch $(u',0)$ erzielen kann, wobei $u'$ den Rest von $u+r$ modulo $a$ bezeichnet. Wir starten also mit
    $(u,0).$
Durch Umschüttung kann man
    $(0,u)$
erreichen. Durch Auffüllen des kleinen Eimers und anschließende Umfüllung in den großen kann man
    $(0,u+a)$
erreichen, und ebenso der Reihe nach
    $(0,u+2a),\,(0,u+2a),\ldots ,(0,u+ka),$
wobei $k$ so gewählt sei, dass
    $u+ka\leq b\,$
und
    $u+(k+1)a>b\,$
sei. Von hier aus erreichen wir
    $(a,u+ka).$
Wir füllen nun den Inhalt des ersten Eimers in den zweiten, bis dieser voll ist. Es sei $m$ die umgefüllte Menge. Diese erfüllt
    $u+ka+m=b\,.$
Die im ersten Eimer verbleibende Wassermenge ist somit
    $a-m=a-(b-u-ka)=u+(k+1)a-b\,.$
Diese Menge ist also der Rest von $u-b=u+r$ modulo $a$, wie behauptet.
Aufgrund von dieser Beobachtung können wir der Reihe nach folgende Belegungen erzielen (bzw. die Reste davon modulo a).
    $(0,0),(r,0),(2r,0),(3r,0),\ldots .$
Da $b$ teilerfremd zu $a$ ist, gibt es nach dem Lemma von Bezout positive ganze Zahlen $n,m$ mit
    $ma-nb=1\,$
(Falls $n,m$ negativ sind, betrachtet man einfach $(sb+m)a-(sa+n)b=1$ für ein ausreichend großes $s$).
Somit ist modulo $a$
    $nr\equiv -nb=1-ma=1\,,$
sodass bei Division durch $a$ für ein gewisses $n$ der Rest von $nr$ gleich $1$ ist.

### Aufgabe (5 (2+3) Punkte)

Zu einer positiven natürlichen Zahl $n$ sei $a_{n}$ das kleinste gemeinsame Vielfache der Zahlen $1,2,3,\ldots ,n$.
* Was ist die kleinste Zahl $n$ mit
    $a_{n}=a_{n+1}=a_{n+2}\,?$
* Zeige, dass die Reihe konvergiert.
    $\sum _{n=1}^{\infty }{\frac {1}{a_{n}}}$
Lösung
* Genau dann ist wenn $n+1$ eine Primzahlpotenz $p^{k}$, $k\geq 1$, ($p$ Primzahl) ist, da diese nicht als Faktor einer kleineren Zahl auftauchen. Man muss also nach der kleinsten Folge von zwei Zahlen ohne Primzahlpotenzen suchen. Dies ist $14,15$, die Antwort ist also $13$.
    $a_{n+1}>a_{n}\,,$
* Für $n\geq 2$ ist $a_{n}$ insbesondere ein Vielfaches von $n$ und $n-1$. Da diese beiden Zahlen teilerfremd sind, ist $a_{n}$ ein Vielfaches von $n(n-1)$. Somit ist und Also ist Da die Kehrwerte der Quadratzahlen bekanntlich konvergieren, liegt nach dem Majorantenkriterium Konvergenz vor.
    $a_{n}\geq n(n-1)\,$
    ${\frac {1}{a_{n}}}\leq {\frac {1}{n(n-1)}}\,.$
    ${\begin{aligned}\sum _{n=1}^{\infty }{\frac {1}{a_{n}}}&\leq 1+\sum _{n=2}^{\infty }{\frac {1}{n(n-1)}}\\&\leq 1+\sum _{n=2}^{\infty }{\frac {1}{(n-1)^{2}}}\\&=1+\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}.\end{aligned}}$

### Aufgabe (4 Punkte)

Berechne das folgende Jacobi-Symbol mittels des quadratischen Reziprozitätsgesetzes, ohne dabei die Primfaktorzerlegung zu verwenden:
    $\left({\frac {1003}{4459}}\right).$
Lösung
Die Zahlen $1003$ und $4459$ haben beide modulo $4$ den Rest $3$. Somit ist
    $\left({\frac {1003}{4459}}\right)=-\left({\frac {4459}{1003}}\right)=-\left({\frac {447}{1003}}\right)\,.$
Die Zahl $447$ hat ebenfalls den Rest $3$ modulo $4$, also ist dies gleich
    $\left({\frac {1003}{447}}\right)=\left({\frac {109}{447}}\right)\,.$
Die Zahl $109$ hat den Rest $1$ modulo $4$, somit ist dies gleich
    ${\begin{aligned}\left({\frac {447}{109}}\right)&=\left({\frac {11}{109}}\right)\\&=\left({\frac {109}{11}}\right)\\&=\left({\frac {10}{11}}\right)\\&=\left({\frac {2}{11}}\right)\cdot \left({\frac {5}{11}}\right)\\&=\left({\frac {2}{11}}\right)\cdot \left({\frac {11}{5}}\right)\\&=\left({\frac {2}{11}}\right)\cdot \left({\frac {1}{5}}\right)\\&=\left({\frac {2}{11}}\right).\end{aligned}}$
Wegen $2^{5}=32=-1\mod 11$ ist dies nach dem Euler-Kriterium gleich $-1$.

### Aufgabe (5 Punkte)

Zeige, dass es kein rechtwinkliges Dreieck gibt, dessen Seitenlängen alle rational sind und dessen Flächeninhalt gleich $2$ ist.
Lösung
Wir nehmen an, dass es ein solches rechtwinkliges Dreieck gibt. Wir können die beteiligten rationalen Seitenlängen mit einem gemeinsamen Hauptnenner $h$ schreiben und setzen die Seitenlängen als ${\frac {a}{h}},{\frac {b}{h}},{\frac {c}{h}}$ an, mit
    $a^{2}+b^{2}=c^{2}\,.$
Die Flächenbedingung bedeutet
    ${\frac {1}{2}}\cdot {\frac {a}{h}}\cdot {\frac {b}{h}}=2\,$
bzw.
    $ab=4h^{2}\,.$
Wir lösen nach $b$ auf und erhalten
    $b={\frac {4h^{2}}{a}}\,$
und setzen dies in die pythagoreische Gleichung ein und erhalten
    $a^{2}+{\left({\frac {4h^{2}}{a}}\right)}^{2}=c^{2}\,$
bzw.
    $a^{4}+16h^{4}=a^{2}c^{2}\,.$
Dann wäre aber das Tripel $(a,2h,ac)$ eine nichttriviale Lösung der Gleichung
    $x^{4}+y^{4}=z^{2}\,,$
was es nach Fakt nicht geben kann.

### Aufgabe (10 (2+2+6) Punkte)

* Es sei $F$ ein normiertes Polynom aus $\mathbb {Z} [X]$ und es gebe eine Primzahl $q$ mit der Eigenschaft, dass $F$ modulo $q$, also aufgefasst in $\mathbb {Z} /(q)[X]$, irreduzibel sei. Zeige, dass dann schon $F$ irreduzibel ist.
* Zeige, dass die erste Aussage für ein nichtnormiertes Polynom nicht stimmen muss.
* Es sei $p$ eine Primzahl und $G\in \mathbb {Z} /(p)[X]$ ein normiertes Polynom. Zeige, dass es ein normiertes Polynom $F\in \mathbb {Z} [X]$ gibt, das modulo $p$ mit $G$ übereinstimmt und das zusätzlich irreduzibel ist.
Lösung
* Nehmen wir an, dass $F\in \mathbb {Z} [X]$ nicht irreduzibel ist. Es gibt dann eine Zerlegung in $\mathbb {Z} [X]$, wobei $G,H$ ebenfalls normierte Polynome sind, die einen kleineren Grad als $F$ besitzen. Da die Reduktion modulo $q$ ein Ringhomomorphismus ist, der für normierte Polynome den Grad unverändert lässt, folgt sofort eine Faktorzerlegung die der Irreduzibilität von ${\overline {F}}$ in $\mathbb {Z} /(q)[X]$ widerspricht.
    $F=GH\,$
    $\mathbb {Z} [X]\longrightarrow \mathbb {Z} /(q)[X],\,F\longmapsto {\overline {F}},$
    ${\overline {F}}={\overline {G}}\cdot {\overline {H}}\,,$
* Es sei $F=2X$, wobei diese Darstellung unmittelbar zeigt, dass $F$ nicht irreduzibel in $\mathbb {Z} [X]$ ist. Für $q=3$ ist die Reduktion modulo $3$ gleich $2X$, doch dies ist, da $2$ eine Einheit in $\mathbb {Z} /(3)$ ist, assoziiert zum irreduziblen Polynom $X$.
* Es sei nun $G\in \mathbb {Z} /(p)[X]$ ein normiertes Polynom vom Grad $n$. Es sei $q\neq p$ eine weitere Primzahl. Da es einen Körper $K$ mit $q^{n}$ Elementen gibt, und da die Einheitengruppe eines endlichen Körpers nach Fakt von einem Element erzeugt wird, ist $K$ eine einfache endliche Körpererweiterung von $\mathbb {Z} /(q)$. Also ist mit einem normierten irreduziblen Polynom $H\in \mathbb {Z} /(q)[X]$. Es sei ein normiertes ganzzahliges Polynom, das modulo $p$ mit $G$ übereinstimmt. Diese Eigenschaft ändert sich nicht, wenn wir Vielfache von $pX^{i}$ mit $i$ zwischen $0$ und $n-1$ dazuaddieren. Wir behaupten, dass wir durch solche Additionen erreichen können, dass die Reduktion modulo $q$ zum irreduzibeln Polynom $H$ wird. Aus Teil (1) folgt dann, dass dieses neue $G'$ irreduzibel ist. Die Abänderung können wir komponentenweise durchführen. Es sei mit $b_{i}\in \mathbb {Z} /(q)$. Da ${\overline {p}}$ in $\mathbb {Z} /(q)$ eine Einheit ist, erzeugt es als Gruppe $\mathbb {Z} /(q)$, d.h. $0,{\overline {p}},2{\overline {p}},\ldots$ durchläuft alle Elemente von $\mathbb {Z} /(q)$. Somit kann man durch Addition eines Vielfachen von $p$ erreichen, dass $a_{i}+kp$ modulo $q$ mit $b_{i}$ übereinstimmt.
    $K\cong \mathbb {Z} /(q)[X]/(H)\,$
    ${\tilde {G}}=X^{n}+a_{n-1}X^{n-1}+\cdots +a_{1}X+a_{0}\in \mathbb {Z} [X]\,$
    $H=X^{n}+b_{n-1}X^{n-1}+\cdots +b_{1}X+b_{0}\in \mathbb {Z} [X]\,$

### Aufgabe (4 Punkte)

Zeige, dass jedes Ideal ${\mathfrak {a}}\neq 0$ in einem Zahlbereich $R$ eine ganze Zahl $m\neq 0$ enthält.
Lösung
Sei $0\neq f\in {\mathfrak {a}}$. Dieses Element ist nach der Definition eines Zahlbereiches ganz über $\mathbb {Z}$ und erfüllt demnach eine Ganzheitsgleichung
    $f^{n}+k_{n-1}f^{n-1}+k_{n-2}f^{n-2}+\cdots +k_{1}f+k_{0}=0\,$
mit ganzen Zahlen $k_{i}$. Bei $k_{0}=0$ kann man die Gleichung mit $f$ kürzen, da $f\neq 0$ ein Nichtnullteiler ist. So kann man sukzessive fortfahren und erhält schließlich eine Ganzheitsgleichung, bei der der konstante Term nicht $0$ ist. Es sei also in obiger Gleichung $k_{0}\neq 0$. Dann ist
    $f{\left(f^{n-1}+k_{n-1}f^{n-2}+k_{n-2}f^{n-3}+\cdots +k_{1}\right)}=-k_{0}\,$
und somit ist $k_{0}\in (f)\cap \mathbb {Z} \subseteq {\mathfrak {a}}$.

### Aufgabe (4 Punkte)

Es sei $R$ ein Zahlbereich und seien $f,g\in \mathbb {Z}$ teilerfremde Zahlen. Zeige, dass für den (im Quotientenkörper $Q(R)$ genommenen) Durchschnitt
    $R_{f}\cap R_{g}=R\,$
gilt.
Lösung
Sei
    $q\in R_{g}\cap R_{f}.$
Das bedeutet, dass es Zähler $a,b\in R$ und Exponenten $r,s\in \mathbb {N}$ gibt, dass
    $q={\frac {a}{g^{r}}}={\frac {b}{f^{s}}}\,$
gilt. Da $g$ und $f$ teilerfremd sind, sind auch $g^{r}$ und $f^{s}$ teilerfremd und somit gibt es nach dem Lemma von Bezout ganze Zahlen $u,v\in \mathbb {Z}$ mit
    $ug^{r}+vf^{s}=1\,.$
Somit ist
    ${\begin{aligned}q&=q\cdot 1\\&=q\cdot {\left(ug^{r}+vf^{s}\right)}\\&={\frac {a}{g^{r}}}ug^{r}+{\frac {b}{f^{s}}}vf^{s}\\&=au+bv,\end{aligned}}$
und dies gehört zu $R$.

### Aufgabe (2 Punkte)

Bestimme einen Erzeuger für das gebrochene Ideal ${\mathfrak {f}}\subseteq \mathbb {Q}$, das durch die rationalen Zahlen
    ${\frac {3}{7}},\,{\frac {5}{6}},\,{\frac {3}{10}}\,$
erzeugt wird.
Lösung
Wir bringen die drei Brüche auf einen Hauptnenner, was
    ${\frac {90}{210}},\,{\frac {175}{210}},\,{\frac {63}{210}}$
ergibt. Der größte gemeinsame Teiler der beiden ersten Zähler ist $5$. Da dies teilerfremd zu $63$ ist, sind die drei Zähler insgesamt teilerfremd. Daher wird das gebrochene Ideal durch ${\frac {1}{210}}$ erzeugt.

### Aufgabe (4 Punkte)

Es sei $R$ ein quadratischer Zahlbereich und ${\mathfrak {a}}\neq 0$ ein Ideal in $R$. Zeige, dass es ein Element $f\in {\mathfrak {a}}$ mit der Eigenschaft gibt, dass für alle maximale Ideale ${\mathfrak {m}}$ gilt:
    $f\in {\mathfrak {m}}{\text{ genau dann, wenn }}{\mathfrak {a}}\subseteq {\mathfrak {m}}.$
Lösung
Da die Idealklassengruppe von $R$ endlich ist, gibt es ein $n\in \mathbb {N} _{+}$ derart, dass die $n$-te Potenz von ${\mathfrak {a}}$ ein Hauptideal ist. Somit ist
    ${\mathfrak {a}}^{n}=(g)\,$
mit einem gewissen $g\in R$, $g\neq 0$. Da ${\mathfrak {a}}$ und ${\mathfrak {a}}^{n}$ das gleiche Radikal besitzen, ist
    $f=g^{k}\in {\mathfrak {a}}\,$
für ein gewisses $k$. Somit stimmen die Radikale zu ${\mathfrak {a}}$, zu ${\mathfrak {a}}^{n}$, zu $(g)$ und zu $(f)$ überein. Für ein maximales Ideal ${\mathfrak {m}}$ gilt nun ${\mathfrak {a}}\subseteq {\mathfrak {m}}$ genau dann, wenn ${\mathfrak {a}}^{n}\subseteq {\mathfrak {m}}$ genau dann, wenn $g\in {\mathfrak {m}}$ genau dann, wenn $f\in {\mathfrak {m}}$.