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

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	1	2	3	5	4	3	3	2	6	4	3	6	2	5	2	3	4	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Assoziiertheit von Elementen ${}a,b$ in einem kommutativen Ring ${}R$.
2. Ein Primelement ${}p\in R,\,p\neq 0$, in einem kommutativen Ring ${}R$.
3. Ein euklidischer Bereich ${}R$.
4. Das Jacobi-Symbol.
5. Die erste Tschebyschow-Funktion.
6. Eine Fermatsche Primzahl.

Lösung

1. Zwei Elemente ${}a$ und ${}b$ heißen assoziiert, wenn es eine Einheit ${}u\in R$ derart gibt, dass  ${}a=ub$  ist.
2. Das Element ${}p$ heißt prim, wenn es eine Nichteinheit ist und wenn Folgendes gilt: Teilt ${}p$ ein Produkt ${}ab$ mit ${}a,b\in R$, so teilt es einen der Faktoren.
3. 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).$

4. Für eine ungerade Zahl ${}n$ und eine ganze Zahl ${}k$ definiert man das Jacobi-Symbol, geschrieben ${}\left({\frac {k}{n}}\right)$, wie folgt. Es sei  ${}n=p_{1}\cdots p_{r}$  die Primfaktorzerlegung von ${}n$. Dann setzt man

   ${}\left({\frac {k}{n}}\right):=\left({\frac {k}{p_{1}}}\right)\cdots \left({\frac {k}{p_{r}}}\right)\,.$

5. Die erste Tschebyschow-Funktion ${}\vartheta (x)$ ist durch

   ${}\vartheta (x)=\sum _{p\leq x,p{\text{ prim}}}\ln(p)\,$

   gegeben.

6. Eine Primzahl der Form ${}2^{s}+1$, wobei ${}s$ eine positive natürliche Zahl ist, heißt Fermatsche Primzahl.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Struktur der Einheitengruppe von ${}\mathbb {Z} /(p)$ für eine Primzahl ${}p$.
2. Das quadratische Reziprozitätsgesetz für ungerade Primzahlen.
3. Das Bertrandsche Postulat.

Lösung

1. Die Einheitengruppe ${}{\left(\mathbb {Z} /(p)\right)}^{\times }$ ist zyklisch mit der Ordnung ${}p-1$.
2. Es seien ${}p$ und ${}q$ zwei verschiedene ungerade Primzahlen. Dann gilt:

   ${}\left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}={\begin{cases}-1\,,{\text{ wenn }}p=q=3\mod 4\,,\\1\,,{\text{ sonst}}\,.\end{cases}}\,$

3. Für jede positive natürliche Zahl ${}n$ gibt es eine Primzahl zwischen ${}n+1$ und ${}2n$.

Aufgabe (1 Punkt)

Ist die Abbildung

$\varphi \colon \mathbb {N} _{+}\times \mathbb {N} _{+}\longrightarrow \mathbb {N} _{+}\times \mathbb {N} _{+}\times \mathbb {N} _{+},\,(a,b)\longmapsto (a+b,ab,a^{b}),$

injektiv oder nicht?

Lösung

Die Abbildung ist nicht injektiv, da wegen

${}2^{4}=16=4^{2}\,$

die beiden Paare ${}(2,4)$ und ${}(4,2)$ unter ${}\varphi$ auf das gleiche Element abgebildet werden.

Aufgabe (2 (1+1) Punkte)

a) Berechne den größten gemeinsamen Teiler der ganzen Zahlen ${}2\cdot 3^{2}\cdot 7^{4}$ und ${}2^{4}\cdot 3^{3}\cdot 5^{11}\cdot 7$.

b) Berechne den größten gemeinsamen Teiler der ganzen Zahlen ${}2\cdot 3^{2}\cdot 6\cdot 7$ und ${}2^{2}\cdot 3^{3}\cdot 5^{4}$.

Lösung

a) Beide Zahlen liegen in ihrer Primfaktorzerlegung vor, daher ist nach Fakt der größte gemeinsame Teiler gleich

${}2\cdot 3^{2}\cdot 7=126\,.$

b) Es ist

