From 3cc801ff90729bc7c168cf74df2763e52f3fdc43 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= 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') 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