kap8.tex

\documentclass[main.tex]{subfiles}
\begin{document}
\chapter{Zahlentheorie}
\chapterauthor{Bruno}

\section{Körper}


\begin{Definition}
	Ein Körper ist eine Menge $K$, versehen mit zwei inneren zweistelligen Verknüpfungen $+$ und $\cdot$, also Addition und Multiplikation, für welche eine Addition
	$$\oplus\quad : \quad K \times K \rightarrow K \qquad;\qquad(a;b) \longmapsto a+b $$\\
	und eine Multiplikation
	$$\odot \quad : \quad K \times K \rightarrow K \qquad;\qquad(a;b) \longmapsto a \cdot b $$\\
	gegeben sind, sodass folgende Gesetze bewisen sind:\\

	$\begin{array}{rcl}
		\text{\color{blue}Assoziativgesetz} &  (A1) & a+(b+c) = (a+b)+c \\\\
		\text{\color{blue}Kommutativgesetz} &  (A2) & a+b = b+a\\\\
		\text{\color{blue}Neutrales\,\, Element} &  (A3) & \exists ! \quad 0 \quad  mit:  \\\\
		& & a+0 = 0+a = a\\\\
		\text{\color{blue}Inverses\,\, Element} &  (A4) & \forall a\in K \quad \exists ! -a \in K  mit:  \\\\
		 & &a+(-a) = 0\\\\\\
		\text{\color{blue}Assoziativgesetz} &  (M1) & a\cdot (b \cdot c) = (a\cdot b) \cdot c \\\\
		\text{\color{blue}Kommutativgesetz} &  (M2) & a\cdot b = b\cdot a    \\\\
		\text{\color{blue}Neutrales\,\, Element} &  (M3) & \exists ! \quad 1 \in K  mit \\\\
		& & 1\cdot a = a \cdot 1 = a  \\\\
		\text{\color{blue}Inverses\,\, Element} & (M4) & \exists ! \quad \dfrac{1}{a} \quad zu jedem a \in K \backslash \{0\}  mit: \\\\
		 && a \cdot \dfrac{1}{a} = 1 \\\\\\
		\text{\color{blue}Distributivgesetz} & (D) & a\cdot (b+c) = ab + ac \\
	\end{array}$
\end{Definition}

Dies erfüllen $\Q$, $\R$, $\R^{n}$ (Vektorräume), $\C$, Matritzen, prime Restklassengruppen $\Z / p\Z$ ...


\section{Mengenoperatoren}

% Definition der Kreise
\def\firstcircle{(0,0) circle (1.5cm)}
\def\secondcircle{(0:2cm) circle (1.5cm)}

\colorlet{circle edge}{bblue!50}
\colorlet{circle area}{bblue!20}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}

%\setlength{\parskip}{5mm}
% Set A und B
\begin{tikzpicture}
    \begin{scope}
        \clip \firstcircle;
        \fill[filled] \secondcircle;
    \end{scope}
    \draw[outline] \firstcircle node {$A$};
    \draw[outline] \secondcircle node {$B$};
    \node[anchor=south] at (current bounding box.north) {$A \cap B$};
\end{tikzpicture}\quad
%Set A oder B augeschlossen (A und B) 
\begin{tikzpicture}
    \draw[filled, even odd rule] \firstcircle node {$A$}
                                 \secondcircle node{$B$};
    \node[anchor=south] at (current bounding box.north) {$\overline{A \cap B}$};
\end{tikzpicture}\quad
% Set A oder B
\begin{tikzpicture}
    \draw[filled] \firstcircle node {$A$}
                  \secondcircle node {$B$};
    \node[anchor=south] at (current bounding box.north) {$A \cup B$};
\end{tikzpicture}
\\\\
% Set A ohne B
\begin{tikzpicture}
    \begin{scope}
        \clip \firstcircle;
        \draw[filled, even odd rule] \firstcircle node {$A$}
                                     \secondcircle;
    \end{scope}
    \draw[outline] \firstcircle
                   \secondcircle node {$B$};
    \node[anchor=south] at (current bounding box.north) {$A - B$};
\end{tikzpicture}\quad
% Set B ohne A
\begin{tikzpicture}
    \begin{scope}
        \clip \secondcircle;
        \draw[filled, even odd rule] \firstcircle
                                     \secondcircle node {$B$};
    \end{scope}
    \draw[outline] \firstcircle node {$A$}
                   \secondcircle;
    \node[anchor=south] at (current bounding box.north) {$B - A$};
\end{tikzpicture}



\section{Teilbarkeit}
\subsection{Teilbarkeitseigenschaften}

\begin{Definition}
	Die ganze Zahl $a\in\Z$ teilt $b\in\Z$, wenn es ein $x$ gibt, mit $b=a\cdot x$. Man schreibt:
	$$a \mid b$$
	$a$ ist ein \textbf{Teiler} von $b$ und $b$ ist \textbf{Vielfaches} von $a$

	Zwei Zahlen $a,b\in\Z$  sind \textbf{teilerfrend}, wenn aus $ c \mid  a  $ und $c\mid b$ folgt $|c| =1$
\end{Definition}

\begin{Theorem}
	Aus dieser Teilbarkeitsrelation ergeben sich mehrere Eigenschaften:
	
	Sei $a,b,c,t\in\Z$ und $t\neq0$:
	\begin{enumerate}
		\item $a \mid b$ $\quad$ und $\quad$ $a \mid c$ $\quad$ dann $\quad$ $a \mid b \pm c$
		\item $a \mid b$ $\quad$ und $\quad$ $b \mid c$ $\quad$ dann $\quad$ $a \mid c$
		\item $a \mid b$ $\quad$ dann $\quad$ $a \mid bc$
		\item $at \mid bt$ $\quad$ $\Leftrightarrow$ $\quad$ $a \mid b$
		\item $a \mid b$ $\quad$ dann $\quad$ $b=0$ $\quad$ oder $\quad$ $|a| \leq |b|$
		\item $a \mid b$ $\quad$ und $\quad$ $b\mid a$ $\quad$ dann $\quad$ $a=\pm b$
	\end{enumerate}
\end{Theorem}

