Pseudoprimzahlen: Catalan-Pseudoprimzahlen

Alle ungeraden Primzahlen $\ n$ erfüllen die Kongruenz

(-1)^{\frac {n-1}{2}}\cdot C_{\frac {n-1}{2}}\equiv 2{\pmod {n}}

,

wobei $C_{m}$ 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:

C_{m}={\frac {1}{m+1}}{2m \choose m}={\frac {(2m)!}{(m+1)!\,m!}}=\prod \limits _{k=2}^{m}{\frac {m+k}{k}}\qquad {\text{mit }}m\geq 0.

Mit $m={\frac {n-1}{2}}$ eingesetzt lautet die Kongruenz

(-1)^{\frac {n-1}{2}}\cdot C_{\frac {n-1}{2}}=(-1)^{\frac {n-1}{2}}\cdot {\frac {(n-1)!}{({\frac {n+1}{2}})!\,({\frac {n-1}{2}})!}}\equiv 2{\pmod {n}}

bzw.

(-1)^{\frac {n-1}{2}}\cdot {\frac {2}{n+1}}{n-1 \choose {\frac {n-1}{2}}}=\prod \limits _{k=2}^{\frac {n-1}{2}}{\frac {m+k}{k}}\equiv 2{\pmod {n}}

.

Da die Berechnung von $C_{m}$ für große $m\$ bzw. $n$ sehr aufwendig ist, eignet sie sich nicht für Primzahltests.

Zum Vergleich: nach dem Satz von Wilson gilt

(p-1)!\equiv -1{\pmod {p}}\Longleftrightarrow p\ \mathrm {ist} \ \mathrm {prim.}

Also ist jedes $p$ , 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 $p$ berechnet werden, um Berechnungen mit sehr großen Zahlen ( $>n^{2}$ ) zu vermeiden; dann kann der Test auch abgebrochen und damit verkürzt werden, wenn $k!\equiv 0{\pmod {n}}$ ist.