Pseudoprimzahlen

Über das folgende Verfahren hat der Mathematiker Lehmer gezeigt, das unendlich viele fermatsche Pseudoprimzahlen existieren müssen:

Man nimmt eine natürliche Zahl ${\displaystyle k\ }$, die größer, oder auch gleich Fünf ist. Mit dieser Zahl ${\displaystyle k\ }$ bildet man die beiden Zahlen ${\displaystyle 2^{k}-1\ }$ und ${\displaystyle 2^{k}+1\ }$. Von diesen beider Zahlen nimmt man jeweils einen Primfaktor. Also je eine Primzahl ${\displaystyle p\ }$ und ${\displaystyle q\ }$, so daß gilt: ${\displaystyle p\ }$ teilt ${\displaystyle 2^{k}-1\ }$ und ${\displaystyle q\ }$ teilt ${\displaystyle 2^{k}+1\ }$. Das Produkt ${\displaystyle p\cdot q}$ ist dann eine fermatsche Pseudoprimzahl zur Basis ${\displaystyle 2^{k}\ }$.

Beispiel

Man nimmt als ${\displaystyle k\ }$ die Zahl 6. ${\displaystyle 2^{6}-1=63=3^{2}\cdot 7}$ und ${\displaystyle 2^{6}+1=65=5\cdot 13}$. Wenn man sich jetzt als ${\displaystyle p\ }$ 7 wählt und als ${\displaystyle q\ }$ 5, dann bekommt man mit ${\displaystyle 5\cdot 7}$ die fermatsche Pseudoprimzahl 35.