\begin{Beweis}
	\begin{itemize}
		\item (2) \quad Wenn $a \mid b$ und $b \mid c$, dann gibt es $x,y\in\Z$ mit $b=a\cdot x$ und $c=b\cdot y$. Also gilt auch $c=b\cdot y=a\cdot(xy)$ und somit $a\mid c$\\
		\item (3) \quad Weil offensichtlich $b\mid bc$ gilt, folgt die Aussage sofort aus Aussage (3) \\
		\item (4)  \quad $at\mid bt\quad \Leftrightarrow\quad \exists x \in \Z : \, \, bt=atx \quad\Leftrightarrow \quad b=ax \quad\Leftrightarrow \quad a\mid b$ \\
		\item (5) \quad Sei $b=ax$ mit $x\in\Z$. Wenn $x=0$, dann ist $b=0$. In alles anderen Fällen ist $|x| >1$ und daher $|b|  = |a|  \cdot |x|  \geq |a| $
		\item (6) \quad Wenn weder $a=0$ noch $b=0$ ist, dann folgt aus (4) $|a| \geq|b| \geq|a| $ und daher $a=\pm b$. Wenn also  $a=0$, dann folgt $b=0$
	\end{itemize}
\end{Beweis}


\subsection{Euklidische Division}

\begin{Definition}
	Seien $a$ und $b$ zwei natürliche Zahlen. Es gibt dann immer $q,r \in \N$ sodass
	$$a= b\cdot q + r \qquad 0\leq r < b$$
	$q$ heißt \textbf{Quotient} und $r$  heißt \textbf{Rest}.
	Man schreibt: \qquad $q=a \div b$ \qquad und \qquad $r \equiv a \mod b$
\end{Definition}


\section{Primzahlen}

Hier die Liste der Primzahlen bis 100:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

\begin{Definition}
	Eine natürliche Zahl heißt Primzahl, wenn sie in $\N$ genau zwei Teiler besitzt.
\end{Definition}


\begin{Theorem}[Unednlichkeit der Primzahlen]
	Es gibt unendlich viele Primzahlen
\end{Theorem}


