From e89e7949b93d684c387db5062b2743c0207205ca Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Sun, 7 Mar 2021 18:40:42 +0100
Subject: two new problems

---
 .../30-endlichekoerper/uebungsaufgaben/3003.tex    | 72 ++++++++++++++++++++++
 1 file changed, 72 insertions(+)
 create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex

(limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex')

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}
-- 
cgit v1.2.1