% % euklid.tex % % (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Der euklidische Algorithmus \label{buch:section:euklid}} \rhead{Der euklidische Algorithmus} Der euklidische Algorithmus bestimmt zu zwei gegebenen ganzen Zahlen $a$ und $b$ den grössten gemeinsamen Teiler $g$. Zusätzlich findet er ganze Zahlen $s$ und $t$ derart, dass \[ sa + tb = g. \] In diesem Abschnitt soll der Algorithmus zunächst für ganze Zahlen vorgestellt werden, bevor er auf Polynome verallgemeinert und dann in Matrixform niedergeschrieben wird. % % Der euklidische Algorithmus für ganze Zahlen % \subsection{Ganze Zahlen} Gegeben sind zwei ganze Zahlen $a$ und $b$ und wir dürfen annehmen, dass $a\ge b$. Gesucht ist der grösste gemeinsame Teiler $g$ von $a$ und $b$. Wir schreiben $g|a$ für ``$g$ ist Teiler von $a$'' oder ``$g$ teilt $a$'', gesucht ist also die grösste ganze Zahl $g$ derart, dass $g|a$ und $g|b$. Ist $b|a$, dann ist offenbar $b$ der grösste gemeinsame Teiler von $a$ und $b$. Im Allgemeinen wird der grösste gemeinsame Teiler aber kleiner sein. Wir teilen daher $a$ durch $b$, was nur mit Rest möglich ist. Es gibt ganze Zahlen $q$, der Quotient, und $r$, der Rest, derart, dass \begin{equation} a = qb+ r \qquad \Rightarrow \qquad r = a - qb. \label{lifting:euklid:raqb} \end{equation} Nach Definition des Restes ist $r < b$. Da der grösste gemeinsame Teiler sowohl $a$ als auch $b$ teilt, muss er wegen~\eqref{lifting:euklid:raqb} auch $r$ teilen. Somit haben wir das Problem, den grössten gemeinsamen Teiler von $a$ und $b$ zu finden, auf das ``kleinere'' Problem zurückgeführt, den grössten gemeinsamen Teiler von $b$ und $r$ zu finden. Um den eben beschriebenen Schritt zu wiederholen, wählen wir die folgende Notation. Wir schreiben $a_0=a$ und $b_0=b$. Im ersten Schritt finden wird $q_0$ und $r_0$ derart, dass $a_0-q_0b_0 = r_0$. Dann setzen wir $a_1=b_0$ und $b_1=r_0$. Mit $a_1$ und $b_1$ wiederholen wir den Divisionsschritt, der einen neuen Quotienten $q_1$ und einen neuen Rest $r_1$ liefert mit $a_1-q_1b_1=r_1$. So entstehen vier Folgen von Zahlen $a_k$, $b_k$, $q_k$ und $r_k$ derart, dass in jedem Schritt gilt \begin{align*} a_k - q_kb_k &= r_k & g&|a_k & g&|b_k & a_k &= b_{k-1} & b_k = r_{k-1} \end{align*} Der Algorithmus bricht im Schritt $n$ ab, wenn $r_{n+1}=0$. Der letzte nicht verschwindende Rest $r_n$ muss daher der grösste gemeinsame Teiler sein: $g=r_n$. \begin{beispiel} \label{buch:endlichekoerper:beispiel1} Wir bestimmen den grössten gemeinsamen Teiler von $76415$ und $23205$ mit Hilfe des eben beschriebenen Algorithmus. Wir schreiben die gefundenen Zahlen in eine Tabelle: \begin{center} \renewcommand{\arraystretch}{1.1} \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} \hline k& a_k& b_k& q_k& r_k\\ \hline 0&76415&23205& 3&6800\\ 1&23205& 6800& 3&2805\\ 2& 6800& 2805& 2&1190\\ 3& 2805& 1190& 2& 425\\ 4& 1190& 425& 2& 340\\ 5& 425& 340& 1& 85\\ 6& 340& 85& 4& 0\\ \hline \end{tabular} \end{center} Der Algorithmus bricht also mit dem letzten Rest $r_n=85$ ab, dies ist der grösste gemeinsame Teiler. \end{beispiel} Die oben protokollierten Werte von $q_k$ werden für die Bestimmung des grössten gemeinsamen Teilers nicht benötigt. Wir können sie aber verwenden, um die Zahlen $s$ und $t$ zu bestimmen. \begin{beispiel} Wir drücken die Reste im obigen Beispiel durch die Zahlen $a_k$, $b_k$ und $q_k$ aus und setzen sie in den Ausdruck $g=a_5-q_5b_5$ ein, bis wir einen Ausdruck in $a_0$ und $b_0$ für $g$ finden: \begin{align*} r_5&=a_5-q_5 b_5=a_5-1\cdot b_5& g &= a_5 - 1 \cdot b_5 = b_4 - 1 \cdot r_4 \\ r_4&=a_4-q_4 b_4=a_4-2\cdot b_4& &= b_4 - (a_4 -2b_4) = -a_4 +3b_4 = -b_3 + 3r_3 \\ r_3&=a_3-q_3 b_3=a_3-2\cdot b_3& &= -b_3 + 3(a_3-2b_3) = 3a_3 - 7b_3 = 3b_2 -7r_2 \\ r_2&=a_2-q_2 b_2=a_2-2\cdot b_2& &= 3b_2 -7(a_2-2b_2) = -7a_2 + 17b_2 = -7b_1 + 17r_1 \\ r_1&=a_1-q_1 b_1=a_1-3\cdot b_1& &= -7b_1 + 17(a_1-3b_1) = 17a_1 - 58b_1 = 17 b_0 - 58 r_0 \\ r_0&=a_0-q_0 b_0=a_0-3\cdot b_0& &= 17b_0 - 58(a_0t-3b_0) = -58a_0+191b_0 \end{align*} Tatsächlich gilt \[ -58\cdot 76415 + 191 \cdot 23205 = 85, \] die Zahlen $t=-58$ und $s=191$ sind also genau die eingangs versprochenen Faktoren. \end{beispiel} % % Matrixschreibeweise für den euklidischen Algorithmus % \subsection{Matrixschreibweise \label{buch:endlichekoerper:subsection:matrixschreibweise}} Die Durchführung des euklidischen Algorithmus lässt sich besonders elegant in Matrixschreibweise dokumentieren. In jedem Schritt arbeitet man mit zwei ganzen Zahlen $a_k$ und $b_k$, die wir als zweidimensionalen Spaltenvektor betrachten können. Der Algorithmus macht aus $a_k$ und $b_k$ die neuen Zahlen $a_{k+1} = b_k$ und $b_{k+1} = r_k = a_k - q_kb_k$, dies kann man als \[ \begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix} = \begin{pmatrix} b_k \\ r_k \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -q_k \end{pmatrix} \begin{pmatrix} a_{k} \\ b_{k} \end{pmatrix} \] schreiben. Der Algorithmus bricht ab, wenn die zweite Komponente des Vektors $=0$ ist, in der ersten steht dann der grösste gemeinsame Teiler. Hier ist die Durchführung des Algorithmus in Matrix-Schreibweise: \begin{align*} \begin{pmatrix} 23205 \\ 6800 \end{pmatrix} &= \begin{pmatrix} 0&1\\1&-3 \end{pmatrix} \begin{pmatrix} 76415 \\ 23205 \end{pmatrix} \\ \begin{pmatrix} 6800 \\ 2805 \end{pmatrix} &= \begin{pmatrix} 0&1\\1&-3 \end{pmatrix} \begin{pmatrix} 23205 \\ 6800 \end{pmatrix} \\ \begin{pmatrix} 2805 \\ 1190 \end{pmatrix} &= \begin{pmatrix} 0&1\\1&-2 \end{pmatrix} \begin{pmatrix} 6800 \\ 2805 \end{pmatrix} \\ \begin{pmatrix} 1190 \\ 425 \end{pmatrix} &= \begin{pmatrix} 0&1\\1&-2 \end{pmatrix} \begin{pmatrix} 2805 \\ 1190 \end{pmatrix} \\ \begin{pmatrix} 425 \\ 340 \end{pmatrix} &= \begin{pmatrix} 0&1\\1&-2 \end{pmatrix} \begin{pmatrix} 1190 \\ 425 \end{pmatrix} \\ \begin{pmatrix} 340 \\ 85 \end{pmatrix} &= \begin{pmatrix} 0&1\\1&-1 \end{pmatrix} \begin{pmatrix} 425 \\ 340 \end{pmatrix} \\ \begin{pmatrix} 85 \\ 0 \end{pmatrix} &= \begin{pmatrix} 0&1\\1&-4 \end{pmatrix} \begin{pmatrix} 340 \\ 85 \end{pmatrix} = \begin{pmatrix}g\\0\end{pmatrix}. \end{align*} \begin{definition} Wir kürzen \[ Q(q_k) = \begin{pmatrix} 0 & 1 \\ 1 & -q_k \end{pmatrix} \] ab. \end{definition} Mit dieser Definition lässt sich der euklidische Algorithmus wie folgt beschreiben. \begin{algorithmus}[Euklid] \label{lifting:euklid} Der Algorithmus operiert auf zweidimensionalen Zustandsvektoren $x\in\mathbb Z^2$ wie folgt: \begin{enumerate} \item Initialisiere den Zustandsvektor mit den ganzen Zahlen $a$ und $b$: $\displaystyle x = \begin{pmatrix}a\\b\end{pmatrix}$ \item Bestimme den Quotienten $q$ als die grösste ganze Zahl, für die $qx_2\le x_1$ gilt. \item Berechne den neuen Zustandsvektor als $Q(q)x$. \item Wiederhole Schritte 2 und 3 bis die zweite Komponente des Zustandsvektors verschwindet. Die erste Komponente ist dann der gesuchte grösste gemeinsame Teiler. \end{enumerate} \end{algorithmus} Auch die Berechnung der Zahlen $s$ und $t$ lässt sich jetzt leichter verstehen. Nach Algorithmus~\ref{lifting:euklid} ist \[ \begin{pmatrix} g \\ 0 \end{pmatrix} = Q(q_n)Q(q_{n-1})\cdots Q(q_0) \begin{pmatrix} a \\ b \end{pmatrix}. \] Schreiben wir $Q=Q(q_n)Q(q_{n-1})\cdots Q(q_0)$, dann enthält die Matrix $Q$ in der erste Zeile die ganzen Zahlen $s$ und $t$, mit denen sich der grösste gemeinsame Teiler aus $a$ und $b$ darstellen lässt: \[ Q = \begin{pmatrix} s&t\\ q_{21}&q_{22} \end{pmatrix} \qquad\Rightarrow\qquad \bigg\{ \quad \begin{aligned} g&=sa+tb\\ 0&=q_{21}a+q_{22}b. \end{aligned} \] \begin{beispiel} Wir verifizieren die Behauptung durch Nachrechnen: \begin{align*} Q &= \begin{pmatrix} 0&1 \\ 1&-q_n\end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-q_{n-1}\end{pmatrix} \cdots \begin{pmatrix} 0&1 \\ 1&-q_{0}\end{pmatrix} \\ &= \underbrace{ \begin{pmatrix} 0&1 \\ 1& -4 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1& -1 \end{pmatrix} }_{} \underbrace{ \begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix} }_{} \underbrace{ \begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1& -3 \end{pmatrix} }_{} \begin{pmatrix} 0&1 \\ 1& -3 \end{pmatrix} \\ &= \underbrace{ \begin{pmatrix} 1 & -1 \\ -4 & 5 \end{pmatrix} \begin{pmatrix} 1 & -2 \\ -2 & 5 \end{pmatrix} }_{} \underbrace{ \begin{pmatrix} 1 & -2 \\ -3 & 7 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -3 \end{pmatrix} }_{} \\ &= \begin{pmatrix} 3 & -7 \\ -14 & 33 \end{pmatrix} \begin{pmatrix} -3 & 10 \\ 7 & -23 \end{pmatrix} = \begin{pmatrix} -58 & 191 \\ 273 & -899 \end{pmatrix}. %(%i9) Q6 . Q5 % [ 1 - 1 ] %(%o9) [ ] % [ - 4 5 ] %(%i10) Q4 . Q3 % [ 1 - 2 ] %(%o10) [ ] % [ - 2 5 ] %(%i11) Q2 . Q1 % [ 1 - 3 ] %(%o11) [ ] % [ - 2 7 ] %(%i12) Q6 . Q5 . Q4 . Q3 % [ 3 - 7 ] %(%o12) [ ] % [ - 14 33 ] %(%i13) Q2 . Q1 . Q0 % [ - 3 10 ] %(%o13) [ ] % [ 7 - 23 ] %(%i14) Q6 . Q5 . Q4 . Q3 . Q2 . Q1 . Q0 % [ - 58 191 ] %(%o14) [ ] % [ 273 - 899 ] \end{align*} In der zweiten Zeile findet man Zahlen, die $a$ und $b$ zu 0 kombinieren: \[ 273 \cdot 76415 - 899 \cdot 23205 = 0, \] in der ersten stehen die Zahlen $s=-58$ und $t=191$ und tatsächlich ergibt \[ ta+sb = -58\cdot 76415 + 191\cdot 23205 = 85 = g \] den grössten gemeinsamen Teiler von 76415 und 23205. \end{beispiel} Die Wirkung der Matrix \[ Q(q) = \begin{pmatrix} 0 & 1 \\ 1 & -q \end{pmatrix} \] lässt sich mit genau einer Multiplikation und einer Addition berechnen. Dies ist die Art von Matrix, die wir für die Implementation der Wavelet-Transformation anstreben. % % Vereinfachte Durchführung des euklidischen Algorithmus % \subsection{Vereinfachte Durchführung \label{buch:endlichekoerper:subsection:matrixschreibweise}} Die Durchführung des euklidischen Algorithmus mit Hilfe der Matrizen $Q(q_k)$ ist etwas unhandlich. In diesem Abschnitt sollen die Matrizenprodukte daher in einer Form dargestellt werden, die leichter als Programm zu implementieren ist. In Abschnitt~\ref{buch:endlichekoerper:subsection:matrixschreibweise} wurde gezeigt, dass das Produkt der aus den Quotienten $q_k$ gebildeten Matrizen $Q(q_k)$ berechnet werden müssen. Dazu beachten wir zunächst, dass die Multiplikation mit der Matrix $Q(q_k)$ die zweite Zeile in die erste Zeile verschiebt: \[ Q(q_k) \begin{pmatrix} u&v\\ c&d\\ \end{pmatrix} = \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}. \] Die Matrizen \[ Q_k = Q(q_k)Q(q_{k-1})\dots Q(q_0) \] haben daher jeweils für aufeinanderfolgende Werte vo $k$ eine Zeile gemeinsam. Wir bezeichnen die Einträge der ersten Zeile der Matrix $Q_k$ mit $c_k$ und $d_k$. Es gilt dann \[ Q_k = \begin{pmatrix} c_{k} &d_{k} \\ c_{k+1}&d_{k+1} \end{pmatrix} = Q(q_k) \begin{pmatrix} c_{k-1}&d_{k-1}\\ c_{k} &d_{k} \end{pmatrix} \] Daraus ergeben sich die Rekursionsformeln \begin{equation} \begin{aligned} c_{k+1}&=c_{k-1}-q_kc_k\\ d_{k+1}&=d_{k-1}-q_kd_k. \end{aligned} \label{buch:endlichekoerper:eqn:cdrekursion} \end{equation} Die Auswertung des Matrizenproduktes von links nach rechts beginnt mit der Einheitsmatrix, es ist \[ Q_0 = Q(q_0) I = \begin{pmatrix} 0&1\\ 1&-q_0 \end{pmatrix} \begin{pmatrix} 1&0\\0&1\end{pmatrix}, \] woraus man ablesen kann, dass \begin{equation} Q_{-1} = \begin{pmatrix} c_{-1}&d_{-1}\\ c_0&d_0 \end{pmatrix} = \begin{pmatrix} 1&0\\ 0&1 \end{pmatrix} \label{buch:endlichekoerper:eqn:cdinitial} \end{equation} gesetzt werden muss. Mit diesen Notationen kann man den Algorithmus jetzt in der früher verwendeten Tabelle durchführen, die man um die zwei Spalten $c_k$ und $d_k$ hinzufügt und die Werte in dieser Spalte mit Hilfe der Rekursionsformeln~\eqref{buch:endlichekoerper:eqn:cdrekursion} aus den initialen Werten~\eqref{buch:endlichekoerper:eqn:cdinitial} berechnet. \begin{beispiel} Wir erweitern das Beispiel von Seite~\pageref{buch:endlichekoerper:beispiel1} zur Bestimmung des grössten gemeinsamen Teilers von $76415$ und $23205$ zur Berechnung der Koeffizienten $c_k$ und $d_k$ Wir schreiben die gefundenen Zahlen in eine Tabelle: \begin{center} \label{buch:endlichekoerper:beispiel1erweitert} \renewcommand{\arraystretch}{1.1} \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} \hline k& a_k& b_k& q_k& r_k& c_k& d_k\\ \hline & & & & & 1& 0\\ 0& 76415& 23205& 3& 6800& 0& 1\\ 1& 23205& 6800& 3& 2805& 1& -3\\ 2& 6800& 2805& 2& 1190& -3& 10\\ 3& 2805& 1190& 2& 425& 7& -23\\ 4& 1190& 425& 2& 340& -17& 56\\ 5& 425& 340& 1& 85& 41& -135\\ 6& 340& 85& 4& 0& -58& 191\\ 7& 85& 0& & & 273& -899\\ \hline \end{tabular} \end{center} Aus den letzten zwei Spalten der Tabelle kann man ablesen, dass \begin{align*} -58\cdot 76415 + 191\cdot 23205 &= 85\\ 273\cdot 76415 - 899\cdot 23205 &= 0, \end{align*} wie erwartet. Die gesuchten Zahlen $s$ und $t$ sind also $s=-58$ und $t=191$. \end{beispiel} Die Matrizen $Q_k$ kann man auch as der Tabelle ablesen, sie bestehen aus den vier Elementen in den Zeilen $k$ und $k+1$ in den Spalten $c_k$ und $d_k$. Auf jeder Zeile gilt $b_k = c_ka_0 + d_kb_0$, für $k>0$ ist dies $c_ka_0+d_kb_0=r_{k-1}$. Bis jetzt gingen wir immer davon aus, dass $a>b$ ist. Dies ist jedoch nicht nötig, wie die Durchführung des Algorithmus für das obige Beispiel mit vertauschten Werten von $a$ und $b$ zeigt. Wir bezeichnen die Elemente zur Unterscheidung von der ursprünglichen Durchführung mit einem Strich: \begin{center} \renewcommand{\arraystretch}{1.1} \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} \hline k& a_k'& b_k'& q_k'& r_k'& c_k'& d_k'\\ \hline & & & & & 1& 0\\ 0& 23205& 76415& 0& 23205& 0& 1\\ 1& 76415& 23205& 3& 6800& 1& 0\\ 2& 23205& 6800& 3& 2805& -3& 1\\ 3& 6800& 2805& 2& 1190& 10& -3\\ 4& 2805& 1190& 2& 425& -23& 7\\ 5& 1190& 425& 2& 340& 56& -17\\ 6& 425& 340& 1& 85& -135& 41\\ 7& 340& 85& 4& 0& 191& -58\\ 8& 85& 0& & & -899& 273\\ \hline \end{tabular} \end{center} Da für $a{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} \hline k& a_k& b_k& q_k& r_k\\ \hline 0& X^4 - 2X^3 -7 X^2 + 8X + 12& X^4 + X^3 -7X^2 -X + 6& 1&-3X^3+9X+6\\ 1&X^4+X^3-7X^2-X+6 &-3X^3+9X+6 &-\frac13X-\frac13&-4X^2+4X+8\\ 2&-3X^3+9X+6 &-4X^2+4X+8& \frac34 X + \frac34& 0\\ \hline \end{tabular} \end{center} Daraus kann man ablesen, dass $-4x^2+4x+8$ grösster gemeinsamer Teiler ist. Normiert auf einen führenden Koeffizienten $1$ ist dies das Polynom $x^2-x+2=(x+2)(x-1)$. Wir berechnen auch noch die Polynome $s$ und $t$. Dazu müssen wir die Matrizen $Q(q_k)$ miteinander multiplizieren: \begin{align*} Q &=Q(q_2) Q(q_1) Q(q_0) \\ &= \begin{pmatrix} 0 & 1 \\ 1 & -\frac34(X+1) \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & \frac13(X+1) \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix} \\ &= % [ x 1 2 x ] % [ - + - - - - ] % [ 3 3 3 3 ] %(%o22) [ ] % [ 2 2 ] % [ x x 3 x x 3 ] % [ (- --) - - + - -- - - - - ] % [ 4 2 4 4 4 2 ] \begin{pmatrix} \frac13(X+1)&-\frac13(X-2)\\ -\frac14(X^2+2X-3)&\frac14(X^2-X-6) \end{pmatrix}. \end{align*} In der ersten Zeile finden wir die Polynome $t(X)$ und $s(X)$, mit denen \begin{align*} ta+sb &= \frac13(X+1) (X^4-2X^3-7X^2+8X+12) -\frac13(X-2) (X^4+X^3-7X^2-X+6) \\ &= -4X^2+4X+8 \end{align*} und dies ist tatsächlich der gefundene grösste gemeinsame Teiler. Die zweite Zeile von $Q$ gibt uns die Polynomfaktoren, mit denen $a$ und $b$ gleich werden: \begin{align*} q_{21}a+q_{22}b &= -\frac14(X^2+2X-3) (X^4-2X^3-7X^2+8X+12) +\frac14(X^2-X-6) (X^4+X^3-7X^2-X+6) \\ &=0. \qedhere \end{align*} Man kann natürlich den grössten gemeinsamen Teiler auch mit Hilfe einer Faktorisierung der Polynome $a$ und $b$ finden: \begin{align*} &\text{Faktorisierung von $a$:}& a &= (X-3) (X-2)\phantom{(X-1)}(X+1) (X+2) \phantom{(X+3)}\\ &\text{Faktorisierung von $b$:}& b &=\phantom{(X-3)}(X-2) (X-1) (X+1)\phantom{(X+2)} (X+3) \\ &\text{gemeinsame Faktoren:}& g &=\phantom{(X-3)}(X-2)\phantom{(X-1)}(X+1)\phantom{(X+2)}\phantom{(X+3)} = X^2 -X + 2\\ && v=a/g&= (X-3)\phantom{(X-2)(X-1)(X+1)} (X+2) \phantom{(X+3)} = X^2-X-6 \\ && u=b/g&=\phantom{(X-3)(X-2)} (X-1)\phantom{(X+1)(X+2)}(X+3) = X^2+2X-3 \end{align*} Aus den letzten zwei Zeilen folgt $ua-vb = ab/g - ab/g = 0$, wie erwartet. \end{beispiel} % % Das kleinste gemeinsame Vielfache % \subsection{Das kleinste gemeinsame Vielfache \label{buch:subsection:daskgv}} Das kleinste gemeinsame Vielfache zweier Zahlen $a$ und $b$ ist \[ \operatorname{kgV}(a,b) = \frac{ab}{\operatorname{ggT}(a,b)}. \] Wir suchen nach einen Algorithmus, mit dem man das kleinste gemeinsame Vielfache effizient berechnen kann. Die Zahlen $a$ und $b$ sind beide Vielfache des grössten gemeinsamen Teilers $g=\operatorname{ggT}(a,b)$, es gibt also Zahlen $u$ und $v$ derart, dass $a=ug$ und $b=vg$. Wenn $t$ ein gemeinsamer Teiler von $u$ und $v$ ist, dann ist $tg$ ein grösserer gemeinsamer Teiler von $a$ und $b$. Dies kann nicht sein, also müssen $u$ und $v$ teilerfremd sein. Das kleinste gemeinsame Vielfache von $a$ und $b$ ist dann $ugv=av=ub$. Die Bestimmung des kleinsten gemeinsamen Vielfachen ist also gleichbedeutend mit der Bestimmung der Zahlen $u$ und $v$. Die definierende Eigenschaften von $u$ und $v$ kann man in Matrixform als \begin{equation} \begin{pmatrix} a\\b \end{pmatrix} = \underbrace{ \begin{pmatrix} u&?\\ v&? \end{pmatrix}}_{\displaystyle =K} \begin{pmatrix} \operatorname{ggT}(a,b)\\ 0 \end{pmatrix} \label{buch:eindlichekoerper:eqn:uvmatrix} \end{equation} geschrieben werden, wobei wir die Matrixelemente $?$ nicht kennen. Diese Elemente müssen wir auch nicht kennen, um $u$ und $v$ zu bestimmen. Bei der Bestimmung des grössten gemeinsamen Teilers wurde der Vektor auf der rechten Seite von~\eqref{buch:eindlichekoerper:eqn:uvmatrix} bereits gefunden. Die Matrizen $Q(q_i)$, die die einzelne Schritte des euklidischen Algorithmus beschreiben, ergeben ihn als \[ \begin{pmatrix} \operatorname{ggT}(a,b)\\0 \end{pmatrix} = Q(q_n)Q(q_{n-1}) \dots Q(q_1)Q(q_0) \begin{pmatrix}a\\b\end{pmatrix}. \] Indem wir die Matrizen $Q(q_n)$ bis $Q(q_0)$ auf die linke Seite der Gleichung schaffen, erhalten wir \[ \begin{pmatrix}a\\b\end{pmatrix} = Q(q_0)^{-1} Q(q_1)^{-1} \dots Q(q_{n-1})^{-1} Q(q_n) \begin{pmatrix}\operatorname{ggT}(a,b)\\0\end{pmatrix}. \] Eine mögliche Lösung für die Matrix $K$ in \eqref{buch:eindlichekoerper:eqn:uvmatrix} ist der die Matrix \[ K = Q(q_0)^{-1} Q(q_1)^{-1} \dots Q(q_{n-1})^{-1} Q(q_n). \] Insbesondere ist die Matrix $K$ die Inverse der früher gefundenen Matrix $Q$. Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht sehr effizient. Genauso wie es möglich war, das Produkt $Q$ der Matrizen $Q(q_k)$ iterativ zu bestimmen, muss es auch eine Rekursionsformel für das Produkt der inversen Matrizen $Q(q_k)^{-1}$ geben. Schreiben wir die gesuchte Matrix \[ K_k = Q(q_0)^{-1}\dots Q(q_{k-1})^{-1} = \begin{pmatrix} e_k & e_{k-1}\\ f_k & f_{k-1} \end{pmatrix}, \] dann kann man $K_k$ durch die Rekursion \begin{equation} K_{k+1} = K_{k} Q(q_k)^{-1} = K_k K(q_k) \qquad\text{mit}\qquad K_0 = \begin{pmatrix}1&0\\0&1\end{pmatrix} = I \label{buch:endlichekoerper:eqn:kgvrekursion} \end{equation} berechnen. Die Inverse von $Q(q)$ ist \[ K(q) = Q(q)^{-1} = \frac{1}{\det Q(q)} \begin{pmatrix} q&1\\ 1&0 \end{pmatrix} \quad\text{denn}\quad K(q)Q(q) = \begin{pmatrix} q&1\\ 1&0 \end{pmatrix} \begin{pmatrix} 0&1\\ 1&-q \end{pmatrix} = \begin{pmatrix} 1&0\\ 0&1 \end{pmatrix}. \] Da die zweite Spalte von $K(q)$ die erste Spalte einer Einheitsmatrix ist, wird die zweite Spalte des Produktes $AK(q)$ immer die erste Spalte von $A$ sein. In $K_{k+1}$ ist daher nur die erste Spalte neu, die zweite Spalte ist die erste Spalte von $K_k$. Aus der Rekursionsformel \eqref{buch:endlichekoerper:eqn:kgvrekursion} für die Matrizen $K_k$ kann man jetzt eine Rekursionsbeziehung für die Folgen $e_k$ und $f_k$ ablesen, es gilt \begin{align*} e_{k+1} &= q_ke_k + e_{k-1} \\ f_{k+1} &= q_kf_k + f_{k-1} \end{align*} für $k=0,1,\dots ,n$. Damit können $e_k$ und $f_k$ gleichzeitig mit den Zahlen $c_k$ und $d_k$ in einer Tabelle berechnen. \begin{beispiel} Wir erweitern das Beispiel von Seite~\pageref{buch:endlichekoerper:beispiel1erweitert} um die beiden Spalten zur Berechnung von $e_k$ und $f_k$: \begin{center} \renewcommand{\arraystretch}{1.1} \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} \hline k& a_k& b_k& q_k& r_k& c_k& d_k& e_k& f_k\\ \hline & & & & & 1& 0& 0& 1\\ 0& 76415& 23205& 3& 6800& 0& 1& 1& 0\\ 1& 23205& 6800& 3& 2805& 1& -3& 3& 1\\ 2& 6800& 2805& 2& 1190& -3& 10& 10& 3\\ 3& 2805& 1190& 2& 425& 7& -23& 23& 7\\ 4& 1190& 425& 2& 340& -17& 56& 56& 17\\ 5& 425& 340& 1& 85& 41& -135& 135& 41\\ 6& 340& 85& 4& 0& -58& 191& 191& 58\\ 7& 85& 0& & & 273& -899& 899& 273\\ \hline \end{tabular} \end{center} Der grösste gemeinsame Teiler ist $\operatorname{ggT}(a,b)=85$. Aus der letzten Zeile der Tabelle kann man jetzt die Zahlen $u=e_7=899$ und $v=f_7=273$ ablesen, und tatsächlich ist \[ a=76415 = 899\cdot 85 \qquad\text{und}\qquad b=23205 = 273 \cdot 85. \] Daraus kann man dann auch das kleinste gemeinsame Vielfache ablesen, es ist \[ \operatorname{kgV}(a,b) = \operatorname{kgV}(76415,23205) = \left\{ \begin{aligned} ub &= 899\cdot 23205\\ va &= 273\cdot 76415 \end{aligned} \right\} = 20861295. \qedhere \] \end{beispiel} Der erweiterte Algorithmus kann auch dazu verwendet werden, das kleinste gemeinsame Vielfache zweier Polynome zu berechnen. Dies wird zum Beispiel bei der Decodierung des Reed-Solomon-Codes in Kapitel~\ref{chapter:reedsolomon} verwendet. \subsubsection{Polynome \label{buch:endlichekoerper:eqn:polynomkgv}} Im Beispiel auf Seite~\pageref{buch:endlichekoerper:eqn:polynomggt} wird der grösste gemeinsame Teiler der Polynome \[ a = X^4 - 2X^3 -7 X^2 + 8X + 12, \qquad b = X^4 + X^3 -7X^2 -X + 6 \] berechnet. Dies kann jetzt erweitert werden für die Berechnung des kleinsten gemeinsamen Vielfachen. \begin{beispiel} Die Berechnungstabelle nur für die Spalten $e_k$ und $f_k$ ergibt \begin{center} \renewcommand{\arraystretch}{1.4} \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} \hline k& q_k& e_k& f_k\\ \hline & & 0& 1\\ 0& 1& 1& 0\\ 1&-\frac13X-\frac13& 1& 1\\ 2& \frac34X+\frac34& -\frac13X+\frac23& -\frac13X-\frac13\\ & &-\frac14X^2+\frac14X+\frac32&-\frac14X^2-\frac12X+\frac34\\ \hline \end{tabular} \end{center} Daraus kann man ablesen, dass \[ u = -\frac14X^2+\frac14X+\frac32 \qquad\text{und}\qquad v = -\frac14X^2-\frac12X+\frac34. \] Daraus ergibt sich das kleinste gemeinsame Vielfache auf zwei verschiedene Weisen: \[ \operatorname{ggT}(a,b) = \left\{ \begin{aligned} \textstyle (-\frac14X^2+\frac14X+\frac32)&\cdot(X^4 - 2X^3 -7 X^2 + 8X + 12) \\ \textstyle (-\frac14X^2-\frac12X+\frac34)&\cdot(X^4 + X^3 -7X^2 -X + 6) \end{aligned} \right\} = -\frac14X^6+\frac72X^4-\frac{49}4X^2+9. \] Die beiden Berechnungsmöglichkeiten stimmen wie erwartet überein. \end{beispiel} \subsubsection{Anwendung: Decodierung des Reed-Solomon-Codes} Der Reed-Solomon-Code verwendet Polynome zur Codierung der Daten, dies wird in Kapitel~\ref{chapter:reedsolomon} im Detail beschrieben. Bei der Decodierung muss der Faktor $u$ für zwei gegebene Polynome $n(X)$ und $r(X)$ bestimmt werden. Allerdings ist das Polynom $r(X)$ nicht vollständig bekannt, nur die ersten paar Koeffizienten sind gegeben. Dafür weiss man zusätzlich, wieviele Schritte genau der Euklidische Algorithmus braucht. Daraus lässt sich genügend Information gewinnen, um die Faktoren $u$ und $v$ zu bestimmen. Das Video \url{https://youtu.be/uOLW43OIZJ0} von Edmund Weitz erklärt die Theorie hinter dieser Teilaufgabe anhand von Beispielen. \begin{beispiel} Wir berechnen also die Faktoren $u$ und $v$ für die beiden Polynome \begin{align*} n(X) &= X^12+12 \\ r(X) &= 7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + w(X) \end{align*} in $\mathbb{F}_13[X]$, wobei $w(X)$ ein unbekanntes Polynom vom Grad $5$ ist. Man weiss zusätzlich noch, dass der euklidische Algorithmus genau drei Schritte braucht, es gibt also genau drei Quotienten, die in die Berechnung der Zahlen $e_k$ und $f_k$ einfliessen. Im ersten Schritt des euklidischen Algorithmus ist der Quotient $n(X) / r(X)$ zu bestimmen, der Grad $1$ haben muss. \begin{align*} a_0=n(X) &= X^12+12 \\ b_0=r(X) &= 7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + \dots \\ q_0 &= 2X+10 \\ r_0 = a_0-b_0\cdot q_0 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots \\ a_1 &= 7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + \dots \\ b_1 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots \\ q_1 &= 2X+2 \\ r_1 = a_1 - b_1q_1 &= 5X^9 + 10 X^8 + \dots \\ a_2 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots \\ b_2 &= 5X^9 + 10 X^8 + \dots \\ q_2 &= 2X+10 \end{align*} Aus den Polynomen $q_k$ können jetzt die Faktoren $u$ und $v$ bestimmt werden: \begin{center} \begin{tabular}{|>{$}c<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} \hline k& q_k& e_k& f_k\\ \hline & & 0& 1\\ 0& 2X+10& 1& 0\\ 1& 2X+2 & 2X+10& 1\\ 2& 2X+10& 4X^2+11X+8& 2X+2\\ & & 8X^3+10X^2+11X+12& 4X^2+11X+8\\ \hline \end{tabular} \end{center} Die Faktorisierung des Polynoms \[ u = 8X^3+10X^2+11X+12 \] kann bestimmt werden, indem man alle Zahlen $1,2,\dots,12\in\mathbb{F}_{13}$ einsetzt. Man findet so die Nullstellen $3$, $4$ und $8$, also muss das Polynom $u$ faktorisiert werden können als \[ u= 8(X-3)(X-4)(X-8) = 8X^3 - 120X^2+544X-768 = 8X^3 +10X^2+11X+12. \qedhere \] \end{beispiel}