\begin{Beweis}[nach Euklid]
	Jede ganze Zahl $n>1$ ist durch eine Primzahl teilbar. Entweder ist $n$ selber eine Primzahl oder $n=a\cdot b$ mit $a,b\in\N$.
	
	Also ist $1<a=\dfrac{n}{b}<n$. Wenn man diesen Schritt endlich oft macht, kommt man am Ende auf ein neues $a'\in\mathbb{P}$.
	
	$\A$: Nehmen wir jetzt an, es gäbe nur endlich viele Primzahlen $p_{1},p_{2},...,p_{r-1},p_{r}$.
	
	Dann ist $$N=p_{1}\cdot p_{2}\cdot ... \cdot p_{r-1} \cdot p_{r} +1 = \left (\prod_{r=1}^{r}P_{r}\right ) + 1 $$ eine ganze Zahl $>1$ und hat daher mindestens einen Primteiler $p_{l} \in\mathbb{P}$ und $l\in\{1,2,...,r-1,r\}$
	Dann hat man:

	$\Rightarrow \left\{ \begin{array}{rcl}
		p_{l} & \mid & p_{1} \cdot p_{2} \cdot...\cdot p_{r-1} \cdot p_{r} \\
		p_{l} & \mid & p_{1} \cdot p_{2} \cdot...\cdot p_{r-1} \cdot p_{r} +1
	\end{array} \right.$.

	$\Leftrightarrow p_{l} \mid  \, p_{1}\cdot p_{2} \cdot...\cdot p_{r-1} \cdot p_{r} - \left (  p_{1}\cdot p_{2} \cdot...\cdot p_{r-1} \cdot p_{r} +1 \right )$
	
	$\Leftrightarrow p_{l} \mid  \, (-1) \quad $oder$ \quad p_{l} \mid  1$ \qquad  \lightning, da $p_{l}=1$ aber $1\notin \mathbb{P}$

	$N$ muss also einen Primteiler haben ungleich $p_{r} \quad mit \quad r\in\{1,2,3,...,r-1,r\}$ oder \textbf{selber prim sein}.
\end{Beweis}


\begin{Theorem}
	Jede natürliche Zahl $n\geq2$, die nicht prim ist, besitzt einen Primfaktor $p$, für den gilt
	$$p^2\leq n \quad\Leftrightarrow\quad p\leq \sqrt{n}$$
	Also lässt sich jede Zahl, die nicht prim ist, in Primfaktoren zerlegen.

	Jede natürliche Zahl $n\geq2$ besitzt eine eindeutige \textbf{Primfaktorzerlegung} der Form
	$$n=(p_{1})^{a_{1}} \cdot (p_{2})^{a_{2}} \cdot ... \cdot (p_{k-1})^{a_{k-1}} \cdot (p_{k})^{a_{k}}   $$
	mit $p_{1}< p_{2}< ... < p_{k-1}< p_{k}$ \quad und \quad $ \left\{ p_{1}, p_{2}, ... , p_{k-1}, p_{k} \right\} \in \mathbb{P}$ \quad und \quad $a_{1}, a_{2}, ...  a_{k-1}, a_{k} \in \N $
\end{Theorem}


\section{Restklassen oder Kongruenzklassen}

\begin{Definition}
	Seien drei natürliche Zahlen $a, b, n \in \N$ mit $n\geq 2$.\\ Wenn $a=q_{1} \cdot n + r_{1}$  \qquad und \qquad  $b=q_{2} \cdot n + r_{2}$ \qquad und \quad $r_{1}=r_{2}$,\qquad also falls $a$ und $b$ bei der euklidischen Division durch $n$ den gleichen Rest besitzen, dann gilt
	$$a \equiv b\mod n$$
\end{Definition}

\begin{Beispiel}
	\begin{itemize}
		\item $29\equiv-121 \mod 5 $ \quad da $29 \equiv 5\cdot 5 +4$ \quad und \quad $-121 = 5\cdot (-25) +4$
		\item $88\equiv 24 \mod 8 $ \quad da $8\mid 88$ \quad und \quad $8\mid 24$
		\item $87\equiv 23 \mod 8$
	\end{itemize}
\end{Beispiel}

\begin{Theorem}
	Seien $a,b$ zwei ganze Zahlen und $n\in\N$ mit $n\geq 2$, dann gilt
	
	(1)\qquad $ a\equiv b \mod n \quad \Leftrightarrow \quad n\mid (a-b)$\\
	(2)\qquad $ a\equiv 0 \mod n \quad\Leftrightarrow\quad n\mid a$\\
	(3)\qquad falls $n'\geq 2$ und $n'\mid n$ dann gilt: \quad $a \equiv b \mod n \quad \Rightarrow \quad a \equiv b \mod n' $\\\\
\end{Theorem}

\begin{Beweis}
	\begin{itemize}
		\item (1) \quad $ a \equiv b \mod n \quad\Leftrightarrow\quad a - b \equiv 0 \mod n \quad\Leftrightarrow\quad $ $n$ teilt $(a-b)$
	\end{itemize}
\end{Beweis}

\begin{Beispiel}
	\begin{itemize}
		\item (1) \quad $61 \equiv 29 \mod 8$ \quad (Rest 5) $\quad\Leftrightarrow\quad 8\mid  (61-29) = 32 $
		\item (3) \quad $4 \geq 2$ \, und \, $4\mid 12$ \quad $43 \equiv 67 \mod 12 \quad(r=7)\qquad \Rightarrow \quad 43 \equiv 67 \mod 4  $
	\end{itemize}
\end{Beispiel}

\begin{Theorem}
	Für jedes $n\in \N$ mit $n\geq 2$ gilt: \\Jede ganze Zahl $a$ ist modulo $n$ kongruent zu einer natürlichen Zahl $r$ mit $0 \geq r \geq n-1$
	
	Anders gesagt gibt es zu jeder Zahl immer Kongruenzklassen.
\end{Theorem}

\begin{Definition}
	Es seien $n \in \N$ mit $n \geq 2$ und $r \in \N$ mit $0 \leq r < n$

	Die Menge $ [r] \mod n $ ist die Menge aller ganzen Zahlen $z$, die bei der euklidischen Division durch $n$ den Rest $r$ liefern.
	
	Sie ist eine Menge von Zahlen, die den Abstand $n$ zueinander haben.
	
	Kongruenzen sind mit der Addition und der Multiplikation verträglich. Seien $a, b, a^{*}, b^{*}$ ganze Zahlen:
	
	$\Rightarrow \left \{ \begin{array}{rcl}
		a & \equiv & a^{*} \mod n  \\
		b & \equiv & b^{*}\mod n
	\end{array} \right .$

	$\Rightarrow a+b \equiv a^{*} + b^{*} \mod n$ \qquad und \qquad  $a\cdot b \equiv a^{*} \cdot b^{*} \mod n$
\end{Definition}

\begin{Beispiel}
	\begin{itemize}
		\item $ [1] \mod 4 = \{ ... , -7, -3, 1, 5, 9, ... \} $
		\item $ [2] \mod 4 = \{ ... , -6, -2, 2, 6, 10, ... \} $
		\item $ [3] \mod 4 = \{ ... , -5, -1, 3, 7, 11, ... \} $
		\item $ [4] \mod 4 = [0] \mod 4 = \{ ... , -8, -4, 0, 4, 8, 12, ... \} $
	\end{itemize}
\end{Beispiel}

\begin{Theorem}
	Seien $a,b \in \N$ mit \quad $a,b \geq 2$ \quad und $a\mid b$, dann gilt
	$$[r] \mod b \quad \subseteq \quad [r] \mod a $$
	($\subseteq$ heißt "Teilmenge")
\end{Theorem}

\begin{Beispiel}
	So gilt zum Beispiel:

	$\begin{array}{rccl}
		& [2] \mod 10 & \subseteq & [2] \mod 5\\
		\Leftrightarrow & \{ ... , -28, -18, -8, 2, 12, 22, ... \} & \subseteq & \{ ..., \textcolor{red}{-18}, -13, \textcolor{red}{-8}, -3, \textcolor{red}{2}, 7, \textcolor{red}{12}, 17, ... \}\
	\end{array}$.
\end{Beispiel}


\subsection{Mit Kongruenzen rechnen und beweisen}

\begin{Definition}
	Kongruenzen sind mit der Addition und der Multiplikation verträglich. Daraus folgen diese Eigenschaften:
	
	Sei $n \in \N$ mit $n \geq 2$. $a$ und $a^{*}$ zwei (beliebige) ganze Zahlen.

	\begin{enumerate}
		\item Für jede ganze Zahl $k$ gilt:
			$$a \equiv a^{*} \mod n \quad \Rightarrow \quad k \cdot a \equiv k \cdot a^{*} \mod n$$
		\item Für jede natürliche Zahl $p \in \N \, \backslash \{0\}$ gilt:
			$$a \equiv a^{*} \mod n \quad \Rightarrow \quad a^p \equiv {a^{*}}^p \mod n$$
	\end{enumerate}
	Diese Eigenschaften sind \textbf{keine} Äquivalenzen, sondern Folgerungen! Bei Beweisen kann man also nicht vom Ergebnis ausgehen, und dann durch das dividieren auf beiden Seiten des Kongruenzzeichens auf ein einfaches Ergebnis kommen. Man muss von etwas einfachem ausgehen, und  das dann so umformen, dass man auf die gewünschte Kongruenz kommt.
\end{Definition}

\begin{Beispiel}
	$\zz$ : $35^{228} + 84^{501} \equiv 0 \mod 17$

	\begin{minipage}[b]{0.3\linewidth}
		$\begin{array}{rccl}
			\Rightarrow & 35 &=& 34 + 1 = 17 \cdot 2 + 1 \\
			\Rightarrow & 35 &\equiv& 1 \mod 17\\
			\Rightarrow & 35^{228} &\equiv& 1 \mod 17
		\end{array}$
	\end{minipage}
	\hfill \vline \hfill
	\begin{minipage}[b]{0.6\linewidth}
		$\begin{array}{rccl}
			\Rightarrow & 84 &=& 85 - 1 = 17 \cdot 5 - 1 \\
			\Rightarrow & 84 &\equiv& -1 \mod 17 \\
			\Rightarrow & 84^{501} &\equiv& -1 \mod 17
		\end{array}$
	\end{minipage}
	$$\Rightarrow \quad 35^{228} + 84^{501}\quad\equiv\quad 1-1 \mod 17 \quad\equiv\quad 0 \mod 17$$
\end{Beispiel}

\begin{Definition}
	Es seien $a$ und $b$ zwei natürliche Zahlen größer Null mit $a>b$. $r$ sei der Rest der Euklidischen Division von a durch b. Dann gilt:

	\begin{enumerate}
		\item Wenn $r = 0$, dann sind die gemeinsamen Teiler von $a$ und $b$ die Teiler von $b$. Da die Division aufgeht, teilt $b$ die Zahl $a$. $a$ ist also ein Vielfaches von $b$, deshalb sind die Teiler von $a$ auch die Teiler von $b$.
		\item Wenn $r \neq 0$, dann sind die gemeinsamen Teiler von $a$ und $b$ gerade die gemeinsamen Teiler von $b$ und $r$. (Äquivalenz $\Leftrightarrow$)
	\end{enumerate}
\end{Definition}

\begin{Beweis}
	Die Euklidische Division sagt \quad $a = b \cdot q +r$
	
	$\begin{array}{rcl}
		n | a \quad \land \quad n | b \, \Rightarrow \, n | q \cdot b & \Rightarrow & n | a - q\cdot b \\
		& \Rightarrow & n | r \\
	\end{array}$
	
	Alle Teiler $n$ haben die Eigeschaften: $n | a$, $n | b$ und $n | r$. $n$ ist also Teiler von $a$, $b$ und $r$.
	
	Umgekehrt gilt: wenn $n | b$ und $n | r$:
	
	$\Rightarrow \quad n | q \cdot b + r$

	$\Rightarrow \quad $$n | a$
\end{Beweis}


\subsection{Der Euklidische Algorithmus}

Der Euklidische Algorithmus ist eine effiziente Methode um den ggT (größter gemeinsamer Teiler) zweier Zahlen zu finden, wenn die Primfaktorzerlegung nicht vorliegt.

\begin{Definition}
	Seien $a,b \in \N$. Sei $a$ die größere Zahl, also $a > b$. Sei $b$ kein Teiler von $a$. Nun wiederholt man immer wieder die Euklidische Division mit den Resten der vorherigen Division. Nach obigem Satz sind die Teiler von $a$ und $b$ auch die Teiler von $b$ und $r$. Man möchte ja den ersten gemeinsamen Teiler der Zahlen $a$ und $b$ finden.
	$$\begin{array}{rccl}
		a & = & q_{1} \cdot b + r_{1} \qquad \qquad &0 < r_{1}  < b \\
		b & = & q_{2} \cdot r_{1} + r_{2} \qquad \qquad &0 < r_{2}  < r_{1} \\
		r_{1} & = & q_{3} \cdot r_{2} + r_{3} \qquad \qquad &0 < r_{3}  < r_{2} \\
		&& \vdots & \\
		r_{n-2} & = & q_{n} \cdot r_{n-1} + r_{n} \qquad \qquad &0 < r_{n}  < r_{n-1} \\
		r_{n-1} & = & q_{n+1} \cdot r_{n} + 0 \qquad \qquad &  \\
		\end{array}$$
	Deshalb ist $r_{n}$ der größte gemeinsame Teiler der Zahlen $a$ und $b$:
	
	Die Folge der Reste $r_{k} \in \N$ mit $k = \{1, 2, ..., n-1, n\}$ ist streng monoton fallend. Diese Folge hat den Grenzwert $g = 0$. Deshalb gibt es immer \textbf{ein} letztes $r_{n}$ der Folge.

	Die \textbf{Existenz} von der letzten Zahl $r_{n}$ ist sicher, da $b \nmid a$. Die Teiler von $a$ und $b$ sind also auch die Teiler von $b$ und $r_{1}$. Da die Folge der Reste monoton fallend ist, kommt man am Ende auf jeden Fall auf eine Zahl $r_{n}$, die Teilerin von $a$ und $b$ ist.
\end{Definition}

\begin{Theorem}
	Aus vorheriger Definition des Euklidischen Algorithmus ergeben sich diese Eigenschaften der Zahl $r_{n}$:
	\begin{enumerate}
		\item $r_{n}$ ist gleichzeitig Teiler von $a$ und $b$.
		\item Jeder andere Teiler von $a$ und $b$ ist auch Teiler von $r_{n}$
		\end{enumerate}
		$r_{n}$ ist der größte gemeinsame Teiler von $a$ und $b$.\quad ggT$(a\,;b) = r_{n}$. Es gilt also:
		\begin{itemize}
		\item ggT$(a\,;b) =$ ggT$(b\,;a)$
		\item $a | c$ und $b | d \quad \Rightarrow \quad$ ggT$(a\,;b) |$ ggT$(c\,;d)$
		\item ggT$(a^2;b^2)$ $=$ $\left ( \text{ggT}(a;b) \right )^2$
	\end{itemize}
\end{Theorem}

\begin{Beispiel}
	Man sucht den ggT von $a = 780$ und $b = 567$.
	$$\left. \begin{array}{rcccl}
		780 & = & 1 \cdot 567 & + & 213 \\
		567 & = & 2 \cdot 213 & + & 141 \\
		213 & = & 1 \cdot 141 & + & 72 \\
		141 & = & 1 \cdot 72 & + & 69 \\
		72 & = & 1 \cdot 69 & + & 3 \\
		69 & = & 23 \cdot 3 & + & 0 \\
	\end{array} \right\} \qquad ggT(780;567) = ggT(567;780) = 3$$

	Jetzt sucht man den ggT von $c = 3\cdot 780 = 2340$ und $d = 567 \cdot 5 = 2835$.
	$$\left. \begin{array}{rcccl}
		2835 & = & 1 \cdot 2340 & + & 495 \\
		2340 & = & 4 \cdot 495 & + & 360 \\
		495 & = & 1 \cdot 360 & + & 135 \\
		360 & = & 2 \cdot 135 & + & 90 \\
		135 & = & 1 \cdot 90 & + & 45 \\
		90 & = & 2 \cdot 45 & + & 0 \\
	\end{array} \right\} \qquad ggT(2340;2835) = ggT(2835;2340) = 45 $$
	$780\, |\, 2340$ und $567 | 2835$ \quad folgt \quad  ggT$(780,567)\, |\,$ ggT$(2340;2385)\,\,\,$ oder auch $3 \,|\, 45$