${}6=2\cdot 3\,,$

daher lautet die Primfaktorzerlegung der ersten Zahl

$2^{2}\cdot 3^{3}\cdot 7$

und somit ist der größte gemeinsame Teiler gleich

${}2^{2}\cdot 3^{3}=4\cdot 27=108\,.$

Aufgabe (3 Punkte)

Bestimme den Exponenten zu ${}2$ von ${}203264$.

Lösung

Es ist

${}{\begin{aligned}203264&=2\cdot 101632\\&=2^{2}\cdot 50816\\&=2^{3}\cdot 25408\\&=2^{4}\cdot 12704\\&=2^{5}\cdot 6352\\&=2^{6}\cdot 3176\\&=2^{7}\cdot 1588\\&=2^{8}\cdot 794\\&=2^{9}\cdot 397.\end{aligned}}$

Da ${}397$ ungerade ist, ist der Exponent zu ${}2$ von ${}203264$ gleich ${}9$.

Aufgabe (5 Punkte)

Zeige, dass die Untergruppen von ${}\mathbb {Z}$ genau die Teilmengen der Form

${}\mathbb {Z} d=\left\{kd\mid k\in \mathbb {Z} \right\}\,$

mit einer eindeutig bestimmten nicht-negativen Zahl ${}d$ sind.

Lösung

Eine Teilmenge der Form ${}\mathbb {Z} d$ ist aufgrund des Distributivgesetzes eine Untergruppe. Es sei umgekehrt  ${}H\subseteq \mathbb {Z}$  eine Untergruppe. Bei  ${}H=0$  kann man  ${}d=0$  nehmen, sodass wir voraussetzen dürfen, dass ${}H$ neben ${}0$ noch mindestens ein weiteres Element ${}x$ enthält. Wenn ${}x$ negativ ist, so muss die Untergruppe ${}H$ auch das Negative davon, also ${}-x$ enthalten, welches positiv ist. D.h. ${}H$ enthält auch positive Zahlen. Es sei nun ${}d$ die kleinste positive Zahl aus ${}H$. Wir behaupten  ${}H=\mathbb {Z} d$.  Dabei ist die Inklusion  ${}\mathbb {Z} d\subseteq H$  klar, da mit ${}d$ alle (positiven und negativen) Vielfachen von ${}d$ dazugehören müssen. Für die umgekehrte Inklusion sei  ${}h\in H$  beliebig. Nach der Division mit Rest gilt

$h=qd+r{\text{ mit }}0\leq r<d.$

Wegen $h\in H$ und $qd\in H$ ist auch  ${}r=h-qd\in H$.  Nach der Wahl von ${}d$ muss wegen  ${}r<d$  gelten:  ${}r=0$.  Dies bedeutet  ${}h=qd$  und damit  ${}h\in \mathbb {Z} d$,  also  ${}H\subseteq \mathbb {Z} d$. 

Aufgabe (4 Punkte)

Bestimme in ${}{\mathbb {Z} }[{\mathrm {i} }]$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}7+4{\mathrm {i} }$ und ${}5+3{\mathrm {i} }$.

Lösung

Wir setzen  ${}a=7+4{\mathrm {i} }$  und  ${}b=5+3{\mathrm {i} }$  und führen die Division mit Rest ${}a/b$ durch. Es ist (in ${}{\mathbb {C} }$ oder in $\mathbb {Q} [{\mathrm {i} }]$)

${}{\frac {a}{b}}={\frac {7+4{\mathrm {i} }}{5+3{\mathrm {i} }}}={\frac {(7+4{\mathrm {i} })(5-3{\mathrm {i} })}{(5+3{\mathrm {i} })(5-3{\mathrm {i} })}}={\frac {47-{\mathrm {i} }}{34}}={\frac {47}{34}}-{\frac {1}{34}}{\mathrm {i} }\,.$

Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist ${}1$, sodass die Division mit Rest ergibt:

$a=1\cdot b+r{\text{ mit }}r=a-b=2+{\mathrm {i} }.$

Die nächste durchzuführende Division ist somit

