two new problems

3 files changed, 324 insertions, 0 deletions

diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex
new file mode 100644
index 0000000..83ba7f2
--- /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}=\mathcal{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\mathcal{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..66ac560
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex
@@ -0,0 +1,231 @@
+Der Körper $\mathbb{F}_2$ ist besonders einfach, da er nur zwei Elemente
+$0$ und $1$ enthält.
+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=-3cm]
+	\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=3cm]
+	\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 UND.
+\begin{teilaufgaben}
+\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 $\mathcal{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 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..ed85185
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m
@@ -0,0 +1,21 @@
+#
+# matrix.m
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+
+n = 4
+N = 20;
+
+d = 0;
+while d == 0
+	A = round(N * rand(n,n));
+	B = mod(A, 2);
+	d = det(B);
+	d = mod(d, 2);
+	d = d * B(1,1);
+end
+A
+det(A)
+B
+det(B)