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 :)
