+1 Daumen
1,1k Aufrufe
Ich habe gelesen, dass Euler bewiesen haben soll, dass 2^31 - 1 eine Primzahl ist. Welche Rechentechniken hat er genutzt, um dies so früh in der Geschichte zu beweisen? Werden Primzahlen heute nicht per Computer berechnet bzw. nachgewiesen?

Wisst ihr, ob Euler ein Team von Mathematikern hatte, die ihm dabei halfen?
Avatar von

2 Antworten

0 Daumen
2^31 -1 = 2147483647

Das sind also nur knapp 2.1 Milliarden.

Das können wir doch locker durch alle Primzahlen teilen. PS. Dafür brauche ich aber nur alle Primzahlen bis zur Wurzel aus 2147483647 probieren und das wären 46341. Die Menge an Primzahlen ist also durchaus überschaubar und das ist nur ein klein wenig Arbeit.
Avatar von 477 k 🚀
0 Daumen

Es handelt sich hier um eine Mersenne-Primzahl, also eine Zahl der Form 2^31 - 1.

Euler hat kein Team an Mathematikern benötigt, um die Zahl als Primzahl nachzuweisen. Er hat die Berechnung vereinfacht und konnte die Zahl so als Primzahl bestimmen. 

Wenn q ein Primfaktor der Form 2^p - 1 ist, dann gilt 2^p ≡ 1 (mod q) und folglich p|q-1, also q ≡ 1(mod p). Das bedeutet, wenn p=31 ist, dann musst du etwa 31 Primzahlen prüfen.

Du kannst auch schlussfolgern, dass q ≡ ±1(mod 8) gilt, da 2 ≡ 2^{p+1} ≡ ( 2(p+1)/2 )^2 (mod q) 

Wie du siehst, muss 2 ein Quadrat modulo (Quadratischer Rest) q sein. So werden die möglichen Werte für q weiter reduziert!

Das bedeutet also: q ≡ 63 oder q ≡ 1(mod 8 · 31 = 248). Die kleinstmögliche Lösung für q ist hier 311. Die nächste ist q = 1303. Wie du siehst, reduziert das sehr schön die Anzahl an Überprüfungen, die wir für die Primzahl vornehmen müssen. 

Mit n=2^31 - 1 musst du nur die Primfaktoren bis √(2^31) - 1 < 46341 prüfen. Grob geschätzt erwarten wir 70 Primzahlen in diesem Bereich, die die o.g. Bedingungen erfüllen (exakt sind es 84).

---

Im Übrigen ist es nicht notwendig, 2^31 - 1 mit Division durch q zu prüfen, also um festzustellen, ob es eine Primzahl ist. Stattdessen kannst du 2^32 (mod q) mit wiederholtem Quadrieren berechnen. Nachfolgend ein Beispiel für q = 311:

2^2 ≡ 4 (mod 311)
2^4 ≡ 4^2 ≡ 16 (mod 311)
2^8 ≡ 16^2 ≡ 256 ≡ -55 (mod 311)
2^16 ≡ (-55)^2 ≡ -85 (mod 311)
2^32 ≡ (-85)^2 ≡ 72 (mod 311)

An 2^32 ≢ 2 (mod 311) erkennen wir, dass 2^31 - 1 nicht durch 311 teilbar ist :)

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
0 Daumen
1 Antwort
0 Daumen
0 Antworten
0 Daumen
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community