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	${}\sum$
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 ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$.
2. Eine primitive Einheit in ${}{\left(\mathbb {Z} /(n)\right)}^{\times }$.
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 ${}{\mathfrak {a}}\subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
   1. Für alle ${}a,b\in {\mathfrak {a}}$ ist auch ${}a+b\in {\mathfrak {a}}$.
   2. Für alle ${}a\in {\mathfrak {a}}$ und ${}r\in R$ ist auch ${}ra\in {\mathfrak {a}}$.
2. Eine Einheit ${}u\in {\left(\mathbb {Z} /(n)\right)}^{\times }$ heißt primitiv, wenn sie die Einheitengruppe erzeugt.
3. 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}}\,$

4. Ein pythagoreisches Tripel ist eine ganzzahlige Lösung ${}(x,y,z)\in \mathbb {Z} ^{3}$ der diophantischen Gleichung

   ${}x^{2}+y^{2}=z^{2}\,.$

5. Eine Primzahl der Form ${}2^{n}-1$ heißt Mersennesche Primzahl.
6. Eine natürliche Zahl ${}n$, die nicht prim ist, und die die Eigenschaft besitzt, dass für jede zu ${}n$ teilerfremde ganze Zahl ${}a$

   ${}a^{n-1}=1\mod n\,$

   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. 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$.
2. Für eine Primzahl ${}p$ und eine beliebige ganze Zahl ${}a$ gilt

   $a^{p}\equiv a\mod p.$

3. Es gilt die asymptotische Abschätzung

   ${}\pi (x)\sim {\frac {x}{\ln(x)}}\,.$

   Das heißt

   ${}\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}}\,,$

woraus direkt die Teileranzahl

$(k_{1}+1)(k_{2}+1)\cdots (k_{r}+1)$

ablesbar ist. Da ${}n$ klein sein soll, können wir direkt mit den ersten Primzahlen arbeiten und ferner

${}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} }\,,$

so dass 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$.