Elementare und algebraische Zahlentheorie/18/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	0	0	3	5	5	0	0	0	0	0	0	0	0	12	31

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine zyklische Gruppe ${}G$.
2. Ein gemeinsamer Teiler von Elementen ${}a_{1},\ldots ,a_{k}$ in einem kommutativen Ring ${}R$.
3. /Definition/Begriff
4. /Definition/Begriff
5. /Definition/Begriff
6. /Definition/Begriff

Lösung

1. Eine Gruppe ${}G$ heißt zyklisch, wenn sie von einem Element erzeugt wird.
2. Ein Element ${}t\in R$ heißt gemeinsamer Teiler der ${}a_{1},\ldots ,a_{n}$, wenn ${}t$ jedes ${}a_{i}$ teilt.
3. /Definition/Begriff/Inhalt
4. /Definition/Begriff/Inhalt
5. /Definition/Begriff/Inhalt
6. /Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Lösung

1. /Fakt
2. /Fakt
3. /Fakt

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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

Man berechne in ${}\mathbb {Z} /(80)$ die Elemente

a) ${}3^{1234567}$,

b) ${}2^{1234567}$,

c) ${}5^{1234567}$.

Lösung

a) Es ist ${}3^{4}=81=1$ und ${}3$ ist eine Einheit. Daher hängt die Potenz nur von der Restklasse des Exponenten modulo ${}4$ ab, also

${}3^{1234567}=3^{67}=3^{7}=3^{3}=27\,.$

b) Wir verwenden die Isomorphie des chinesischen Restsatzes, also

$\mathbb {Z} /(80)\cong \mathbb {Z} /(16)\times \mathbb {Z} /(5).$

Das Element ${}2$ entspricht bei dieser Zerlegung dem Paar ${}(2,2)$. Die Potenz kann man komponentenweise ausrechnen, dabei erhält man vorne ${}0$, da der Exponent ${}\geq 4$ ist. Hinten ist ${}2$ eine Einheit der Ordnung ${}4$, daher ist in ${}\mathbb {Z} /(5)$

${}2^{1234567}=2^{3}=3\,.$

Das Ergebnis ist also das Paar ${}(0,3)$. Diesem entspricht das Element ${}48$.

c) Wir verwenden wieder den chinesischen Restsatz, diesmal geht es um das Element ${}(5,0)$. Die Ordnung von ${}5$ modulo ${}16$ ergibt sich aus

$5^{2}=25=9,\,5^{4}=9^{2}=81=1,$

die Ordnung ist also wieder ${}4$. Daher ist in ${}\mathbb {Z} /(16)$

${}5^{1234567}=5^{3}=125=13\,.$

Dem Paar ${}(13,0)$ entspricht das Element ${}45$.

Aufgabe (5 Punkte)

Beweise das Euler-Kriterium für Quadratreste.

Lösung

Es ist ${}{\left(k^{\frac {p-1}{2}}\right)}^{2}=k^{p-1}=1$ nach Fakt. Daher ist

${}k^{\frac {p-1}{2}}=\pm 1\,.$

Die Abbildung

${\left(\mathbb {Z} /(p)\right)}^{\times }\longrightarrow \{\pm 1\},\,k\longmapsto k^{\frac {p-1}{2}},$

ist (wie jedes Potenzieren) ein Gruppenhomomorphismus. Die Quadrate werden darunter auf ${}1$ abgebildet, da für ${}k=x^{2}$ die Gleichheit

${}k^{\frac {p-1}{2}}=(x^{2})^{\frac {p-1}{2}}=x^{p-1}=1\,$

gilt. Da nach Fakt die Einheitengruppe ${}{\left(\mathbb {Z} /(p)\right)}^{\times }$ zyklisch ist, muss diese Abbildung surjektiv sein (sonst hätte jedes Element eine kleinere Ordnung). Damit muss diese Abbildung mit der durch das Legendre-Symbol gegebenen übereinstimmen.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (12 Punkte)

Beweise den Gitterpunktsatz von Minkowski.

Lösung

Wir betrachten das verdoppelte Gitter ${}2\Gamma$. Ist ${}v_{1},\ldots ,v_{n}$ eine Basis für ${}\Gamma$, so ist ${}2v_{1},\ldots ,2v_{n}$ eine Basis für ${}2\Gamma$. Wir bezeichnen die Grundmasche von ${}2\Gamma$ mit ${}{\mathfrak {N}}$, für ihr Volumen gilt ${}\operatorname {Vol} ({\mathfrak {N}})=2^{n}\operatorname {Vol} ({\mathfrak {M}})$. Zu jeder Masche ${}{\mathfrak {N}}_{Q}=Q+{\mathfrak {N}}$, ${}Q\in 2\Gamma$, betrachten wir den Durchschnitt

