Rest mittels Euler-Fermat < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:32 Sa 28.03.2009 | | Autor: | chappa |
| Aufgabe | Berechne (ohne Taschenrechner), mit Hilfe des Satzes von
Euler-Fermat die Potenz
[mm] 2^{(2^{32})} [/mm] mod 11 |
Also den Satz von Euler-Fermat kann ich soweit anwenden, allerdings weiß ich bei dieser großen Potenz nicht weiter. Sage hat mir für diese Aufgabe Rest 1 ausgespuckt, allerdings weiß ich nicht, wie ich darauf kommen sollte. Bin für jeden Denkanstoß dankbar :)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:50 Sa 28.03.2009 | | Autor: | abakus |
> Berechne (ohne Taschenrechner), mit Hilfe des Satzes von
> Euler-Fermat die Potenz
>
> [mm]2^{(2^{32})}[/mm] mod 11
> Also den Satz von Euler-Fermat kann ich soweit anwenden,
> allerdings weiß ich bei dieser großen Potenz nicht weiter.
> Sage hat mir für diese Aufgabe Rest 1 ausgespuckt,
> allerdings weiß ich nicht, wie ich darauf kommen sollte.
> Bin für jeden Denkanstoß dankbar :)
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Hallo,
untersuche doch einfach mal die Reste der Potenzen [mm] 2^k [/mm] mod 11.
Es gilt
[mm] 2^0 [/mm] /equiv 1 mod 11
[mm] 2^1 [/mm] /equiv 2 mod 11
[mm] 2^2 [/mm] /equiv 4 mod 11
[mm] 2^3 [/mm] /equiv 8 mod 11
[mm] 2^4 [/mm] /equiv 5 mod 11
...
2^10 /eqiv 1 mod 11 (was übrigens auch aus dem Kleinen Satz Von Fermat folgt.
Danach geht es wieder von vorn los:
[mm] 2^{11} [/mm] /equiv 2 mod 11
[mm] 2^{12} [/mm] /equiv 4 mod 11
[mm] 2^{13} [/mm] /equiv 8 mod 11
[mm] 2^{14} [/mm] /equiv 5 mod 11
Alle 10 Schritte wiederholen sich also die Reste mod 11.
Der Exponent 2^32 ist ein Vielfache von 10 plus einem Rest. Dieser letzte Rest entscheidet, ob nun
[mm] 2^{(2^{32})}\equiv 2^0 [/mm] mod 11 oder
[mm] 2^{(2^{32})}\equiv 2^1 [/mm] mod 11 oder
[mm] 2^{(2^{32})}\equiv 2^2 [/mm] mod 11 oder
... oder
[mm] 2^{(2^{32})}\equiv 2^9 [/mm] mod 11 gilt.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:36 Di 31.03.2009 | | Autor: | felixf |
Hallo
> Berechne (ohne Taschenrechner), mit Hilfe des Satzes von
> Euler-Fermat die Potenz
>
> [mm]2^{(2^{32})}[/mm] mod 11
> Also den Satz von Euler-Fermat kann ich soweit anwenden,
> allerdings weiß ich bei dieser großen Potenz nicht weiter.
Euler-Fermat sagt doch: [mm] $2^{2^{32}} \equiv 2^n \pmod{11}$ [/mm] wenn $n [mm] \equiv 2^{32}$ [/mm] modulo [mm] $\phi(11) [/mm] = 10$ ist.
Also musst du [mm] $2^{32}$ [/mm] modulo 10 bestimmen. Dazu kannst du wiederum Euler-Fermat benutzen: du musst 32 modulo [mm] $\phi(10)$ [/mm] bestimmen (und [mm] $\phi(10)$ [/mm] auch).
LG Felix
|
|
|
|
