\documentclass{algblatt}
\usepackage{multicol}
\input{config.tex}
\geometry{tmargin=2.0cm,bmargin=2.0cm,lmargin=2.7cm,rmargin=2.7cm}

%\setlength{\titleskip}{0.7em}
\setlength{\aufgabenskip}{1.0em}

\begin{document}

\vspace*{-1.5cm}
\maketitle{12}{Abgabe bis 8. Juli 2013, 17:00 Uhr}

\begin{aufgabe}{Allgemeines zu Gruppen}
\begin{enumerate}
\item Gibt es in der Permutationsgruppe~$\SSS_5$ eine Untergruppe mit~$70$
Elementen?

\item Sei~$G$ eine Gruppe. Sei~$H$ eine Untergruppe von~$G$ und~$K$ eine
Untergruppe von~$H$. Wieso ist~$K$ dann auch eine Untergruppe von~$G$?

\item Sei~$G$ eine Gruppe und~$\sigma \in G$. Zeige, dass~$\sigma^i \circ
\sigma^j = \sigma^{i + j}$ für beliebige \emph{ganze} Zahlen~$i,j$.
\end{enumerate}

\begin{loesungE}
\item Nein, denn nach dem Satz von Lagrange wäre~$70$ dann ein Teiler der
Ordnung von~$\SSS_5$. Diese ist aber~$5! = 120$.

\item Zur Erinnerung die nötigen Definitionen:
\begin{quote}
  Eine \emph{Gruppe}~$G$ ist eine Teilmenge einer~$\SSS_n$, die die
  Identitätspermutation enthält und außerdem unter
  Komposition und Inversenbildung abgeschlossen ist.

  In dieser Situation ist eine \emph{Untergruppe}~$L$ von~$G$ eine
  Teilmenge derselben symmetrischen Gruppe~$\SSS_n$, welche die 
  Identitätspermutation enthält und außerdem unter
  Komposition und Inversenbildung abgeschlossen ist, und außerdem eine
  Teilmenge von~$G$ ist.
\end{quote}
Dann ist die Behauptung klar: Zu zeigen ist, dass~$K \subseteq G$ und dass~$K$
die Identitätspermutation enthält und unter Komposition und Inversenbildung
abgeschlossen ist. Letzteres gilt nach Voraussetzung, und ersteres folgt aus~$K
\subseteq H$ und~$H \subseteq G$.

\item Wir unterscheiden mehrere Fälle. Falls~$i = 0$ oder~$j = 0$, ist die
Behauptung klar (wieso?). Für~$i,j > 0$ gilt
\[ \sigma^i \circ \sigma^j =
  \underbrace{\sigma \circ \cdots \circ \sigma}_{\text{$i$ Faktoren}}
  \circ
  \underbrace{\sigma \circ \cdots \circ \sigma}_{\text{$j$ Faktoren}} =
  \underbrace{\sigma \circ \cdots \circ \sigma}_{\text{$i+j$ Faktoren}} =
  \sigma^{i+j}. \]
Für~$i, j < 0$ gilt
\[ \sigma^i \circ \sigma^j =
  \underbrace{\sigma^{-1} \circ \cdots \circ \sigma^{-1}}_{\text{$-i$ Faktoren}}
  \circ
  \underbrace{\sigma^{-1} \circ \cdots \circ \sigma^{-1}}_{\text{$-j$ Faktoren}} =
  \underbrace{\sigma^{-1} \circ \cdots \circ \sigma^{-1}}_{\text{$-(i+j)$ Faktoren}} =
  \sigma^{i+j}. \]
Für~$i > 0, j < 0, i > -j$ gilt
\[ \sigma^i \circ \sigma^j =
  \underbrace{\sigma \circ \cdots \circ \sigma}_{\text{$i$ Faktoren}}
  \circ
  \underbrace{\sigma^{-1} \circ \cdots \circ \sigma^{-1}}_{\text{$-j$ Faktoren}} =
  \underbrace{\sigma \circ \cdots \circ \sigma}_{\text{$i+j$ Faktoren}} =
  \sigma^{i+j}. \]
