Merge pull request #1 from AndreasFMueller/master

update

6 files changed, 644 insertions, 0 deletions

diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex
new file mode 100644
index 0000000..4f4d56d
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex
@@ -0,0 +1,102 @@
+Im Rahmen der Aufgabe, die Zehntausenderstelle der Zahl $5^{5^{5^{5^5}}}$
+zu berechnen muss Michael Penn im Video 
+\url{https://youtu.be/Xg24FinMiws} bei 12:52 zwei Zahlen $x$ und $y$ finden,
+so dass,
+\[
+5^5x
++
+2^5y
+=
+1
+\]
+ist.
+Verwenden Sie die Matrixform des euklidischen Algorithmus.
+
+\begin{loesung}
+Zunächst berechnen wir die beiden Potenzen
+\[
+5^5 = 3125
+\qquad\text{und}\qquad
+2^5 = 32.
+\]
+Damit können wir jetzt den Algorithmus durchführen.
+Die Quotienten und Reste sind
+\begin{align*}
+a_0&=q_0\cdot b_0 + r_0&
+3125 &= 97 \cdot 32 + 21& q_0&=97 & r_0&= 21\\
+a_1&=q_1\cdot b_1 + r_1&
+32 &= 1\cdot 21 + 10    & q_1&= 1 & r_1&= 11\\
+a_2&=q_2\cdot b_2 + r_2&
+21 &= 1\cdot 11 + 10    & q_2&= 1 & r_2&= 10\\
+a_3&=q_3\cdot b_3 + r_3&
+11 &= 1\cdot 10 +  1    & q_3&= 1 & r_3&=  1\\
+a_4&=q_4\cdot b_4 + r_4&
+10 &= 10\cdot 1 +  0    & q_4&=10 & r_4&=  0
+\end{align*}
+Daraus kann man jetzt auch die Matrizen $Q(q_k)$ bestimmen und
+ausmultiplizieren:
+\begin{align*}
+Q
+&=
+\begin{pmatrix}
+0&1\\1&-10
+\end{pmatrix}
+\underbrace{
+\begin{pmatrix}
+0&1\\1&-1
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\1&-1
+\end{pmatrix}
+}_{}
+\underbrace{
+\begin{pmatrix}
+0&1\\1&-1
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\1&-97
+\end{pmatrix}
+}_{}
+\\
+&=
+\begin{pmatrix}
+0&1\\1&-10
+\end{pmatrix}
+\underbrace{
+\begin{pmatrix}
+0&-1\\-1&2
+\end{pmatrix}
+\begin{pmatrix}
+1&-97\\-1&98
+\end{pmatrix}
+}_{}
+\\
+&=
+\underbrace{
+\begin{pmatrix}
+0&1\\1&-10
+\end{pmatrix}
+\begin{pmatrix}
+2&-195\\-3&293
+\end{pmatrix}
+}_{}
+\\
+&=
+\begin{pmatrix}
+-3&293\\32&-3125
+\end{pmatrix}.
+\end{align*}
+Daras kann man jetzt ablesen, dass
+\[
+-3\cdot 3125
++ 
+293\cdot 32
+=
+-9375
++
+9376
+=
+1.
+\]
+Die gesuchten Zahlen sind also $x=-3$ und $y=293$.
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex
new file mode 100644
index 0000000..63200a7
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex
@@ -0,0 +1,9 @@
+Berechnen Sie $666^{666}$ in $\mathbb{F}_{13}$.
+
+\begin{loesung}
+Zunächst ist die Basis der Potenz $666=3$ in $\mathbb{F}_{13}$, es
+muss also nur $3^{666}$ berechnet werden.
+Nach dem kleinen Satz von Fermat ist $3^{12}=1$ in $\mathbb{F}_{13}$.
+Wegen $666 = 12\cdot 50+6$ folgt
+$ 3^{666} = 3^6=729=1$ in $\mathbb{F}_{13}$.
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex
new file mode 100644
index 0000000..8a83256
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex
@@ -0,0 +1,72 @@
+Die Zahl $p=47$ ist eine Primzahl, der Ring
+$\mathbb{Z}/p\mathbb{Z}=\mathbb{F}_{47}$ ist daher ein Körper.
+Jeder von Null verschiedene Rest $b\in\mathbb{F}_p^*$ hat daher eine
+multiplikative Inverse.
+Berechnen Sie die multiplikative Inverse von $b=11\in\mathbb{F}_{47}$.
+
+\begin{loesung}
+Der euklidische Algorithmus muss auf die Zahlen $p=47$ und $b=11$ angewendet
+werden, es ergeben sich die Quotienten und Reste der folgenden Tabelle:
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k&a_k&b_k&q_k&r_k\\
+\hline
+0& 47& 11& 4& 3\\
+1& 11&  3& 3& 2\\
+2&  3&  2& 1& 1\\
+3&  2&  1& 2& 0\\
+\hline
+\end{tabular}
+\end{center}
+Wie erwartet ist der grösste gemeinsame Teiler
+$\operatorname{ggT}(47,11)=r_2=1$.
+Um die Zahlen $s,t$ zu finden, für die $sp+tb=1$ gilt, können wir die
+Matrixform verwenden, wir berechnen dazu
+\begin{align*}
+Q
+=
+Q(2)Q(1)Q(3)Q(4)
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-1 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-3 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-4 \end{pmatrix}
+\\
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-1 \end{pmatrix}
+\begin{pmatrix} 1&-4\\-3&13\end{pmatrix}
+\\
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} -3&13\\4&-17 \end{pmatrix}
+\\
+&=
+\begin{pmatrix} 4&-17\\ -11&47 \end{pmatrix}.
+\end{align*}
+Daraus kann man ablesen, dass $s=4$ und $t=-17$, tatsächlich ist
+$4\cdot 47-47\cdot 11=188-187=1$.
+Wir schliessen daraus, dass $-17=30\in\mathbb{F}_{47}$ die multiplikative
+Inverse von $b=11$ ist.
+Die Rechnung $11\cdot 30 = 330 = 7\cdot 47 + 1$ zeigt, dass dies
+der Fall ist.
+
+Alternativ zur Matrixdarstellung kann man die Koeffizienten $s$ und $t$
+auch mit Hilfe der erweiterten Tabelle finden:
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k&a_k&b_k&q_k&r_k&c_k&d_k\\
+\hline
+ &   &   &   &   &  1&  0\\
+0& 47& 11&  4&  3&  0&  1\\
+1& 11&  3&  3&  2&  1& -4\\
+2&  3&  2&  1&  1& -3& 13\\
+3&  2&  1&  2&  0&  {\color{red}4}&{\color{red}-17}\\
+4&  1&  0&   &   &-11& 47\\
+\hline
+\end{tabular}
+\end{center}
+Die gesuchten Zahlen $s$ und $t$ sind rot hervorgehoben.
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex
new file mode 100644
index 0000000..046ac94
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex
@@ -0,0 +1,234 @@
+Der Körper $\mathbb{F}_2$ ist besonders einfach, da er nur zwei Elemente
+$0$ und $1$ enthält.
+\begin{teilaufgaben}
+\item
+Bestimmen Sie die Additions- und Multiplikationstabelle für $\mathbb{F}_2$.
+\item
+Lösen Sie das lineare Gleichungssystem
+\[
+\begin{linsys}{4}
+x_1&+& x_2& &   & &   &=& 0\\
+   & & x_2&+&x_3&+&x_4&=& 1\\
+x_1&+& x_2&+&x_3&+&x_4&=& 1\\
+   & & x_2&+&x_3& &   &=& 0\\
+\end{linsys}
+\]
+über dem Körper $\mathbb{F}_2$ mit dem Gauss-Algorithmus.
+\item Bestimmen Sie die Inverse $A^{-1}\in \operatorname{GL}_2(\mathbb{F}_2)$
+der Koeffizientenmatrix $A$ des Gleichungssystems.
+\item Kontrollieren Sie das Resultat durch Ausmultiplizieren des Produktes
+$AA^{-1}$.
+\end{teilaufgaben}
+
+\begin{loesung}
+\begin{teilaufgaben}
+\item
+Die Additions- und Multiplikationstabellen sind
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\def\ds{0.5}
+\def\punkt#1#2{({(#1)*\ds},{(-#2)*\ds})}
+\def\tabelle{
+	\foreach \x in {-0.5,0.5,2.5}{
+		\draw \punkt{\x}{-0.5} -- \punkt{\x}{2.5};
+	}
+	\foreach \y in {-0.5,0.5,2.5}{
+		\draw \punkt{-0.5}{\y} -- \punkt{2.5}{\y};
+	}
+	\node at \punkt{1}{0} {$0$};
+	\node at \punkt{2}{0} {$1$};
+	\node at \punkt{0}{1} {$0$};
+	\node at \punkt{0}{2} {$0$};
+}
+\begin{scope}[xshift=-2cm]
+	\tabelle
+	\node at (0,0) {$+$};
+	\node at \punkt{1}{1} {$0$};
+	\node at \punkt{2}{1} {$1$};
+	\node at \punkt{1}{2} {$1$};
+	\node at \punkt{2}{2} {$0$};
+\end{scope}
+\begin{scope}[xshift=2cm]
+	\tabelle
+	\node at (0,0) {$\cdot$};
+	\node at \punkt{1}{1} {$0$};
+	\node at \punkt{2}{1} {$0$};
+	\node at \punkt{1}{2} {$0$};
+	\node at \punkt{2}{2} {$1$};
+\end{scope}
+\end{tikzpicture}
+\end{center}
+Betrachtet als Bitoperationen entspricht die Addition dem XOR, die
+Multiplikation dem AND.
+\item
+Die Gauss-Tableaux sind
+\begin{align*}
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1\\
+   0 & 1 & 1 & 1 &  0\\
+   1 & 1 & 1 & 1 &  0\\
+   0 & 1 & 1 & 0 &  1\\
+\hline
+\end{tabular}
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1\\
+   0 & 1 & 1 & 1 &  0\\
+   0 & 0 & 1 & 1 &  1\\
+   0 & 1 & 1 & 0 &  1\\
+\hline
+\end{tabular}
+%\\
+%&
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1\\
+   0 & 1 & 1 & 1 &  0\\
+   0 & 0 & 1 & 1 &  1\\
+   0 & 0 & 0 & 1 &  1\\
+\hline
+\end{tabular}
+\\
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1\\
+   0 & 1 & 1 & 0 &  1\\
+   0 & 0 & 1 & 0 &  0\\
+   0 & 0 & 0 & 1 &  1\\
+\hline
+\end{tabular}
+%\\
+&
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1\\
+   0 & 1 & 0 & 0 &  1\\
+   0 & 0 & 1 & 0 &  0\\
+   0 & 0 & 0 & 1 &  1\\
+\hline
+\end{tabular}
+%\\
+%&
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+   1 & 0 & 0 & 0 &  0\\
+   0 & 1 & 0 & 0 &  1\\
+   0 & 0 & 1 & 0 &  0\\
+   0 & 0 & 0 & 1 &  1\\
+\hline
+\end{tabular}
+\end{align*}
+In der ersten Zeile stehen die Schritt der Vorwärtsreduktion, in der
+zweiten die Schritte des Rückwärtseinsetzens.
+Als Lösung liest man ab
+\[
+x=\begin{pmatrix}0\\1\\0\\1 \end{pmatrix},
+\]
+die Korrektheit kann man leicht durch Einsetzen überprüfen.
+\item
+Wir wenden erneut den Gauss-Algorithmus an:
+\begin{align*}
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1 & 0 & 0 & 0 \\
+   0 & 1 & 1 & 1 &  0 & 1 & 0 & 0 \\
+   1 & 1 & 1 & 1 &  0 & 0 & 1 & 0 \\
+   0 & 1 & 1 & 0 &  0 & 0 & 0 & 1 \\
+\hline
+\end{tabular}
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1 & 0 & 0 & 0 \\
+   0 & 1 & 1 & 1 &  0 & 1 & 0 & 0 \\
+   0 & 0 & 1 & 1 &  1 & 0 & 1 & 0 \\
+   0 & 1 & 1 & 0 &  0 & 0 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1 & 0 & 0 & 0 \\
+   0 & 1 & 1 & 1 &  0 & 1 & 0 & 0 \\
+   0 & 0 & 1 & 1 &  1 & 0 & 1 & 0 \\
+   0 & 0 & 0 & 1 &  0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1 & 0 & 0 & 0 \\
+   0 & 1 & 1 & 0 &  0 & 0 & 0 & 1 \\
+   0 & 0 & 1 & 0 &  1 & 1 & 1 & 1 \\
+   0 & 0 & 0 & 1 &  0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+   1 & 1 & 0 & 0 &  1 & 0 & 0 & 0 \\
+   0 & 1 & 0 & 0 &  1 & 1 & 1 & 0 \\
+   0 & 0 & 1 & 0 &  1 & 1 & 1 & 1 \\
+   0 & 0 & 0 & 1 &  0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+   1 & 0 & 0 & 0 &  0 & 1 & 1 & 0 \\
+   0 & 1 & 0 & 0 &  1 & 1 & 1 & 0 \\
+   0 & 0 & 1 & 0 &  1 & 1 & 1 & 1 \\
+   0 & 0 & 0 & 1 &  0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\end{align*}
+Daraus liest man die Inverse $A^{-1}$ der Koeffizientenmatrix $A$ ab als
+\[
+A^{-1}
+=
+\begin{pmatrix}
+   0 & 1 & 1 & 0 \\
+   1 & 1 & 1 & 0 \\
+   1 & 1 & 1 & 1 \\
+   0 & 1 & 0 & 1 
+\end{pmatrix}
+\]
+\item Wir prüfen das Resultat durch Ausmultiplizieren:
+\[
+AA^{-1}
+=
+\begin{pmatrix}
+   1 & 1 & 0 & 0 \\
+   0 & 1 & 1 & 1 \\
+   1 & 1 & 1 & 1 \\
+   0 & 1 & 1 & 0 
+\end{pmatrix}
+\begin{pmatrix}
+   0 & 1 & 1 & 0 \\
+   1 & 1 & 1 & 0 \\
+   1 & 1 & 1 & 1 \\
+   0 & 1 & 0 & 1 
+\end{pmatrix}
+=
+\begin{pmatrix}
+   1 & 0 & 0 & 0 \\
+   0 & 1 & 0 & 0 \\
+   0 & 0 & 1 & 0 \\
+   0 & 0 & 0 & 1 
+\end{pmatrix}
+\]
+Dabei kann man verwenden, dass der Eintrag in Zeile $i$ und Spalte $k$ des
+Produktes die Anzahl der Positionen ist, wo in der Zeile $i$ von $A$
+und in der Spalte $j$ von $A^{-1}$ eine $1$ steht.
+\end{teilaufgaben}
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m
new file mode 100644
index 0000000..42e9d9f
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m
@@ -0,0 +1,22 @@
+#
+# matrix.m
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+
+n = 4
+N = 20;
+p = 2;
+
+d = 0;
+while d == 0
+	A = round(N * rand(n,n));
+	B = mod(A, p);
+	d = det(B);
+	d = mod(d, p);
+	d = d * B(1,1);
+end
+A
+det(A)
+B
+det(B)
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex
new file mode 100644
index 0000000..28f4d2c
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex
@@ -0,0 +1,205 @@
+Das Polynom $m(X)=X^2+X+1$ ist als Polynom in $\mathbb{F}_3[X]$ irreduzibel.
+Dies bedeutet, dass der Ring der Polynome $\mathbb{F}_3[X] / (m(X))$ 
+ein Körper ist, man bezeichnet ihn auch mit $\mathbb{F}_3(\alpha)$,
+wobei man sich $\alpha$ als eine Nullstelle von $m(X)$
+oder als die Matrix
+\[
+\alpha = \begin{pmatrix} 0&2\\1&2\end{pmatrix}
+\]
+vorstellen kann.
+\begin{teilaufgaben}
+\item 
+Stellen Sie die Additions- und Multiplikationstabellen für das Rechnen
+in $\mathbb{F}_3$ auf.
+\item
+Berechnen Sie $\alpha^{-1}$ in $\mathbb{F}_3(\alpha)$ aus der
+Bedingung $m(\alpha)=0$.
+\item
+Verwenden Sie den euklidischen Algorithmus, um $(1+\alpha)^{-1}$
+in $\mathbb{F}_3(\alpha)$ zu bestimmen.
+\item
+Berechnen Sie $\alpha^3$.
+\end{teilaufgaben}
+
+\begin{loesung}
+\begin{teilaufgaben}
+\item
+Die Additions- und Multiplikationstabelle von $\mathbb{F}_3$ ist
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\def\ds{0.5}
+\def\punkt#1#2{({(#1)*\ds},{-(#2)*\ds})}
+\def\tabelle{
+\foreach \x in {-0.5,0.5,3.5}{
+	\draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5};
+	\draw \punkt{-0.5}{\x} -- \punkt{3.5}{\x};
+}
+\node at \punkt{0}{1} {$0$};
+\node at \punkt{0}{2} {$1$};
+\node at \punkt{0}{3} {$2$};
+\node at \punkt{1}{0} {$0$};
+\node at \punkt{2}{0} {$1$};
+\node at \punkt{3}{0} {$2$};
+}
+\begin{scope}[xshift=-2cm]
+\tabelle
+\node at \punkt{0}{0} {$+$};
+\node at \punkt{1}{1} {$0$};
+\node at \punkt{1}{2} {$1$};
+\node at \punkt{1}{3} {$2$};
+\node at \punkt{2}{1} {$1$};
+\node at \punkt{2}{2} {$2$};
+\node at \punkt{2}{3} {$0$};
+\node at \punkt{3}{1} {$2$};
+\node at \punkt{3}{2} {$0$};
+\node at \punkt{3}{3} {$1$};
+\end{scope}
+\begin{scope}[xshift=2cm]
+\tabelle
+\node at \punkt{0}{0} {$\cdot$};
+\node at \punkt{1}{1} {$0$};
+\node at \punkt{1}{2} {$0$};
+\node at \punkt{1}{3} {$0$};
+\node at \punkt{2}{1} {$0$};
+\node at \punkt{2}{2} {$1$};
+\node at \punkt{2}{3} {$2$};
+\node at \punkt{3}{1} {$0$};
+\node at \punkt{3}{2} {$2$};
+\node at \punkt{3}{3} {$1$};
+\end{scope}
+\end{tikzpicture}
+\end{center}
+\item
+Wegen $m(\alpha)=\alpha^2+\alpha+1=0$ folgt $\alpha+1+\alpha^{-1}=0$
+oder $\alpha^{-1} = -\alpha - 1 = 2+2\alpha$.
+Als Matrix kann man
+\[
+\alpha^{-1}
+=
+2\alpha + 2
+=
+\begin{pmatrix}
+0&4\\
+2&4
+\end{pmatrix}
++
+\begin{pmatrix}
+2&0\\0&2
+\end{pmatrix}
+=
+\begin{pmatrix}
+2&4\\2&2
+\end{pmatrix}
+\equiv
+\begin{pmatrix}2&1\\2&0\end{pmatrix}
+\mod 3
+\]
+schreiben und durch Nachrechnen verifizieren dass, tatsächlich gilt
+\[
+\alpha\alpha^{-1}
+=
+\begin{pmatrix}
+0&2\\
+1&2
+\end{pmatrix}
+\begin{pmatrix}
+2&1\\
+2&0
+\end{pmatrix}
+=
+\begin{pmatrix}
+4&0\\
+6&1
+\end{pmatrix}
+\equiv
+\begin{pmatrix}
+1&0\\
+0&1
+\end{pmatrix}
+\mod 3.
+\]
+\item
+Für den euklidischen Algorithmus müssen wir wiederholt eine Polynomdivision
+in $\mathbb{F}_3[X]$ durchführen.
+Im ersten Schritt ist es
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcr}
+ \llap{$($}X^2&+&X&+&1\rlap{$)$}&\;:&(X&+&1)&=&X = q_1\\
+\llap{$-($}X^2&+&X\rlap{$)$}& &  & &  & &  & & \\ \cline{1-3}
+     & &0&+&1 &\rlap{$\mathstrut = r_1$}\phantom{)}& &  & &  & \\
+\end{array}
+\]
+Die nächste Division ist $(X+1) : 1$, die als Quotient $q_2=X+1$ und den
+Rest $r_2=0$ hat.
+Mit der Matrixform des euklidischen Algorithmus kann man jetzt auch die
+Koeffizienten $s$ und $t$ bestimmen, die beide Polynome in $\mathbb{F}_3[X]$
+sind:
+\begin{align*}
+Q
+&=
+Q(q_2)
+Q(q_1)
+=
+\begin{pmatrix}
+0&1\\1&-q_2
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\1&-q_1
+\end{pmatrix}
+=
+\begin{pmatrix}
+0&1\\1&2X+2
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\{\color{red}1}&{\color{red}2X}
+\end{pmatrix}
+=
+\begin{pmatrix}
+{\color{red}1}&{\color{red}2X}\\
+2X&X^2+X+1
+\end{pmatrix}.
+\end{align*}
+Die gesuchten Polynome sind $s=1$ und $t=2X$ und man kann nachrechnen,
+dass
+\begin{align*}
+s\cdot m(X) + t\cdot (X+1)
+&=
+X^2+X+1 + 2X\cdot (X+1)
+=
+X^2+X+1 + 2X^2 + 2X
+\\
+&= 3X^2+3X+1\equiv 1 \mod 3.
+\end{align*}
+Natürlich kann man $s$ und $t$ auch mit der erweiterten Tabelle
+finden:
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|}
+\hline
+k&    a_k&b_k& q_k&r_k& c_k&     d_k\\
+\hline
+ &       &   &    &   &   1&       0\\
+0&X^2+X+1&X+1& X  &  1&   0&       1\\
+1&    X+1&  1& X+1&  0&{\color{red}   1}&{\color{red}      2X}\\
+2&      1&  0&    &  0&2X+2& 2X^2+2X\\
+\hline
+\end{tabular}
+\end{center}
+In allen Fällen ist also $(1+X)^{-1} = 2X$.
+\item
+Wegen $m(\alpha)=0$ ist $\alpha^2=-\alpha-1=2\alpha+2$ und damit
+\begin{align*}
+\alpha^3
+&=
+\alpha\cdot \alpha^2 = \alpha (2\alpha +2) = 
+2\alpha^2 + 2\alpha
+=
+2(\underbrace{\alpha^2 + \alpha + 1}_{\displaystyle=0} + 2)
+=
+2\cdot 2
+=
+1.
+\qedhere
+\end{align*}
+\end{teilaufgaben}
+\end{loesung}