Elementare und algebraische Zahlentheorie/10/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	1	3	4	8	6	2	0	2	5	3	3	4	5	0	52

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$.
2. Die Folge der euklidischen Reste zu Elementen ${}a,b\in R$ mit ${}b\neq 0$ in einem euklidischen Bereich.
3. Ein faktorieller Bereich ${}R$.
4. Eine primitive Einheit in ${}{\left(\mathbb {Z} /(n)\right)}^{\times }$.
5. Ein Primideal ${}{\mathfrak {p}}$ in einem kommutativen Ring ${}R$.
6. Der Hauptdivisor zu einem Element ${}f\in R$ ${}f\neq 0$, in einem Zahlbereich ${}R$.

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. Man nennt die durch die Anfangsbedingungen ${}r_{0}=a$ und ${}r_{1}=b$ und die mittels der Division mit Rest

   ${}r_{i}=q_{i}r_{i+1}+r_{i+2}\,$

   rekursiv bestimmte Folge ${}r_{i}$ die Folge der euklidischen Reste.

3. Ein Integritätsbereich heißt faktorieller Bereich, wenn die beiden folgenden Eigenschaften erfüllt sind.
   1. Jedes irreduzible Element in ${}R$ ist prim.
   2. Jedes Element ${}a\in R$, ${}a\neq 0$, ist ein Produkt aus irreduziblen Elementen.
4. Eine Einheit ${}u\in {\left(\mathbb {Z} /(n)\right)}^{\times }$ heißt primitiv, wenn sie die Einheitengruppe erzeugt.
5. Ein Primideal ist ein Ideal, wenn ${}{\mathfrak {p}}\neq R$ ist und wenn für ${}r,s\in R$ mit ${}r\cdot s\in {\mathfrak {p}}$ folgt: ${}r\in {\mathfrak {p}}$ oder ${}s\in {\mathfrak {p}}$.
6. Der durch ${}f$ definierte Hauptdivisor ist die Abbildung, die jedem Primideal ${}{\mathfrak {p}}\neq 0$ in ${}R$ die Ordnung ${}\operatorname {ord} _{\mathfrak {p}}(f)$ zuordnet.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der kleine Fermat.
2. Der Satz über die Darstellbarkeit einer natürlichen Zahl als Summe von zwei Quadraten.
3. Der Satz über die Diskriminante quadratischer Zahlbereiche.

Lösung

1. Für eine Primzahl ${}p$ und eine beliebige ganze Zahl ${}a$ gilt

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

2. Es sei ${}n$ eine positive natürliche Zahl. Wir schreiben ${}n=r^{2}m$, wobei jeder Primfaktor von ${}m$ nur einfach vorkomme. Dann ist ${}n$ die Summe von zwei Quadraten genau dann, wenn in der Primfaktorzerlegung von ${}m$ nur ${}2$ und Primzahlen vorkommen, die modulo ${}4$ den Rest ${}1$ haben.
3. Es sei ${}D\neq 0,1$ eine quadratfreie Zahl und ${}A_{D}$ der zugehörige quadratische Zahlbereich. Dann ist die Diskriminante von ${}A_{D}$ gleich

   $\triangle =4D,{\text{ wenn }}D=2,3\mod 4$

   und

   $\triangle =D,{\text{ wenn }}D=1\mod 4.$

Aufgabe (1 Punkt)

Finde zwei natürliche Zahlen, deren Summe ${}65$ und deren Produkt ${}1000$ ist.

Lösung

Die Primfaktorzerlegung von ${}1000$ ist

${}1000=2^{3}\cdot 5^{3}\,.$

Die beiden gesuchten Zahlen müssen also Teiler davon sein, also von der Form ${}2^{i}5^{j}$ mit ${}i,j\leq 3$. Da die Summe ungerade ist, besitzt die eine Zahl die Form

$8\cdot 5^{j}.$

Dies führt auf die ${}40$ und ${}25$.

Aufgabe (3 Punkte)

Wir betrachten das kleine Einmaleins als eine Verknüpfungstabelle, in der alle Produkte ${}i\cdot j$ mit ${}1\leq i,j\leq 9$ stehen. Bestimme die Primfaktorzerlegung des Produktes über alle Einträge in der Tabelle.