Analog behandelt man den Fall~$i > 0, j < 0, i < -j$ und den Fall~$i < 0, j >
0$.
\end{loesungE}
\end{aufgabe}

\ifloesungen\newpage\fi
\begin{aufgabe}{Elementordnungen}
\begin{enumerate}
\item Sei~$G$ eine Gruppe und $\sigma \in G$ ein Element der Ordnung~$n$.
Zeige, dass die Ordnung einer be\-lie\-bi\-gen Potenz~$\sigma^m$ durch~$n \mathrel{/}
\operatorname{ggT}(n,m)$ gegeben ist.

\item Bestimme die Ordnungen aller Elemente der zyklischen Gruppe~$\CCC_n$.

\item Bestimme alle Erzeuger der zyklischen Gruppe~$\CCC_n$.
\end{enumerate}

\begin{loesungE}
\item Wir müssen also folgende Frage beantworten: Für welchen Exponenten~$k
\geq 1$ ist~$(\sigma^m)^k$ das erste Mal gleich der Identitätspermutation?
Da für eine ganze Zahl~$\ell$ genau dann~$\sigma^\ell = \id$ gilt, wenn~$\ell$
ein Vielfaches von~$n$ ist, können wir die Frage äquivalent umformulieren: Für
welchen Exponenten~$k \geq 1$ ist~$m \cdot k$ das erste Mal ein Vielfaches
von~$n$? Diese Frage nun können wir mit Schulwissen beantworten: Das ist dann
der Fall, wenn~$m \cdot k$ das kleinste gemeinsame Vielfache von~$n$ und~$m$
ist, also wenn~$k = \operatorname{kgV}(n,m) \mathrel{/} m = nm \mathrel{/}
(\operatorname{ggT}(n,m) \cdot m) = n \mathrel{/}
\operatorname{ggT}(n,m)$ ist.

\item Die zyklische Gruppe ist durch
\[ \CCC_n = \{ \tau^0, \ldots, \tau^{n-1} \} \]
gegeben, wobei~$\tau =
\begin{pmatrix}1&2&\cdots&n-1&n\\2&3&\cdots&n&1\end{pmatrix} \in \SSS_n$.
Diese Permutation~$\tau$ hat Ordnung~$n$. Daher
folgt für die Ordnungen nach Teilaufgabe~a)
\[ \ord \tau^m = n \mathrel{/} \operatorname{ggT}(n,m). \]

\item Ein \emph{Erzeuger} einer endlichen Gruppe~$G$ ist ein solches
Element~$\sigma \in G$, sodass alle Elemente von~$G$ gewisse Potenzen
von~$\sigma$ sind. Das ist gleichbedeutend damit, dass die Ordnung von~$\sigma$
gleich der Gruppenordnung ist: Denn in der unendlichen Liste
\[ \ldots, \sigma^{-2}, \sigma^{-1}, \sigma^0, \sigma^1, \sigma^2, \ldots \]
kommen genau~$(\ord g)$ viele verschiedene Gruppenelemente vor.

Mit dieser allgemeinen Überlegung können wir die Frage der Aufgabe klären: Ein
beliebiges Element~$\tau^m \in \CCC_n$ ist genau dann ein Erzeuger
von~$\CCC_n$, wenn seine Ordnung~$n / \operatorname{ggT}(n,m)$ gleich~$n$ ist,
also wenn~$n$ und~$m$ zueinanander teilerfremd sind.
\end{loesungE}
\end{aufgabe}

\begin{aufgabe}{Kreisteilungspolynome}
\begin{enumerate}
\item Berechne die Kreisteilungspolynome~$\Phi_3(X)$, $\Phi_6(X)$
und~$\Phi_9(X)$.

\item Zerlege das Polynom~$X^3 + X^2 + X + 1$ über den rationalen Zahlen
in irreduzible Faktoren.
\end{enumerate}

