Potenz ausrechnen

27.05.2018, 15:42

Maik33

Potenz ausrechnen

Meine Frage:
Rechne $\begin{eqnarray*} 3^{3^{3^{3^{.^{.} } } } } \end{eqnarray*}$ (2018 mal) in mod 100.

Meine Ideen:
Satz von Euler, aber ich verstehe nicht wie ich die gewünschte Darstellung erhalten soll.

27.05.2018, 18:19

HAL 9000

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} n = 3^{3^{3^{3^{.^{.}}}}} \end{eqnarray*}$ (2018 mal) die fragliche Zahl.

Statt der Eulerschen $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Funktion würde ich hier mit der Carmichael-Funktion arbeiten, geht einfach etwas schneller.

Hinreichend für $\begin{eqnarray*} 3^x\equiv 3^y\bmod 100 \end{eqnarray*}$ ist $\begin{eqnarray*} x\equiv y\bmod 20 \end{eqnarray*}$ , wegen $\begin{eqnarray*} \lambda(100)=20 \end{eqnarray*}$

Hinreichend für $\begin{eqnarray*} 3^x\equiv 3^y\bmod 20 \end{eqnarray*}$ ist $\begin{eqnarray*} x\equiv y\bmod 4 \end{eqnarray*}$ , wegen $\begin{eqnarray*} \lambda(20)=4 \end{eqnarray*}$ .

Hinreichend für $\begin{eqnarray*} 3^x\equiv 3^y\bmod 4 \end{eqnarray*}$ ist $\begin{eqnarray*} x\equiv y\bmod 2 \end{eqnarray*}$ , wegen $\begin{eqnarray*} \lambda(4)=2 \end{eqnarray*}$ .

Jetzt das ganze "rückwärts", ausgehend von $\begin{eqnarray*} m = 3^{3^{3^{3^{.^{.}}}}} \end{eqnarray*}$ (2015 mal):

$\begin{eqnarray*} m\equiv 1\bmod 2 \end{eqnarray*}$

$\begin{eqnarray*} 3^m\equiv 3\bmod 4 \end{eqnarray*}$

$\begin{eqnarray*} 3^{3^m}\equiv 7\bmod 20 \end{eqnarray*}$

$\begin{eqnarray*} n=3^{3^{3^m}}\equiv 87\bmod 100 \end{eqnarray*}$ .

Mit Euler- $\begin{eqnarray*} \varphi \end{eqnarray*}$ geht die Argumentation auch, sind halt ein paar Schritte mehr. Augenzwinkern

27.05.2018, 18:49

Maik33

Auf diesen Beitrag antworten »

Hmm okay, ich verstehe nicht wirklich wie ich das mit der Eulerfunktion technisch mache..

$\begin{eqnarray*} 3^{\varphi(3^{2017}) } \end{eqnarray*}$

Wie soll ich sowas runterbrechen auf Dimensionen wo ich die Funktion anwenden kann? Das verstehe ich nicht und deswegen habe ich auch Probleme mit deinem Lösungsweg.

27.05.2018, 18:58

HAL 9000

Auf diesen Beitrag antworten »

Ich hab ja auch nicht von $\begin{eqnarray*} 3^{\varphi(3^{2017}) } \end{eqnarray*}$ gesprochen.

27.05.2018, 19:50

Maik33

Auf diesen Beitrag antworten »

Ok ich habe jetzt das vorgehen verstanden.Zur Verständis: Warum ist phi(100)=40 die Begründung dafür anstatt mod 100 dann nur mod 40 betrachten zu müssen, weil $\begin{eqnarray*} 3^{\varphi{(100)}} \equiv 1 \end{eqnarray*}$ ist? Das verstehe ich noch nicht zu 100%.. Ich bin nun soweit:

$\begin{eqnarray*} \varphi{(100)}=40 \end{eqnarray*}$
$\begin{eqnarray*} \varphi{(40)}=16 \end{eqnarray*}$
.
.

$\begin{eqnarray*} m\equiv 1 && mod 2 \end{eqnarray*}$
$\begin{eqnarray*} 3^{m}\equiv 3 && mod 4 \end{eqnarray*}$
$\begin{eqnarray*} 3^{3^{m} }\equiv 3 && mod 8 \end{eqnarray*}$
$\begin{eqnarray*} 3^{3^{3^{m} } }\equiv 11 && mod 16 \end{eqnarray*}$

nun jetzt ist es schwierig 3^(11) zu bestimmen oder wie bist du bei den 3^7 vorgegangen?

27.05.2018, 19:54

HAL 9000

Auf diesen Beitrag antworten »

Fermat-Euler sagt: Sind $\begin{eqnarray*} a,k \end{eqnarray*}$ teilerfremd, so ist $\begin{eqnarray*} a^{\varphi(k)}\equiv 1\bmod k \end{eqnarray*}$ , damit ist auch $\begin{eqnarray*} a^{q\cdot \varphi(k)+r} \equiv a^r\bmod k \end{eqnarray*}$ , oder mit anderen Worten:

Aus $\begin{eqnarray*} x\equiv y\bmod \varphi(k) \end{eqnarray*}$ folgt auch $\begin{eqnarray*} a^x\equiv a^y\bmod k \end{eqnarray*}$ .

Im Prinzip habe ich oben dasselbe genutzt, nur mit $\begin{eqnarray*} \lambda(k) \end{eqnarray*}$ statt $\begin{eqnarray*} \varphi(k) \end{eqnarray*}$ , was wegen $\begin{eqnarray*} a^{\lambda(k)}\equiv 1\bmod k \end{eqnarray*}$ ja auch möglich ist.

27.05.2018, 19:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Maik33
nun jetzt ist es schwierig 3^(11) zu bestimmen

(Intelligent) Rechnen! Z.B. ist $\begin{eqnarray*} 3^4=81\equiv 1\bmod 40 \end{eqnarray*}$ , da sollte es so schwierig nicht sein, $\begin{eqnarray*} 3^{11}=3^{2\cdot 4+3}\bmod 40 \end{eqnarray*}$ auszurechnen.

27.05.2018, 21:01

Maik33

Auf diesen Beitrag antworten »

Danke für deine Hilfe!
Für 3^27 hab ich bestimmt nicht den leichtesten Weg gefunden:
3^27=3^7*3^20=3^7 * 3^40^0.5=3^7=3^2 * 3^2 *3^3 =81*3*3^2=43*9=87

(Hier mal nicht ganz korrekt ohne Kongruentszeichen)

Neue Frage »

Antworten »

Potenz ausrechnen

Verwandte Themen