Zum Inhalt springen

Pseudoprimzahlen: Catalan-Pseudoprimzahlen

Aus Wikibooks

Alle ungeraden Primzahlen erfüllen die Kongruenz

,  

wobei die m-te Catalan-Zahl ist. Catalan-Pseudoprimzahlen sind zusammengesetzte Zahlen, die diese Kongruenz erfüllen. Die einzigen bekannten Catalan-Pseudoprimzahlen sind 5907, 1194649, und 12327121; die beiden letzten sind die Quadrate der Wieferich-Primzahlen. Allgemein gilt: alle Quadrate der Wieferich-Primzahlen (zur Basis 2) sind Catalan-Pseudoprimzahlen.

Catalan-Zahlen können wie folgt ausgedrückt werden:

 

Mit eingesetzt lautet die Kongruenz

bzw.  
.  


Da die Berechnung von für große bzw. sehr aufwendig ist, eignet sie sich nicht für Primzahltests.

Zum Vergleich: nach dem Satz von Wilson gilt

 

Also ist jedes , das diese Kongruenz erfüllt, eine Primzahl (der Umkehrschluss gilt in diesem Fall). Ein Test nach diesem Kriterium wäre auch schon aufwendiger als Probedivisionen und würde ähnlich viele Multiplikationen wie die Berechnung der Catalan-Zahl erforden. Außerdem kann jedes Produkt modulo berechnet werden, um Berechnungen mit sehr großen Zahlen () zu vermeiden; dann kann der Test auch abgebrochen und damit verkürzt werden, wenn ist.