\end{Beispiel}


\subsection{Der kleine Satz von Fermat}

\begin{Definition}
	Sei $a$ eine ganze Zahl und $p \in \mathbb{P}$ kein Teiler von $a$. Dann gilt
	$$a^{p-1} \equiv 1 \mod p$$
	$$\Rightarrow a^p \equiv a \mod p$$
\end{Definition}

\begin{Beweis}
	Seien $p$ eine Primzahl und $a \in Z$ und zwei Listen (oder Mengen) von Zahlen
	$$M: a, 2a, 3a, 4a, ..., (p-2)a, (p-1)a$$
	$$N: 1, 2, 3, 4, ..., (p-2), (p-1)$$
	Erst wird bewiesen, dass bei der Division von 2 Zahlen $k,k' \in \N$ mit $k \neq k'$ ein anderer Rest rauskommt. Dies wird und später hilfreich sein.

	$\begin{array}{rcccl}
		\Rightarrow & k & \not\equiv & k' \mod p  & \text{(da $k \neq k'$ und $k<p$ und $k'<p$)} \\
		\Rightarrow & k \cdot a & \not\equiv & k' \cdot a \mod p  &
	\end{array}$
	
	Die Reste von beliebigen Zahlen $x \in M$ durch $p \in \mathbb{P}$ ergeben genau die Zahlen $y \in N$, da in beiden Mengen genau $(p-1)$ verschiedene Elemente sind und da gerade gezeigt wurde dass jedes Element aus $M$ bei der Division durch p einen unterschiedlichen Rest hat. Die Reihenfolge der zu $x \in M$ zugehörigen Reste $y \in N$  ist natürlich nicht klar (ganz normal bei Mengen).
	s
	Wir benennen um, damit es klarer wird:

	$$\left.\begin{array}{r c l}
		a & \equiv & r_{1} \mod p\\
		2a & \equiv & r_{2} \mod p \\
		3a & \equiv & r_{3} \mod p \\
		& & \vdots \\
		(p - 2)a & \equiv & r_{p-2} \mod p \\
		(p - 1)a & \equiv & r_{p-1} \mod p
	\end{array} \right\}$$

	$r_{1}, r_{2}, ..., r_{p-1}$ sind alle voneinander verschieden ($\widehat{=}$ paarweise verschieden) und sind genau alle Elemente aus der Menge $N$
	
	Demnach gilt die Schreibweise:
	$$r_1 \cdot r_2 \cdot r_3 \cdot ... \cdot r_{p-2} \cdot r_{p-1} \quad = \quad 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-2) \cdot (p-1) \quad = \quad (p-1)! $$
	Daraus folgt:
	$$\begin{array}{rcl}
		 a \cdot 2a \cdot 3a \cdot ... \cdot (p-1)a & \equiv & r_1 \cdot r_2 \cdot r_3 \cdot ... \cdot r_{p-1} \mod p \\
		(p-1)! a^{p-1} & \equiv & (p-1)! \mod p
	\end{array}$$

	Da ggT$\left ( (p-1)! ; p \right ) = 1$, kann man durch (p-1)! teilen, ohne dass sich das Modulo verändert
	
	$ \Rightarrow a^{p-1} \equiv 1 \mod p$
