Potenzen mit Modul reduzieren < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Berechne (ohne Taschenrechner), mit Hilfe des Satzes von Euler-Fermat die Potenzen
a) [mm] 2^{32} [/mm] mod 11 [mm] b)2^{(2^{32})} [/mm] mod 11 c) [mm] [3]^{(2^{32})} [/mm] in [mm] \IZ_{50} [/mm] |
Hallo, meine Frage wäre wie ich folgende Potenz berechne:
[mm] 2^{(2^{32})} [/mm] mod 11
[mm] 2^{32} [/mm] mod 11 stellt kein Problem dar, wenn ich den Satz von Euler-Fermat verwende, aber [mm] 2^{(2^{32})} [/mm] mod 11 sieht mir so nach [mm] 2^{~4mrd} [/mm] mod 11 aus und da wirds dann ein wenig schwer, wär die Klammer nicht da, dann würd ichs mit [mm] 2^{64} [/mm] mod 11 rechnen und dass ging dann auch wieder. Ich wäre froh wenn jemand einen Tipp hätte wie ich das lösen könnte.
lg tom
|
|
| |
|
Hallo original_tom,
> Berechne (ohne Taschenrechner), mit Hilfe des Satzes von
> Euler-Fermat die Potenzen
>
> a) [mm]2^{32}[/mm] mod 11 [mm]b)2^{(2^{32})}[/mm] mod 11 c) [mm][3]^{(2^{32})}[/mm] in
> [mm]\IZ_{50}[/mm]
> Hallo, meine Frage wäre wie ich folgende Potenz berechne:
>
> [mm]2^{(2^{32})}[/mm] mod 11
>
> [mm]2^{32}[/mm] mod 11 stellt kein Problem dar, wenn ich den Satz
> von Euler-Fermat verwende, aber [mm]2^{(2^{32})}[/mm] mod 11 sieht
> mir so nach [mm]2^{~4mrd}[/mm] mod 11 aus und da wirds dann ein
> wenig schwer, wär die Klammer nicht da, dann würd ichs mit
> [mm]2^{64}[/mm] mod 11 rechnen und dass ging dann auch wieder. Ich
> wäre froh wenn jemand einen Tipp hätte wie ich das lösen
> könnte.
Nach Euler-Fermat gilt ja
[mm]2^{10} \equiv 1 \ \left(11\right)[/mm]
Berechne daher zunächst [mm]r=2^{32} \ mod \ 10[/mm]
Dann gilt offensichtlich
[mm]2^{2^{32}} \equiv 2^{r} \ \left(11\right)[/mm]
Das heisst, es ist nur noch [mm]2^{r} \ mod \ 11 [/mm] zu berechnen.
>
> lg tom
Gruß
MathePower
|
|
|
| |
|
Erstmals danke für die schnelle Antwort. Ich hab aber noch eine Frage dazu:
bei [mm] 2^{32} [/mm] mod 10 steh ich gerade auf der Leitung, da ja der Satz von Euler-Fermat hier nicht gilt oder seh ich das jetzt falsch. Dazu müsste ggT(32,10) = 1 sein...
Irgendwie schaffe ich es nicht eine sinnvolle Rechnung zu erstellen. Vl könntest du mir noch einen Tipp geben.
lg tom
|
|
|
| |
|
Hallo Tom,
ich denke, da ist MathePower ein Tippfehler unterlaufen.
Es ist dort [mm] $r=2^{32}\mod \blue{11}$ [/mm] gemeint
Es ist [mm] $2^{10}\equiv [/mm] 1 [mm] \mod [/mm] 11$, also [mm] $2^{30}=\left(2^{10}\right)^3\equiv 1^3=1 \mod [/mm] 11$
Damit [mm] $r=2^{32}=2^2\cdot{}2^{30}\equiv 2^2\cdot{}1=4 \mod [/mm] 11$
Und damit dann [mm] $2^r=2^{\left(2^{32}\right)}\equiv 2^{4}=16\equiv [/mm] 5 [mm] \mod [/mm] 11$
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:36 Mi 15.04.2009 | | Autor: | Lorence |
Und was mit aufgabe 3?
Ich habe mir folgendes überlegt:
[mm] 3^{2^{32}} [/mm] mod 50
da fällt mir direkt ein:
[mm] a^{\phi(n)}\equiv [/mm] 1 mod m
[mm] \phi(50) [/mm] = 20
also folgt doch:
[mm] a^{\phi(50)}\equiv [/mm] 1 mod 50
und daraus
[mm] a^{20}\equiv [/mm] 1 mod 50
Jetzt kann ich doch für a=2 einsetzen um somit wie bei den Aufgabeteilen vorher, erst die potenz zu berechnen:
[mm] 2^{20}\equiv [/mm] 1 mod 50
, aber wenn ich dass per taschenrechner nachrechne kommt da 26 mod 50 raus und nicht 2 mod 50!
hat jemand ne idee warum?
|
|
|
| |
|
Hallo Lorence,
[mm] a^{\varphi(n)}\equiv 1\mod{\blue{n}} [/mm] gilt nur für teilerfremde a,n.
Glücklicherweise brauchst Du zur Lösung der Aufgabe aber sowieso erst einmal den Schritt
[mm] 3^r\equiv 1\mod{50}, [/mm] so dass Dir die Formel doch weiterhilft.
In der Tat ist [mm] 3^{20}\equiv 1\mod{50}.
[/mm]
Nun müsstest Du noch bestimmen, was [mm] 2^{32}\mod{20} [/mm] ist, dann kannst Du die Aufgabe lösen.
Kontrollendergebnis: 21.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:36 Mi 15.04.2009 | | Autor: | Lorence |
[mm] 2^{32}\equiv [/mm] 16 mod 20
aber wie gehe ich jetzt weiter?
r = 16 mod 20
ich bin doch aber in mod 50.
3^(16 mod 20) mod 50???
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:40 Mi 15.04.2009 | | Autor: | Lorence |
achso, ich glaube ich muss jetzt nurnoch
3^(16) mod 50 berechnen, dass ist aber sehr anstrengend ohne taschenrechner oder?
Gruß
|
|
|
| |
|
Hallo Lorence,
stimmt schon.
1) [mm] 3^{\blue{20}}\equiv 1\mod{\red{50}}
[/mm]
2) [mm] 2^{32}\equiv \green{16}\mod{\blue{20}}
[/mm]
[mm] 1)\wedge 2)\quad \Rightarrow 3^{\left(2^{32}\right)} \equiv 3^{\green{16}}\mod{\red{50}}
[/mm]
...und das ist ja wegen [mm] 16=2^4 [/mm] ganz schnell auszurechnen:
[mm] 3,9,81\equiv31,961\equiv11,121\equiv21
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 14:52 Mi 15.04.2009 | | Autor: | reverend |
Lang ist's her...
Aber da die Diskussion gerade wieder aufgewärmt wird:
MathePower ist kein Fehler unterlaufen. Gesucht ist tatsächlich [mm] r=2^{32} \mod{\blue{10}}.
[/mm]
Auch das ist mit Euler-Fermat zu bestimmen.
10=2*5
[mm] 2^{32}\equiv 0\mod{2},\quad 2^{32}\equiv 1\mod{5}
[/mm]
[mm] \Rightarrow 2^{32}\equiv \green{6}\mod{10}
[/mm]
[mm] \Rightarrow 2^{\left(2^{32}\right)} \equiv 2^{\green{6}}=64\equiv 9\mod{11}
[/mm]
Grüße
reverend
|
|
|
|
