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

Definiere die folgenden (kursiv gedruckten) Begriffe.
* Ein Integritätsbereich.
* Eine Sophie-Germain-Primzahl.
* Der Quotientenkörper zu einem kommutativen Ring $R$.
* Ein $R$-Modul $M$ über einem kommutativen Ring $R$.
* Ein (ganzer) Zahlbereich.
* Das Ideal zu einem effektiven Divisor $D$ in einem Zahlbereich $R$.
Lösung
* Ein kommutativer, nullteilerfreier, von null verschiedener Ring heißt Integritätsbereich.
* Eine Sophie-Germain-Primzahl ist eine Primzahl $p$ mit der Eigenschaft, dass auch $2p+1$ eine Primzahl ist.
* Zu einem Integritätsbereich $R$ ist der Quotientenkörper $Q(R)$ als die Menge der formalen Brüche mit natürlichen Identifizierungen und Operationen definiert.
    $Q(R)={\left\{{\frac {r}{s}}\mid r,s\in R,\,s\neq 0\right\}}\,$
* Man nennt $M$ einen $R$-Modul, wenn eine Operation festgelegt ist, die folgende Axiome erfüllt (dabei seien $r,s\in R$ und $u,v\in M$ beliebig):
    $R\times M\longrightarrow M,\,(r,v)\longmapsto rv=r\cdot v,$
** $r(su)=(rs)u$,
** $r(u+v)=(ru)+(rv)$,
** $(r+s)u=(ru)+(su)$,
** $1u=u$.
* Unter einem Zahlbereich versteht man den ganzen Abschluss von $\mathbb {Z}$ in $L$, wobei $\mathbb {Q} \subseteq L$ eine endliche Körpererweiterung ist.
* Zu einem effektiven Divisor nennt man das Ideal zum Divisor $D$.
    $D=\sum _{\mathfrak {p}}n_{\mathfrak {p}}\cdot {\mathfrak {p}}\,$
    ${\left\{f\in R\mid \operatorname {div} (f)\geq D\right\}}$

### Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.
* Der Chinesische Restsatz für $\mathbb {Z}$.
* Der Satz über die Charakterisierung von Carmichael-Zahlen.
* Der Satz über die Potenzen von Idealen in einem quadratischen Zahlbereich.
Lösung
* Es sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung $n=p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}{\cdots }p_{k}^{r_{k}}$. Dann induzieren die kanonischen Ringhomomorphismen $\mathbb {Z} /(n)\rightarrow \mathbb {Z} /(p_{i}^{r_{i}})$ einen Ringisomorphismus
    $\mathbb {Z} /(n)\cong \mathbb {Z} /(p_{1}^{r_{1}})\times \mathbb {Z} /(p_{2}^{r_{2}})\times \cdots \times \mathbb {Z} /(p_{k}^{r_{k}})\,.$
* Eine natürliche nicht-prime Zahl $n\geq 2$ ist genau dann eine Carmichael-Zahl, wenn jeder Primteiler $p$ von $n$ einfach ist und $p-1$ die Zahl $n-1$ teilt.
* Sei $R=A_{D}$ ein quadratischer Zahlbereich und sei ${\mathfrak {a}}$ ein Ideal in $R$. Dann gibt es ein $n\geq 1$ derart, dass ${\mathfrak {a}}^{n}$ ein Hauptideal ist.

### Aufgabe (6 Punkte)

Es seien $\ell ,m\in \mathbb {N} _{+}$ und es sei $x$ die Zahl mit $\ell$ Neunen und $y$ die Zahl mit $m$ Neunen (im Zehnersystem). Zeige, dass $y$ genau dann von $x$ geteilt wird, wenn $m$ von $\ell$ geteilt wird.
Lösung
Wir schreiben
    $x=10^{\ell }-1\,$
und
    $y=10^{m}-1\,.$
Es sei zuerst $\ell$ ein Teiler von $m$, also
    $m=\ell k\,.$
Dann ist
    ${\begin{aligned}y&=10^{m}-1\\&=10^{\ell k}-1\\&={\left(10^{\ell }\right)}^{k}-1\\&={\left(10^{\ell }-1\right)}\cdot {\left(10^{(k-1)\ell }+\cdots +10^{2\ell }+10^{\ell }+1\right)},\end{aligned}}$
also ist $x$ ein Teiler von $y$.
Für die Umkehrung schreiben wir
    $m=\ell k+r\,$
