path: root/content/eaz.tex

\newcommand{\Primes}{\mathbb{P}}

\section*{Teilbarkeit}

Sei $n \in \N$. $d \in \N$ ist Teiler von $n$, falls $\exists t \in \N : d \cdot t = n$. Man schreibt $d \mid n$. $n$ ist Vielfaches von $d$.

Die Menge aller Teiler ist endlich da $\forall d \mid n : d \leq n$.

Der \emph{größte gemeinsame Teiler} von $m$ und $n$ wird notiert als $ggT(m,n)$ oder $(m,n)$.

Das \emph{kleinste gemeinsame Vielfache} ist $kgV(m,n)$.

Zahlen $m, n \in \N$ heißen \emph{teilerfremd}, wenn $1 \in \N$ der einzige gemeinsame Teiler ist.

\subsection*{$ggT$ als Linearkombination}

Für $m, n \in \Z$ ex. $c, d \in \Z$ s.d. $mc + nd = ggT(m,n)$

\subsection*{Division mit Rest}

$\forall k \in \Z, n \in \N \exists! d \in \Z, r \in \{0,\cdots,n-1\}: k = dn+r$.

$r$ ist Rest der Division von $k$ durch $n$.

\section*{Primzahlen}

Eine \emph{Primzahl} ist ein $1 < n \in \N$ welches keinen natürlichen Teiler außer $1$ und $p$ hat.

$\Primes = \{ n \in \N | n > 1, \forall d,t < n : d \cdot t \neq n \}$

\subsection*{Fundamentalsatz der Arithmetik}

Jedes $n \in \N$ lässt sich eindeutig als sortiertes Produkt von Primzahlen schreiben.

\subsection*{$p$-adische Bewertung}

Sei $p \in \Primes$. Dann:

$\forall 0 \neq k \in \Z \exists! v_p(k) \in \N_0 : p^{v_p(k)} \mid k \land p^{v_p(k)+1} \nmid k$

Insb.: $k = \pm \displaystyle\prod_{p \in \Primes} p^{v_p(k)}$

\vspace*{-4mm}
\begin{align*}
\forall k, l \in \Z: v_p(k+l)   &\geq \min\{v_p(k),v_p(l)\} \\
             v_p(k \cdot l) &= v_p(k) + v_p(l)
\end{align*}

Weiterhin gilt für $a, b \in \N$:

$b \mid a \iff \forall p \in \Primes : v_p(b) \leq v_p(a)$

$ggT(a,b) = \displaystyle\prod_{p \in \Primes} p^{e_p}$ mit $e_p = \min\{v_p(a),v_p(b)\}$

$kgV(a,b) = \displaystyle\prod_{p \in \Primes} p^{f_p}$ mit $f_p = \max\{v_p(a),v_p(b)\}$

\subsection*{Kleiner Satz von Fermat}

Sei $p \in \Primes, c \in \Z$. Dann gilt $p \mid c^p - c$.

\subsection*{Primzahlverteilung}

Sei $k \in \N$. Dann ex. $M \in \N$ s.d. zwischen $M$ und $M+k$ keine Primzahl liegt.

$\forall \epsilon > 0 \exists x_0 \in \R \forall x \geq x_0 \exists p \in \Primes : p \in [x,(1+\epsilon)x]$

\vspace*{2mm}

Die Funktion $\pi(x) := \#\{ p \in \Primes | p \leq x \}$ zählt die Anzahl der Primzahlen unterhalb $x \in \R$.

Der \emph{Primzahlsatz} besagt: $\lim_{x \to \infty} \pi(x) \cdot \frac{\log{x}}{x} = 1$.

Der \emph{Dichtheitssatz} besagt: Die Menge aller Brüche $p/l$ mit $p, l \in \Primes$ liegt dicht in $\R_{\geq 0}$.

\section*{Magmen}

Ein Magma ist Menge mit Verknüpfung $(M, \star)$ wobei $\star : M \times M \to M$ eine Abbildung ist.

\vspace*{2mm}

Ein Magma ist \emph{assoziativ} gdw.:

$\forall l, m, n \in M : ( l \star m ) \star n = l \star ( m \star n )$

Ein Magma ist \emph{kommutativ} gdw.:

$\forall m, n \in M : m \star n = n \star m$

Ein assoziatives Magma heißt \emph{Halbgruppe}.

Ein assoziatives Magma mit beiseitigem Neutralelement heißt \emph{Monoid}.

\subsection*{Magmenhomomorphismen}

Seien $(M,\star)$, $(N,\circ)$ Magmen.

$\Phi : M \rightarrow N$ ist Magmenhomomorphismus, wenn:

$\forall m_1, m_2 \in M : \Phi(m_1 \star m_2) = f(m_1) \circ f(m_2)$

\subsection*{Untermagmen}

$U \subseteq M$ ist Untermagma gdw.: $U \star U \subseteq U$.

\vspace*{2mm}

$\cap_{i \in I} U_i$ ist Untermagma von $M$.

Für $X \subseteq M$ ist $\langle X \rangle_{\text{Magma}}$ Schnitt aller Untermagmen $U$ von $M$ mit $X \subseteq U$.

$\langle X \rangle_{\text{Magma}}$ heißt Magmenerzeugnis von $X$ in $M$.

\subsection*{Untermonoide}

Ein Untermonoid eines Monoids $M$, d.h. eines assoziativen Magmas mit Neutralelement, ist ein Untermagma mit beidseitigem Neutralelement.

\subsection*{Symmetrische Gruppen}