${}{\frac {b}{r}}={\frac {5+3{\mathrm {i} }}{2+{\mathrm {i} }}}={\frac {(5+3{\mathrm {i} })(2-{\mathrm {i} })}{(2+{\mathrm {i} })(2-{\mathrm {i} })}}={\frac {13+{\mathrm {i} }}{5}}={\frac {13}{5}}+{\frac {1}{5}}{\mathrm {i} }\,.$

Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist ${}3$, sodass die Division mit Rest ergibt:

$b=3\cdot r+s{\text{ mit }}s=b-3r=5+3{\mathrm {i} }-3(2+{\mathrm {i} })=-1.$

Da dies eine Einheit ist, sind ${}a=7+4{\mathrm {i} }$ und ${}b=5+3{\mathrm {i} }$ teilerfremd.

Aufgabe (3 Punkte)

Bestimme das inverse Element zu ${}{\overline {25}}$ in ${}\mathbb {Z} /(89)$.

Lösung

Der euklidische Algorithmus liefert

${}89=3\cdot 25+14\,,$

${}25=1\cdot 14+11\,,$

${}14=1\cdot 11+3\,,$

${}11=3\cdot 3+2\,,$

${}3=1\cdot 2+1\,.$

Somit ist

${}{\begin{aligned}1&=3-1\cdot 2\\&=3-1\cdot (11-3\cdot 3)\\&=4\cdot 3-1\cdot 11\\&=4\cdot (14-1\cdot 11)-1\cdot 11\\&=4\cdot 14-5\cdot 11\\&=4\cdot 14-5\cdot (25-1\cdot 14)\\&=9\cdot 14-5\cdot 25\\&=9\cdot (89-3\cdot 25)-5\cdot 25\\&=9\cdot 89-32\cdot 25.\end{aligned}}$

Daher ist

${}-32=57\,$

das inverse Element zu ${}25$ in ${}\mathbb {Z} /(89)$.

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 (2 Punkte)

Bestimme eine primitive Einheit  ${}v\in \mathbb {Z} /(5)$  und ein Urbild  ${}u\in \mathbb {Z} /(25)$  von ${}v$, das in ${}\mathbb {Z} /(25)$ nicht primitiv ist.

Lösung

Es ist  ${}2\in \mathbb {Z} /(5)$  eine primitive Einheit. Das Urbild ${}7$ davon erfüllt moduo ${}25$ die Bedingungen

${}7^{4}=7^{2}\cdot 7^{2}=49\cdot 49=(-1)\cdot (-1)=1\,.$

Seine Ordnung ist also ${}4$ und nicht ${}20$, wie das bei einer primitiven Einheit von ${}\mathbb {Z} /(25)$ sein müsste.

Aufgabe (6 Punkte)

Es sei ${}p$ eine ungerade Primzahl und sei ${}k$ eine zu ${}p$ teilerfremde natürliche Zahl. Es sei

$\pi _{k}\colon {\left(\mathbb {Z} /(p)\right)}^{\times }\longrightarrow {\left(\mathbb {Z} /(p)\right)}^{\times },\,x\longmapsto kx,$

die zu ${}k$ gehörende Permutation auf der Einheitengruppe ${}{\left(\mathbb {Z} /(p)\right)}^{\times }$ und ${}\operatorname {sgn} (\pi _{k})$ das Signum dieser Permutation. Zeige

${}\left({\frac {k}{p}}\right)=\operatorname {sgn} (\pi _{k})\,.$

Lösung

Die Abbildung

${\left(\mathbb {Z} /(p)\right)}^{\times }\longrightarrow S_{p-1},\,k\longmapsto \pi _{k},$

der Einheitengruppe in die Permutationsgruppe zu ${}p-1$ Elementen ist ein Gruppenhomomorphismus. Nach Fakt ist die Abbildung

$\varphi \colon S_{p-1}\longrightarrow \{1,-1\},\,\pi \longmapsto \operatorname {sgn} (\pi ),$

ein Gruppenhomomorphismus, sodass auch die Verknüpfung

${\left(\mathbb {Z} /(p)\right)}^{\times }\longrightarrow \{1,-1\},\,k\longmapsto \operatorname {sgn} (\pi _{k}),$