mit $0\leq r<\ell$ und setzen voraus, dass $y$ von $x$ geteilt wird. Es ist $r=0$ zu zeigen. Es ist
    ${\begin{aligned}y&=10^{m}-1\\&=10^{\ell k+r}-1\\&=10^{\ell k}\cdot 10^{r}-1\\&={\left(10^{\ell k}-1\right)}\cdot 10^{r}+10^{r}-1.\end{aligned}}$
Nach der Hinrichtung ist der linke Faktor des linken Summanden ein Vielfaches von $10^{\ell }-1$. Wenn auch $y$ ein Vielfaches von $10^{\ell }-1$ ist, so muss auch die Differenz, also $10^{r}-1$ ein Vielfaches von $10^{\ell }-1$ sein. Dies kann aber aus Größengründen nur bei $r=0$ sein.

### Aufgabe (4 Punkte)

Finde unter den Zahlen $\leq 1000$ diejenige Zahl mit der maximalen Anzahl an Teilern.
Lösung
Wir betrachten direkt die Primfaktorzerlegungen
    $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\,,$
    $(k_{1}+1)(k_{2}+1)\cdots (k_{r}+1)$
$n$
    $k_{1}\geq k_{2}\geq \ldots \geq k_{r}\,$
annehmen. Bei $r=1$ ist
    $2^{9}=512<1000\,,$
welches $10$ Teiler besitzt, $2^{10}$ ist schon zu groß. Bei $r=2$ besitzt (wir führen nur ernsthafte Kandidaten auf)
    $2^{8}\cdot 3=768\,$
$18$ Teiler,
    $2^{6}\cdot 3^{2}=576\,$
hat $21$ Teiler,
    $2^{5}3^{3}=864\,$
hat $24$ Teiler,
    $2^{4}3^{4}=1296>1000\,.$
Bei $r=3$ besitzt
    $2^{6}\cdot 3\cdot 5=960\,$
$28$ Teiler,
    $2^{4}\cdot 3^{2}\cdot 5=720\,$
hat $30$ Teiler,
    $2^{3}\cdot 3^{3}\cdot 5=1080\,$
ist zu groß,
    $2^{2}\cdot 3^{2}\cdot 5^{2}=900\,$
hat $27$ Teiler. Bei $r=3$ besitzt
    $2^{3}\cdot 3\cdot 5\cdot 7=840\,$
$32$ Teiler.
    $2^{2}\cdot 3^{2}\cdot 5\cdot 7=1260\,$
ist zu groß. Wegen
    $2\cdot 3\cdot 5\cdot 7\cdot 11=2310>1000\,$
kann es nicht mehr Primfaktoren geben. Also besitzt $840$ unter allen Zahlen unterhalb von $1000$ die maximale Anzahl an Teilern, nämlich $32$.

### Aufgabe (3 Punkte)

Bestimme in $\mathbb {Z} [{\mathrm {i} }]$ die Primfaktorzerlegung von $8-{\mathrm {i} }$. Begründe, warum die Faktoren prim sind.
Lösung
Wir haben
    $(8-{\mathrm {i} })(8+{\mathrm {i} })=65=5\cdot 13\,.$
Beide Primfaktoren der Norm haben also den Rest $1$ modulo $4$ und sind damit zerlegt im Ring der ganzen Gaußschen Zahlen. Es ist $5=(2+{\mathrm {i} })(2-{\mathrm {i} })$ und $13=(3+2{\mathrm {i} })(3-2{\mathrm {i} })$, und diese Faktoren sind prim nach Fakt. Die Primfaktorzerlegung von $8-{\mathrm {i} }$ muss also (bis auf eine Einheit) aus einem Primfaktor von $5$ und einem Primfaktor von $13$ bestehen.
Die eine Möglichkeit ist
    $(2+{\mathrm {i} })(3+2{\mathrm {i} })=4+7{\mathrm {i} }\,,$
die aber nicht zu $8-{\mathrm {i} }$ assoziiert ist. Die andere Möglichkeit ist
    $(2+{\mathrm {i} })(3-2{\mathrm {i} })=8-{\mathrm {i} }\,,$
die die gesuchte Primfaktorzerlegung ist.

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

a) Bestimme die primitiven Elemente von $\mathbb {Z} /(11)$.
b) Man gebe einen Gruppenisomorphismus der additiven Gruppe $(\mathbb {Z} /(10),+)$ in die Einheitengruppe ${\left(\mathbb {Z} /(11)\right)}^{\times }$ an.
c) Bestimme für jede Einheit aus $\mathbb {Z} /(11)$ die Ordnung.
Lösung Restklassenringe von Z/mod 11/Primitives Element/Isomorphismus der Einheitengruppe zu Z mod 10/Ordnungen/Aufgabe/Lösung

