Bestimmen von Primteiler von 2^{131} - 1

Question

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?

Comments

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.

Answer 1

Notfalls hilft ausrechnen:
2⁰ ≡ 1 mod 263
2¹ ≡ 2 mod 263
2² ≡ 4 mod 263
2⁴ ≡ 16 mod 263
2⁸ ≡ -7 mod 263
2¹⁶ ≡ 49 mod 263
2³² ≡ 34 mod 263
2⁶⁴ ≡ 104 mod 263
2¹²⁸ ≡ 33 mod 263
2¹³¹ ≡ 2³·33 ≡ 1 mod 263.

Comments

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.