$\text{Sym}(D) := \{ \sigma \in \text{Abb}(D,D) | \sigma \text{ ist bijektiv}\}$

$\text{Sym}(D)$ ist Untermagma von $\text{Abb}(D,D)$.

$S_d$ für $d \in \N$ ist die aus genau $d$ Elementen bestehende symmetrische Gruppe.

\section*{Gruppen}

Eine Gruppe ist ein assoziatives Magma $(M, \star)$ mit beidseitig neutralem Element $e$ und mindestens einer Inversen bzgl. $\star$ für $\forall m \in M$.

Eine Gruppe heißt \emph{kommutativ} bzw. \emph{abelsch} wenn sie als Magma kommutativ ist.

\subsection*{Untergruppen}

Eine Untergruppe ist ein Untermagma $\emptyset \neq U \leq G$ welches unter Inversenbildung abgeschlossen ist.

$U \neq \emptyset \implies x \in U \implies x^{-1} \in U \implies e_G \in U$

$U \leq G \iff \emptyset \neq U \subseteq G \land \forall x, y \in U : xy^{-1} \in U$

Schnitt von Untergruppen ist selbst Untergruppe.

\subsection*{Gruppenerzeugnis}

Der Schnitt aller ein $M \subset G$ beinhalten Untergruppen wird geschrieben als $\langle M \rangle$ und bezeichnet als (Gruppen-)Erzeugnis von $M$.

$\langle M \rangle = \{ x_1 \cdots x_k | k \in \N_0, \forall i \leq k : x_i \in M \lor x_i^{-1} \in M \}$

\subsection*{Zyklische Gruppen}

Gruppe $G$ ist \emph{zyklisch}, wenn $\exists a \in G : G = \langle a \rangle$.

$\forall n \in \N : [1]$ erzeugt $\Z / n\Z$.

$\langle g \rangle = \{ g^k | k \in \Z \}$ ist von $g$ erzeugte zyklische Grp.

\subsubsection*{Ordnung}

Die Ordnung einer Gruppe ist ihre Kardinalität. Die Ordnung eines $g \in G$ ist die Ordnung der von $g$ erzeugten Untergruppe.

Hat $\langle g \rangle$ endliche Ordnung so $\exists k \in \N : g^k = e_G$.

\subsubsection*{Satz von Lagrange}

Sei $G$ endliche Gruppe und $H \leq G$. Dann ist die Ordnung von $H$ ein Teiler der Ordnung von $G$.

\subsubsection*{Index}

Sei $g_1 \sim g_2 := g_1 g_2^{-1} \in H$ Äquivalenzrel. auf $G$.

Die Äquivalenzklasse von $g \in G$ ist definiert als: $[g] = Hg := \{ hg | h \in H\}$.

Für Gruppen $H \leq G$ heißt die Anzahl der Äquivalenzklassen bzgl. $\sim$ Index von $H$ in $G$, geschrieben als $(G : H)$.

Entsprechend gilt für endl. Grp.: $\#G = \#H \cdot (G : H)$.

\subsubsection*{Primzahlordnung einer Gruppe}

In jeder endlichen Gruppe ist Ordnung jedes Elements ein Teiler der Gruppenordnung. Daraus folgt, dass jede Gruppe mit Primzahlordnung eine zyklische Gruppe ist. $G = \langle g \rangle \iff g \neq e_G$

\subsection*{Normalteiler}

Eine $N \leq G$ ist Normalteiler, falls $\forall n \in N, g \in G : gng^{-1} \in N$ gilt. d.h. $N$ ist invariant unter allen inneren Automorphismen.

Es gilt für Normalteiler $N$: $\forall g \in G : gNg^{-1} = N$

Ist $U \leq G$ ein Normalteiler, so schreibt man $U \triangleleft G$.

Untergruppen abelscher Gruppen sind normal.

\subsection*{Einfachheit}

Die nichttriviale Gruppe $G$ heißt \emph{einfach}, wenn sie keine Normalteiler außer $G$ und $\{e_G\}$ besitzt.

\subsection*{Nebenklassen}

Seien $U \leq G$ Gruppen. Dann sind $g, h \in G$ \emph{kongruent modulo $U$}, wenn $g^{-1}h \in U$. Diese Relation bildet Äquivalenzklassen $gU = \{gu | u \in U\}$.

Diese Äquivalenzklassen heißen \emph{Linksnebenklassen} nach $U$, die Menge aller Nebenklassen heißt \emph{Faktorraum} $G/U$.

$\pi_U : G \rightarrow G/U, g \mapsto gU$ ist kanonische Projektion.

\subsection*{Faktorgruppen}

Sei $N \triangleleft G$. $(gN) \cdot (hN) := ghN$ definiert auf $G/N$ eine wohldefinierte Verknüpfung. $G/N$ ist mit dieser Verknüpfung die \emph{Faktorgruppe von $G$ modulo $N$}.

Die kanonische Projektion $\pi_N$ ist Gruppenhomomorphismus mit Kern $N$. Jeder Normalteiler kann also als Kern eines Gruppenhomomorphismus realisiert werden.

\section*{Gruppenhomomorphismen}

Seien $(G,\star)$, $(H,\circ)$ Gruppen.

$f : G \rightarrow H$ ist Gruppenhomomorphismus, wenn:

\begin{enumerate}[label=(\alph*)]
	\item $\forall x, y \in G : f(x \star y) = f(x) \circ f(y)$
	\item $f(e_G) = e_H$
	\item $\forall x \in G : f(