Pfeilschreibweise und modulare Arithmetik

15.05.2013, 10:53	irre.flexiv	Auf diesen Beitrag antworten »
Pfeilschreibweise und modulare Arithmetik Hallo liebe Matheboard'ler, im Zusammenhang mit der Ackermannfunktion versuche ich gerade folgenden Wert zu berechnen (Pfeilnotation nach Knuth): $\begin{eqnarray} 2 \uparrow ^{8} 13 \mod 5^{10} \end{eqnarray}$ Mir ist klar, dass ich den Satz von Euler anwenden muss, aber es gelingt mir nicht. Weiß jemand Rat?
17.05.2013, 14:55	irre.flexiv	Auf diesen Beitrag antworten »
$\begin{eqnarray} 2 \uparrow^8 13 \end{eqnarray}$ ist ein Potenzturm bestehend aus Zweien. Man setzt einfach $\begin{eqnarray} x_0 = 2 \uparrow^8 13 = 2^{x_1} \end{eqnarray}$ und bekommt $\begin{eqnarray} x_0 \equiv 2^{x_1 \mod \varphi(5^{10})} \mod 5^{10} \end{eqnarray}$ $\begin{eqnarray} x_1 \equiv 2^{x_2 \mod \varphi(\varphi(5^{10}))} \mod \varphi(5^{10}) \end{eqnarray}$ $\begin{eqnarray} x_2 \equiv 2^{x_3 \mod \varphi(\varphi(\varphi(5^{10})))} \mod \varphi(\varphi(5^{10})) \end{eqnarray}$ usw. bis $\begin{eqnarray} x_9 \equiv 2^{x_{10} \mod \varphi^{10}(5^{10})} \mod \varphi^9(5^{10}) \end{eqnarray}$ Da $\begin{eqnarray} \varphi^{10}(5^{10}) = 2^{11} \end{eqnarray}$ eine Zweier-Potenz ist folgt $\begin{eqnarray} x_{10} \equiv 0 \mod \varphi^{10}(5^{10}) \end{eqnarray}$ Dann noch sukzessive rückwärts auflösen und man hat es.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »