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

Definiere die folgenden (kursiv gedruckten) Begriffe.
* Ein Ideal ${\mathfrak {a}}\subseteq R$ in einem kommutativen Ring $R$.
* Eine primitive Einheit in ${\left(\mathbb {Z} /(n)\right)}^{\times }$.
* Das Legendre-Symbol.
* Ein pythagoreisches Tripel.
* Eine Mersennesche Primzahl.
* Eine Carmichael-Zahl.
Lösung
* Ein Ideal ist eine nichtleere Teilmenge ${\mathfrak {a}}\subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
** Für alle $a,b\in {\mathfrak {a}}$ ist auch $a+b\in {\mathfrak {a}}$.
** Für alle $a\in {\mathfrak {a}}$ und $r\in R$ ist auch $ra\in {\mathfrak {a}}$.
* Eine Einheit $u\in {\left(\mathbb {Z} /(n)\right)}^{\times }$ heißt primitiv, wenn sie die Einheitengruppe erzeugt.
* Für eine ungerade Primzahl $p$ und eine zu $p$ teilerfremde Zahl $k\in \mathbb {Z}$ definiert man das Legendre-Symbol durch
    $\left({\frac {k}{p}}\right):={\begin{cases}1,{\text{ falls }}k{\text{ quadratischer Rest modulo }}p{\text{ ist}},\\-1,{\text{ falls }}k{\text{ kein quadratischer Rest modulo }}p{\text{ ist}}.\end{cases}}\,$
* Ein pythagoreisches Tripel ist eine ganzzahlige Lösung $(x,y,z)\in \mathbb {Z} ^{3}$ der diophantischen Gleichung
    $x^{2}+y^{2}=z^{2}\,.$
* Eine Primzahl der Form $2^{n}-1$ heißt Mersennesche Primzahl.
* Eine natürliche Zahl $n$, die nicht prim ist, und die die Eigenschaft besitzt, dass für jede zu $n$ teilerfremde ganze Zahl $a$ gilt, heißt Carmichael-Zahl.
    $a^{n-1}=1\mod n\,$

### Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.
* Das Lemma von Euklid für einen Hauptidealbereich.
* Der kleine Fermat.
* Der Primzahlsatz.
Lösung
* Es sei $R$ ein Hauptidealbereich und $a,b,c\in R$. Es seien $a$ und $b$ teilerfremd und $a$ teile das Produkt $bc$. Dann teilt $a$ den Faktor $c$.
* Für eine Primzahl $p$ und eine beliebige ganze Zahl $a$ gilt
    $a^{p}\equiv a\mod p.$
* Es gilt die asymptotische Abschätzung Das heißt
    $\pi (x)\sim {\frac {x}{\ln(x)}}\,.$
    $\lim _{x\rightarrow \infty }{\frac {\pi (x)}{\frac {x}{\ln(x)}}}=\lim _{x\rightarrow \infty }{\frac {\pi (x)\ln(x)}{x}}=1\,.$

### 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
    $7=4+1+1+1\,$
darstellbar mit vier Quadraten. Die einzigen Quadrate unterhalb von $7$ sind $0,1,4$. Die $0$ trägt nicht zu einer minimalen Darstellung bei. Zweimal die $4$ ist schon zu groß, daher gibt es keine Darstellung als Summe von drei Quadraten.

### Aufgabe (5 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 (4 Punkte)

Bestimme in $\mathbb {Z} [{\mathrm {i} }]$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von $23+2{\mathrm {i} }$ und $1+23{\mathrm {i} }$.
Lösung
Wir multiplizieren die zweite Zahl mit der Einheit $-{\mathrm {i} }$ und erhalten $23-{\mathrm {i} }$. Damit ist
    $23+2{\mathrm {i} }=1(23-{\mathrm {i} })+3{\mathrm {i} }\,.$
Im nächsten Schritt ist (wir können mit $3$ statt mit $3{\mathrm {i} }$ arbeiten)
    ${\frac {23-{\mathrm {i} }}{3}}=7+{\frac {2}{3}}-{\frac {\mathrm {i} }{3}}\,$
