Mercurial > 13ws.ds
view notes/tex/algebra.tex @ 56:1cbb4a5e6ce7
nicer euklid; ue15 notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Tue, 25 Feb 2014 00:26:19 +0100 |
parents | 4192e96b7b3e |
children |
line wrap: on
line source
\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}, +_{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}, +_{10}, 0}$ die Restklassen Modulo 10.\\ Dann ist $H = \alg{\left\{ 0, 2, 4, 6, 8 \right\}, +_{10}, 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, +_i, 0}$ sind zyklisch mit dem Generator $1$.\\ Betrachte $\alg{\Z_7, +_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} \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{alignat}{2} \alert{21} &= 1 \cdot \structure{99} - 1 \cdot \structure{78} \\ \alert{15} &= 1 \cdot \structure{78} - 3 \cdot \structure{21} &&= -\hphantom{1}3 \cdot \structure{99} + \hphantom{1}4 \cdot \structure{78} \\ \alert{6} &= 1 \cdot \structure{21} - 1 \cdot \structure{15} &&= \hphantom{-1}4 \cdot \structure{99} - \hphantom{1}5 \cdot \structure{78} \\ \alert{3} &= 1 \cdot \structure{15} - 2 \cdot \hphantom{1}\structure{6} &&= -11 \cdot \structure{99} + 14 \cdot \structure{78} \end{alignat} \vspace{-2em} \end{example} \end{frame} \begin{frame} \frametitle{Erweiterter Euklidscher Algorithmus} \begin{theorem}[] Die vorhergehende Rechnung kann kompakter in einer Tabelle dargestellt werden. Setze dazu \begin{align} q_k &= r_{k-1} \div r_k & s_k &= s_{k-2} - s_{k-1} \cdot q_{k-1} \\ r_k &= r_{k-2} \mod r_{k-1} & t_k &= t_{k-2} - t_{k-1} \cdot q_{k-1} \end{align} Und initialisiere die Tabelle folgendermaßen: \begin{center} \tabulinesep=3pt \begin{tabu} {c|[1pt]cccc} $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-} 0 & - & 99 & 1 & 0 \\ 1 & & 78 & 0 & 1 \\ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ n & - & 0 & - & - \end{tabu} \end{center} Dann gilt für jedes $k$: $a \cdot s_k + b \cdot t_k = r_k$ und \begin{align} a \cdot s_{n-1} + b \cdot t_{n-1} = \ggt(a,b) \end{align} \end{theorem} \end{frame} \begin{frame} \frametitle{Erweiterter Euklidscher Algorithmus} \begin{example}[] Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.\\ \begin{center} \tabulinesep=3pt \begin{tabu} {c|[1pt]cccc} $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-} 0 & - & \structure{99} & 1 & 0 \\ 1 & 1 & \structure{78} & 0 & 1 \\ 2 & 3 & 21 & 1 & -1 \\ 3 & 1 & 15 & -3 & 4 \\ 4 & 2 & 6 & 4 & -5 \\ 5 & 2 & \alert{3} & \alert{-11} & \alert{14} \\ 6 & - & 0 & - & - \end{tabu} \end{center} Es ist $\alert{3} = \alert{-11} \cdot \structure{99} + \alert{14} \cdot \structure{78}$. \end{example} \end{frame} }