13ws.ds: notes/tex/algebra.tex annotate

annotate 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

rev	line source
53 a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	1 \defineUnit{algebradefinitionen}{%
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	2 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	3 \frametitle{Modulo}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	4
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	5 \begin{definition}[Modulo-Kongruenz]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	6 Zwei Zahlen $a, b \in \Z$ heißen \structure{kongruent Modulo $n \in \N$}, falls
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	7 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	8 \exists k \in Z.\; a = k \cdot n + b
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	9 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	10 Wir schreiben dann $a \equiv b \pmod n$ oder $a \equiv_n b$.\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	11 Durch $\equiv_n$ wird eine \alert{Äquivalenzrelation} definiert.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	12 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	13
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	14 \begin{definition}[Modulo-Operator]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	15 Der \structure{Modulo-Operator} ordnet jeder Zahl $a \in \Z$ seine Äquivalenzklasse (\structure{Restklasse}) Modulo $n \in \N$ zu. Es gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	16 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	17 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
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	18 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	19 Modulo gibt den \alert{Rest} bei einer \alert{Ganzzahldivision} zurück.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	20 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	21
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	22 \vfill
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	23
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	24 \begin{example}[]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	25 \vspace{-1.5em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	26 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	27 5 \mod 3 &= 2 & 6 \mod 3 &= 0 & -5 \mod 3 &= 1
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	28 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	29 \vspace{-1.5em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	30 \end{example}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	31 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	32
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	33 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	34 \frametitle{Algebren}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	35
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	36 \begin{definition}[Algebra]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	37 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.\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	38 Eine \structure{innere Verknüpfung} auf $M$ ist eine Abbildung
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	39 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	40 \circ : M \times M \to M
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	41 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	42 Eine Verknüpfung heißt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	43 \begin{description}[kommutativ\qquad]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	44 \item[assoziativ] wenn $\left( a \circ b \right) \circ c = a \circ \left( b \circ c \right)$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	45 \item[kommutativ] wenn $a \circ b = b \circ a$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	46 \end{description}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	47 für alle $a, b, c \in M$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	48 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	49
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	50 \vfill
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	51
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	52 \begin{example}[]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	53 Einige Beispiele für Algebren sind (mit üblichen Verknüpfungen)
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	54 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	55 \item $\langle \Z, +, \cdot \rangle$ die ganzen Zahlen
54 4192e96b7b3e qualify modulo operations Markus Kaiser <markus.kaiser@in.tum.de> parents: 53 diff changeset	56 \item $\langle \Z_{11}, +_{11}\rangle$ die Restklassen Modulo 11
53 a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	57 \item $\langle \R^3, +, \cdot\rangle$ der 3-Dimensionale $\R$-Vektorraum
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	58 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	59 \end{example}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	60 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	61
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	62 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	63 \frametitle{Gruppen}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	64
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	65 \begin{definition}[Gruppe]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	66 Eine Algebra $\alg{G, \circ, e}$ heißt \structure{Gruppe}, wenn für alle $a, b, c \in G$ gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	67 \begin{description}[Neutrales Element\qquad]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	68 \item[Assoziativität] $(a \circ b) \circ c = a \circ (b \circ c)$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	69 \item[Neutrales Element] Für $e$ gilt $a \circ e = e \circ a = a$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	70 \item[Inverse Elemente] Es gibt $a^{-1}$ mit $a \circ a^{-1} = a^{-1} \circ a = e$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	71 \end{description}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	72 Wir schreiben auch kurz $G$.\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	73 Wir nennen $G$ \structure{abelsch (oder kommutativ)}, wenn $\circ$ kommutativ ist.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	74 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	75
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	76 \begin{example}[]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	77 Die Menge $[4]$ zusammen mit der Multiplikation modulo $5$ beschreibt die Gruppe $\alg{[4], \cdot_5, 1} = \Z^*_5$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	78 \vspace{.5em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	79 \begin{columns}[T]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	80 \begin{column}{.4\textwidth}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	81 \centering
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	82 \tabulinesep=3pt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	83 \begin{tabu} to .8\textwidth {X\|[1pt]XXXX}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	84 $\cdot_5$ & 1 & 2 & 3 & 4\\\tabucline[1pt]{-}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	85 1 & 1 & 2 & 3 & 4\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	86 2 & 2 & 4 & 1 & 3\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	87 3 & 3 & 1 & 4 & 2\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	88 4 & 4 & 3 & 2 & 1\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	89 \end{tabu}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	90 \end{column}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	91 \begin{column}{.6\textwidth}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	92 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	93 \item Erfüllt \enquote{Sudokuprinzip}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	94 \item Multiplikation ist assoziativ
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	95 \item $1$ ist neutrales Element
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	96 \item Inverse existieren
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	97 \item Kommutativ da symmetrisch
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	98 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	99 \end{column}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	100 \end{columns}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	101 \end{example}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	102 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	103
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	104 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	105 \frametitle{Untergruppen}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	106
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	107 \begin{definition}[Untergruppe]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	108 Sei $G$ eine Gruppe und $H \subseteq G$ eine Teilmenge.\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	109 $H$ heißt \structure{Untergruppe} von $G$, wenn für $a, b \in H$ gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	110 \begin{description}[Abgeschlossenheit\qquad]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	111 \item[Abgeschlossenheit] $a \circ b \in H$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	112 \item[Inverse] $a^{-1} \in H$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	113 \end{description}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	114 Wir schreiben $H < G$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	115 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	116
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	117 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	118 \item Um zu zeigen dass $H < G$ gilt, reicht es zu zeigen dass
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	119 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	120 a, b \in H \rightarrow ab^{-1} \in H
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	121 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	122 \item Jede Gruppe enthält $\left\{ e \right\}$ und sich selbst als Untergruppe
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	123 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	124
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	125 \begin{example}[]
54 4192e96b7b3e qualify modulo operations Markus Kaiser <markus.kaiser@in.tum.de> parents: 53 diff changeset	126 Betrachte $G = \alg{\Z_{10}, +_{10}, 0}$ die Restklassen Modulo 10.\\
4192e96b7b3e qualify modulo operations Markus Kaiser <markus.kaiser@in.tum.de> parents: 53 diff changeset	127 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$.
53 a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	128 \end{example}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	129 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	130
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	131 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	132 \frametitle{Ordnung und Erzeugnis}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	133
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	134 Sei $\alg{G, \circ, e}$ eine Gruppe.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	135 \begin{definition}[Ordnung]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	136 Die \structure{Ordnung} eines Elements $a \in G$ ist die kleinste Potenz $k$, sodass $a^k = e$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	137 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	138 \ord(a) \defeq \min \left\{ k \in \N \setminus \left\{ 0 \right\} \mid a^k = e \right\}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	139 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	140 Existiert kein solches $k$, so ist $\ord(a) \defeq \infty$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	141 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	142
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	143 \vfill
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	144
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	145 \begin{definition}[Erzeugnis]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	146 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.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	147 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	148 \alg{a} \defeq \left\{ a^k \mid k \in \alert{\Z} \right\}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	149 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	150 Es gilt $\alg{a} < G$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	151 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	152 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	153
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	154 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	155 \frametitle{Zyklische Gruppen}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	156
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	157 \begin{definition}[Zyklische Gruppe]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	158 Man nennt eine Gruppe $G$ \structure{zyklisch}, wenn ein Element $a \in G$ existiert, sodass $a$ die gesamte Gruppe erzeugt.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	159 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	160 \alg{a} = G
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	161 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	162 Man nennt $a$ einen \structure{Generator (oder Erzeuger)}.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	163 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	164
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	165 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	166 \item Alle Untergruppen einer zyklischen Gruppe sind \alert{zyklisch}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	167 \item Zyklische Gruppen sind isomorph zu einer $\Z_i$ oder $\Z$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	168 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	169
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	170 \vfill
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	171
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	172 \begin{example}[]
54 4192e96b7b3e qualify modulo operations Markus Kaiser <markus.kaiser@in.tum.de> parents: 53 diff changeset	173 Die ganzen Zahlen $\Z$ und alle Gruppen der Form $\alg{\Z_i, +_i, 0}$ sind zyklisch mit dem Generator $1$.\\
4192e96b7b3e qualify modulo operations Markus Kaiser <markus.kaiser@in.tum.de> parents: 53 diff changeset	174 Betrachte $\alg{\Z_7, +_7, 0}$. Es ist
53 a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	175 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	176 \item $\Z_7 = \left\{ 0, 1, 2, 3, 4, 5, 6 \right\}$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	177 \item $\alg{2} = \left\{ 2, 4, 6, 1, 3, 5, 0 \right\} = \alg{1} = \Z_7$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	178 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	179 \end{example}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	180 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	181
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	182 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	183 \frametitle{Homomorphismen}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	184
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	185 Seien $\alg{G, \circ, e}$ und $\alg{G^\prime, \bullet, e^\prime}$ Gruppen.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	186 \begin{definition}[Homomorphismus]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	187 Eine Abbildung $\varphi : G \to G^\prime$ heißt \structure{Homomorphismus}, wenn gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	188 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	189 \varphi(a \circ b) = \varphi(a) \bullet \varphi(b)
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	190 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	191 Ist $\varphi$ bijektiv, so nennt man sie einen \structure{Isomorphismus}.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	192 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	193
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	194 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	195 \item Homomorphismen sind \alert{strukturerhaltend}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	196 \item Sie betten eine Gruppe in eine andere ein
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	197 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	198
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	199 \vfill
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	200
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	201 \begin{theorem}[]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	202 Ist $\varphi : G \to G^\prime$ ein Homomorphismus, so gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	203 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	204 \item $\varphi(e) = e^\prime$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	205 \item Für alle $a \in G$ gilt $\varphi(a)^{-1} = \varphi(a^{-1})$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	206 \item Ist $H < G$, dann auch $\varphi(H) < G^\prime$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	207 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	208 \end{theorem}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	209 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	210
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	211 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	212 \frametitle{Nebenklassen}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	213
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	214 Sei $\alg{G, \circ, e}$ eine Gruppe und $H < G$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	215 \begin{definition}[Nebenklasse]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	216 Zu einem Element $a \in G$ nennen wir
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	217 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	218 aH &\defeq \left\{ ax \mid x \in H \right\}\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	219 Ha &\defeq \left\{ xa \mid x \in H \right\}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	220 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	221 die \structure{linke/rechte Nebenklasse} von $a$ bezüglich $H$.\\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	222 Die Anzahl der Nebenklassen zu $H$ nennt man ihren \structure{Index $\ind(G: H)$}.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	223 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	224
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	225 \begin{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	226 \item Die Nebenklassen zu $H$ sind eine \alert{Partition} von $G$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	227 \end{itemize}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	228
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	229 \vfill
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	230
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	231 \begin{theorem}[Satz von Lagrange]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	232 Ist $G$ eine endliche Gruppe, so gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	233 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	234 \ord(G) &= \ord(H) \cdot \ind(G : H)
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	235 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	236 Daraus folgt direkt \structure{$\ord(a) \mid \ord(G)$} für alle $a \in G$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	237 \end{theorem}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	238 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	239
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	240 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	241 \frametitle{Eulersche $\varphi$-Funktion}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	242
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	243 \begin{definition}[Eulersche $\varphi$-Funktion]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	244 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.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	245 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	246 \varphi(n) \defeq \abs{\left\{ x \mid x \in [n], \ggt(x, n) = 1 \right\}}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	247 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	248 \vspace{-1.5em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	249 \end{definition}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	250
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	251 Es gilt für
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	252 \begin{description}[$p$ prim, $k > 0$\qquad]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	253 \item[$\ggt(m, n) = 1$] $\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	254 \item[$p$ prim] $\varphi(p) = p - 1$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	255 \item[$p$ prim, $k > 0$] $\varphi(p^k) = p^{k -1} (p - 1)$
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	256 \end{description}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	257
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	258 \begin{theorem}[Euler-Fermat]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	259 Für $m \in \N$ mit $m \geq 2$ und $k \in \Z$ mit $\ggt(k, m) = 1$ gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	260 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	261 k^{\varphi(m)} &\equiv 1 \pmod m
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	262 \intertext{ist $p$ prim, so gilt im speziellen}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	263 k^{p - 1} &\equiv 1 \pmod p
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	264 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	265 \vspace{-2em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	266 \end{theorem}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	267 \end{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	268 }
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	269
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	270 \defineUnit{erweitertereuklid}{%
56 1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	271 %\begin{frame}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	272 %\frametitle{Erweiterter Euklidscher Algorithmus}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	273
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	274 %\vspace{-1em}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	275 %\begin{block}{Erweiterter Euklidscher Algorithmus}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	276 %Der \structure{erweiterte Euklische Algorithmus} berechnet für zwei Zahlen $a, b \in \N$ ganze Zahlen $x, y \in \Z$, sodass gilt
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	277 %\begin{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	278 %a \cdot x + b \cdot y &= \ggt(x, y)
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	279 %%\intertext{Er verwendet dazu die Beobachtung, dass für $a > b > 0$ gilt}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	280 %%\ggt(a, b) &= \ggt(b, a-b)
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	281 %\end{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	282 %\vspace{-1.5em}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	283 %\end{block}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	284
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	285 %\begin{example}[]
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	286 %Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	287 %\begin{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	288 %\structure{99} &= 1 \cdot \structure{78} + \structure{21} &&\longrightarrow& \alert{21} &= \structure{99} - 1 \cdot \structure{78} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	289 %\structure{78} &= 3 \cdot \structure{21} + \structure{15} &&\longrightarrow& \alert{15} &= \structure{78} - 3 \cdot \structure{21} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	290 %\structure{21} &= 1 \cdot \structure{15} + \hphantom{1}\structure{6} &&\longrightarrow& \alert{6} &= \structure{21} - 1 \cdot \structure{15} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	291 %\structure{15} &= 2 \cdot \hphantom{1}\structure{6} + \hphantom{1}\structure{3} &&\longrightarrow& \alert{3} &= \structure{15} - 2 \cdot \structure{6} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	292 %\structure{6} &= 2 \cdot \hphantom{1}\structure{3} + \hphantom{1}\structure{0}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	293 %\end{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	294 %\vspace{-1.5em}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	295 %\begin{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	296 %\alert{3} &= \hphantom{(-)}1 \cdot \structure{15} - \hphantom{1}2 \cdot \structure{6} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	297 %&= \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} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	298 %&= (-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} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	299 %&= \hphantom{(-)}3 \cdot \structure{78} - 11 \cdot \left( \structure{99} - 1 \cdot \structure{78} \right) = (-11) \cdot \alert{99} + 14 \cdot \alert{78}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	300 %\end{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	301 %\vspace{-2em}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	302 %\end{example}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	303 %\end{frame}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	304
53 a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	305 \begin{frame}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	306 \frametitle{Erweiterter Euklidscher Algorithmus}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	307
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	308 \vspace{-1em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	309 \begin{block}{Erweiterter Euklidscher Algorithmus}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	310 Der \structure{erweiterte Euklische Algorithmus} berechnet für zwei Zahlen $a, b \in \N$ ganze Zahlen $x, y \in \Z$, sodass gilt
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	311 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	312 a \cdot x + b \cdot y &= \ggt(x, y)
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	313 %\intertext{Er verwendet dazu die Beobachtung, dass für $a > b > 0$ gilt}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	314 %\ggt(a, b) &= \ggt(b, a-b)
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	315 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	316 \vspace{-1.5em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	317 \end{block}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	318
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	319 \begin{example}[]
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	320 Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	321 \begin{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	322 \structure{99} &= 1 \cdot \structure{78} + \structure{21} &&\longrightarrow& \alert{21} &= \structure{99} - 1 \cdot \structure{78} \\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	323 \structure{78} &= 3 \cdot \structure{21} + \structure{15} &&\longrightarrow& \alert{15} &= \structure{78} - 3 \cdot \structure{21} \\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	324 \structure{21} &= 1 \cdot \structure{15} + \hphantom{1}\structure{6} &&\longrightarrow& \alert{6} &= \structure{21} - 1 \cdot \structure{15} \\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	325 \structure{15} &= 2 \cdot \hphantom{1}\structure{6} + \hphantom{1}\structure{3} &&\longrightarrow& \alert{3} &= \structure{15} - 2 \cdot \structure{6} \\
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	326 \structure{6} &= 2 \cdot \hphantom{1}\structure{3} + \hphantom{1}\structure{0}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	327 \end{align}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	328 \vspace{-1.5em}
56 1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	329 \begin{alignat}{2}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	330 \alert{21} &= 1 \cdot \structure{99} - 1 \cdot \structure{78} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	331 \alert{15} &= 1 \cdot \structure{78} - 3 \cdot \structure{21} &&= -\hphantom{1}3 \cdot \structure{99} + \hphantom{1}4 \cdot \structure{78} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	332 \alert{6} &= 1 \cdot \structure{21} - 1 \cdot \structure{15} &&= \hphantom{-1}4 \cdot \structure{99} - \hphantom{1}5 \cdot \structure{78} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	333 \alert{3} &= 1 \cdot \structure{15} - 2 \cdot \hphantom{1}\structure{6} &&= -11 \cdot \structure{99} + 14 \cdot \structure{78}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	334 \end{alignat}
53 a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	335 \vspace{-2em}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	336 \end{example}
a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	337 \end{frame}
56 1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	338
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	339 \begin{frame}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	340 \frametitle{Erweiterter Euklidscher Algorithmus}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	341
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	342 \begin{theorem}[]
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	343 Die vorhergehende Rechnung kann kompakter in einer Tabelle dargestellt werden. Setze dazu
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	344 \begin{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	345 q_k &= r_{k-1} \div r_k & s_k &= s_{k-2} - s_{k-1} \cdot q_{k-1} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	346 r_k &= r_{k-2} \mod r_{k-1} & t_k &= t_{k-2} - t_{k-1} \cdot q_{k-1}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	347 \end{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	348 Und initialisiere die Tabelle folgendermaßen:
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	349 \begin{center}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	350 \tabulinesep=3pt
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	351 \begin{tabu} {c\|[1pt]cccc}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	352 $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	353 0 & - & 99 & 1 & 0 \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	354 1 & & 78 & 0 & 1 \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	355 $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	356 n & - & 0 & - & -
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	357 \end{tabu}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	358 \end{center}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	359 Dann gilt für jedes $k$: $a \cdot s_k + b \cdot t_k = r_k$ und
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	360 \begin{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	361 a \cdot s_{n-1} + b \cdot t_{n-1} = \ggt(a,b)
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	362 \end{align}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	363 \end{theorem}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	364 \end{frame}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	365
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	366 \begin{frame}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	367 \frametitle{Erweiterter Euklidscher Algorithmus}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	368
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	369 \begin{example}[]
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	370 Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.\\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	371
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	372 \begin{center}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	373 \tabulinesep=3pt
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	374 \begin{tabu} {c\|[1pt]cccc}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	375 $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	376 0 & - & \structure{99} & 1 & 0 \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	377 1 & 1 & \structure{78} & 0 & 1 \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	378 2 & 3 & 21 & 1 & -1 \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	379 3 & 1 & 15 & -3 & 4 \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	380 4 & 2 & 6 & 4 & -5 \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	381 5 & 2 & \alert{3} & \alert{-11} & \alert{14} \\
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	382 6 & - & 0 & - & -
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	383 \end{tabu}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	384 \end{center}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	385
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	386 Es ist $\alert{3} = \alert{-11} \cdot \structure{99} + \alert{14} \cdot \structure{78}$.
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	387 \end{example}
1cbb4a5e6ce7 nicer euklid; ue15 notes Markus Kaiser <markus.kaiser@in.tum.de> parents: 54 diff changeset	388 \end{frame}
53 a9b64faf4b8f fourteenth sheet and notes Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	389 }

Mercurial > 13ws.ds

annotate notes/tex/algebra.tex @ 56:1cbb4a5e6ce7