From 3cc801ff90729bc7c168cf74df2763e52f3fdc43 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Sat, 9 Jan 2021 17:07:25 +0100
Subject: add problem to chapter 3

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

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

diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex
new file mode 100644
index 0000000..7e40dfe
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex
@@ -0,0 +1,102 @@
+Im Rahmen der Aufgabe, die Zehntausernderstelle 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}
-- 
cgit v1.2.1