bzw.
    $23-{\mathrm {i} }=7\cdot 3+2-{\mathrm {i} }\,.$
Weiter ist
    $3=(2-{\mathrm {i} })+1+{\mathrm {i} }\,$
und
    $(2-{\mathrm {i} })=(1+{\mathrm {i} })(1-{\mathrm {i} })-{\mathrm {i} }\,,$
sodass also Teilerfremdheit vorliegt.

### Aufgabe (4 Punkte)

Beweise das Lemma von Euklid für einen Hauptidealbereich.
Lösung
Da $a$ und $b$ teilerfremd sind, gibt es nach dem Lemma von Bezout Elemente $r,s\in R$ mit $ra+sb=1$. Die Voraussetzung, dass $a$ das Produkt $bc$ teilt, schreiben wir als $bc=da$. Damit gilt
    $c=c1=c(ra+sb)=cra+csb=acr+ads=a(cr+ds)\,,$
was zeigt, dass $c$ ein Vielfaches von $a$ ist.

### Aufgabe (3 Punkte)

Beweise den Satz, dass für einen endlichen Körper $K$ das Produkt aller von $0$ verschiedener Elemente aus $K$ gleich $-1$ ist.
Lösung
Die Gleichung $x^{2}=1$ hat in einem Körper nur die Lösungen $1$ und $-1$, die allerdings gleich sein können. Das bedeutet, dass für $x\neq 1,-1$ immer $x\neq x^{-1}$ ist. Damit kann man das Produkt aller Einheiten als
    $1(-1)x_{1}x_{1}^{-1}\cdots x_{k}x_{k}^{-1}$
schreiben. Ist $-1\neq 1$, so ist das Produkt $-1$. Ist hingegen $-1=1$, so fehlt in dem Produkt der zweite Faktor und das Produkt ist $1=-1$.

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

In dieser Aufgabe geht es um den Restklassenring $\mathbb {Z} /(360)$.
a) Schreibe $\mathbb {Z} /(360)$ als Produktring (im Sinne des chinesischen Restsatzes).
b) Wie viele Einheiten besitzt $\mathbb {Z} /(360)$?
c) Schreibe das Element $239$ in komponentenweiser Darstellung. Begründe, warum es sich um eine Einheit handelt und finde das Inverse in komponentenweiser Darstellung.
d) Berechne die Ordnung von $239$ in $\mathbb {Z} /(360)$.
Lösung
a) Es ist
    $360=2^{3}\cdot 3^{2}\cdot 5\,,$
daher ist
    $\mathbb {Z} /(360)=\mathbb {Z} /(8)\times \mathbb {Z} /(9)\times \mathbb {Z} /(5)\,.$
b) Nach der Formel für die eulersche $\varphi$-Funktion ist die Anzahl der Einheiten gleich
    $\varphi (360)=4\cdot 6\cdot 4=96\,.$
c) Die Reste von $239$ modulo $8,9$ und $5$ sind
    $(7,5,4).$
Da jede Komponente teilerfremd zu den zugehörigen Modulozahlen sind, handelt sich es sich insgesamt um eine Einheit. Das Inverse ist
    $(7,2,4).$
d) Zur Berechnung der Ordnung von $239$ modulo $360$ schreiben wir
    $(7,5,4)=(-1,5,-1)\,.$
Die Ordnung in der ersten und der dritten Komponente ist $2$, die Ordnung in der zweiten Komponente ist wegen $5^{2}=7$, $5^{3}=35=-1$ gleich $6$, da ja $\mathbb {Z} /(9)^{\times }$ die Ordnung $6$ besitzt. Daher ist die Ordnung von $239$ gleich $6$.

### Aufgabe (2 Punkte)

Bestimme die Anzahl der hinteren Nullen in der Dezimalentwicklung von $100!$.
Lösung
Die $5$ kommt in den $20$ Zahlen $5,10,\ldots ,100$ jeweils einmal vor und in $25,50,75,100$ nochmal zusätzlich mit einer weiteren Potenz. In $100!$ kommt also der Primfaktor $5$ mit dem Exponenten $24$ vor. Wegen der $50$ geraden Zahlen kommt der Primfaktor $2$ öfters vor. In $100!$ ist also $10^{24}$ die größte Zehnerpotenz und somit besitzt $100!$ genau $24$ Nullen am Ende.