### Aufgabe (4 Punkte)

Berechne mit Hilfe des quadratischen Reziprozitätsgesetzes und seiner Ergänzungssätze das Legendre-Symbol
    $\left({\frac {53}{311}}\right).$
Lösung
Wir berechnen Schritt für Schritt das Legendre-Symbol.
    ${\begin{aligned}\left({\frac {53}{311}}\right)&=\left({\frac {311}{53}}\right)\\&=\left({\frac {46}{53}}\right)\\&=\left({\frac {2}{53}}\right)\left({\frac {23}{53}}\right)\\&=-\left({\frac {23}{53}}\right)\\&=-\left({\frac {53}{23}}\right)\\&=-\left({\frac {7}{23}}\right)\\&=\left({\frac {23}{7}}\right)\\&=\left({\frac {2}{7}}\right)\\&=1.\end{aligned}}$
Also ist $53$ ein Quadratrest modulo $311$.

### Aufgabe (4 Punkte)

Beschreibe mittels geeigneter Kongruenzbedingungen diejenigen ungeraden Primzahlen $p$ mit der Eigenschaft, dass $7$ ein Quadratrest modulo $p$ ist.
Gibt es unendlich viele solche Primzahlen?
Lösung
$7$ ist selbst ein Quadratrest modulo $7$, sodass wir im Folgenden annehmen, dass $p$ teilerfremd zu $7$ ist.
Wir benutzen das quadratische Reziprozitätsgesetz und zwar zunächst für den Fall $p=3\mod 4$. Dann ist
    $\left({\frac {7}{p}}\right)=-\left({\frac {p}{7}}\right)=-\left({\frac {p\mod 7}{7}}\right)\,.$
Die Nichtquadrate modulo $7$ sind $3,5,6$. Wir müssen also eine Bedingung dafür finden, dass $p=3\mod 4$ und gleichzeitig $p=3,5,6\mod 7$ ist. Mit dem Chinesischen Restsatz ergibt sich die Kongruenzbedingung
    $p=3,19,27\mod 28.$
Für den Fall $p=1\mod 4$ ist
    $\left({\frac {7}{p}}\right)=\left({\frac {p}{7}}\right)=\left({\frac {p\mod 7}{7}}\right)\,.$
Die Quadrate modulo $7$, die zugleich Einheiten sind ($p=7$ ist ausgeschlossen), sind $1,2,4$. Wir müssen also eine Bedingung finden, dass $p=1\mod 4$ und zugleich $p=1,2,4\mod 7$ ist. Mit dem Chinesischen Restsatz ergibt sich die Kongruenzbedingung
    $p=1,9,25\mod 28.$
Insgesamt hat man also die sieben Möglichkeiten
    $p=1,3,7,9,19,25,27\mod 28.$
Da diese Zahlen (bis auf $7$) teilerfremd zu $28$ sind, folgt aus dem Satz von Dirichlet über arithmetische Progressionen, dass es unendlich viele solche Primzahlen gibt.

### Aufgabe (4 Punkte)

Es sei $p\in \mathbb {Z}$ eine Primzahl und $n\in \mathbb {N} _{+}$. Zeige, dass der Restklassenring $\mathbb {Z} /(p^{n})$ nur die beiden trivialen idempotenten Elemente $0$ und $1$ besitzt.
Lösung
Es sei $e\in \mathbb {Z} /(p^{n})$ ein idempotentes Element. Dies bedeutet
    $e^{2}=e\,$
und somit ist $e(e-1)$ ein Vielfaches von $p^{n}$, sagen wir
    $e(e-1)=ap^{n}\,.$
Nehmen wir $e\neq 0,1$ an. Wegen der eindeutigen Primfaktorzerlegung in $\mathbb {Z}$ ist
    $e=bp^{i}\,$
und
    $e-1=cp^{j}\,$
mit
    $i+j=n\,.$
Wären $i,j\geq 1$, so wäre sowohl $e$ als auch $e-1$ ein Vielfaches von $p$, und das würde dann auch für $1=e-(e-1)$ gelten, was nicht der Fall ist. Also ist $i=n$ oder $j=n$, was $e=0$ oder $e-1=0$ im Restklassenring $\mathbb {Z} /(p^{n})$ bedeutet.

### Aufgabe (4 Punkte)