\end{Beweis}


\subsection{Zusammenhänge zwischen ggT und kgV}


\begin{Theorem}
	Das kgV besitzt ähnliche Eigenschaften wie der ggT
	Seien $a,b,c,d,k$ ganze Zahlen ungleich Null. Dann gilt:
	\begin{enumerate}
		\item kgV($a;b$) = kgV($b;a$)
		\item kgV($k\cdot a ; k \cdot b$) = $|k| \cdot$ kgV ($a;b$)
		\item Falls $a | c$ und $b | d$, dann gilt auch kgV($a;b$) | kgV($c;d$)
	\end{enumerate}

	Eine wichtige Eigenschaft, die oft benutzt wird, ist folgende:
	$$\text{ggT}(a;b) \cdot \text{kgV}(a;b) = |a \cdot b|$$

	Eine andere Art, den ggT und den kgV zu ermitteln ist die über die Primfaktorzerlegung. Diese wird gleich mithilfe eines Beispiels erklärt.
\end{Theorem}

\begin{Beispiel}
	$\begin{array}{rcccl}
		a = 12474 &=& 2 \cdot 3^4 \cdot 7 \cdot 11 &=& 2^1 \cdot 3^{\textcolor{red}{4}} \cdot 5^0 \cdot 7^1 \cdot 11^{\textcolor{red}{1}} \cdot 17^0 \\
		b = 33320 &=& 2^3 \cdot 5 \cdot 7^2 \cdot17 &=& 2^{\textcolor{red}{3}} \cdot 3^0 \cdot 5^{\textcolor{red}{1}} \cdot 7^{\textcolor{red}{2}} \cdot 11^0 \cdot 17^{\textcolor{red}{1}} \\
	\end{array}$
	
	Daraus ergeben sich

	ggT($a;b$) $= 2^1 \cdot 7^1 \quad = \quad 14$

	kgV($a;b$) $= 2^{\textcolor{red}{3}} \cdot 3^{\textcolor{red}{4}} \cdot 5^{\textcolor{red}{1}} \cdot 7^{\textcolor{red}{2}} \cdot 11^{\textcolor{red}{1}} \cdot 17^{\textcolor{red}{1}} \quad = \quad 29688120 $
\end{Beispiel}



\subsection{Die Sätze von Bézout, Gauß und der Fundamentalsatz des ggT}