Lösung

Es sei ${}n$ das Produkt aller Zahlen im kleinen Einmaleins. Als Primfaktoren kommen nur ${}2,3,5,7$ in Frage. Jede Zahl ${}i\leq 9$ wird mit jeder der neun einstelligen Zahl sowohl von links als auch von rechts multipliziert und dadurch tritt die Primfaktorzerlegung von ${}i$ in der ${}18$-ten Potenz auf. Somit ergibt sich

${}{\begin{aligned}n&=2^{18}\cdot 3^{18}\cdot 4^{18}\cdot 5^{18}\cdot 6^{18}\cdot 7^{18}\cdot 8^{18}\cdot 9^{18}\\&=2^{18}\cdot 3^{18}\cdot 2^{36}\cdot 5^{18}\cdot 2^{18}\cdot 3^{18}\cdot 7^{18}\cdot 2^{54}\cdot 3^{36}\\&=2^{126}\cdot 3^{72}\cdot 5^{18}\cdot 7^{18}.\end{aligned}}$

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

Wir betrachten eine (einfachere, aber langsamere) Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen ${}a,b$.

Der Algorithmus geht folgendermaßen. Wenn ${}a\neq b$ ist, so ersetzte das Paar ${}(a,b)$ durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn ${}a=b$ ist, so ist man fertig und es wird das Ergebnis ${}a$ ausgegeben.

1. Führe diesen Algorithmus für das Paar ${}(7,3)$ durch.
2. Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
3. Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsmen Teiler ausgibt.
4. Man gebe für jedes ${}n$ ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante ${}n$ Schritte benötigt.

Lösung

1. Der Algorithmus ersetzt sukzessive

   $(7,3)\mapsto (4,3)\mapsto (3,1)\mapsto (2,1)\mapsto (1,1),$

   der größte gemeinsame Teiler ist also ${}1$.

2. Wenn ${}a=b$ ist, so hört der Algorithmus auf. Wenn genau eine Zahl ${}0$ ist, so ist das Folgepaar ${}(c,c)$ und dann hört der Algorithmus auf. Es sei also ohne Einschränkung

   ${}a>b>0\,.$

   Das Folgepaar ist dann ${}(a-b,b)$ und beide Zahlen sind kleiner als ${}a$. D.h. unter dieser Voraussetzung wird das Maximum mit jedem Rechenschritt kleiner. Da sich alles innerhalb der natürlichen Zahlen abspielt, bricht das Verfahren irgendwann ab.

3. Bei ${}a=b$ ist diese Zahl auch der größte gemeinsame Teiler. Wir zeigen, dass sich bei jedem Rekursionsschritt, bei dem ${}(a,b)$ (es sei wieder $a\geq b$) durch ${}(a-b,b)$ ersetzt wird, der größte gemeinsame Teiler der beiden Paare übereinstimmt. Dazu muss man nur zeigen, dass ${}a$ und ${}b$ einerseits und ${}a-b$ und ${}b$ andererseits die gleichen gemeinsamen Teiler haben. Es sei also ${}t\in \mathbb {N}$ und ${}a=tm$ und ${}b=tn$. Dann ist

   ${}a-b=mt-nt=(m-n)t\,$

   ebenfalls ein Vielfaches von ${}t$. Wenn umgekehrt ${}a-b=rt$ und ${}b=st$ ist, so ist

   ${}a=a-b+b=rt+st=(r+s)t\,$

   ebenfalls ein Vielfaches von ${}t$.

4. Wir betrachten das Paar ${}(n,1)$. Der euklidische Algorithmus liefert

   ${}n=n\cdot 1+0\,$

   und ist fertig. Die Variante ersetzt ${}(n,1)$ durch ${}(n-1,1)$, sie braucht also ${}n-1$ Schritte, um die Abbruchbedingung ${}(1,1)$ zu erreichen.

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)

Man gebe ein Beispiel an, wo das Jacobi-Symbol den Wert ${}1$ hat, aber kein Quadratrest vorliegt.

Lösung

Betrachte in

${}\mathbb {Z} /(15)\cong \mathbb {Z} /(5)\times \mathbb {Z} /(3)\,$

