Potenzen in Restklassengruppen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:14 Fr 16.11.2012 | | Autor: | Nisse |
| Aufgabe | | Zeige: $5 [mm] \mid 2^{2^{11}} [/mm] -1$ |
Hallo zusammen,
ich habe gerade Probleme bei der Rechnung mit Potenzen in Restklassengruppen. Kann bitte jemand überprüfen, ob ich so rechnen darf?
Alternativ zu zeigen: [mm] $2^{2^{11}} \equiv [/mm] 1 [mm] \mod [/mm] 5$
[mm] $2^4 [/mm] = 16 [mm] \equiv [/mm] 1 [mm] \mod [/mm] 5$
[mm] $2^{2^{11}} [/mm] = [mm] 2^{2^4 \cdot 2^4 \cdot 2^3} \equiv 2^{1 \cdot 1 \cdot 8} [/mm] = [mm] 2^8 [/mm] = [mm] 2^4 \cdot 2^4 \equiv [/mm] 1 [mm] \cdot [/mm] 1 = 1 [mm] \mod [/mm] 5$
|
|
| |
|
Hallo Nisse,
> Zeige: [mm]5 \mid 2^{2^{11}} -1[/mm]
> Hallo zusammen,
>
> ich habe gerade Probleme bei der Rechnung mit Potenzen in
> Restklassengruppen. Kann bitte jemand überprüfen, ob ich
> so rechnen darf?
>
> Alternativ zu zeigen: [mm]2^{2^{11}} \equiv 1 \mod 5[/mm]
>
> [mm]2^4 = 16 \equiv 1 \mod 5[/mm]
Bis hierhin alles ok, auch der richtige Ansatz.
> [mm]2^{2^{11}} = 2^{2^4 \cdot 2^4 \cdot 2^3} \equiv 2^{1 \cdot 1 \cdot 8} = 2^8 = 2^4 \cdot 2^4 \equiv 1 \cdot 1 = 1 \mod 5[/mm]
Nein, das geht nicht, bzw. hier nur zufällig.
Im Exponenten sind die Restklassen so nicht anwendbar.
Ein Beispiel: [mm] 3\equiv 8\mod{5} [/mm] ist sicher richtig.
Aber: [mm] 2^3\equiv 3\mod{5} [/mm] und [mm] 2^8\equiv 1\mod{4}, [/mm] also [mm] 2^3\not\equiv 2^8\mod{5}
[/mm]
Was Du brauchst, ist hier [mm] 2^{2^{11}}=2^{2^{2}*2^{9}}=\left(\blue{2^4}\right)^{2^9}
[/mm]
Für die blaue "16" kannst Du jetzt so weiter verfahren, wie Du wolltest.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:53 Fr 16.11.2012 | | Autor: | Nisse |
Danke, reverend, das hat geholfen!
[mm] $2^{2^{11}} [/mm] = [mm] 2^{2^2 \cdot 2^9} [/mm] = [mm] (2^4)^{2^9} \equiv 1^{2^9} [/mm] = 1 [mm] \mod [/mm] 5$
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:59 Fr 16.11.2012 | | Autor: | reverend |
Hallo nochmal,
> Danke, reverend, das hat geholfen!
>
> [mm]2^{2^{11}} = 2^{2^2 \cdot 2^9} = (2^4)^{2^9} \equiv 1^{2^9} = 1 \mod 5[/mm]
Genau so ist es richtig.
Dass übrigens [mm] 2^4\equiv 1\mod{5} [/mm] ist, folgt aus dem "kleinen Fermat" sofort. Und genau deswegen gilt im Exponenten eben auch nie der gleiche Modul wie bei der Basis. Nach Euler-Fermat müsstest Du Dir aber leicht herleiten können, was da stattdessen gilt. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:07 Fr 16.11.2012 | | Autor: | Nisse |
| Aufgabe | | Zeige: $641 [mm] \mid 2^{2^5} [/mm] +1$ |
Okay, ich hätte also [mm] $2^{5-1} \mod [/mm] 5$ nicht ausrechnen müssen!
Hast Du vielleicht noch einen Ansatz für die nächste Teilaufgabe? Ich kann über die brute-force-Primfaktorzerlegung nachvollziehen, dass die Behauptung stimmt, aber das kommt mir nicht elegant genug vor:
[mm] $2^{32} [/mm] +1 = 4294967297 = 6700417 [mm] \cdot [/mm] 641$
Ich finde keinen Zusammenhang zwischen [mm] $2^5$ [/mm] und $641$.
|
|
|
| |
|
Hallo nochmal,
na, so brachial wirst Du in einer Klausur nicht vorgehen können.
> Zeige: [mm]641 \mid 2^{2^5} +1[/mm]
> Okay, ich hätte also [mm]2^{5-1} \mod 5[/mm]
> nicht ausrechnen müssen!
Eben.
> Hast Du vielleicht noch einen Ansatz für die nächste
> Teilaufgabe? Ich kann über die
> brute-force-Primfaktorzerlegung nachvollziehen, dass die
> Behauptung stimmt, aber das kommt mir nicht elegant genug
> vor:
>
> [mm]2^{32} +1 = 4294967297 = 6700417 \cdot 641[/mm]
>
> Ich finde keinen Zusammenhang zwischen [mm]2^5[/mm] und [mm]641[/mm].
Ich so auf Anhieb auch nicht, außer dass [mm] 641=20*2^5+1 [/mm] ist.
Vermutlich sollst Du hier einfach vorführen, dass Du schonmal von "square and multiply" gehört hast:
[mm] 2^2\equiv 4\mod{641}
[/mm]
[mm] 4^2\equiv 2^{2^2}\equiv 16\mod{641}
[/mm]
[mm] 16^2\equiv 2^{2^3}\equiv 256\mod{641}
[/mm]
[mm] 256^2\equiv 2^{2^4}\equiv 154\mod{641}
[/mm]
[mm] 154^2\equiv 2^{2^5}\equiv 640\mod{641}
[/mm]
Das kriegt man ja ggf. auch zu Fuß noch hin.
Grüße
reverend
|
|
|
|
