From e89e7949b93d684c387db5062b2743c0207205ca Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 18:40:42 +0100 Subject: two new problems --- .../30-endlichekoerper/uebungsaufgaben/3003.tex | 72 +++++++ .../30-endlichekoerper/uebungsaufgaben/3004.tex | 231 +++++++++++++++++++++ .../uebungsaufgaben/3004/matrix.m | 21 ++ 3 files changed, 324 insertions(+) create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') 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) -- cgit v1.2.1