\begin{Definition}[Fundamentalsatz des ggT]
	Der \textbf{Fundamentalsatz des ggT} besagt, dass für $a,b \, \in \N$ ganze Zahlen $u$ und $v$ exisitieren, sodass gilt:
	$$a\cdot u + b\cdot v \,=\, \text{ggT(a; b)} $$
	Wenn $a$ und $b$ teilerfrend sind, dann gilt im Sonderfall: $\exists u, v \, \in \Z$:
	$$a\cdot u + b\cdot v \,=\, \text{ggT(a; b)} \,=\, 1 $$
	
	Daraus folgt der \textbf{Satz von Bézout}. Zwei ganze Zahlen ungleich Null sind genau dann teilerfrend, wenn $\exists u, v \, \in \Z$ gibt, sodass gilt:
	$$a\cdot u + b\cdot v \,=\, 1 $$
	
	Der \textbf{Satz von Gauß} ist bei diophantischen Gleichungen nützlich: Es seien $a$, $b$ und $c$ ganze Zahlen ungleich Null und seien $a$ und $b$ teilerfrend.
	$$a | bc \quad \Rightarrow \quad a | c$$
	
	Daraus folgt:
	$$\text{ggT(a; $b_{1}$)} \quad \text{und} \quad \text{ggT(a; $b_{2}$)} \qquad \Leftrightarrow \qquad \text{ggT(a; $b_{1}\cdot b_{2}$)}$$
\end{Definition}



\begin{Beispiel}
	Musterlösung einer diophantischen Gleichung:
	
	$$(1)\qquad 12597 a - 3813 b = 3$$

	Enweder man sucht mit dem Taschenrechner eine Lösung oder man verwendet den oft längen Weg mit einer hohen Vorzeichenfehlerwahrscheinlichkeit. Wir sind mutig und die Zahken sind groß, deshalb nehmen wir den Weg mit dem Gaus'schen Algorithmus. Man merkt dass 12597, 3813 mit 3 gekürzt werden kann.

	$$(1) \quad \Leftrightarrow \quad 4199 a - 1271 b = 1$$

	$\begin{array}{rcl}
		4199 & = & 3 \cdot 1271 + 386 \\
		1271 & = & 3 \cdot 386 + 113 \\
		386 & = & 3 \cdot 113 + 47 \\
		113 & = & 2 \cdot 47 + 19 \\
		47 & = & 2 \cdot 19 + 9 \\
		19 & = & 2 \cdot 9 + 1 \\
	\end{array}$

	Jetzt wird zurück eingesetzt, um auf eine Lösung zu kommen

	$\begin{array}{rcl}
		1 &=& 19 - 2 \cdot (9) \\
		1 &=& 19 - 2 \cdot (47 - 2\cdot 19) = 5 \cdot 19 - 2 \cdot 47 \\
		1 &=& 5 \cdot (113 - 2\cdot 47) - 2 \cdot 47 = 5 \cdot 113 - 12 \cdot 47 \\
		1 &=& 5 \cdot 113 - 12 \cdot (386 - 3\cdot 113) = 41 \cdot 113 - 12 \cdot 386 \\
		1 &=& 41 \cdot(1271 - 3\cdot 386) - 12\cdot 386 = 41 \cdot 1271 - 135 \cdot 386 \\
		1 &=& 41 \cdot 1271 - 135 \cdot (4199 - 3 \cdot 1271) = 446 \cdot 1271 - 135 \cdot 4199 \\
	\end{array}$

	Eine Lösung dieser Gleichung ist also das Zahlentupel $(-135;-446)$. Jetzt zieht man eine Gleichung von der anderen ab:

	$\begin{array}{rl}
		\Rightarrow & 4199 (a + 135) - 1271 (b + 446) = 0 \\
		\Leftrightarrow & 4199 (a + 135) = 1271 (b + 446) \\
	\end{array}$

	Unter Verwendung des Satzes von Gauß folgert man

	$\begin{array}{rl}
		\Rightarrow & 4199 | b + 446  \\
		\Rightarrow & 4199k = b + 446 \\
		\Leftrightarrow & b =  4199k - 446 \\
	\end{array}$

	Jetzt wird eingesetzt

	$\begin{array}{rl}
		\Rightarrow & 4199a +135\cdot4199 = 1271 (4199k -446 + 446 ) = 1271 \cdot 4199k \\
		\Leftrightarrow & a = 1271k - 135 \\
	\end{array}$

	Die Lösungsmenge Für die Geichung (1) lautet
	$$\mathbb{L} = \{ (1271k -135 ; 4199k - 446) ; \quad k \in \Z  \}$$
	Jetzt kann man jede ganze Zahl $F$ durch unendlich viele Linearkombinationen von 1271 und 4199 darstellen. Sei die Aufgabe
	$$ 4199 a - 1271 b = F$$
	$$\mathbb{L}_{F} = \{ (1271k -  (F \cdot 135) ; 4199k - (F \cdot 446)) ; \quad k \in \Z  \}$$
\end{Beispiel}


\subsection{Das RSA Verschlüsselungsverfahren}


Die RSA-Verschlüsselung ist eine sehr sichere Verschlüsselungsmethode, welche auch sehr viele Kommunikationsdienste benutzen. Mit einem langen Schlüssel kann ein brute force Angriff (Rumprobieren) mehrere Generationen dauern und noch ist kein Algorithmus (öffentlich) bekannt, der entschlüsseln kann.

\subsubsection{Konstruktion der Schlüssel}

\begin{enumerate}
\item Man nimmt 2 sehr große Primzahlen $p$ und $q$, die privat bleiben.
\item Man rechnet das Rsa-Modul $N=p \cdot q$ aus. $N$ ist ein Teil des öffentlichen Schlüssels und hat mehrere hunderte von Dezimalstellen
\item Man bestimmt die Anzahl der zu $N$ teilerfrenden Zahlen. Wenn man dazu nur $N$ kennt, brauchen Computer Jahre. Da wir aber die Primfaktorzerlegung haben, ist \, $\varphi(N) = (p - 1) \cdot (q - 1)$. $\varphi$ sei die Funktion die die Anzahl an teilerfrenden Zahlen angibt. Die Anzahl der zu $N$ teilerfrenden Zahlen ist das Produkt der zu $p$ teilerfrenden Zahlen mit den zu $q$ teilerfrenden Zahlen. $p$ und $q$ sind prim, deshalb ist $\varphi(p)=(p - 1)$.
\item Man wählt eine Zahl $e$ mit $1<e<(p-1)\cdot(q-1)$ mit ggT($e;(p-1)(q-1)$) $= 1$. Sie ist also teilerfrend mit $\varphi(N)$