${}T_{Q}=T\cap {\mathfrak {N}}_{Q}\,.$

Da ${}T$ kompakt und insbesondere beschränkt ist, gibt es nur endlich viele Maschen derart, dass dieser Durchschnitt nicht leer ist. Es seien diese Maschen (bzw. ihre Ausgangspunkte bzw. ihre Durchschnitte) mit ${}{\mathfrak {N}}_{i}\,({\text{bzw. }}Q_{i}{\text{bzw. }}T_{i})$, ${}i\in I$, bezeichnet (da der Nullpunkt aufgrund der Konvexität und der Zentralsymmetrie zu ${}T$ gehört, umfasst ${}I$ zumindest ${}2^{n}$ Elemente). Die in die Grundmasche ${}{\mathfrak {N}}$ verschobenen Durchschnitte bezeichnen wir mit

${}{\tilde {T}}_{i}:=T_{i}-Q_{i}\,.$

Wir behaupten zunächst, dass die ${}{\tilde {T}}_{i}$ nicht paarweise disjunkt sind. Es sei also angenommen, sie wären paarweise disjunkt. Mindestens eines der ${}T_{i}$ (und damit der ${}{\tilde {T}}_{i}$) hat positives Volumen, sagen wir für ${}i=1$. Wegen der angenommenen Disjunktheit sind insbesondere

$X:={\tilde {T}}_{1}\,\,{\text{ und }}\,\,Y:=\bigcup _{i\in I,i\neq 1}{\tilde {T}}_{i}$

disjunkt zueinander. Wir haben also zwei disjunkte kompakte Teilmengen, und diese besitzen einen Minimalabstand ${}d$ (d.h. zu jedem Punkt aus ${}X$ liegen in einer ${}d$-Umgebung keine Punkte aus ${}Y$, siehe Aufgabe). Sei ${}x\in X$ ein innerer Punkt (den es gibt, da ${}X$ konvex ist und ein positives Volumen besitzt) und sei ${}y\in Y$. Mit ${}S$ sei die Verbindungsstrecke von ${}x$ nach ${}y$ bezeichnet, die ganz in ${}{\mathfrak {N}}$ verläuft. Wir wählen einen Punkt ${}s\in S$, der weder zu ${}X$ noch zu ${}Y$ gehört (solche Punkte gibt es wegen des Minimalabstandes). Da ${}s$ sowohl zu ${}X$ als auch zu ${}Y$ einen Minimalabstand besitzt, gibt es eine ${}\epsilon$-Umgebung ${}B$ von ${}s$, die disjunkt zu ${}X$ und ${}Y$ ist. Wir können ferner annehmen, dass ${}B$ ganz innerhalb von ${}{\mathfrak {N}}$ liegt (wegen der Wahl von ${}x$). Als eine Ballumgebung hat ${}B$ ein positives Volumen, was zu folgendem Widerspruch führt.

${}{\begin{aligned}\operatorname {Vol} ({\mathfrak {N}})&\geq \operatorname {Vol} (X\cup Y\cup B)\\&=\operatorname {Vol} {\left(\bigcup _{i\in I}{\tilde {T}}_{i}\right)}+\operatorname {Vol} (B)\\&>\sum _{i\in I}\operatorname {Vol} ({\tilde {T}}_{i})\\&=\sum _{i\in I}\operatorname {Vol} (T_{i})\\&=\operatorname {Vol} (T)\\&\geq 2^{n}\operatorname {Vol} ({\mathfrak {M}})\\&=\operatorname {Vol} ({\mathfrak {N}}).\end{aligned}}$

Es gibt also Indizes ${}i\neq j$ und einen Punkt ${}z\in {\tilde {T}}_{i}\cap {\tilde {T}}_{j}$ (${}z$ muss selbst nicht zu ${}T$ gehören). Sei

$z_{i}:=z+Q_{i}\in T_{i}\,\,{\text{ und }}\,\,z_{j}:=z+Q_{j}\in T_{j}.$

Wegen ${}Q_{i},Q_{j}\in 2\Gamma$ ist auch ${}Q_{i}-Q_{j}\in 2\Gamma$ und daher

${}0\neq {\frac {Q_{i}-Q_{j}}{2}}\in \Gamma \,.$

Aus ${}z_{j}\in T$ folgt (wegen der Zentralsymmetrie) auch ${}-z_{j}\in T$ und wegen der Konvexität von ${}T$ ergibt sich

${}{\frac {Q_{i}-Q_{j}}{2}}={\frac {1}{2}}(z_{i}-z)-{\frac {1}{2}}(z_{j}-z)={\frac {1}{2}}z_{i}-{\frac {1}{2}}z_{j}\in T\,.$

Wir haben also einen von Nullpunkt verschiedenen Gitterpunkt in ${}T$ gefunden.