Der Lucas-Test für Mersennsche Primzahlen
Der Satz von Wilson, der ja eine Charakterisierung der Primzahlen darstellt, scheint zunächst als Primzahltest vielversprechend zu sein.Da die Berechnung der Fakultät jedoch viel zu aufwändig ist, scheideter als praktischer Test aus.
Der kleine Satz von Fermat lautet für primes p und eine natürliche Zahl a, die kein Vielfaches von p ist, dass erfüllt ist. Allerdings möchten wir an dieser Stelle anmerken, dass die Umkehrung dieses Satzes nicht gilt – es gibt zerlegbare Zahlen N und a ≥ 2 mit . Lucas entdeckte im Jahre 1876 eine richtige Umkehrung von Fermats kleinem Satz. Diese besagt:
Das Problem dieses zunächst perfekt aussehenden Tests: Er benötigt aufeinander folgende Multiplikationen mit a und das Finden der Reste modulo N – dies sind zuviele Operationen.
Lucas gab 1891 den folgenden Test an:
Für die Fermatschen Primzahlen reicht es aus, im Lucas Test die Zahl a = 3 zu überpriifen:
