Merge pull request #1 from AndreasFMueller/master

update

1 files changed, 65 insertions, 0 deletions

diff --git a/vorlesungen/slides/4/division.tex b/vorlesungen/slides/4/division.tex
new file mode 100644
index 0000000..846738f
--- /dev/null
+++ b/vorlesungen/slides/4/division.tex
@@ -0,0 +1,65 @@
+%
+% division.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\begin{frame}[t]
+\frametitle{Division in $\mathbb{F}_p$}
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Inverse {\bf berechnen}}
+Gegeben $a\in\mathbb{F}_p$, finde $b=a^{-1}\in\mathbb{F}_p$
+\begin{align*}
+\uncover<2->{&& a{\color{blue}b} &\equiv 1 \mod p}
+\\
+\uncover<3->{&\Leftrightarrow& a{\color{blue}b}&=1 + {\color{blue}n}p}
+\\
+\uncover<4->{&&a{\color{blue}b}-{\color{blue}n}p&=1}
+\end{align*}
+\uncover<5->{Wegen
+$\operatorname{ggT}(a,p)=1$ gibt es
+$s$ und $t$ mit
+\[
+{\color{red}s}a+{\color{red}t}p=1
+\Rightarrow
+{\color{blue}b}={\color{red}s},\;
+{\color{blue}n}=-{\color{red}t}
+\]}
+\uncover<6->{%
+$\Rightarrow$ Die Inverse kann mit dem euklidischen Algorithmus
+berechnet werden}
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<7->{%
+\begin{block}{Beispiel in $\mathbb{F}_{1291}$}
+Finde $47^{-1}\in\mathbb{F}_{1291}$
+%\vspace{-10pt}
+\begin{center}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k& a_k& b_k&q_k&  c_k& d_k\\
+\hline
+ &    &    &   &    1&   0\\
+0&  47&1291&\uncover<8->{  0}&    0&   1\\
+1&\uncover<9->{ 1291&  47}&\uncover<11->{ 27}&\uncover<10->{    1&   0}\\
+2&\uncover<12->{  47&  22}&\uncover<14->{  2}&\uncover<13->{  -27&   1}\\
+3&\uncover<15->{  22&   3}&\uncover<17->{  7}&\uncover<16->{   55&  -2}\\
+4&\uncover<18->{   3&   1}&\uncover<20->{  3}&\uncover<19->{{\color{red}-412}&{\color{red}15}}\\
+5&\uncover<21->{   1&   0}&   &\uncover<22->{ 1291& -47}\\
+\hline
+\end{tabular}
+\end{center}
+\uncover<23->{%
+\[
+{\color{red}-412}\cdot 47 +{\color{red}15}\cdot 1291 = 1
+\uncover<24->{\;\Rightarrow\;
+47^{-1}={\color{red}879}}
+\]}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}