Der öffentliche Schlüssel ist $(e,N)$. Geheim bleiben $p$, $q$, und $(p - 1) \cdot (q-1)$.
\item Jetzt bestimmt man eine Zahl $d$ mit \, $e \cdot d \equiv 1 \mod (p-1)(q-1)$. Man bestimmt also das Inverse Element zu $e$ bei der Rechnung mit $\mod (p-1)(q-1)$. Dies macht man mithilfe des Euklidischen Algorithmus:

$e \cdot d \quad \equiv \quad 1 \mod (p-1)(q-1) $

$\Leftrightarrow (p-1)(q-1) \cdot k \quad = \quad e \cdot d -1 \qquad (k \in \Z)$

$\Leftrightarrow e \cdot d - k \cdot (p-1)(q-1) = 1$ \qquad Eine lösbare Diophantische Gleichung! (ggT($e;(p-1)(q-1)) = 1$))

$\Leftrightarrow e \cdot d + k \cdot (p-1)(q-1) = 1$ \qquad da $k \in \Z$

Der private Schlüssel ist ($d,N$)
\end{enumerate}

\subsubsection{Ver- und Entschlüsselung der Nachricht}

Sei $T$ der Klartext, also der unverschlüsselte Text und $G$ der geheime, verschlüsselte Text.

\begin{description}
	\item[$\bullet$] Verschlüsselung: $\quad G = T^{e} \mod N $
	\item[$\bullet$] Entschlüsselung: $\quad T = G^{d} \mod N $
\end{description}

Damit diese Rechnung funktioniert, muss $(T^{e})^{d} \equiv T \mod N$ gelten. Um dies zu prüfen, schauen wir uns die Ausgangsgleichheiten an:
$$e \cdot d \equiv 1 \mod (p-1)(q-1) \qquad \Leftrightarrow \qquad e \cdot d = r \cdot (p-1)(q-1) +1 \qquad r \in \Z$$
Und es sei die (Eulersche) Formel gegeben (Vorraussetzung: ggT($a;pq$) $= 1$):
$$a^{(p-1)(q-1)} \equiv 1 \mod pq$$

Dann müssen nur Potenzgesetze angewandt werden:

$\begin{array}{rcl}
	\left(T^{e}\right)^d \, = \, T^{e \cdot d} & = &  T^{r \cdot (p-1)(q-1) +1}\\
	& = & T^{r \cdot (p-1)(q-1)} \cdot T \\
	& = & \left(T^{(p-1)(q-1)}\right)^r \cdot T \quad \\
	& \equiv & 1^r \cdot T \mod pq \quad \\
	& \equiv & T \mod N
\end{array}$


\begin{Beispiel}
	Nehmen wir zur Veranschaulichung lieber kleine Primzahlen
	\begin{enumerate}
		\item $p = 7$ und $q = 23$
		\item $N = p \cdot q = 161$
		\item $\varphi(N) = (p-1)(q-1) = 132$
		\item $e = 5$ passt, da ggT($5; 161$) $ = 1$ \,und\, $1<5<132$
		\item Sei $d$ mit $5d \equiv 1 mod 132$ \, oder auch äquivalent \,$5d + 132r = 1$. Ein Lösungstupel ist $(53;-2)$.
	\end{enumerate}
	Der öffentliche Schlüssel ist $(5;161)$ und der geheime Schlüssel ist $(53;161)$

	Nun verschlüsseln wir die Nachricht \glqq ADVENT\grqq. Der Absender bekommt den öffentlichen Schlüssel.

	\begin{tabular}{l*{6}{c}r}
		Nachricht              & A & D & V & E & N  & T  \\
		\hline
		Zugehörige Zahl & 1 & 4 & 22 & 5 & 14 & 20  \\
		$G = T^5 \mod 161$            & 1 & 58 & 22 & 66 &  84 & 125  \\\\
		Übermittlung der Nachricht &&&&&& \\\\
		$T = G^{53} \mod 161$         &  1 & 4 & 22 & 5 & 14 & 20  \\
		Entschlüsselte Nachricht              & A & D & V & E & N  & T  \\
	\end{tabular}
\end{Beispiel}





\section{Die vollständige Induktion}

Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird, die größer oder gleich einem bestimmten Startwert sind.

Daher wird der Beweis in zwei Etappen durchgeführt; mit dem \textbf{Induktionsanfang} beweist man die Aussage für die kleinste Zahl, mit dem \textbf{Induktionsschritt} für die nächste Zahl, also logischerweise für alle darauffolgenden Zahlen.\\\\

\begin{Beweis}[Gaußsche Summenformel]
	$\zz$ : $S(n) = \sum\limits_{i=1}^n i  = \dfrac{n(n+1)}{2}$

	$\begin{array}{rl}
		\textbf{Induktionsanfang}: & 1=\dfrac{1(1+1)}{2} = 1  \\\\
		\textbf{Induktionsvorraussetzung}: & \text{für ein beliebiges, aber festes } k \in \N \text{gilt: } \sum\limits_{i=1}^k  = \dfrac{k(k+1)}{2}\\\\
		\textbf{Induktionsbehauptung}: & \text{man behauptet, dass } \forall n \in \N \text{gilt: } \sum\limits_{i=1}^{n+1}  = \dfrac{(n+1)((n+1)+1)}{2}\\\\
		\textbf{Induktionsschluss}: &  \sum\limits_{i=1}^n + (n+1) = \dfrac{n(n+1)}{2} + \dfrac{2(n+1)}{2} = \dfrac{(n+1)((n+1)+1)}{2}\\\\
	\end{array}$
\end{Beweis}

