Ist 2^63 +1 eine Primzahl?

Question

Wie zeigt man, ob

2⁶³+1 eine Primzahl ist??

Answer 1

Nein.

2^63 + 1 = 9223372036854775809 = 3^3·19·43·5419·77158673929

Comments

Danke für deine Antwort! Aber die Frage kann in meiner mündl. Prüfung auftauchen, wo ich sowas natürlich nicht ohne TR zeigen kann... Gibt es da irgendeinen Trick, wie man das erkennen kann??

VG

---

Such mal nach "Fermatsche Primzahlen". Das sollte dir die Augen öffnen. Vermutlich habt ihr das auch irgendwo im Skript stehen.

---

Hey!

Ja, ich habe die Lösung gefunden :)

Also wenn ich 2⁶³+1 habe, dann kann ich mit Hilfe der Fermat'schen Zahlen zeigen, ob 2⁶³+1 eine Primzahl ist, oder nicht.

Denn die Fermat'schen Zahlen beruhen auf der Grundlage, dass man herausgefunden hat, dass 2^m +1 genau dann eine Primzahl sein kann, wenn m als eine Zweierpotenz dargestellt werden kann.

Das heißt eine Zahl der Form 2^m+1 ist höchstens dann eine Primzahl, wenn sie als 2^{2^n} +1 dargestellt werden kann.

Hier ist m =63 und da 8² = 64 also 2*2*2*2*2*2 = 2⁶ und 32 = 2*2*2*2*2 = 2⁵ ist, kann ich 63 nicht als Zweierpotenz darstellen und somit ist 2⁶³+1 auch keine Primzahl!

Wichtig ist aber, dass nur die Voraussetzung gilt, das 2^{2^n} +1 nur eine Primzahl sein kann, aber nicht sein muss. Denn die 5-te Fermat'sche Zahl ist keine Primzahl, sondern eine zusammengesetzte Zahl.

Falls ich etwas falsch erklärt habe, freue ich mich über eure Anmerkungen :)

---

Das ist so richtig.

Answer 2

$$2^{63}+1 \equiv 2^1 +1 \equiv 0 \mod 3$$, also nicht prim nach dem kleinen Fermat.