ein Gruppenhomomorphismus ist. Es sei ${}g$ ein Erzeuger der nach Fakt zyklischen Gruppe ${}{\left(\mathbb {Z} /(p)\right)}^{\times }$. Die zugehörige Permutation besitzt die Wirkungsweise

$g^{i}\mapsto g\cdot g^{i}=g^{i+1},$

dies ist also ein Zyklus der Länge ${}p-1$. Dieser hat nach Aufgabe das Signum  ${}(-1)^{p-2}=-1$.  Dies bedeutet, dass die Abbildung ${}\varphi$ surjektiv ist, und dass  ${}k=g^{j}$  genau dann auf ${}1$ abgebildet wird, wenn ${}j$ gerade ist. Deshalb stimmt die Abbildung mit dem Legendre-Symbol überein.

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 (3 Punkte)

Es sei ${}p$ eine Primzahl mit  ${}p=1\mod 4$  und sei  ${}p=x^{2}+y^{2}$  eine Darstellung als Summe von zwei Quadraten,  ${}x,y\in \mathbb {N}$.  Es sei ${}k$ ein ungerader Teiler von ${}x$. Zeige: Dann ist ${}k$ ein Quadratrest modulo ${}p$.

Lösung erstellen

Aufgabe (6 (1+5) Punkte)

a) Finde einen Punkt ${}(x,y)$ mit rationalen Koordinaten auf dem Kreis, der durch die Gleichung

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

gegeben ist.

b) Finde eine rationale Parametrisierung des Kreises aus Teil (a).

Lösung

a) Offensichtlich ist  ${}1^{2}+1^{2}=2$,  also ist  ${}\left(x,\,y\right)=\left(1,\,1\right)$  ein Punkt des Kreises mit rationalen Koordinaten.

b) Wir betrachten für ${}t\in K$ die Gerade ${}G_{t}$ durch die Punkte ${}\left(1,\,1\right)$ und ${}\left(2,\,t+1\right)$, also

${}G_{t}=\left\{\left(1,\,1\right)+a\cdot \left(1,\,t\right)\mid a\in K\right\}=\left\{\left(1+a,\,1+at\right)\mid a\in K\right\}\,$

und berechnen den Durchschnitt dieser Geraden mit dem Kreis, indem wir ${}x=1+a$ und ${}y=1+at$ in die Kreisgleichung einsetzen. Dabei ergibt sich

${}{\begin{aligned}0&=x^{2}+y^{2}-2\\&=(1+a)^{2}+(1+at)^{2}-2\\&=(t^{2}+1)a^{2}+(2t+2)a\\&=a((t^{2}+1)a+2t+2).\end{aligned}}$

Wir erhalten als Lösungen die Werte ${}a=0$ (was zu dem bereits bekannten Schnittpunkt ${}\left(1,\,1\right)$ führt) und

${}{\begin{aligned}a&={\frac {-2t-2}{t^{2}+1}}\\\end{aligned}}$

was eingesetzt in ${}G_{t}$ den Schnittpunkt

${}{\begin{aligned}(x,y)&=\left(1+{\frac {-2t-2}{t^{2}+1}},\,1+{\frac {-2t-2}{t^{2}+1}}\cdot t\right)\\&=\left({\frac {t^{2}-2t-1}{t^{2}+1}},\,{\frac {t^{2}-2t+1}{t^{2}+1}}\right)\end{aligned}}$

ergibt. Die Abbildung

${\mathbb {A} }_{K}^{1}\longrightarrow {\mathbb {A} }_{K}^{2},\,t\longmapsto \left({\frac {t^{2}-2t-1}{t^{2}+1}},\,{\frac {t^{2}-2t+1}{t^{2}+1}}\right)$

liefert also eine rationale Parametrisierung des Kreises.

Aufgabe (2 Punkte)

Zeige, dass man ${}1729$ auf zwei unterschiedliche Arten als eine Summe von zwei Kubikzahlen darstellen kann.

Lösung

Es ist

${}1729=1+1728=1^{3}+12^{3}\,$

und

${}1729=729+1000=9^{3}+10^{3}\,.$

