\defineUnit{algebradefinitionen}{%
\begin{frame}
    \frametitle{Modulo}

    \begin{definition}[Modulo-Kongruenz]
        Zwei Zahlen $a, b \in \Z$ heißen \structure{kongruent Modulo $n \in \N$}, falls
        \begin{align}
            \exists k \in Z.\; a = k \cdot n + b
        \end{align}
        Wir schreiben dann $a \equiv b \pmod n$ oder $a \equiv_n b$.\\
        Durch $\equiv_n$ wird eine \alert{Äquivalenzrelation} definiert.
    \end{definition}

    \begin{definition}[Modulo-Operator]
        Der \structure{Modulo-Operator} ordnet jeder Zahl $a \in \Z$ seine Äquivalenzklasse (\structure{Restklasse}) Modulo $n \in \N$ zu. Es gilt
        \begin{align}
            a \mod n = r \text{\qquad gdw. \qquad} \exists q \in \Z.\; a = q \cdot n + r \text{\quad mit \quad } 0 \leq r < n
        \end{align}
        Modulo gibt den \alert{Rest} bei einer \alert{Ganzzahldivision} zurück.
    \end{definition}

    \vfill

    \begin{example}[]
        \vspace{-1.5em}
        \begin{align}
            5 \mod 3 &= 2 & 6 \mod 3 &= 0 & -5 \mod 3 &= 1
        \end{align}
        \vspace{-1.5em}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Algebren}

    \begin{definition}[Algebra]
        Eine \structure{Algebra $\langle M, \left( \circ_i \right)_{i \in I}\rangle$} besteht aus einer Menge von Operanden und einer oder mehrerer innerer Verknüpfungen.\\
        Eine \structure{innere Verknüpfung} auf $M$ ist eine Abbildung
        \begin{align}
            \circ : M \times M \to M
        \end{align}
        Eine Verknüpfung heißt
        \begin{description}[kommutativ\qquad]
            \item[assoziativ] wenn $\left( a \circ b \right) \circ c = a \circ \left( b \circ c \right)$
            \item[kommutativ] wenn $a \circ b = b \circ a$
        \end{description}
        für alle $a, b, c \in M$.
    \end{definition}

    \vfill

    \begin{example}[]
        Einige Beispiele für Algebren sind (mit üblichen Verknüpfungen)
        \begin{itemize}
            \item $\langle \Z, +, \cdot \rangle$ die ganzen Zahlen
            \item $\langle \Z_{11}, +\rangle$ die Restklassen Modulo 11
            \item $\langle \R^3, +, \cdot\rangle$ der 3-Dimensionale $\R$-Vektorraum
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Gruppen}

    \begin{definition}[Gruppe]
        Eine Algebra $\alg{G, \circ, e}$ heißt \structure{Gruppe}, wenn für alle $a, b, c \in G$ gilt
        \begin{description}[Neutrales Element\qquad]
            \item[Assoziativität] $(a \circ b) \circ c = a \circ (b \circ c)$
            \item[Neutrales Element] Für $e$ gilt $a \circ e = e \circ a = a$
            \item[Inverse Elemente] Es gibt $a^{-1}$ mit $a \circ a^{-1} = a^{-1} \circ a = e$
        \end{description}
        Wir schreiben auch kurz $G$.\\
        Wir nennen $G$ \structure{abelsch (oder kommutativ)}, wenn $\circ$ kommutativ ist.
    \end{definition}

    \begin{example}[]
        Die Menge $[4]$ zusammen mit der Multiplikation modulo $5$ beschreibt die Gruppe $\alg{[4], \cdot_5, 1} = \Z^*_5$.
        \vspace{.5em}
        \begin{columns}[T]
            \begin{column}{.4\textwidth}
                \centering
                \tabulinesep=3pt
                \begin{tabu} to .8\textwidth {X|[1pt]XXXX}
                    $\cdot_5$ & 1 & 2 & 3 & 4\\\tabucline[1pt]{-}
                    1 & 1 & 2 & 3 & 4\\
                    2 & 2 & 4 & 1 & 3\\
                    3 & 3 & 1 & 4 & 2\\
                    4 & 4 & 3 & 2 & 1\\
                \end{tabu}
            \end{column}
            \begin{column}{.6\textwidth}
                \begin{itemize}
                    \item Erfüllt \enquote{Sudokuprinzip}
                    \item Multiplikation ist assoziativ
                    \item $1$ ist neutrales Element
                    \item Inverse existieren
                    \item Kommutativ da symmetrisch
                \end{itemize}
            \end{column}
        \end{columns}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Untergruppen}

    \begin{definition}[Untergruppe]
        Sei $G$ eine Gruppe und $H \subseteq G$ eine Teilmenge.\\
        $H$ heißt \structure{Untergruppe} von $G$, wenn für $a, b \in H$ gilt
        \begin{description}[Abgeschlossenheit\qquad]
            \item[Abgeschlossenheit] $a \circ b \in H$
            \item[Inverse] $a^{-1} \in H$
        \end{description}
        Wir schreiben $H < G$.
    \end{definition}

    \begin{itemize}
        \item Um zu zeigen dass $H < G$ gilt, reicht es zu zeigen dass
            \begin{align}
                a, b \in H \rightarrow ab^{-1} \in H
            \end{align}
        \item Jede Gruppe enthält $\left\{ e \right\}$ und sich selbst als Untergruppe
    \end{itemize}

    \begin{example}[]
        Betrachte $G = \alg{\Z_{10}, +, 0}$ die Restklassen Modulo 10.\\
        Dann ist $H = \alg{\left\{ 0, 2, 4, 6, 8 \right\}, +, 0}$ eine Untergruppe von $G$, da die Summe zweier gerader Zahlen gerade ist und für $a \in H$ gilt, dass $a^{-1} = 10 - a \in H$.
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Ordnung und Erzeugnis}

    Sei $\alg{G, \circ, e}$ eine Gruppe.
    \begin{definition}[Ordnung]
        Die \structure{Ordnung} eines Elements $a \in G$ ist die kleinste Potenz $k$, sodass $a^k = e$.
        \begin{align}
            \ord(a) \defeq \min \left\{ k \in \N \setminus \left\{ 0 \right\} \mid a^k = e \right\}
        \end{align}
        Existiert kein solches $k$, so ist $\ord(a) \defeq \infty$.
    \end{definition}

    \vfill

    \begin{definition}[Erzeugnis]
        Das \structure{Erzeugnis $\alg{a}$} von $a$ in $G$ ist die Menge aller Elemente, die durch Potenzierung von $a$ und $a^{-1}$ erhalten werden können.
        \begin{align}
            \alg{a} \defeq \left\{ a^k \mid k \in \alert{\Z} \right\}
        \end{align}
        Es gilt $\alg{a} < G$.
    \end{definition}
