Fermatsche Pseudoprimzahl

Eine natürliche Zahl n wird Fermatsche Pseudoprimzahl (zur Basis a) genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu n teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz

${\displaystyle a^{n-1}\equiv 1\mod n}$

für die zu n teilerfremde Zahl a erfüllt ist.

Anders ausgedrückt muss n die Differenz ${\displaystyle a^{n-1}-1}$ teilen.

Zum Beispiel ist 341 eine Fermatsche Pseudoprimzahl zur Basis 2, da 341 ein Teiler von ${\displaystyle 2^{340}-1}$, aber aufgrund 341=11·31 nicht prim ist.