### Aufgabe (3 Punkte)

Man gebe ein Polynom $P\in \mathbb {Q} [X]$ an, das nicht zu $\mathbb {Z} [X]$ gehört, aber die Eigenschaft besitzt, dass für jede ganze Zahl $n$ gilt: $P(n)\in \mathbb {Z}$.
Lösung
Betrachte das Polynom
    $P={\frac {X(X-1)}{2}}={\frac {X^{2}}{2}}-{\frac {X}{2}}\,.$
Die Koeffizienten liegen in $\mathbb {Q}$, aber nicht in $\mathbb {Z}$. Wenn man in dieses Polynom eine ganze Zahl $n$ einsetzt, so ist genau eine der Zahlen $n$ und $n-1$ gerade. Also ist $P(n)={\frac {n(n-1)}{2}}$ ganzzahlig.

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

Es seien $a,b\geq 2$ und sei $n=ab$.
a) Zeige, dass die beiden Polynome $X^{a}-1$ und $X^{b}-1$ Teiler des Polynoms $X^{n}-1$ sind.
b) Es sei $a\neq b$. Ist $(X^{a}-1)(X^{b}-1)$ stets ein Teiler von $X^{n}-1$?
c) Man gebe drei Primfaktoren von $2^{30}-1$ an.
Lösung
a) Es ist
    $X^{n}-1={\left(X^{b}\right)}^{a}-1={\left(X^{b}-1\right)}{\left({\left(X^{b}\right)}^{a-1}+{\left(X^{b}\right)}^{a-2}+\cdots +{\left(X^{b}\right)}^{2}+X^{b}+1\right)}\,$
und daher ist $X^{b}-1$ (und ebenso $X^{a}-1$) ein Teiler von $X^{n}-1$.
b) Dies ist nicht der Fall. Für
    $n=8=4\cdot 2\,$
ist
    $X^{8}-1=(X^{4}-1)(X^{4}+1)\,.$
Das Polynom $X^{4}+1$ hat keine reelle Nullstelle und ist deshalb kein Vielfaches von $X^{2}-1$. Daher ist $(X^{4}-1)(X^{2}-1)$ kein Teiler von $X^{8}-1$.
c) Da $2,3,5$ Teiler von $30$ sind, ergibt sich aus Teil a), dass $2^{2}-1=3,\,2^{3}-1=7$ und $2^{5}-1=31$ Teiler von $2^{30}-1$ sind. Daher sind $3,7,31$ Primteiler von $2^{30}-1$.

### Aufgabe (4 Punkte)

Berechne mit Hilfe des quadratischen Reziprozitätsgesetzes und seiner Ergänzungssätze das Legendre-Symbol
    $\left({\frac {1117}{1861}}\right)$
und bestimme, ob $1117$ ein Quadratrest modulo $1861$ ist oder nicht ($1861$ 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).
    ${\begin{aligned}\left({\frac {1117}{1861}}\right)&=\left({\frac {1861}{1117}}\right)\\&=\left({\frac {744}{1117}}\right)\\&=\left({\frac {2^{3}}{1117}}\right)\left({\frac {3}{1117}}\right)\left({\frac {31}{1117}}\right)\\&=(-1)\left({\frac {1117}{3}}\right)\left({\frac {1117}{31}}\right)\\&=(-1)\left({\frac {1}{3}}\right)\left({\frac {1}{31}}\right)\\&=-1.\end{aligned}}$
Also ist $1117$ kein Quadratrest modulo $1861$

### Aufgabe (9 Punkte)

Zeige, dass die diophantische Gleichung
    $x^{4}+y^{4}=z^{2}\,$
