eine zusammengesetzte Zahl n mit der Eigenschaft \begin{eqnarray}\begin{array}{cccc}{2}^{n}\equiv 2\,\mathrm{mod}\,n. & & & (1)\end{array}\end{eqnarray}

Ist allgemeiner a eine natürliche Zahl ≥ 2, und erfüllt n die Kongruenz \begin{eqnarray}\begin{array}{cccc}{a}^{n}\equiv a\,\mathrm{mod}\,n, & & & (2)\end{array}\end{eqnarray}

so nennt man n eine Pseudoprimzahl zur Basis a oder einfach a-Pseudoprimzahl.

Erfüllt die zusammengesetzte Zahl n die Kongruenz (1) für alle a ∈ ℕ mit a ≥ 2, so heißt n auch absolute Pseudoprimzahl oder Carmichael-Zahl.

Die Motivation, solche Zahlen zu betrachten, kommt vom kleinen Satz von Fermat: Danach erfüllt eine Primzahl n = p die Kongruenz (2) für jede natürliche Zahl a ≥ 2.

Nach Dickson [1] glaubte Leibniz folgende Behauptung bewiesen zu haben:

(Z) Eine natürliche Zahl n ist genau dann eine Primzahl, wenn sie die Kongruenz (1) erfüllt.

Manchmal wird diese Behauptung der chinesischen Mathematik aus der Zeit von Konfuzius zugeschrieben; daher heißt die Kongruenz (1) auch Chinesische Kongruenz. Wie Ribenboim in seinem Buch [2] nachweist, beruht dies jedoch auf einem Übersetzungsfehler.

Die Behauptung (Z) ist falsch: Sarrus bewies 1819 die Kongruenz \begin{eqnarray}{2}^{341}\equiv 2\,\mathrm{mod}\,341,\end{eqnarray}

und fand damit die erste Pseudoprimzahl 341 = 11 · 31.

Anfang des 20. Jahrhunderts wurden verschiedene Methoden entwickelt, u. a. von Cipolla und Lehmer, unendliche Folgen von Pseudoprimzahlen zu erzeugen. Erdős bewies 1949, daß es zu jedem k ≥ 2 unendlich viele Pseudoprimzahlen gibt, von denen jede das Produkt von k verschiedenen Primzahlen ist.

Interessant ist noch das folgende offene Problem:

(a) Gibt es unendlich viele ganze Zahlen n > 1 mit 2ⁿ ≡ 2 mod n² ?

Rotkiewicz zeigte 1965, daß dieses Problem zu jedem der folgenden äquivalent ist:

(b) Gibt es unendlich viele Pseudoprimzahlen, die zugleich Quadratzahlen sind?

(c) Gibt es unendlich viele Primzahlen p mit 2^p ≡ 2 mod p² ?

[1] Dickson, L. E.: History of the Theory of Numbers, Volume I. New York, 1971.
[2] Ribenboim, P.: The New Book on Prime Number Records. New York, 1996.