\end{frame}

\begin{frame}
    \frametitle{Zyklische Gruppen}

    \begin{definition}[Zyklische Gruppe]
        Man nennt eine Gruppe $G$ \structure{zyklisch}, wenn ein Element $a \in G$ existiert, sodass $a$ die gesamte Gruppe erzeugt.
        \begin{align}
            \alg{a} = G
        \end{align}
        Man nennt $a$ einen \structure{Generator (oder Erzeuger)}.
    \end{definition}

    \begin{itemize}
        \item Alle Untergruppen einer zyklischen Gruppe sind \alert{zyklisch}
        \item Zyklische Gruppen sind isomorph zu einer $\Z_i$ oder $\Z$
    \end{itemize}

    \vfill

    \begin{example}[]
        Die ganzen Zahlen $\Z$ und alle Gruppen der Form $\alg{\Z_i, +, 0}$ sind zyklisch mit dem Generator $1$.\\
        Betrachte $\alg{\Z_7, +, 0}$. Es ist
        \begin{itemize}
            \item $\Z_7 = \left\{ 0, 1, 2, 3, 4, 5, 6 \right\}$
            \item $\alg{2} = \left\{ 2, 4, 6, 1, 3, 5, 0 \right\} = \alg{1} = \Z_7$
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Homomorphismen}

    Seien $\alg{G, \circ, e}$ und $\alg{G^\prime, \bullet, e^\prime}$ Gruppen.
    \begin{definition}[Homomorphismus]
        Eine Abbildung $\varphi : G \to G^\prime$ heißt \structure{Homomorphismus}, wenn gilt
        \begin{align}
            \varphi(a \circ b) = \varphi(a) \bullet \varphi(b)
        \end{align}
        Ist $\varphi$ bijektiv, so nennt man sie einen \structure{Isomorphismus}.
    \end{definition}

    \begin{itemize}
        \item Homomorphismen sind \alert{strukturerhaltend}
        \item Sie betten eine Gruppe in eine andere ein
    \end{itemize}

    \vfill

    \begin{theorem}[]
        Ist $\varphi : G \to G^\prime$ ein Homomorphismus, so gilt
        \begin{itemize}
                \item $\varphi(e) = e^\prime$
                \item Für alle $a \in G$ gilt $\varphi(a)^{-1} = \varphi(a^{-1})$
                \item Ist $H < G$, dann auch $\varphi(H) < G^\prime$
        \end{itemize}
    \end{theorem}
\end{frame}