das Element ${}2$. Die ${}2$ ist weder modulo ${}3$ noch modulo ${}5$ ein Quadratrest, also erst recht nicht modulo ${}15$. Andererseits ist aber nach Definition

${}\left({\frac {2}{15}}\right)=\left({\frac {2}{3}}\right)\left({\frac {2}{5}}\right)=(-1)(-1)=1\,.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

Zeige, dass ein Ideal ${}{\mathfrak {a}}$ in einem kommutativen Ring ${}R$ genau dann ein Radikal ist, wenn der Restklassenring ${}R/{\mathfrak {a}}$ reduziert ist.

Lösung

Es sei ${}{\mathfrak {a}}$ ein Radikal und ${}f\in R/{\mathfrak {a}}$ nilpotent. Dann ist ${}f^{r}=0$ in ${}R/{\mathfrak {a}}$. Zurückübersetzt nach ${}R$ bedeutet dies ${}f^{r}\in {\mathfrak {a}}$. Da ein Radikal vorliegt, ist ${}f\in {\mathfrak {a}}$ und damit ${}f=0$ im Restklassenring. Also ist dieser reduziert.

Es sei umgekehrt ein Ideal

${}{\mathfrak {a}}\subseteq R\,$

mit reduziertem Restklassenring ${}R/{\mathfrak {a}}$ gegeben. Es sei ${}f^{r}\in {\mathfrak {a}}$. Dann ist die Restklasse von ${}f^{r}$ gleich ${}0$. Wegen der Reduziertheit ist bereits ${}f=0$. Dies bedeutet ${}f\in {\mathfrak {a}}$, also ist das Ideal ein Radikal.

Aufgabe (5 Punkte)

Beweise, dass ein faktorieller Integritätsbereich normal ist.

Lösung

Sei ${}K=Q(R)$ der Quotientenkörper von ${}R$ und ${}q\in K$ ein Element, das die Ganzheitsgleichung

${}q^{n}+r_{n-1}q^{n-1}+r_{n-2}q^{n-2}+\cdots +r_{1}q+r_{0}=0\,$

mit ${}r_{i}\in R$ erfüllt. Wir schreiben ${}q=a/b$ mit ${}a,b\in R$, ${}b\neq 0$, wobei wir annehmen können, dass die Darstellung gekürzt ist, dass also ${}a$ und ${}b\in R$ keinen gemeinsamen Primteiler besitzen. Wir haben zu zeigen, dass ${}b$ eine Einheit in ${}R$ ist, da dann ${}q=ab^{-1}$ zu ${}R$ gehört.

Wir multiplizieren die obige Ganzheitsgleichung mit ${}b^{n}$ und erhalten in ${}R$

${}a^{n}+{\left(r_{n-1}b\right)}a^{n-1}+{\left(r_{n-2}b^{2}\right)}a^{n-2}+\cdots +{\left(r_{1}b^{n-1}\right)}a+{\left(r_{0}b^{n}\right)}=0\,.$

Wenn ${}b$ keine Einheit ist, dann gibt es einen Primteiler ${}p$ von ${}b$. Dieser teilt alle Summanden ${}{\left(r_{n-i}b^{i}\right)}a^{n-i}$ für ${}i\geq 1$ und daher auch den ersten, also ${}a^{n}$. Das bedeutet aber, dass ${}a$ selbst ein Vielfaches von ${}p$ ist im Widerspruch zur vorausgesetzten Teilerfremdheit.

Aufgabe (3 Punkte)

Zeige, dass es in jedem Zahlbereich abzählbar unendlich viele Primideale gibt.

Lösung

Die Aussage ist für ${}\mathbb {Z}$ richtig. Es sei ${}\mathbb {Z} \subseteq R$ der Zahlbereich. Zu jeder Primzahl ${}p$ ist ${}R/pR$ ein Fakt endlicher Ring ${}\neq 0$ und besitzt somit endlich viele (und mindestens eins) Primideale. Diese Primideale entsprechen den Primidealen von ${}R$ oberhalb von ${}pR$, und jedes von ${}0$ verschiedene Primideal wird dadurch erfasst. Also ist die Menge der Primideale eine abzählbar unendliche Vereinigung von endlichen (nichtleeren) Mengen und damit abzählbar unendlich.

Aufgabe (3 Punkte)

