From a04efb8ee3eef6ec32b1381801ee244744db1201 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Tue, 2 Mar 2021 10:23:02 +0100
Subject: division in F_p

---
 vorlesungen/slides/4/euklidtabelle.tex | 64 ++++++++++++++++++++++++++++++++++
 1 file changed, 64 insertions(+)
 create mode 100644 vorlesungen/slides/4/euklidtabelle.tex

(limited to 'vorlesungen/slides/4/euklidtabelle.tex')

diff --git a/vorlesungen/slides/4/euklidtabelle.tex b/vorlesungen/slides/4/euklidtabelle.tex
new file mode 100644
index 0000000..2d67823
--- /dev/null
+++ b/vorlesungen/slides/4/euklidtabelle.tex
@@ -0,0 +1,64 @@
+%
+% euklidtabelle.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Durchführung des euklidischen Algorithmus}
+Problem: Berechnung der Produkte $Q(q_k)\cdots Q(q_1)Q(q_0)$ für $k=0,1,\dots,n$
+\begin{block}{Multiplikation mit $Q(q_k)$}
+\vspace{-12pt}
+\begin{align*}
+Q(q_k)
+%\begin{pmatrix}
+%0&1\\1&-q_k
+%\end{pmatrix}
+\begin{pmatrix}
+u&v\\c&d
+\end{pmatrix}
+&=
+\begin{pmatrix}
+c&d\\
+u-q_kc&v-q_kd
+\end{pmatrix}
+&&\Rightarrow&
+\begin{pmatrix}
+c_k&d_k\\c_{k+1}&d_{k+1}
+\end{pmatrix}
+&=
+Q(q_k)
+%\begin{pmatrix}
+%0&1\\1&-q_k
+%\end{pmatrix}
+\begin{pmatrix}
+c_{k-1}&d_{k-1}\\c_{k}&d_{k}
+\end{pmatrix}
+\end{align*}
+\end{block}
+\vspace{-10pt}
+\begin{equation*}
+\begin{tabular}{|>{\tiny$}r<{$}|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|}
+\hline
+k  &q_k    &                     c_k    &                     d_k    \\
+\hline
+-1 &       &                     1      &                     0      \\
+ 0 &q_0    &                     0      &                     1      \\
+ 1 &q_1    &c_{-1} -q_0    \cdot c_0    &d_{-1} -q_0    \cdot d_0    \\
+ 2 &q_2    &c_0    -q_1    \cdot c_1    &d_0    -q_1    \cdot d_1    \\
+\vdots&\vdots&\vdots                    &\vdots                      \\
+ n &q_n    &c_{n-2}-q_{n-1}\cdot c_{n-1}&d_{n-2}-q_{n-1}\cdot d_{n-1}\\
+n+1&       &c_{n-1}-q_{n}  \cdot c_{n}  &d_{n-1}-q_{n}  \cdot d_{n}  \\
+\hline
+\end{tabular}
+\Rightarrow
+\left\{
+\begin{aligned}
+\rlap{$c_{n}$}\phantom{c_{n+1}} a + \rlap{$d_n$}\phantom{d_{n+1}}b &= \operatorname{ggT}(a,b)
+\\
+c_{n+1} a + d_{n+1} b &= 0
+\end{aligned}
+\right.
+\end{equation*}
+\end{frame}
-- 
cgit v1.2.1