\begin{frame}
    \frametitle{Nebenklassen}

    Sei $\alg{G, \circ, e}$ eine Gruppe und $H < G$.
    \begin{definition}[Nebenklasse]
        Zu einem Element $a \in G$ nennen wir
        \begin{align}
            aH &\defeq \left\{ ax \mid x \in H \right\}\\
            Ha &\defeq \left\{ xa \mid x \in H \right\}
        \end{align}
        die \structure{linke/rechte Nebenklasse} von $a$ bezüglich $H$.\\
        Die Anzahl der Nebenklassen zu $H$ nennt man ihren \structure{Index $\ind(G: H)$}.
    \end{definition}

    \begin{itemize}
        \item Die Nebenklassen zu $H$ sind eine \alert{Partition} von $G$
    \end{itemize}

    \vfill

    \begin{theorem}[Satz von Lagrange]
        Ist $G$ eine endliche Gruppe, so gilt
        \begin{align}
            \ord(G) &= \ord(H) \cdot \ind(G : H)
        \end{align}
        Daraus folgt direkt \structure{$\ord(a) \mid \ord(G)$} für alle $a \in G$.
    \end{theorem}
\end{frame}

\begin{frame}
    \frametitle{Eulersche $\varphi$-Funktion}

    \begin{definition}[Eulersche $\varphi$-Funktion]
        Die Funktion $\varphi : \N \setminus \left\{ 0 \right\} \to \N$ heißt \structure{Eulersche $\varphi$-Funktion}. Sie ist definiert durch die Anzahl der zu $n$ \alert{teilerfremden} Zahlen.
        \begin{align}
            \varphi(n) \defeq \abs{\left\{ x \mid x \in [n], \ggt(x, n) = 1 \right\}}
        \end{align}
        \vspace{-1.5em}
    \end{definition}

    Es gilt für
    \begin{description}[$p$ prim, $k > 0$\qquad]
        \item[$\ggt(m, n) = 1$] $\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)$
        \item[$p$ prim] $\varphi(p) = p - 1$
        \item[$p$ prim, $k > 0$] $\varphi(p^k) = p^{k -1} (p - 1)$
    \end{description}

    \begin{theorem}[Euler-Fermat]
        Für $m \in \N$ mit $m \geq 2$ und $k \in \Z$ mit $\ggt(k, m) = 1$ gilt
        \begin{align}
            k^{\varphi(m)} &\equiv 1 \pmod m
            \intertext{ist $p$ prim, so gilt im speziellen}
            k^{p - 1} &\equiv 1 \pmod p
        \end{align}
        \vspace{-2em}
    \end{theorem}
\end{frame}
}

\defineUnit{erweitertereuklid}{%
\begin{frame}
    \frametitle{Erweiterter Euklidscher Algorithmus}

    \vspace{-1em}
    \begin{block}{Erweiterter Euklidscher Algorithmus}
        Der \structure{erweiterte Euklische Algorithmus} berechnet für zwei Zahlen $a, b \in \N$ ganze Zahlen $x, y \in \Z$, sodass gilt
        \begin{align}
            a \cdot x + b \cdot y &= \ggt(x, y)
            %\intertext{Er verwendet dazu die Beobachtung, dass für $a > b > 0$ gilt}
            %\ggt(a, b) &= \ggt(b, a-b)
        \end{align}
        \vspace{-1.5em}
    \end{block}

    \begin{example}[]
        Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.
        \begin{align}
            \structure{99} &= 1 \cdot \structure{78} + \structure{21} &&\longrightarrow& \alert{21} &= \structure{99} - 1 \cdot \structure{78} \\
            \structure{78} &= 3 \cdot \structure{21} + \structure{15} &&\longrightarrow& \alert{15} &= \structure{78} - 3 \cdot \structure{21} \\
            \structure{21} &= 1 \cdot \structure{15} + \hphantom{1}\structure{6} &&\longrightarrow& \alert{6} &= \structure{21} - 1 \cdot \structure{15} \\
            \structure{15} &= 2 \cdot \hphantom{1}\structure{6} + \hphantom{1}\structure{3} &&\longrightarrow& \alert{3} &= \structure{15} - 2 \cdot \structure{6} \\
            \structure{6} &= 2 \cdot \hphantom{1}\structure{3} + \hphantom{1}\structure{0}
        \end{align}
        \vspace{-1.5em}
        \begin{align}
            \alert{3} &= \hphantom{(-)}1 \cdot \structure{15} - \hphantom{1}2 \cdot \structure{6} \\
            &= \hphantom{(-)}1 \cdot \structure{15} - \hphantom{1}2 \cdot \left( \structure{21} - 1 \cdot \structure{15} \right) = \hphantom{1}(-2) \cdot \structure{21} + \hphantom{1}3 \cdot \structure{15} \\
            &= (-2) \cdot \structure{21} + \hphantom{1}3 \cdot \left( \structure{78} - 3 \cdot \structure{21} \right) = \hphantom{(-1)}3 \cdot \structure{78} -11 \cdot \structure{21} \\
            &= \hphantom{(-)}3 \cdot \structure{78} - 11 \cdot \left( \structure{99} - 1 \cdot \structure{78} \right) = (-11) \cdot \alert{99} + 14 \cdot \alert{78}
        \end{align}
        \vspace{-2em}
    \end{example}
\end{frame}
}