\RequirePackage[l2tabu, orthodox]{nag}
\documentclass[a4paper,ngerman,fleqn, 10pt]{article}

\usepackage{microtype}

% math
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}

\usepackage[landscape,margin=8pt]{geometry}
\usepackage[extreme]{savetrees}
\usepackage{multicol}

\newcommand{\zmod}[1]{\mathbb{Z}/#1\,\mathbb{Z}}
\newcommand{\base}[2]{#2_{(#1)}}
\newcommand{\fall}[2]{\forall #1 .\  #2}
\newcommand{\exi}[2]{\exists #1 .\  #2}

\DeclareMathOperator{\ggT}{ggT}
\DeclareMathOperator{\kgV}{kgV}

\newtheorem*{theorem}{Satz}
\newtheorem*{corollary}{Korollar}

\title{Elementare Zahlentheorie}
\begin{document}
\begin{multicols*}{2}

\section*{Algorithmus von Euklid}
\begin{multicols}{2}

$\ggT(a,b)$:
\begin{align*}
a &= q_{1} \cdot b + r_{1}\\
b &= q_{2} \cdot r_{1} + r_{2}\\
  & \vdots \\
r_{n-1} &= q_{*} \cdot r_{n} + 0\\
\end{align*}
\columnbreak{}
$\ggT(a,b) = r_n$
\end{multicols}

\paragraph{Multiplikativ Inverses $x^{-1}$ in $\zmod{n}$}

\[
  x \cdot x^{-1} \equiv 1 \bmod n
\]

Beispiel mit $x = 31$ und $n = 245$:
Gesucht ist $ 31 \cdot x \equiv 1 \bmod 245 \Leftrightarrow 31 \cdot x + 245 \cdot y \equiv 1$

\begin{align*}
245 &= 7 \cdot 31 + 28  &   &= -9 \cdot 31 + 10 \cdot (245 - 7 \cdot 31) &=& 10 \cdot 245 \boxed{- 79} \cdot 31& \uparrow\\
31  &= 1 \cdot 28 + 3   &   &= 28 - 9 \cdot (31 - 1 \cdot 28)            &=& -9 \cdot 31 + 10 \cdot 28         & \uparrow\\
28  &= 9 \cdot 3 + 1    & 1 &= 28 - 9 \cdot 3                            & &                                   &\uparrow\\
\end{align*}
\[-79 \equiv 166\]
$166$ ist das multiplikativ Inverse von $31$ in $\zmod{245}$

\paragraph{Kleinstes gemeinsames Vielfaches $\kgV(a,b)$}
\[
  \ggT(a,b) \cdot \kgV(a,b) = a \cdot b
\]

Beispiel:
\begin{align*}
\kgV(120,315) &= \kgV(2^3 \cdot 3 \cdot 5, 3^2 \cdot 5 \cdot 7)\\
  &= 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520\\
\end{align*}

\paragraph{Berechne $ax + by = c$ mit $x,y \in \mathbb{Z}$}
\begin{enumerate}
  \item Berechne $\ggT(a,b) = \ggT(-a,b)$
  \item Falls $\ggT(a,b) \nmid c$, dann unlösbar.
    \begin{theorem}
      \[
      \fall{ a,b \in \mathbb{N}}{\fall{x,y \in \mathbb{Z}} {\exi{ z \in \mathbb{Z}}{ x \cdot a + y \cdot b = z \cdot \ggT(a,b)}}}
      \]
    \end{theorem}
  \item Berechne Bezout-Koeffizienten: $\ggT(a,b) = a \cdot x' + b \cdot y'$
    
    Falls $\ggT(a,b) \ne 1$, dann
    \[
      \frac{a}{\ggT(a,b)}\cdot x + \frac{b}{\ggT(a,b)}\cdot y = \frac{c}{\ggT(a,b)}
    \]
    \item Berechne Partikularlösung, angenommen $ax' + by' = 1 = \ggT(a,b)$
      \begin{align*}
        &q \cdot \ggT(a,b) = c\\
        \Rightarrow& a \cdot (q\cdot x') + b \cdot (q \cdot y') = q \cdot ggT(a,b) = c\\
        \Rightarrow& (x_0,y_0) = (q\cdot x',q\cdot y') \text{ist Partikularlösung}\\
      \end{align*}
    \item Berechne alle Lösungen: $\mathcal{L} = {(x_o + t \cdot b, y_0 -t \cdot a)| t \in \mathbb{Z}}$
      
      Löse nach $t$:
      \begin{align*}
        x_0 + t \cdot b &\ge 0\\
        y_0 - t \cdot a &\ge 0\\
      \end{align*}
    
\end{enumerate}
Beispiel: $6x + 4y = 14$:
\begin{enumerate}
  \item $\ggT(6,4)=2= 1\cdot 6 + y'\cdot 4$
  \item $2 \mid 14 \to$ lösbar
  \item $ q \cdot 2 = 14 $, also $ q = 7$\\
    Partikularlösung $(7 \cdot 1, 7 \cdot (-1)) = (7,-7)$
  \item Lösungsmenge
    \[
      \mathcal{L} = \left\{(7 + (4/2) \cdot t, -7 + (4/2) \cdot t) \mid t \in \mathbb{Z}\right\}
    \]

\end{enumerate}

\section*{Stellenwertsysteme}
\paragraph{Dezimalsystem $\to$ b-System}
Beispiel: $521$ zur Basis $3$:
\begin{multicols}{2}
\begin{align*}
521 &= 173 \cdot 3 +& 2& \uparrow\\
173 &= 57 \cdot 3 +& 2&\uparrow\\
57 &= 19 \cdot 3 +& 0&\uparrow\\
19 &= 6 \cdot 3 +& 1&\uparrow\\
6 &= 2 \cdot 3 +& 0&\uparrow\\
2 &= 0 \cdot 3 +& 2&\uparrow\\
\end{align*}
\columnbreak{}
\[
  521 = \base{3}{201022}
\]
\end{multicols}

\section*{Dezimalbruchentwicklung}
Bestimme Art der Dezimalbruchentwicklung (endlich, rein- oder gemischtperiodisch) von $\frac{n}{m}$
\begin{enumerate}
  \item Bruch vollständig kürzen. (explizit hinschreiben!)
  \item Faktorisiere Nenner
    \begin{theorem}
      Ein Bruch $\frac{n}{m}$ mit $ m < n$ und $\ggT(m,n) = 1$ hat
      \begin{description}
        \item[\emph{endliche} Dezimalbruchentwicklung] mit $s$ Stellen, wenn $n = 2^a\cdot 5^b$ mit $s = \max(a,b)$
        \item[\emph{reinperiodische} Dezimalbruchentwicklung] mit Periodenlänge $s$, wenn $\ggT(n,10) = 1$ mit $s = \min(s, n) \mid (10^s -1)$
        \item[\emph{gemischtperiodische} Dezimalbruchentwicklung] $0,p_1\dots p_t\overline{q_1\dots q_s}$, wenn $n = n_1 \cdot n_2$ mit $n_1,n_2> 1$ und $\min(t, n_1) \mid 10^t$, $\ggT(n_2,10) = 1$ und $s$ als Periodenlänge von $\frac{1}{n_2}$
      \end{description}
    \end{theorem}
\end{enumerate}
\section*{Periodische Zahl als Bruch}
Beispiel: Stelle $0,\overline{0456}$ als Bruch dar.

Mit $z = 456$ und der Periodenlänge $s=4$
\[
  0,\overline{0456} = \frac{456}{10^s-1} = \frac{456}{9999}
\]

\section*{Kettenbruchdarstellung}
Beispiel: Kettenbruchdarstellung von $\frac{162}{355}$
\begin{multicols}{2}
\begin{align*}
162 &= \boxed{0} \cdot 355 + 162\\
355 &= \boxed{5} \cdot 162 + 7\\
31  &= \boxed{4} \cdot 7 + 3\\
7   &= \boxed{2} \cdot 3 + 1\\
3   &= \boxed{3} \cdot 1 + 0\\
\end{align*}
\columnbreak{}
\[
  \frac{162}{355} = 0 + \dfrac{1}{2 + \dfrac{1}{5 + \dfrac{1}{4 + \dfrac{1}{2 + \dfrac{1}{3}}}}}
\]
\end{multicols}
\section*{$\varphi$, Euler, Fermat}
\begin{theorem}[von Euler]
  Seien $a,m$ teilerfremd, dann $a^{\varphi(m)} \equiv 1 \bmod m$
\end{theorem}
\begin{corollary}[vom kleinen Fermat]
  Für $a \in \mathbb{N}$, $p$ prim, gilt: $a^p\equiv a \bmod p$
\end{corollary}
\begin{description}
\item[Für Primzahlen $p,n \ge 1$]
  \[
    \varphi(p^n) = p^{n-1}\cdot (p-1)
  \]
\item[Für $\ggT(a,b) = 1$]
  \[
    \varphi(a\cdot b) = \varphi(a) \cdot \varphi(b)
  \]
\end{description}

\begin{theorem}[eulersche $\varphi$-Funktion]
  \[
    \varphi(n) = \Pi_{p|n}p^{k_p-1}(p - 1)
  \]
\end{theorem}
Beispiel: $\varphi(72) = \varphi(2^3 \cdot 3^2) = 2^{3-1} \cdot (2 - 1) \cdot 3^{2-1}\cdot (3 - 1) = 24$

\paragraph{$a^b$ in $\zmod{m}$}
\begin{multicols}{2}

Wenn $a,m$ teilerfremd: $a^{\varphi(m)} \equiv 1$

%TODO%

\columnbreak{}
Generell: Fast Modular Exponentation\\
Beispiel: $7^{19} \bmod 17$\\
$19 = 10011_{(2)}$
\begin{align*}
1 \Rightarrow & 1^2 &\cdot 7 &\bmod 17 \equiv &7\\
0 \Rightarrow & 7^2 &&\bmod 17 \equiv &15\\
0 \Rightarrow & 15^2&& \bmod 17 \equiv &4\\
1 \Rightarrow & 4^2 &\cdot 7 &\bmod 17 \equiv &17\\
1 \Rightarrow & 10^2 &\cdot 7 &\bmod 17 \equiv &\boxed{3}\\
\end{align*}

\end{multicols}
\section*{Chinesischer Restesatz}
\begin{multicols}{2}
\begin{align*}
x &\equiv 5 \bmod 11\\
x &\equiv 6 \bmod 14\\
x &\equiv 7 \bmod 15\\
\end{align*}
\columnbreak{}
\begin{align*}
m &= 11 \cdot 14 \cdot 15 &=& 2310\\
q_1 &= 14 \cdot 15 &=&210\\
q_2 &= 11 \cdot 15 &=&165\\
q_3 &= 11 \cdot 14 &=&154\\
\end{align*}
\end{multicols}
\begin{align*}
\text{in } \zmod{11}:\qquad& \overline{q_1} = \overline{210} = 1  &\Rightarrow& q_1' = 1\\
\text{in } \zmod{14}:\qquad& \overline{q_2} = \overline{165} = \overline{11} &\Rightarrow \overline{11} \cdot \underbrace{\overline{9}}_{\text{Inverses}} \equiv 1 \Rightarrow& q_2' = 9\\
\text{in } \zmod{15}:\qquad& \overline{q_3} = \overline{154} = \overline{4} &\Rightarrow \overline{4} \cdot \overline{4} \equiv 1 \Rightarrow& q_2' = 9\\
\end{align*}
\begin{align*}
  x &= a_1 \cdot q_1 \cdot q_1' + \dots\\
    &= 5 \cdot 210 \cdot 1 + 6 \cdot 165 \cdot 9 + 7 \cdot 154 \cdot 4\\
    &= 14272 \equiv 412 \bmod 2310\\
\end{align*}
Eindeutige Lösung $\overline{x} \equiv \overline{412}$

\section*{Teilbarkeitsregeln}
\paragraph{Endstellenregeln}
\begin{theorem}
  Sei $t \mid 10^s$, dann gilt:
  \[
    z_n \dots z_0 \equiv z_{s-1}\dots z_0 \bmod t
  \]
  Beispiel: $ 4 \mid 100$:
  \[
    4 \mid 87954236 \Leftrightarrow 4 \mid 36
  \]
\end{theorem}
\paragraph{Quersummenregeln}\hfill\break{}
Für $t\mid 9$:
\[
  z_n\dots z_0 \equiv z_n+ \dots +z_0 \bmod t
\]
Für $t \mid 99$:
\[
  z_n\dots z_0 \equiv z_nz_{n-1}+\dots+z_1z_0 \bmod t
\]
Beispiel:
$11 \mid 21748 \Leftrightarrow 11 \mid (01 + 17 + 48) \Leftrightarrow 11 \mid 66$

Für $t \mid 11 = 10^1+1$
\[
  z_n\dots z_0 \equiv \dots-z_3+z_2-z_1+z_0 \bmod t
\]
Für $t \mid 101 = 10^2+1$
\[
  z_n\dots z_0 \equiv \dots-z_3z_2+z_1z_0 \bmod t
\]

\section*{Sonstiges}
\begin{multicols}{2}
  

\paragraph{RSA -- Verschlüsseln}
\begin{enumerate}
  \item Wähle $p,q$ prim, $n = p \cdot q$
  \item $\varphi(n) = \varphi(p) \cdot \varphi(q) = (p - 1) \cdot (q - 1)$
  \item Wähle $e$ teilerfremd zu $\varphi(n)$ (z.B. eine Primzahl)
  \item Berechne multiplikativ Inverses $d$ zu $e$ in $\zmod{\varphi(n)}$ 
  \end{enumerate}
  \begin{description}
  \item[Öffentlicher Schlüssel] $(n,e)$
  \item[Privater Schlüssel] $(n,d)$
  \end{description}
  \[
    c = m^{e} \bmod n
  \]
\columnbreak{}
\paragraph{RSA -- Entschlüsseln}
\[
  m = c^d \bmod m
\]
Berechnung mit chinesischem Restesatz:
\begin{enumerate}
  \item $m = c \bmod p$
        $m = c \bmod q$
  \item $t_1 = c^{d \bmod \varphi(p)} \bmod p$
  $t_2 = c^{d \bmod \varphi(q)} \bmod q$
  \item $d_1 = p^{-1} \bmod q$
    $d_2 = q^{-1} \bmod p$
  \item $m = (d_1 \cdot p \cdot t_2 + d_2 \cdot q \cdot t_1) \bmod n$
  \end{enumerate}
\end{multicols}
\end{multicols*}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% TeX-master: t
%%% TeX-master: t
%%% End: