0 Daumen
1,2k Aufrufe

Aufgabe:

Es soll gezeigt werden, dass 2^{131} - 1 eine Primteiler < 500 besitzt.


Problem/Ansatz:

Ich habe den Primteiler 263 bereits mit WolframAlpha ermittelt, doch wie zeige ich jetzt am geschicktesten, dass

263 | 2^{131} - 1    gilt?

Avatar von

Schau mal unter

https://de.m.wikipedia.org/wiki/Mersenne-Zahl

bei Teilbarkeitseigenschaften

@Fragesteller

Wo stammt denn die Aufgabe her?

Wo stammt denn die Aufgabe her?

Ist von einem Übungsblatt aus der Uni

Ich denke @jc bezog sich auf den Absatz

„Ist n eine ungerade Primzahl und q ein Primfaktor [...]“

Das würde auch Sinn machen, denn

263 ≡ 1 mod 2 * 131 gilt, weil

1 mod 262 = 1  und

263 mod 262 = 1

Daraus folgt dann, dass 263 Primfaktor von 2^{131} - 1 ist, oder? Bin mir unsicher weils ja nur eine Implikation ist.

Hallo guest, ja diesen Absatz hatte ich gedacht. Das sollte als Begründung reichen, außer wenn du diesen Satz noch beweisen musst ;)

Ich bin mir ziemlich sicher, dass ich das nicht einfach so verwenden darf, aber danke trotzdem.

Dann suche am besten nach dem Beweis für diesen Satz und übertrage ihn auf den konkreten Fall.

1 Antwort

+2 Daumen
 
Beste Antwort

Notfalls hilft ausrechnen:
20 ≡ 1 mod 263
21 ≡ 2 mod 263
22 ≡ 4 mod 263
24 ≡ 16 mod 263
28 ≡ -7 mod 263
216 ≡ 49 mod 263
232 ≡ 34 mod 263
264 ≡ 104 mod 263
2128 ≡ 33 mod 263
2131 ≡ 23·33 ≡ 1 mod 263.

Avatar von

Kannst du vielleicht erklären, wie man händisch ab

2^32 ≡ 34 mod 263

rechnet?

Ich hätte da jetzt gesagt

2^32 = 2^16 * 2^16 ≡ 49 * 49 mod 263

aber das geht doch sicherlich einfacher oder?

Also die Frage - ich formuliere sie mal anders - ist, ob

2^32 = 2^16 * 2^16 ≡ 49 * 49 mod 263 

über 49 * 49 = 2401 mod 263 = 34 ausgerechnet wird, oder ob das irgendwie effizienter geht.

Der Rechenaufwand hält sich m. E. in engen Grenzen. Viel effizienter geht das vermutlich nicht.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community