blob: 6ffa4c20fc624c1d50b26a17cc826fed2b544301 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
%
% euklidmatrix.tex
%
% (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule
%
\begin{frame}[t]
\frametitle{Matrixform des euklidischen Algorithmus}
\setlength{\abovedisplayskip}{5pt}
\setlength{\belowdisplayskip}{5pt}
\vspace{-20pt}
\begin{columns}[t,onlytextwidth]
\begin{column}{0.52\textwidth}
\begin{block}{Einzelschritt}
\vspace{-10pt}
\[
a_k = b_kq_k + r_k
\;\Rightarrow\;
\left\{
\begin{aligned}
a_{k+1} &= b_k = \phantom{a_k-q_k}\llap{$-\mathstrut$}b_k \\
b_{k+1} &= \phantom{b_k}\llap{$r_k$} = a_k - q_kb_k
\end{aligned}
\right.
\]
\end{block}
\end{column}
\begin{column}{0.44\textwidth}
\begin{block}{Matrixschreibweise}
\vspace{-10pt}
\begin{align*}
\begin{pmatrix}
a_{k+1}\\
b_{k+1}
\end{pmatrix}
&=
\begin{pmatrix}
b_k\\r_k
\end{pmatrix}
=
\underbrace{\begin{pmatrix}0&1\\1&-q_k\end{pmatrix}}_{\displaystyle =Q(q_k)}
\begin{pmatrix}
a_k\\b_k
\end{pmatrix}
\end{align*}
\end{block}
\end{column}
\end{columns}
\vspace{-10pt}
\begin{block}{Ende des Algorithmus}
\vspace{-10pt}
\begin{align*}
\begin{pmatrix}
a_{n+1}\\
b_{n+1}\\
\end{pmatrix}
&=
\begin{pmatrix}
r_{n-1}\\
r_{n}
\end{pmatrix}
=
\begin{pmatrix}
\operatorname{ggT}(a,b) \\
0
\end{pmatrix}
=
\underbrace{Q(q_n)
\dots
Q(q_1)
Q(q_0)}_{\displaystyle =Q}
\begin{pmatrix} a_0\\ b_0\end{pmatrix}
=
Q\begin{pmatrix}a\\b\end{pmatrix}
\end{align*}
\end{block}
\begin{block}{Konsequenzen}
\[
Q=\begin{pmatrix}
q_{11}&q_{12}\\
a_{21}&q_{22}
\end{pmatrix}
\quad\Rightarrow\quad
\left\{
\quad
\begin{aligned}
\operatorname{ggT}(a,b) &= q_{11}a + q_{12}b \\
0 &= q_{21}a + q_{22}b
\end{aligned}
\right.
\]
\end{block}
\end{frame}
|