Aufgabe (5 Punkte)

Man gebe ein Beispiel für eine Teilmenge  ${}T\subseteq \mathbb {N} _{+}$  derart, dass die Reihe ${}\sum _{n\in T}{\frac {1}{n}}$ konvergiert, und dass es in ${}T$ arithmetische Progressionen beliebiger Länge gibt.

Lösung

Wir betrachten

${}T=\{10,100,101,1000,1001,1002,10000,10001,10002,10003,\ldots \}\,.$

Diese Menge enthält die arithmetischen Progressionen

$10^{k},10^{k}+1,10^{k}+2,\ldots ,10^{k}+k-1$

der Länge ${}k$ und damit beliebig lange arithmetische Progressionen. Für einen solchen Strang gilt

${}{\frac {1}{10^{k}}}+{\frac {1}{10^{k}+1}}+\cdots +{\frac {1}{10^{k}+k-1}}\leq k{\frac {1}{10^{k}}}\,.$

Die Summe der Kehrwerte aus ${}T$ kann man daher durch die Reihe

$\sum _{k=1}^{\infty }k{\frac {1}{10^{k}}}$

nach oben abschätzen. Der Quotient von zwei aufeinander folgenden Reihengliedern ist

${}{\frac {{\left(k+1\right)}{\frac {1}{10^{k+1}}}}{k{\frac {1}{10^{k}}}}}={\frac {k+1}{10k}}\,,$

was gegen ${}0$ konvergiert. Daher konvergiert diese Reihe nach dem Quotientenkriterium und daher konvergiert auch die Ausgangsreihe.

Aufgabe (2 Punkte)

Man gebe ein Beispiel für zwei nicht befreundete Zahlen ${}m$ und ${}n$ mit

${}\sigma (m)=\sigma (n)\,.$

Lösung

Es ist

${}\sigma (6)=1+2+3+6=12\,$

und

${}\sigma (11)=1+11=12\,.$

Wegen  ${}12\neq 11$  sind diese beiden Zahlen nicht befreundet.

Aufgabe (3 (2+1) Punkte)

a) Zeige, dass die Endziffer einer Sophie-Germain-Primzahl ${}p$ im Zehnersystem nicht ${}7$ sein kann.

b) Zeige, dass die Zahlen ${}1,3,5,9$ als Endziffer einer Sophie-Germain-Primzahl auftreten können.

Lösung

a) Es sei  ${}p=10n+7$.  Dann ist

${}2p+1=2(10n+7)+1=20n+14+1=5(4n+3)\,,$

also sicher keine Primzahl.

b) Dies ist klar aufgrund der Primzahlpaare ${}(11,23)$, ${}(3,7)$, ${}(5,11)$, ${}(29,59)$

Aufgabe (4 Punkte)

Es sei

$\varphi \colon (\mathbb {Q} ,0,+)\longrightarrow (\mathbb {Q} \setminus \{0\},1,\cdot )$

ein Gruppenhomomorphismus. Zeige, dass ${}\varphi$ trivial ist.

Lösung

Es sei

${}\varphi (r)=q={\frac {a}{b}}\in \mathbb {Q} ^{\times }\,$

mit  ${}a,b\in \mathbb {Z} \setminus \{0\}$  festgelegt. Unter ${}\varphi$ muss dann der Quotient ${}{\frac {r}{n}}$ auf eine ${}n$-te Wurzel von ${}q$ abgebildet werden. Es sei

${}q=\pm p_{1}^{\nu _{1}}\cdots p_{k}^{\nu _{k}}\,$

die eindeutige Faktorzerlegung mit Primzahlen ${}p_{j}$ und  ${}\nu _{j}\in \mathbb {Z}$.  Der Fall ${}q$ negativ ist wegen  ${}n=2$  ausgeschlossen. Bei

${}q\neq 1\,$

wäre ein Exponent  ${}\nu _{j}\geq 1$.  Aufgrund der Quotientenbedingung müsste ${}\nu _{j}$ ein Vielfaches von jedem  ${}n\in \mathbb {N} _{+}$  sein, was nicht möglich ist. Also ist  ${}\varphi (r)=1$.