Berechnung in anderen Zahlenräumen (modulo)

22.01.2008, 11:43	slacker2d	Auf diesen Beitrag antworten »
Berechnung in anderen Zahlenräumen (modulo) Ich habe eine Aufgabe mit der ich kaum was anfangen kann, ausser, dass ich weiß das ich sie modulo 107 rechnen muss... Aber ich weiß nicht wie ich vereinfachen kann. Berechnen Sie in $\begin{eqnarray} \mathbb Z_{107} \end{eqnarray}$ die Zahl $\begin{eqnarray} \omega := \left( \frac{1}{\frac{1}{2} + \frac{1}{3}} \right)^{20} \end{eqnarray}$ Für Hilfe und Tipps wäre ich sehr dankbar
22.01.2008, 16:46	AD	Auf diesen Beitrag antworten »
Zunächst mal kannst du hier im Körper $\begin{eqnarray} \mathbb{Z}_{107} \end{eqnarray}$ formal ganz ähnlich wie von $\begin{eqnarray} \mathbb{R} \end{eqnarray}$ (bzw. die rationalen Zahlen $\begin{eqnarray} \mathbb{Q} \end{eqnarray}$ genügen) her gewohnt folgendermaßen rechnen: $\begin{eqnarray} \left( \frac{1}{\frac{1}{2} + \frac{1}{3}} \right)^{20} = \left( \frac{1}{\frac{5}{6}} \right)^{20} = \left( \frac{6}{5} \right)^{20} \end{eqnarray}$ Dir sollte natürlich klar sein, warum man so vorgehen kann. Und weiter? Da gibt es verschiedene Möglichkeiten, naheliegend wäre jetzt erstmal $\begin{eqnarray} \frac{6}{5}\mod 107 \end{eqnarray}$ auszurechnen, d.h. die Lösung $\begin{eqnarray} x \end{eqnarray}$ der Gleichung $\begin{eqnarray} 5x\equiv 6\mod 107 \end{eqnarray}$ zu bestimmen...
24.01.2008, 22:51	slacker2d	Auf diesen Beitrag antworten »
Ich wollte mal meine Lösung präsentieren, auch wenn das vielleicht nur wenige interessiert. Mir hat es viel Arbyte gemacht, aber jetzt ist es cool. $\begin{eqnarray} \Bigl(\frac{1}{\frac{1}{2} + \frac{1}{3}} \Bigr)^{20} = \Bigl(\frac{1}{2^{-1} + 3^{-1}} \Bigr)^{20} \end{eqnarray}$ Danach muss man die Inversen Elemente zu 2 und 3 finden: $\begin{eqnarray} 2 \cdot x \pmod{107} = 1 \end{eqnarray}$ $\begin{eqnarray} 3 \cdot x \pmod{107} = 1 \end{eqnarray}$ Das habe ich mit dem Euklidischen Algorithmus und dem erweitertem Euklidischen Algorithmus berechnet: ggT(127, 2): $\begin{eqnarray} 107 = 35 \cdot 3 + 2 \end{eqnarray}$ $\begin{eqnarray} 3 = 1 \cdot 2 + 1 \end{eqnarray}$ $\begin{eqnarray} 2 = 2 \cdot 1 + 0 \end{eqnarray}$ ggT(127,3): $\begin{eqnarray} 107 = 53 \cdot 2 + 1 \end{eqnarray}$ $\begin{eqnarray} 2 = 1 \cdot 2 + 0 \end{eqnarray}$ Danach der erweiterte Euklid. Algo. $\begin{eqnarray} 1 = 3 - 2 \cdot 1 \end{eqnarray}$ $\begin{eqnarray} 1 = 3 - 1 \cdot (107 - 35 \cdot 3) \end{eqnarray}$ $\begin{eqnarray} 1 = 36 \cdot 3 - 1 \cdot 107 \end{eqnarray}$ $\begin{eqnarray} 2^{-1} = 36 \pmod{107} = 36 \end{eqnarray}$ $\begin{eqnarray} 1 = 107 - 53 \cdot 2 \end{eqnarray}$ $\begin{eqnarray} 3^{-1} = (-53) \pmod{107} = 54 \end{eqnarray}$ $\begin{eqnarray} \Bigl(\frac{1}{36 + 54}\Bigl)^{20} = \Bigl(\frac{1}{90}\Bigr)^{20} = (90^{-1})^{20} \end{eqnarray}$ ggT(107,90) = 1 (Zwischenschritte lasse ich mal weg, ist wieder der euklid. Algorithmus) $\begin{eqnarray} 1 = 44 \cdot 90 - 37 \cdot 107 \end{eqnarray}$ $\begin{eqnarray} 1 \equiv 44 \cdot 90 \pmod{107} \end{eqnarray}$ $\begin{eqnarray} (90^{-1})^{20} \equiv (44)^{20} \pmod{107} \end{eqnarray}$ Danach Square & Multiply Potenz in die Äquivalente Binärdarstellung bringen. $\begin{eqnarray} 20_{10} = 10100_2 \end{eqnarray}$ $\begin{eqnarray} 44^{20} = 44^{2^4+2^2} \end{eqnarray}$ $\begin{eqnarray} 44^{20} = (((44^2)^2\cdot 44)^2)^2 \end{eqnarray}$ Ausrechnen: $\begin{eqnarray} 44^2 \equiv 10 \pmod{107} \end{eqnarray}$ $\begin{eqnarray} (44^2)^2 \equiv (10 \cdot 10) \equiv 100 \pmod{107} \end{eqnarray}$ $\begin{eqnarray} ((44^2)^2 \cdot 44)^2 \equiv (100 \cdot 10) \equiv (1000)^2 \equiv 62 \pmod{107} \end{eqnarray}$ $\begin{eqnarray} (((44^2)^2 \cdot 44)^2)^2 \equiv 62^2 \equiv 99 \pmod{107} \end{eqnarray}$ $\begin{eqnarray} 99 \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »