%
% 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*}
&& a{\color{red}b} &\equiv 1 \mod p
\\
&\Leftrightarrow& a{\color{red}b}&=1 + {\color{red}n}p
\\
&&a{\color{red}b}-{\color{red}n}p&=1
\end{align*}
Wegen
$\operatorname{ggT}(a,p)=1$ gibt es
$s$ und $t$ mit
\[
sa+tb=1
\Rightarrow
{\color{red}b}=s,\;
{\color{red}n}=-t
\]
$\Rightarrow$ Die Inverse kann mit dem euklidischen Algorithmus
berechnet werden
\end{block}
\end{column}
\begin{column}{0.48\textwidth}
\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&  0&    0&   1\\
1&1291&  47& 27&    1&   0\\
2&  47&  22&  2&  -27&   1\\
3&  22&   3&  7&   55&  -2\\
4&   3&   1&  3&{\color{red}-412}&{\color{red}15}\\
5&   1&   0&   & 1291& -47\\
\hline
\end{tabular}
\end{center}
\[
{\color{red}-412}\cdot 47 +{\color{red}15}\cdot 1291 = 1
\;\Rightarrow\;
47^{-1}={\color{red}879}
\]
\end{block}
\end{column}
\end{columns}
\end{frame}