\begin{loesungE}
\item Bekanntermaßen gilt~$\Phi_1 = X - 1$ und~$\Phi_2 = X + 1$. Dann folgt
jeweils mit Polynomdivision:
\begin{align*}
  X^3 - 1 &= \Phi_1 \cdot \Phi_3
    & \Longrightarrow \Phi_3 &= X^2 + X + 1 \\
  X^6 - 1 &= \Phi_1 \cdot \Phi_2 \cdot \Phi_3 \cdot \Phi_6
    & \Longrightarrow \Phi_6 &= X^2 - X + 1 \\
  X^9 - 1 &= \Phi_1 \cdot \Phi_3 \cdot \Phi_9
    & \Longrightarrow \Phi_9 &= X^6 + X^3 + 1
\end{align*}

\item Wir fügen zunächst künstlich den Faktor~$(X-1)$ hinzu:
\[ (X^3 + X^2 + X + 1) \cdot (X-1) =
  X^4 - 1 = \Phi_1 \cdot \Phi_2 \cdot \Phi_4 =
  (X-1) \cdot (X+1) \cdot (X^2+1). \]
Dann können wir ihn wieder kürzen, und erhalten so die Zerlegung
\[ X^3 + X^2 + X + 1 = (X+1) \cdot (X^2 + 1). \]
Die auftretenden Faktoren sind (wie alle Kreisteilungspolynome) irreduzibel
über den rationalen Zahlen.
\end{loesungE}
\end{aufgabe}

\begin{aufgabe}{Etwas Zahlentheorie}
Sei~$p$ eine Primzahl.
\begin{enumerate}
\item Gib eine Primfaktorzerlegung von~$X^{p-1}-1$
modulo~$p$ an.
\item Zeige, dass der Binomialkoeffizient~$\binom{p^2}{p}$ durch~$p$, aber
nicht durch~$p^2$ teilbar ist.
\end{enumerate}

\begin{loesungE}
\item Nach dem kleinen Satz von Fermat gilt für alle ganzen Zahlen~$a$ die
Beziehung
\[ a^p \equiv a \mod p. \]
Für solche ganze Zahlen~$a$, die modulo~$p$ invertierbar sind (d.\,h. die
teilerfremd zu~$p$ sind), kann man~$a$ auf beiden Seiten einmal kürzen, sodass
man die Beziehung
\[ a^{p-1} \equiv 1 \mod p \]
erhält. Folglich besitzt das gegebene Polynom modulo~$p$ die~$p-1$
verschiedenen Nullstellen~$1,2,\ldots,{p-1}$. Aus Gradgründen folgt dann schon:
\[ X^{p-1} - 1 \equiv (X-1) (X-2) \cdots (X-(p-1)) \mod p. \]

\emph{Bemerkung:} Der kleine Satz von Fermat besagt \emph{nicht}, dass die
Polynomkongruenzen~$X^p \equiv X$ oder~$X^{p-1} \equiv 1$ gelten.

\item Wir rechnen:
\begin{align*}
  \binom{p^2}{p} &=
  \frac{p^2 \cdot (p^2 - 1) \cdots (p^2 - p + 2) \cdot (p^2 - p + 1)}{p \cdot
  (p-1) \cdots 2 \cdot 1} \\[0.5em]
  &= p \cdot \frac{(p^2 - 1) \cdot (p^2-2) \cdots (p^2 - p + 2) \cdot (p^2 - p + 1)}{(p-1)
  \cdot (p-2) \cdots 2 \cdot 1} \\[0.5em]
  &= p \cdot \binom{p^2-1}{p-1}
\end{align*}
Da der hintere Faktor wie jeder Binomialkoeffizient eine ganze Zahl ist, ist
daher~$p$ ein Teiler von~$\binom{p^2}{p}$. Ferner ist~$p^2$ aber kein Teiler,
da im Zähler des hinteren Faktors die Primzahl~$p$ kein einziges Mal vorkommt
(wieso?) [im Nenner auch nicht, aber das tut nichts zur Sache].
\end{loesungE}
\end{aufgabe}

