Endziffern von 7^{9999} best. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Finden Sie die letzten beiden Ziffern von [mm] 9^{(9^{(9^{9})})} [/mm] sowie die letzten drei Ziffern von [mm] 7^{9999} [/mm] |
Hallo!
Die Aufgaben stammen aus den Themengebieten "square and multiply", "chinesischer Restsatz" und Rechnen mit Kongruenzen. Für die Aufgaben muss ich wahrscheinlich
[mm] 9^{(9^{(9^{9})})} [/mm] mod 100
und
[mm] 7^{9999} [/mm] mod 1000
berechnen?
----
Ich fange mal mit
[mm] 7^{9999} [/mm] mod 1000
an, das scheint mir einfacher... Ich könnte zum einen schreiben
9999 = [mm] 3^{2}*11*101
[/mm]
oder
9999 = [mm] 2^{0} [/mm] + [mm] 2^{1} [/mm] + [mm] 2^{2} [/mm] + [mm] 2^{3} [/mm] + [mm] 2^{8} [/mm] + [mm] 2^{9} [/mm] + [mm] 2^{10} [/mm] + [mm] 2^{13}
[/mm]
Aber was mache ich denn jetzt am besten?
[mm] 7^{2^{0}} \equiv [/mm] 7 mod 1000
[mm] 7^{2^{1}} \equiv [/mm] 49 mod 1000
[mm] 7^{2^{2}} \equiv [/mm] 49*49 [mm] \equiv [/mm] 2401 [mm] \equiv [/mm] 401 mod 1000
[mm] 7^{2^{3}} \equiv [/mm] 401*401 [mm] \equiv [/mm] 160801 [mm] \equiv [/mm] 801 mod 1000
scheinen mir auch etwas sehr aufwendig. Könnte mir jemand bitte einen Tipp für diese Aufgabe geben? Was könnte ich vereinfachen / welche Gesetze der Modulo-Rechnung führen hier zum Ziel?
Bei der zweiten Aufgabe weiß ich ehrlich gesagt gar nicht, wie ich mit den Potenzen umgehen soll. Ich habe aber die Vermutung, dass hier und vielleicht auch schon bei der obigen Aufgabe man irgendwas mit der Gleichung
[mm] a^{p-1} \equiv [/mm] 1 mod p
anfangen muss? Ich sehe aber keinen Angriffspunkt.
Könnt ihr mir bitte helfen?
Danke für Eure Mühe!
Stefan.
|
|
| |
|
Wenn Du folgende zwei Informationen hast, findest Du auch leicht Deine Lösung:
I ) [mm] 7^{9999}\equiv a\mod{8}
[/mm]
II) [mm] 7^{9999}\equiv b\mod{125}
[/mm]
I) ist ja leicht zu ermitteln. II) sieht mühsamer aus, aber immerhin ist [mm] 7^{20}\equiv 1\mod{125}.
[/mm]
Für die andere Aufgabe ist es gut zu wissen, dass [mm] 9^{10}\equiv 1\mod{100}.
[/mm]
|
|
|
| |
|
Hallo und danke für deine Antwort!
> Wenn Du folgende zwei Informationen hast, findest Du auch
> leicht Deine Lösung:
> I ) [mm]7^{9999}\equiv a\mod{8}[/mm]
> II) [mm]7^{9999}\equiv b\mod{125}[/mm]
Welche Regel benutzt du dann, um das wieder zusammenzuführen? Ich kann keine passende in unserem Skript finden?
Ich habe raus:
[mm] $7^{9999} \equiv 7\mbox{ mod 8}$
[/mm]
[mm] $7^{9999} \equiv 18\mbox{ mod 8}$
[/mm]
Maple bestätigt mir diese Ergebnisse und sagt außerdem, dass [mm] $7^{9999} \equiv 143\mbox{ mod 1000}$ [/mm] ist. Ich finde nun aber nichts passendes, um meine Teilergebnisse darin zu überführen.
Danke für Eure Hilfe,
Stefan.
|
|
|
| |
|
Du weißt jetzt [mm] 7^{9999}\equiv 7\mod{8} [/mm] und [mm] 7^{9999}\equiv 18\mod{125}. [/mm] Außerdem ist [mm] \a{}ggT(8,125)=1
[/mm]
Es gibt jetzt zwei Wege, die Informationen zusammenzuführen. Hier geht der eine bedeutend leichter:
Es gilt [mm] 125\equiv 5\mod{8}
[/mm]
Gesucht: [mm] a=18+125n\equiv 2+5n\equiv 7\mod{8}
[/mm]
Leicht zu sehen: [mm] \a{}n=1 \Rightarrow \a{}a=18+125*1\equiv 143\mod{1000}
[/mm]
Der andere Weg: Es gilt [mm] 8\equiv 8\mod{125}
[/mm]
Gesucht: [mm] a=7+8m\equiv 18\mod{125}
[/mm]
Es gibt nun nur ein [mm] \a{}m, 0\le m\le \a{}125-1, [/mm] nämlich [mm] \a{}m=17 \Rightarrow \a{}a=7+8*17\equiv 143\mod{1000}.
[/mm]
|
|
|
| |
|
Hallo!
> Du weißt jetzt [mm]7^{9999}\equiv 7\mod{8}[/mm] und [mm]7^{9999}\equiv 18\mod{125}.[/mm]
> Außerdem ist [mm]\a{}ggT(8,125)=1[/mm]
>
> Es gibt jetzt zwei Wege, die Informationen
> zusammenzuführen. Hier geht der eine bedeutend leichter:
>
> Es gilt [mm]125\equiv 5\mod{8}[/mm]
> Gesucht: [mm]a=18+125n\equiv 2+5n\equiv 7\mod{8}[/mm]
Ehrlich gesagt verstehe ich nicht, warum ich ein a suche, das so wie oben beschaffen ist? Das es am Ende funktioniert, ist schön  , aber könntest du es noch einmal genauer erklären, wie du auf diesen Ansatz kommst?
> Leicht zu sehen: [mm]\a{}n=1 \Rightarrow \a{}a=18+125*1\equiv 143\mod{1000}[/mm]
Wie bist du eigentlich darauf gekommen, dass [mm] 7^{20} \equiv [/mm] 1 mod 1000 ist?
Stefan.
|
|
|
| |
|
Hallo Stefan!
> Hallo!
>
> > Du weißt jetzt [mm]7^{9999}\equiv 7\mod{8}[/mm] und [mm]7^{9999}\equiv 18\mod{125}.[/mm]
> > Außerdem ist [mm]\a{}ggT(8,125)=1[/mm]
> >
> > Es gibt jetzt zwei Wege, die Informationen
> > zusammenzuführen. Hier geht der eine bedeutend leichter:
> >
> > Es gilt [mm]125\equiv 5\mod{8}[/mm]
> > Gesucht: [mm]a=18+125n\equiv 2+5n\equiv 7\mod{8}[/mm]
>
> Ehrlich gesagt verstehe ich nicht, warum ich ein a suche,
> das so wie oben beschaffen ist? Das es am Ende
> funktioniert, ist schön , aber könntest du es noch
> einmal genauer erklären, wie du auf diesen Ansatz kommst?
Hier laufen die beiden Restklasseninformationen zusammen. Aus der Betrachtung [mm] \mod{125} [/mm] weiß ich, dass die gesuchte Zahl die Form a=125n+18 hat. Diese Darstellung wähle ich, um das [mm] \mod{125} [/mm] loszuwerden. So kann ich dann nämlich die zweite Information nutzen, indem ich dieses a [mm] \mod{8} [/mm] betrachte.
Das geht - wie gezeigt - auch in der anderen Reihenfolge, ist aber hier nicht so schön zu sehen wie beim Term [mm] 2+5n\equiv \a{}7.
[/mm]
> > Leicht zu sehen: [mm]\a{}n=1 \Rightarrow \a{}a=18+125*1\equiv 143\mod{1000}[/mm]
>
> Wie bist du eigentlich darauf gekommen, dass [mm]7^{20} \equiv[/mm]
> 1 mod 1000 ist?
Intuition nach vielen Restklassenrechnungen, aber nicht schwer nachzuvollziehen.
[mm] 7^2=49=50-1. [/mm] 50 ist hinsichtlich seiner Primfaktorenzerlegung ja schon sehr nah an 100. Aber da steht noch -1, also muss ich sicher quadrieren [mm] 7^4\equiv 401\mod{1000}\equiv 1\mod{100}. [/mm] Das sieht schon besser aus. Ich vermute, dass [mm] 7^{4k} [/mm] schon für ein ziemlich kleines k das gewünschte Ergebnis bringt, und so ist es ja dann für k=5. Das dauert nicht lange und spart danach viel Rechenzeit.
|
|
|
| |
|
Hallo reverend,
danke!!! Jetzt hab ichs verstanden! Hab bloß die ganze Zeit gedacht, dass da bei der Wahl von a irgendwie auch schon das Ergebnis von mod 8 eingeflossen ist 
Grüße,
Stefan.
|
|
|
| |
|
Hallo und nochmal danke für deine Antwort!
Ich versuche mal meine Gedanken zu den Neuner-Potenzen in Worte zu fassen...
[mm] 9^{(9^{(9^{9})})} [/mm] mod 100
Also, wenn ich weiß dass [mm] 9^{10}\equiv [/mm] 1 mod 100 (Wobei mir immer noch schleierhaft ist, wie ihr das immer herausbekommt), müsste ich nun überprüfen was
[mm] 9^{(9^{9})}
[/mm]
für einen Rest bei Division durch 10 lässt. Dann müsste ich nur noch
[mm] 9^{AnzahlRest}*1 [/mm] mod 100
berechnen. Ich habe nun also als neue Aufgabe
[mm] 9^{(9^{9})} [/mm] mod 10
Wenn ich hier [mm] $9^{2} \equiv [/mm] 1 [mm] \mbox [/mm] {mod 10}$ benutze und nochmal dieselbe Überlegung anwende, komme ich zu
[mm] 9^{9} [/mm] mod 2
als Aufgabe. Das ist trivialerweiser
[mm] 9^{9}\equiv [/mm] 1 mod 2
Jetzt wieder nach unten hangeln: Ich weiß nun also dass [mm] 9^{9} [/mm] den Rest 1 lässt, d.h. mein Ergebnis bei
[mm] 9^{(9^{9})} [/mm] mod 10
entspricht dann
[mm] 9^{(9^{9})} \equiv 9^{1}*1 \equiv [/mm] 9 mod 10
Ich erhalte also für die Ausgangsgleichung
[mm] 9^{(9^{(9^{9})})} \equiv 9^{9}*1 [/mm] mod 100
als Aufgabe, und nach einigem Rechnen erhalte ich
[mm] 9^{(9^{(9^{9})})} \equiv 9^{9}*1 \equiv [/mm] 89 mod 100
???
Stimmt das? Ich weiß, dass ich meinen Gedankengang glaub ich nicht für die Außenwelt sonderlich toll beschrieben habe, aber ist das der Weg oder ist alles falsch
Danke für Eure Hilfe,
Stefan.
|
|
|
| |
|
Ok, die Beschreibung ist etwas kraus, aber der Gedankengang an sich richtig, und das Ergebnis auch.
Woher ich wusste, dass [mm] 9^{10}\equiv 1\mod{100} [/mm] ist? Ganz ehrlich, ich hab einfach mal ein paar Potenzen weit nachgerechnet. Die Aufgabe ist halt viel schneller "zu Fuß" zu rechnen, wenn man so eine Beziehung hat:
Dann findet man [mm] 9^9\equiv \bruch{801}{9}\equiv 89\mod{100}
[/mm]
(das darf man ja nunmal gar nicht schreiben...)
Und also [mm] 9^{(9^9)}\equiv 9^{89}\equiv 9^9\equiv 89\mod{100}
[/mm]
...und ist eigentlich schon fertig. Der Weg reproduziert sich ja bis ins Unendliche, egal wie lange ich diese Schachtelpotenzen noch ausbauen will. Das Ergebnis bleibt 89.
|
|
|
| |
|
Hallo!
Ok, danke und Grüße,
Stefan.
|
|
|
| |
|
> Finden Sie die die letzte Ziffer von [mm]7^{9999}[/mm]
7 * 7 = ...9
9 * 7 = ...3
3 * 7 = ...1
1 * 7 = ...7
und dann geht es wieder von vorne los. Das Ganze 9999 Mal.
Beim 9999sten Mal wäre man dann m.E. bei der Endziffer "3".
Auch die Reihenfolge der letzten drei Endziffern wird sich irgendwann immer wieder wiederholen. Mit Hilfe eines Computerprogrammes würde man wohl sehen, wann das der Fall ist.
|
|
|
| |
|
> Auch die Reihenfolge der letzten drei Endziffern wird sich
> irgendwann immer wieder wiederholen. Mit Hilfe eines
> Computerprogrammes würde man wohl sehen, wann das der Fall
> ist.
Taschenrechner genügt !
|
|
|
|
