641 teilt 2^32 + 1 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen sie durch Kongruenzrechnung, dass [mm] 2^{32} [/mm] + 1 durch 641 teilbar ist.
Hinweis: Kombinieren Sie die Gleichungen [mm] 641=5^{4}+2^{4}=5*2{7} [/mm] + 1 |
Hallo,
beginne gerade mit Algebra und Zahlentheorie und würde mich über einen Tipp freuen, habe das mit der modularen Arithmetik noch nicht so richtig verinnerlicht.
Ich habe die Aufgabe mal umgeschrieben in
zu zeigen: [mm] 2^{32}mod641=640mod641
[/mm]
es ist: [mm] 641=5*2^{7}+1\equiv0mod641 [/mm]
[mm] \Rightarrow 5*2^{7}\equiv640mod641
[/mm]
wenn ich jetzt also zeigen könnte, dass [mm] 5*2^{7}mod641\equiv2^{32}mod641 [/mm] gilt, wäre ich fertig. aber wie mag das gehen?
gruß
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 04:38 Mo 31.10.2011 | | Autor: | reverend |
Hallo karlhungus,
zur Zeit ist Deine Frage von 12 Mitgliedern und 7 Gästen insgesamt 31mal gelesen worden. Ich bin dabei eines der Mitglieder und rufe die Frage zum dritten Mal auf. Allerdings bin ich so ratlos wie vorher schon.
Der Tipp scheint nicht sehr hilfreich zu sein.
Das ist ja oft so, bis man die gemeinte (also vom Fragensteller beabsichtigte) Lösung findet.
Jedenfalls ist der Tipp für "Anfänger" nicht gerade sehr zielführend.
Warten wir also ab, ob jemand den nötigen Einfall hat, wie der Tipp zu verwerten ist.
Es ist bestimmt kein Wunder und kein Schandmal, dass Du die Aufgabe nicht so leicht alleine lösen konntest. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:30 Mo 31.10.2011 | | Autor: | statler |
> Zeigen sie durch Kongruenzrechnung, dass [mm]2^{32}[/mm] + 1 durch
> 641 teilbar ist.
> Hinweis: Kombinieren Sie die Gleichungen
> [mm]641=5^{4}+2^{4}=5*2^{7}[/mm] + 1
> Hallo,
> beginne gerade mit Algebra und Zahlentheorie und würde
> mich über einen Tipp freuen, habe das mit der modularen
> Arithmetik noch nicht so richtig verinnerlicht.
> Ich habe die Aufgabe mal umgeschrieben in
> zu zeigen: [mm]2^{32}mod641=640mod641[/mm]
>
> es ist: [mm]641=5*2^{7}+1\equiv0mod641[/mm]
> [mm]\Rightarrow 5*2^{7}\equiv640mod641[/mm]
>
> wenn ich jetzt also zeigen könnte, dass
> [mm]5*2^{7} mod641 \equiv 2^{32} mod641[/mm] gilt, wäre ich fertig.
> aber wie mag das gehen?
Hallo, guten Morgen!
Ich bin ganz übergerascht, daß der reverend das nicht schlagartig weiß.
Es ist nämlich [mm] 5^4 \equiv -2^4 [/mm] (641)
und 5 [mm] \cdot 2^7 \equiv [/mm] -1 (641) sagt der Tip.
Wenn ich die 2. Kongruenz hoch 4 nehme, kriege ich
[mm] 5^4 \cdot 2^{28} \equiv [/mm] 1 (641)
und jetzt setze ich noch die erste ein, dann steht da
[mm] -2^4 \cdot 2^{28} \equiv [/mm] 1 (641)
und das isses im wesentlichen.
Diese Entdeckung stammt übrigens von Euler, Leute kleineren Kalibers erkennen das nicht auf den ersten Blick.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:40 Mo 31.10.2011 | | Autor: | karlhungus |
Vielen Dank.
Sowohl für die aufmunternden Worte, als auch für die Lösung, auf die ich durch Tüfteln bestimmt nicht gekommen wäre. Zumal die Übung heute um 12 ist 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:10 Mo 31.10.2011 | | Autor: | reverend |
Moin statler,
sach ich doch - hinterher versteht man den Tipp und denkt: das ist aber einfach.
Sehr schick.
Im übrigen hatte ich schon immer den Eindruck, dass Herr Euler und ich nicht die gleiche Munition verwenden.
Herzliche Grüße
reverend
|
|
|
|