Bestimme ein Element aus ${}\mathbb {Z} [{\sqrt {-11}}]$, das unter allen Nichteinheiten minimale Norm besitzt. Begründe, dass dieses Element irreduzibel ist.

Lösung

Die Elemente in ${}\mathbb {Z} [{\sqrt {-11}}]$ haben die Form

$z=a+b{\sqrt {-11}}$

mit ${}a,b\in \mathbb {Z}$. Die Norm davon ist

${}N(z)=a^{2}+11b^{2}\,.$

Bei ${}b\geq 1$ ergibt sich zumindest ${}N(z)\geq 11$. Bei ${}b=0$ und ${}a=\pm 2$ ergibt sich die Norm ${}4$. Bei ${}b=0$ und ${}a=\pm 1$ liegt eine Einheit vor, sodass ${}(\pm 2,0)$ die Nichteinheiten mit minimaler Norm sind. Ein solches Element ${}z$ ist irreduzibel, da aus ${}z=uv$ folgt ${}4=N(u)N(v)$. Da es aber kein Element mit Norm ${}\pm 2$ gibt, muss ${}u$ oder ${}v$ die Norm ${}\pm 1$ haben, also eine Einheit sein.

Aufgabe (4 Punkte)

Es seien ${}R$ und ${}S$ Integritätsbereiche und sei ${}R\subseteq S$ eine ganze Ringerweiterung. Es sei ${}f\in R$ ein Element, das in ${}S$ eine Einheit ist. Zeige, dass ${}f$ dann schon in ${}R$ eine Einheit ist.

Lösung

Es sei ${}s\in S$ das Inverse von ${}f$, also ${}fs=1$. Da ${}S$ ganz über ${}R$ ist, gibt es eine Ganzheitsgleichung für ${}s$, sagen wir

$s^{n}+a_{n-1}s^{n-1}+\cdots +a_{1}s+a_{0}=0$

mit ${}a_{i}\in R$. Wir multiplizieren diese Gleichung mit ${}f^{n}$ und erhalten

$(fs)^{n}+a_{n-1}f(fs)^{n-1}+\cdots +a_{1}f^{n-1}(fs)+a_{0}f^{n}=0$

bzw.

$1+a_{n-1}f+\cdots +a_{1}f^{n-1}+a_{0}f^{n}=0.$

Ausklammern von ${}f$ ergibt

$1+f(a_{n-1}+\cdots +a_{1}f^{n-2}+a_{0}f^{n-1})=0$

und damit

$f(-a_{n-1}-\cdots -a_{1}f^{n-2}-a_{0}f^{n-1})=1,$

wobei der Ausdruck in der Klammer zu ${}R$ gehört. Also besitzt ${}f$ auch ein Inverses in ${}R$.

Aufgabe (5 (2+3) Punkte)

Es sei ${}K$ ein endlicher Körper mit ${}q$ Elementen.

1. Zeige, dass die Polynomfunktionen

   $\varphi _{d}\colon K\longrightarrow K,\,x\longmapsto x^{d},$

   mit ${}0\leq d<q$ linear unabhängig sind.

2. Zeige, dass die Exponentialfunktionen

   $\psi _{b}\colon K\longrightarrow K,\,x\longmapsto b^{x},$

   mit ${}0\leq b<q$ linear unabhängig sind.

Lösung

1. Nach dem Interpolationssatz kann man jede Abbildung

   $f\colon K\longrightarrow K$

   eindeutig als ein Polynom vom Grad ${}<q$ schreiben. Wegen der Eindeutigkeit sind die Potenzfunktionen ${}x\mapsto x^{d}$ linear unabhängig.

2. Wir betrachten die ${}q\times q$-Matrix

   $(b^{d})_{0\leq b,d\leq q-1}.$

   In der ${}d$-ten Spalte stehen alle Werte (eine vollständige Wertetabelle) von ${}x^{d}$ (an den Stellen ${}b$). Diese Tupel sind nach Teil (1) linear unabhängig. In der ${}b$-ten Zeile stehen alle Werte der Exponentialfunktion zur Basis ${}b$ (an den Stellen ${}d$). Nach Fakt sind mit den Spalten auch die Zeilen linear unabhängig. Somit sind die Exponentialfunktionen linear unabhängig.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung