%
% 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}