2^32+1 ist keine Primzahl < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige, dass [mm] 2^{32}\equiv [/mm] -1 (mod 641) und dmait ist 2^32+1 keine Primzahl. |
Hi,
zu dieser Aufgabe habe ich folgende Lösung:
[mm] 2^{32}\equiv [/mm] -1 (mod 641)
641=640+1 [mm] =5*2^7+1 [/mm] (1)
[mm] 641=625+16=5^4+2^4 [/mm] (2)
Damit ergibt sich
(1) [mm] 5*2^7 \equiv [/mm] -1 (mod 641) und damit auch
[mm] 5^4*2^{28} \equiv [/mm] 1 (mod 641)
(2) [mm] 5^4 \equiv -2^4 [/mm] (mod 641)
und damit
[mm] 5^4 2^{28} \equiv (-2^4)2^{28} [/mm] (mod 641) [mm] \equiv -2^{32} [/mm] (mod 641) [mm] \equiv [/mm] 1 (mod 641)
Und damit [mm] 2^{32} \equiv [/mm] -1 (mod 641).
Also bei dieser Aufgabe habe ich mich gefragt, wie kommt man denn, wenn es eine Klausur wäre, auf diese Schritte:
641=640+1 [mm] =5*2^7+1 [/mm] (1)
[mm] 641=625+16=5^4+2^4 [/mm] (2)
???? Denn das ist ja sozusagen der entscheidende Schritt. Habt ihr da irgendwie Tipps, wie man auf sowas kommt?
Und dann noch eine Frage zur Potenzrechnung. Kann man [mm] (-2^4)2^{28} [/mm] einfach zusammenfassen, obwohl bei der einen Basis ein Minus davor steht???
Grüße
|
|
| |
|
> Zeige, dass [mm]2^{32}\equiv[/mm] -1 (mod 641) und dmait ist 2^32+1
> keine Primzahl.
> Hi,
>
> zu dieser Aufgabe habe ich folgende Lösung:
>
> [mm]2^{32}\equiv[/mm] -1 (mod 641)
>
> 641=640+1 [mm]=5*2^7+1[/mm] (1)
> [mm]641=625+16=5^4+2^4[/mm] (2)
>
> Damit ergibt sich
>
> (1) [mm]5*2^7 \equiv[/mm] -1 (mod 641) und damit auch
>
> [mm]5^4*2^{28} \equiv[/mm] 1 (mod 641)
>
> (2) [mm]5^4 \equiv -2^4[/mm] (mod 641)
>
> und damit
>
> [mm]5^4 2^{28} \equiv (-2^4)2^{28}[/mm] (mod 641) [mm]\equiv -2^{32}[/mm]
> (mod 641) [mm]\equiv[/mm] 1 (mod 641)
>
> Und damit [mm]2^{32} \equiv[/mm] -1 (mod 641).
>
>
> Also bei dieser Aufgabe habe ich mich gefragt, wie kommt
> man denn, wenn es eine Klausur wäre, auf diese Schritte:
>
> 641=640+1 [mm]=5*2^7+1[/mm] (1)
> [mm]641=625+16=5^4+2^4[/mm] (2)
>
> ???? Denn das ist ja sozusagen der entscheidende Schritt.
> Habt ihr da irgendwie Tipps, wie man auf sowas kommt?
Hallo Steve,
für eine Klausur ist diese Aufgabe wohl eine Nummer zu
groß (ohne irgendeinen hilfreichen Tipp). Leonhard Euler
rechnete wohl auch ziemlich lange, bis er auf diese
Idee kam. Siehe ![[]](/images/popup.gif) Fermat-Zahl
Der wichtigste Schritt war dabei, die Zahl 641 als Teiler
erst einmal zu finden.
Wenn aber dieser Modul 641 einmal bekannt ist, ist
der Nachweis von [mm]2^{32}\equiv[/mm] -1 (mod 641)
eigentlich eine Standardaufgabe, die man mit mehr
oder weniger Aufwand durchführen kann.
Der vorgeschlagene Lösungsweg ist schon etwas
"ausgetüftelt" - darauf kommt man nicht einfach
so ganz leicht. Man kann den Nachweis aber auch
anders führen, zum Beispiel so:
[mm] 2^{32}=\left(2^8\right)^4=256^4=\left(256^2\right)^2
[/mm]
Nun berechnet man zuerst [mm] 256^2=65536 [/mm] und reduziert
dies modulo 641 zu 154. Dies wieder quadrieren ergibt
23716. Modulo 641 reduziert ergibt dies 640 oder -1 .
> Und dann noch eine Frage zur Potenzrechnung. Kann man
> [mm](-2^4)2^{28}[/mm] einfach zusammenfassen, obwohl bei der einen
> Basis ein Minus davor steht???
Dieses Minuszeichen gehört nicht zur Basis, sondern
zur gesamten Potenz !
LG Al-Chw.
|
|
|
| |
|
Hi, nochmal eine kleine Frage zu den Potenzgesetzen.
> Und dann noch eine Frage zur Potenzrechnung. Kann man
> $ [mm] (-2^4)2^{28} [/mm] $ einfach zusammenfassen, obwohl bei der einen
> Basis ein Minus davor steht???
> Dieses Minuszeichen gehört nicht zur Basis, sondern
> zur gesamten Potenz !
Die Regel lautet ja:
[mm] a^u*a^v=a^{u+v}
[/mm]
In der Aufgabe haben wir aber jetzt bei der einen Potenz auch ein Minuszeichen. Gilt denn auch:
[mm] (-a^u)*(a^v)=-a^{u+v}???
[/mm]
|
|
|
| |
|
Hallo steve.joke,
> Hi, nochmal eine kleine Frage zu den Potenzgesetzen.
>
> > Und dann noch eine Frage zur Potenzrechnung. Kann man
> > [mm](-2^4)2^{28}[/mm] einfach zusammenfassen, obwohl bei der
> einen
> > Basis ein Minus davor steht???
>
> > Dieses Minuszeichen gehört nicht zur Basis, sondern
> > zur gesamten Potenz !
>
>
> Die Regel lautet ja:
>
> [mm]a^u*a^v=a^{u+v}[/mm]
>
> In der Aufgabe haben wir aber jetzt bei der einen Potenz
> auch ein Minuszeichen. Gilt denn auch:
>
> [mm](-a^u)*(a^v)=-a^{u+v}???[/mm]
Ja, denn [mm](-a^{u})\cdot{}(a^v)=(-1)\cdot{}(a^{u})\cdot{}(a^v)=(-1)\cdot{}a^{u+v}=-a^{u+v}[/mm]
Anders sähe es aus, wenn die Klammerung anders wäre:
[mm]\left(\red{(}-a\red{)}^{u}\right)\cdot{}(a^v)=...[/mm]
Hier gehört die -1 mit zur Basis, oben nicht!
Gruß
schachuzipus
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:47 Di 21.06.2011 | | Autor: | steve.joke |
ok, danke euch!!!
|
|
|
|
