aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/30-endlichekoerper/uebungsaufgaben
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-03-07 18:40:42 +0100
committerAndreas Müller <andreas.mueller@ost.ch>2021-03-07 18:40:42 +0100
commite89e7949b93d684c387db5062b2743c0207205ca (patch)
treee1902081db7f86cb0b95c69baffe9ce48781ccaa /buch/chapters/30-endlichekoerper/uebungsaufgaben
parentadd all the papers (diff)
downloadSeminarMatrizen-e89e7949b93d684c387db5062b2743c0207205ca.tar.gz
SeminarMatrizen-e89e7949b93d684c387db5062b2743c0207205ca.zip
two new problems
Diffstat (limited to '')
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex72
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex231
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m21
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)