\ifloesungen\newpage\fi
\begin{aufgabe}{Primitive Wurzeln}
\begin{enumerate}
\item Gib alle primitiven Wurzeln \emph{modulo~$5$} an.

\item Sei~$X$ die Menge der~$n$-ten \emph{komplexen} Einheitswurzeln. Zeige, dass die
Abbildung
\[ \sigma_d : X \longrightarrow X,\ \zeta \longmapsto \zeta^d \]
genau dann eine Bijektion ist, wenn die feste natürliche Zahl~$d$ teilerfremd
zu~$n$ ist.
\end{enumerate}

\begin{loesungE}
\item Eine \emph{primitive Wurzel modulo~$p$} ist eine solche~$(p-1)$-te
Einheitswurzel in~$\ZZ/(p)$, sodass jede~$(p-1)$-te Einheitswurzel in~$\ZZ/(p)$
eine gewisse Potenz von ihr ist.

Von den Zahlen~$0,1,2,3,4$ sind genau die Zahlen~$1,2,3,4$ vierte
Einheitswurzeln, denn es gilt
\begin{align*}
  0^4 &\equiv 0, & 1^4 &\equiv 1, & 2^4 &\equiv 1, & 3^4 &\equiv 1, &
  4^4 &\equiv 1
\end{align*}
modulo~$5$. Zur Überprüfung der Primitivität legen wir folgende Tabelle an:
\begin{center}
  \begin{tabular}{r|c|c|c|c|c|c|c}
    $\xi$ & $\xi^0$ & $\xi^1$ & $\xi^2$ & $\xi^3$ & $\xi^4$ & $\xi^5$ & $\cdots$ \\\hline
    $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $\cdots$ \\
    $2$ & $1$ & $2$ & $4$ & $3$ & $1$ & $2$ & $\cdots$ \\
    $3$ & $1$ & $3$ & $4$ & $2$ & $1$ & $3$ & $\cdots$ \\
    $4$ & $1$ & $4$ & $1$ & $4$ & $1$ & $4$ & $\cdots$
  \end{tabular}
\end{center}
Also sind~$2$ und~$3$ primitive Wurzeln modulo~$5$, da in ihren Zeilen
\emph{alle} vierten Einheitswurzeln vorkommen. Die Zahlen~$1$ und~$4$ sind zwar
vierte Einheitswurzeln, aber nicht primitive vierte Einheitswurzeln.

\item \emph{Fall 1:} $d$ ist teilerfremd zu~$n$. Dann gibt es eine
Bézoutdarstellung~$1 = ad + bn$. Folglich ist~$\sigma_a$ Umkehrabbildung
zu~$\sigma_d$: Für alle~$\zeta \in X$ gilt
\[ (\sigma_a \circ \sigma_d)(\zeta) =
  (\zeta^d)^a = \zeta^{1 - bn} = \zeta \cdot (\zeta^n)^{-b} = \zeta \cdot 1 =
  \zeta \]
und analog gilt~$(\sigma_d \circ \sigma_a)(\zeta) = \zeta$.

\emph{Fall 2:} $d$ ist nicht teilerfremd zu~$n$. Dann gibt es also einen
gemeinsamen Teiler~$k \geq 2$, sodass~$d = pk$ und~$n = qk$ für gewisse~$p,q
\geq 0$. Sei~$\zeta_0$ eine feste primitive~$n$-te Einheitswurzel. Dann folgt
\[ \sigma_d(\zeta_0^q) = \zeta_0^{qd} = \zeta_0^{qpk} = \zeta_0^{np} =
(\zeta_0^n)^p = 1^p = 1 = \sigma_d(1), \]
also ist~$\sigma_d$ nicht injektiv (es gilt~$\zeta_0^q \neq 1 = \zeta_0^0$) und
somit insbesondere nicht bijektiv.
\end{loesungE}
\end{aufgabe}

Zur Erinnerung: \textbf{Algebra-Treffen} am 10. Juli um 18:30 Uhr

\end{document}
