Verkettung von Potenzen

07.11.2008, 12:14

Bjoern1982

Verkettung von Potenzen

Hallo,

ich soll die letzten beiden Ziffern von $\begin{eqnarray*} n=9^{{9^9}^9}=9^a \end{eqnarray*}$ mit $\begin{eqnarray*} a=9^b \end{eqnarray*}$ und $\begin{eqnarray*} b=9^9 \end{eqnarray*}$

Jemand eine Idee ?

Bestimmung der letzte beiden Ziffern hört sich ja schwer nach mod 100 an.
Das jetzt aber dreimal zu machen, und dann mühsam mit square and multiply (wenn es denn überhaupt so geht) ist bestimmt hier nicht verlangt...

Gruß Björn

07.11.2008, 13:29

tigerbine

Auf diesen Beitrag antworten »

Ähnliches Problem: Dezimaldarstellung^9

Vielleicht kannst du damit schon mal weiterarbeiten. Wink

07.11.2008, 17:27

Bjoern1982

Auf diesen Beitrag antworten »

Kommt dem ganzen ja schon recht nah.
Bei mir würde das dann zunächst auf die Berechnung von 9^9 mod 40 hinauslaufen, jedoch nachher bräuchte ich auf alle Fälle wieder square and multiply - es sei denn ich habe es misverstanden...

Gruß und danke für den Link

07.11.2008, 17:35

tigerbine

Auf diesen Beitrag antworten »

Zitat:

square and multiply

Was das denn? Ich bin hier nicht so fit drin, Arthur (und andere) wohl eher. Denen überlasse ich gerne das Feld. Hab mich eben nur an den verlinkten Thread erinnert. Wink

Ich würde mich freuen, wenn du am Ende die Aufgabe so aufschreibst, dass wir was schönes in der Boardsuche haben. Das Problem scheint ja öfters mal aufzutreten.

Gerne kopiere ich das dann auch in einen [Artikel]

Gruß und danke Wink

07.11.2008, 17:47

Bjoern1982

Auf diesen Beitrag antworten »

Square and multiply kann man benutzen, wenn man unangenehm hohe Exponenten hat, um damit dann eine Potenz a^x mod n per Hand auszurechnen, indem man den Exponenten x als Summe s von 2er Potenzen ausdrückt und dann a^s in mehrere Produkte aufteilt...usw
Ich führe das gerne vor wenn sich Arthur oder andere Zahlentheoriefreunde zu Wort melden und mir sagen, dass ich da eh nicht drum herum kommen werde dieses Verfahren anzuwenden.

Zitat:

Ich würde mich freuen, wenn du am Ende die Aufgabe so aufschreibst, dass wir was schönes in der Boardsuche haben. Das Problem scheint ja öfters mal aufzutreten.

Werde ich sehr gerne tun wenn ich zu einer korrekten Lösung komme smile

07.11.2008, 18:21

Auf diesen Beitrag antworten »

Square & Multiply ist eine Option, aber hier ist man doch mit Euler-Fermat viel schneller am Ziel:

Wie schon erwähnt, kann man wegen $\begin{eqnarray*} \varphi(100)=40 \end{eqnarray*}$ gemäß Euler-Fermat

$\begin{eqnarray*} 9^{9^{9^9}} \equiv 9^m \mod 100 \end{eqnarray*}$ für $\begin{eqnarray*} 9^{9^9} \equiv m \mod 40 \end{eqnarray*}$

schließen. Nun erinnere ich mal noch an

$\begin{eqnarray*} 9^2 = 81 \equiv 1 \mod 40 \end{eqnarray*}$ .

Klingelt da irgendwas?

07.11.2008, 20:32

Bjoern1982

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} 9^{9^{9^9}} \equiv 9^m \mod 100 \end{eqnarray*}$ für $\begin{eqnarray*} 9^{9^9} \equiv m \mod 40 \end{eqnarray*}$

Und daraus kann man ja nochmal $\begin{eqnarray*} 9^9 \equiv n\ mod\ 16 \end{eqnarray*}$ machen und das ist mit $\begin{eqnarray*} \varphi(16)=8 \end{eqnarray*}$ logischerweise 9 mod 16.

$\begin{eqnarray*} 9^9\ mod\ 40 \equiv 3^{18}\ mod\ 40 \equiv 9\ mod\ 40 \end{eqnarray*}$ mit $\begin{eqnarray*} \varphi(40)=16 \end{eqnarray*}$

So und dann $\begin{eqnarray*} 9^9\ mod\ 100 \equiv (9^3)^3\ mod\ 100 \equiv 29^3=24389\ mod\ 100 \equiv 89\ mod\ 100 \end{eqnarray*}$

Also würde bei mir für die letzten beiden Ziffern 89 rauskommen.
Ist das korrekt oder habe ich es mir zu kompliziert gemacht, denn

Zitat:

$\begin{eqnarray*} 9^2 = 81 \equiv 1 \mod 40 \end{eqnarray*}$

habe ich hier ja gar nicht benutzt...

Gruß Björn

07.11.2008, 20:56

Auf diesen Beitrag antworten »

Viel komplizierter ist es nicht, ich hätte es nur an einer Stelle abgekürzt: Es ist ja $\begin{eqnarray*} 9^9 \end{eqnarray*}$ ungerade, also ist mit einer ganzen Zahl $\begin{eqnarray*} k \end{eqnarray*}$

$\begin{eqnarray*} 9^{9^9} = 9^{2k+1} = 81^k\cdot 9 \equiv 1^k\cdot 9 = 9\mod 40 \end{eqnarray*}$ ,

und dann weiter wie bei dir, also

$\begin{eqnarray*} 9^{9^{9^9}} \equiv 9^9 \equiv 89 \mod 100 \end{eqnarray*}$ .

07.11.2008, 21:03

tigerbine

Auf diesen Beitrag antworten »

OT: Ich rufe Arthur schon mal ein Danke zu. Augenzwinkern