Zeige: Für eine Primzahl $p$ ist die Mersennesche Zahl $M_{p}$ quasiprim zur Basis $2$.
Lösung
Wir haben zu zeigen, dass für $m=2^{p}-1$ gilt: $2^{m-1}=1$ modulo $m$. Es ist $2^{p}=2$ modulo $p$ nach dem kleinen Fermat. Damit ist $m-1=2^{p}-2=0$ modulo $p$. Also ist $m-1$ ein Vielfaches von $p$, sagen wir $m-1=ap$. Wegen $2^{p}=1$ modulo $m$ gilt dann $2^{m-1}=(2^{p})^{a}=1$ modulo $m$.

### Aufgabe (4 Punkte)

Es sei $R$ ein kommutativer Ring und ${\mathfrak {p}}$ ein Ideal. Zeige, dass ${\mathfrak {p}}$ genau dann ein Primideal ist, wenn der Restklassenring $R/{\mathfrak {p}}$ ein Integritätsbereich ist.
Lösung
Es sei zunächst ${\mathfrak {p}}$ ein Primideal. Dann ist insbesondere
${\mathfrak {p}}\subset R$ und somit ist der Restklassenring $R/{\mathfrak {p}}$ nicht der Nullring. Sei $fg=0$ in $R/{\mathfrak {p}}$ wobei $f,g$ durch Elemente in $R$ repräsentiert seien. Dann ist $fg\in {\mathfrak {p}}$ und damit $f\in {\mathfrak {p}}$ oder $g\in {\mathfrak {p}}$. was in $R/{\mathfrak {p}}$ gerade $f=0$ oder $g=0$ bedeutet.
Ist umgekehrt $R/{\mathfrak {p}}$ ein Integritätsbereich, so handelt es sich nicht um den Nullring und daher ist ${\mathfrak {p}}\neq R$. Sei $f,g\notin {\mathfrak {p}}$. Dann ist $f,g\neq 0$ in $R/{\mathfrak {p}}$ und daher $fg\neq 0$ in $R/{\mathfrak {p}}$, also ist $fg\notin {\mathfrak {p}}$.

### Aufgabe (3 Punkte)

Es sei $p$ eine Primzahl, $q=p^{e}$ mit $e\geq 1$ und sei ${\mathbb {F} }_{q}$ der Körper mit $q$ Elementen und $R={\mathbb {F} }_{q}[X]$ der Polynomring darüber. Zeige, dass jeder Restklassenring $R/{\mathfrak {a}}$ zu einem Ideal ${\mathfrak {a}}\neq 0$ endlich ist.
Lösung
Sei ${\mathfrak {a}}\neq 0$ ein Ideal. Der Polynomring über einem Körper ist ein Hauptidealbereich, daher ist ${\mathfrak {a}}=(P)$ mit einem Polynom $P\neq 0$. Man kann annehmen, dass $P$ normiert ist, dass also der Leitkoeffizient $1$ ist. Dann ist
    $R/{\mathfrak {a}}=R/(P)={\mathbb {F} }_{q}[X]/(X^{n}+a_{n-1}X^{n-1}+\cdots +a_{1}X+a_{0})\,.$
Dies bedeutet, dass man im Restklassenring die Potenz $X^{n}<$ durch kleinere Potenzen ausdrücken kann. Iterativ kann man dann überhaupt jede Potenz $X^{k}$ durch Polynome vom Grad $\leq n-1$ ausdrücken, d.h. die Potenzen $X^{0},X^{1},\ldots ,X^{n-1}$ bilden ein ${\mathbb {F} }_{q}$-Erzeugendensystem (sogar eine Basis) dieser ${\mathbb {F} }_{q}$-Algebra. Damit liegt ein endlichdimensionaler Vektorraum über einem endlichen Körper vor, und dieser hat nur endlich viele Elemente.

### Aufgabe (6 Punkte)

Man gebe ein Beispiel von zwei Zahlbereichen $R$ und $S$, die als Ringe nicht isomorph sind, aber die Eigenschaft haben, dass sowohl die additiven Strukturen $(R,+,0)$ und $(S,+,0)$ als Gruppen isomorph als auch die multiplikativen Strukturen $(R,\cdot ,1)$ und $(S,\cdot ,1)$ als Monoide isomorph sind.
Lösung
Wir suchen unter den quadratischen Zahlbereichen. Nach Fakt ist ihre additive Struktur stets gleich $\mathbb {Z} ^{2}$, einen additiven Isomorphismus gibt es also stets. Zu verschiedenen quadratfreien Zahlen $D,E\neq 0,1$ sind die Ringe $A_{D}$ und $A_{E}$ nicht isomorph, da in $A_{D}$ die Zahl $E$ keine Quadratwurzel besitzt (dies gilt sogar in den Quotientenkörpern, und ein Ringisomorphismus der Ringe würde einen Körperisomorphismus auf den Quotientenkörpern induzieren). Um einen Isomorphismus der multiplikativen Struktur zu erhalten, such wir nach Beispielen, wo diese besonders einfach ist. Dies trifft im faktoriellen Fall zu, dann dann jedes von $0$ verschiedene Element $f$ eine Darstellung
    $f=up_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\,$