\begin{Beweis}[Summe ungerader Zahlen]
	$\zz$ $\forall n \in \N  :  \sum\limits_{k=1}^n (2k-1) = n^2$

	$\begin{array}{rl}
		\textbf{Induktionsanfang}: & \sum\limits_{k=1}^1 (2k-1) = 2\cdot 1 -1 = 1 = 1^2  \\\\
		\textbf{Induktionsvorraussetzung}: & \text{für ein beliebiges, aber festes } i \in \N \text{gilt: } \sum\limits_{k=1}^i (2k-1) = i^2 \\\\
		\textbf{Induktionsbehauptung}: & \text{man behauptet, dass } \forall n \in \N :  \sum\limits_{k=1}^{n+1} (2k-1) = (n+1)^2 \\\\
		\textbf{Induktionsschluss}: & \sum\limits_{k=1}^{n+1} (2k-1) = \sum\limits_{k=1}^{n} (2k-1) + 2(n+1)-1 = n^2 +2n+1 = (n+1)^2 
	\end{array}$
\end{Beweis}

\begin{Beweis}[Bernoullische Ungleichung]
	$\zz$ : $ \forall n \in \N \quad n>0 :  \qquad (1+x)^n \geq 1+nx  \qquad;  x\geq -1$

	$\begin{array}{rl}
		\textbf{Induktionsanfang}: & (1+x)^0 = 1 \geq 1 = 1+0x \\\\
		\textbf{Induktionsvorraussetzung}: & \text{Es gelte nun: } (1+x)^n \geq 1+nx ; n\in \N_{0} \\\\
		\textbf{Induktionsbehauptung}: &  (1+x)^{n+1} \geq 1+(n+1)x \\\\
		\textbf{Induktionsschluss}: &  (1+x)^{n+1} = (1+x)^n \cdot (1+x) {\overset{\text{I.V.}} \geq} (1+nx)\cdot(1+x) = nx^2+nx+x+1\\\\
		&\geq 1+x+nx = 1+(n+1)x
	\end{array}$
\end{Beweis}


\begin{Beweis}[Summe der Quadratzahlen]
	Mittels Induktion lässt sich ''nur''  eine vorhandene Formel beweisen.

	$\zz$ : $S(n) = \sum\limits_{i=1}^n i^2 = \dfrac{n(n+1)(2n+1)}{6}$

	$\begin{array}{rl}
		\textbf{Induktionsanfang}: &  S(1) = \sum\limits_{i=1}^1 i^2 = 1^2 = 1 = \dfrac{1(1+1)(2+1)}{6}\\\\
		\textbf{Induktionsvorraussetzung}: & keine Ahnung was hier rein soll\\\\
		\textbf{Induktionsbehauptung}: & S(n+1)=\sum\limits_{i=1}^{n+1} i^2 = \dfrac{(n+1)(n+2)(2(n+1)+1)}{6}\\\\
		\textbf{Induktionsschluss}: & S(n) +(n+1)^2 = \dfrac{n(n+1)(2n+1)}{6} +(n+1)^2 = \dfrac{2n^3 +9n^2+13n+6}{6}\\\\
		& \dfrac{(n+1)(n+2)(2(n+1)+1)}{6}  = \dfrac{2n^3 +9n^2+13n+6}{6} \\\\
	\end{array}$
\end{Beweis}

\begin{Beweis}[Summe der Quadratzahlen (Abschätzung)]
	$\zz$ : $\sum\limits_{i=1}^n i^2 > \dfrac{n^3}{3}$

	$\begin{array}{rl}
		\textbf{Induktionsanfang}: &  1^2 > \dfrac{1^3}{3}  \\\\
		\textbf{Induktionsvorraussetzung}: & \text{für ein beliebiges, aber festes } k \in \N \text{ gilt: } \sum \limits_{i=1}^k i^2  > \dfrac{k^3}{3} \\\\
		\textbf{Induktionsbehauptung}: & \text{man behauptet, dass } \forall n \in \N \text{ gilt: } \sum\limits_{i=1}^{n+1} i^2  > \dfrac{(n+1)^3}{3} \\\\
		\textbf{Induktionsschluss}: &  \sum\limits_{i=1}^{n+1} i^2 = \overbrace{\sum\limits_{i=1}^{n} i^2}^{>\textcolor{red}{\dfrac{n^3}{3}}} + (n+1)^2 > \textcolor{red}{\dfrac{n^3}{3}} +(n+1)^2 \\\\
		&= \dfrac{n^3+3n^2+6n+3}{3} \\\\
		&= \dfrac{n^3+3n^2+3n+1+3n+2}{3}  \\\\
		& = \dfrac{(n+1)^3}{3} + \dfrac{3n+2}{3} \overbrace{>}^{\textcolor{red}{n\geq0}} \dfrac{(n+1)^3}{3} 
	\end{array}$
\end{Beweis}


\begin{Beweis}[Abschätzung der Fakultät]
	$\forall n\in \N,\quad n\geq 4 : \quad n! >n^2 $

	$\begin{array}{rl}
		\textbf{Induktionsanfang}: & n_{o}=4 : \quad 4! = 4\cdot3 \cdot 2 \cdot 1 \cdot 0! = 24>16=4^2 \\\\
		\textbf{Induktionsvorraussetzung}: & \exists n\in\N, \quad n\geq 4:\quad n!>n^2  \\\\
		\textbf{Induktionsbehauptung}: &  n!\,\geq n^2 \Rightarrow (n+1)! > (n+1)^2 = \textcolor{red}{ (n+1)\cdot(n+1)} \\\\
		\textbf{Induktionsschluss}: &  (n+1)! = (n+1)\cdot n ! \quad>\quad \textcolor{red}{ (n+1)\cdot n^2}  \\\\
		& \Rightarrow n^2 \overset{\mathrm{?}}{>} (n+1)  \\\\
		\textbf{Mini-induktion}: &n_{0}=4: \quad 4^2=16>5=4+1 \\\\
		& \Rightarrow (n^2)' \overset{\mathrm{?}}{>} (n+1)' \\\\
		&\Leftrightarrow 2n \overset{\mathrm{!}}{>} 1 \qquad \forall n \in \N \\
	\end{array}$
\end{Beweis}

\end{document}