keine ganzzahlige nichttriviale Lösung besitzt.
Lösung
Es sei $(x,y,z)$ eine nichttriviale Lösung, d.h. alle Einträge sind $\neq 0$. 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 $z$ (unter allen nichttrivialen Lösungen). Wir zeigen, dass es dann eine Lösung mit kleinerem positiven $z_{1}$ gibt, was einen Widerspruch bedeutet.
Wegen der Minimalität ist $(x,y,z)$ primitiv, die Einträge sind also (sogar paarweise) teilerfremd. Wir können $x$ als ungerade annehmen. Es ist dann
    $(x^{2},y^{2},z)$
ein primitives pythagoreisches Tripel. Daher gibt es nach Fakt teilerfremde natürliche Zahlen $(u,v)$ mit
    $x^{2}=u^{2}-v^{2},\,y^{2}=2uv,\,z=u^{2}+v^{2}$
und mit $u+v$ ungerade. Betrachtung der ersten Gleichung modulo $4$ zeigt, dass $u$ ungerade sein muss (und $v$ gerade). Die erste Gleichung
    $u^{2}=x^{2}+v^{2}\,$
ist selbst ein primitives pythagoreisches Tripel. Es gibt als erneut teilerfremde natürliche Zahlen $(r,s)$ mit
    $x=r^{2}-s^{2},\,v=2rs,\,u=r^{2}+s^{2}$
($x$ ist ungerade, $v$ gerade) mit $r+s$ ist ungerade. Somit sind $r,s,r^{2}+s^{2}=u$ paarweise teilerfremd. Aus
    $y^{2}=2uv=4(r^{2}+s^{2})rs\,$
folgt
    $\left({\frac {y}{2}}\right)^{2}=(r^{2}+s^{2})rs\,$
und aus der Teilerfremdheit der Faktoren folgt, dass die einzelnen Faktoren hier selbst Quadrate sind, also
    $r=x_{1}^{2},\,s=y_{1}^{2},\,r^{2}+s^{2}=z_{1}^{2}.$
Damit ist
    $z_{1}^{2}=r^{2}+s^{2}=x_{1}^{4}+y_{1}^{4}\,$
eine neue nichttriviale Lösung der ursprünglichen Gleichung. Wegen
    $z_{1}\leq z_{1}^{2}=r^{2}+s^{2}=u<u^{2}+v^{2}=z\,$
widerspricht dies der Minimalität von $z$.

### Aufgabe (5 Punkte)

Zeige, dass es unendlich viele Primzahlen gibt, die modulo $4$ den Rest $1$ besitzen.
Lösung
Wir ziehen Fakt heran, wonach eine ungerade Primzahl $p$ genau dann den Rest $1$ modulo $4$ besitzt, wenn $-1$ eine Quadratwurzel in $\mathbb {Z} /(p)$ ist. Nehmen wir an, dass es nur endlich viele Primzahlen $p_{1},\ldots ,p_{k}$ von diesem Typ gibt. Wir betrachten das Polynom
    $f(x)=x^{2}+1\,.$
Die Zahl
    $f(2p_{1}\cdots p_{k})=4(p_{1}\cdots p_{k})^{2}+1\,$
besitzt einen Primteiler $q$, der von allen $p_{i}$ und von $2$ verschieden ist. Es ist
    $f(2p_{1}\cdots p_{k})=0\mod q\,.$
Doch dies bedeutet, dass $f(x)$ eine Nullstelle modulo $q$ besitzt und somit ist $-1$ ein Quadrat modulo $q$, also hat $q$ den Rest $1$ modulo $4$.

### Aufgabe (3 Punkte)

Es sei $n\in \mathbb {N} _{+}$. Zeige, dass das Produkt von $n$ aufeinanderfolgenden natürlichen Zahlen von $n!$ geteilt wird.
Lösung
Es ist
    $\prod _{j=1}^{n}(k+j)={\frac {(k+n)!}{k!}}=n!{\frac {(k+n)!}{n!k!}}=n!{\binom {k+n}{k}}\,.$
Da der Binomialkoeffizient ${\binom {k+n}{k}}$ eine ganze Zahl ist, folgt, dass das Produkt der $n$ aufeinanderfolgenden Zahlen von $n!$ geteilt wird.

### 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$.