mit einer Einheit $u$ besitzt, und wobei die $p_{i}$ bis auf Assoziiertheit eindeitg bestimmt sind. Um Komplikationen mit Einheiten aus dem Weg zu gehen, betrachten wir imaginär-quadratische Zahlkörper zu
    $D\leq -5\,,$
da dort nur $1$ und $-1$ Einheiten sind. Somit betrachten wir die beiden quadratischen Zahlbereiche $A_{D}$ zu $D=-7$ und $D=-11$, die nach Fakt faktoriell sind. In beiden Ringen gibt es abzählbar unendlich viele Primelemente und man wählt in beiden Ringen Assoziiertheitsklassen
$p_{n}\in A_{-7},\,n\in \mathbb {N} ,$ bzw. $q_{n}\in A_{-11},\,n\in \mathbb {N} ,$ aus Primelementen aus. Dann erhält man durch die Zuordnung
    $A_{-7}\longrightarrow A_{-11},\,\pm \prod _{n\in \mathbb {N} }p_{n}^{k_{n}}\longmapsto \pm \prod _{n\in \mathbb {N} }q_{n}^{k_{n}}$
(und $0$ auf $0$) einen Monoidisomorphismus.

### Aufgabe (4 Punkte)

Es sei $R=\mathbb {Z} [{\mathrm {i} }]$. Berechne einen Erzeuger für das gebrochene Ideal aus $Q(R)=\mathbb {Q} [{\mathrm {i} }]$, das durch die beiden Erzeuger
    ${\frac {5}{7}}\,\,{\text{ und }}\,\,{\frac {-8+6{\mathrm {i} }}{5}}$
gegeben ist.
Lösung
Man bringt die beiden Erzeuger auf den Hauptnenner, also
    ${\frac {25}{35}}\,{\text{ und }}{\frac {-56+42{\mathrm {i} }}{35}}.$
Von den beiden Zählern muss man den größten gemeinsamen Teiler mit Hilfe des Euklidischen Algorithmus ausrechnen.
Zunächst ist
    $-56+42{\mathrm {i} }=25(-2+2{\mathrm {i} })-6-8{\mathrm {i} }.$
(Da $25$ ganzzahlig ist, kann man direkt eine gute Approximation sehen).
Im nächsten Schritt bilden wir den Quotienten
    ${\frac {25}{-6-8{\mathrm {i} }}}={\frac {25(-6+8{\mathrm {i} })}{(-6-8{\mathrm {i} })(-6+8{\mathrm {i} })}}={\frac {-150+200{\mathrm {i} }}{100}}=-1+2{\mathrm {i} }-{\frac {1}{2}}\,,$
Multiplikation mit dem Nenner ergibt:
    $25=(-1+2{\mathrm {i} })(-6-8{\mathrm {i} })+3+4{\mathrm {i} }.$
Der nächste Schritt liefert
    $-6-8{\mathrm {i} }=-2(3+4{\mathrm {i} }).$
Also ist $3+4{\mathrm {i} }$ der größte gemeinsame Teiler und damit ist
    ${\frac {3+4{\mathrm {i} }}{35}}$
der Erzeuger des gebrochenen Ideals.

### Aufgabe (5 Punkte)

Es sei $R$ ein quadratischer Zahlbereich. Zeige, dass es ein $f\in R$, $f\neq 0$, mit der Eigenschaft gibt, dass die Nenneraufnahme $R_{f}$ faktoriell ist.
Lösung Quadratischer Zahlbereich/Nenneraufnahme/Faktoriell/Aufgabe/Lösung

### Aufgabe (3 Punkte)

Ergänze die Matrix
    ${\begin{pmatrix}7892&1551\\&\end{pmatrix}}$
zu einer ganzzahligen Matrix mit Determinante $1$.
Lösung 2x2-Matrix/Zeile/Ergänze/2/Aufgabe/Lösung