diff options
Diffstat (limited to 'vorlesungen/slides/4/euklidtabelle.tex')
-rw-r--r-- | vorlesungen/slides/4/euklidtabelle.tex | 64 |
1 files changed, 64 insertions, 0 deletions
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} |