Eulersche phi Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe 1 | | Berechnen Sie bitte die letzten beiden Stellen, d.h. die niedrigstwertigen beiden Stellen, die die Zahl [mm] 33^{1024} [/mm] im Dezimalsystem hat. |
| Aufgabe 2 | | Wie lauten die letzten drei Stellen, d.h. die drei niedrigstwertigen Stellen, die die Zahl [mm] 333^{816} [/mm] im Dezimalsystem hat. |
Hallo,
ich hoffe diese Frage ist in diesem Bereich richtig untergebracht.
Zu Aufgabe 1 gibt es eine Musterlösung:
Es ist ggT(33,100)=1, daher ist [mm] 33^{\phi(100)} \equiv [/mm] 1(mod 100).
[mm] \phi(100)=\phi(2^2*5^2)=\phi(2^2)*\phi(5^2)=2*(5^2-5^1)=40
[/mm]
1024=25*40+24. Damit folgt
[mm] 33^{1024}\equiv 33^{24} \equiv 33^8*33^{16} \equiv (((33^2)^2)^2*33^{16} \equiv (89^2)^2*33^{16} \equiv 21^2*33^{16} \equiv 41*41^2 \equiv [/mm] 41*81 [mm] \equiv [/mm] 21 (mod100)
Die beiden letzten Stellen lauten 21.
Ich verstehe bei dieser Aufgabe einfach nichts und kann auch nichts auf die zweite Aufgabe transferieren. Leider habe ich das gesamte Prinzip scheinbar nicht verstanden. Kann mir vielleicht jemand auf die Sprünge helfen?
LG
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo fuechsin151,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Berechnen Sie bitte die letzten beiden Stellen, d.h. die
> niedrigstwertigen beiden Stellen, die die Zahl [mm]33^{1024}[/mm] im
> Dezimalsystem hat.
> Wie lauten die letzten drei Stellen, d.h. die drei
> niedrigstwertigen Stellen, die die Zahl [mm]333^{816}[/mm] im
> Dezimalsystem hat.
> Hallo,
>
> ich hoffe diese Frage ist in diesem Bereich richtig
> untergebracht.
> Zu Aufgabe 1 gibt es eine Musterlösung:
>
> Es ist ggT(33,100)=1, daher ist [mm]33^{\phi(100)} \equiv[/mm] 1(mod
> 100).
>
> [mm]\phi(100)=\phi(2^2*5^2)=\phi(2^2)*\phi(5^2)=2*(5^2-5^1)=40[/mm]
>
> 1024=25*40+24. Damit folgt
>
> [mm]33^{1024}\equiv 33^{24} \equiv 33^8*33^{16} \equiv (((33^2)^2)^2*33^{16} \equiv (89^2)^2*33^{16} \equiv 21^2*33^{16} \equiv 41*41^2 \equiv[/mm]
> 41*81 [mm]\equiv[/mm] 21 (mod100)
>
> Die beiden letzten Stellen lauten 21.
>
> Ich verstehe bei dieser Aufgabe einfach nichts und kann
> auch nichts auf die zweite Aufgabe transferieren. Leider
> habe ich das gesamte Prinzip scheinbar nicht verstanden.
> Kann mir vielleicht jemand auf die Sprünge helfen?
Lies Dir mal das durch:![[]](/images/popup.gif) Eulersche [mm]\varphi[/mm]-Funktion.
>
> LG
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruss
MathePower
|
|
|
| |
|
Hallo MathePower,
vielleicht ist es hier die nicht Regel, aber ich informiere mich schon vorab, was ich zu einem Thema finden kann. Deshalb habe ich den Artikel natürlich schon gelesen gehabt. Leider setzt mein Hirn bei Mathe aus und ich verstehe nichts. Daher dachte ich, jemand kann mir vielleicht erklären - Schritt für Schritt - wie ich hier vorzugehen habe. Halt an Hand der vorhandenen Lösung, so dass ich die zweite Aufgabe lösen kann und verstehe, was zu tun ist.
Lieben Gruß
fuechsin
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:38 Fr 25.03.2011 | | Autor: | abakus |
Hallo,
die Endziffern der ersten Teilaufgabe entsprechen dem Rest von [mm] 33^{1024} [/mm] bei Teilung durch 100.
Da es nur 100 mögliche Reste gibt, müssen sich spätestens ab [mm] 33^{101} [/mm] (sicher schon zeitiger) die bis dahin aufgetretenen Reste wiederholen.
Es wird insbesondere auch irgendwann mal der Rest 1 auftreten, also es wird
[mm] 33^n\equiv [/mm] 1 mod 100 gelten.
Danach geht es zwangsläufig weiter mit
[mm] 33^{n+1}\equiv [/mm] 33 mod 100,
[mm] 33^{n+2}\equiv 33^2 [/mm] mod 100,
usw.
Die Eulerscher Phi-Funktion kann dir vermutlich helfen, das erstmalige Auftreten des Restes 1 zu ermitteln. Damit hast du die Zykluslänge, mit der sich die Reste wiederholen.
Gruß Abakus
|
|
|
|
