Eine zusammengesetzte ganze Zahl n, so dass für jede zu n teilerfremde ganze Zahl a gilt: a^{n−1} ≡ 1 (mod n); n verhält sich also bezüglich der Fermat-Kongruenz wie eine Primzahl für alle teilerfremden Basen.

Prinzip

Erfasst zusammengesetzte Moduli, die den Fermat-Primalitätstest für jede teilerfremde Basis bestehen; äquivalent durch Korselt-ähnliche Bedingungen beschreibbar (quadratfrei und für jeden primen Teiler p gilt p−1 | n−1).

Demonstration

Das kleinste Beispiel ist 561 = 3·11·17; für jedes a, das zu 561 teilerfremd ist, gilt a^{560} ≡ 1 (mod 561), daher ist 561 eine Carmichael-Zahl und würde einen einfachen Fermat-Test beständig täuschen.

Fehlanwendung

Alle Fermat-Pseudoprimzahlen (die die Kongruenz nur für einige Basen erfüllen) als Carmichael-Zahlen bezeichnen oder annehmen, eine Zahl, die die Kongruenz für viele kleine Basen erfüllt, sei automatisch Carmichael, ohne die Bedingung für alle teilerfremden Basen zu prüfen.

Konsequenz

Belegt die Grenzen naiver Primalitätstests: Das Vorhandensein von Carmichael-Zahlen erfordert stärkere deterministische oder probabilistische Tests; ihre Verteilung beeinflusst die Verlässlichkeit von basenbasierten Tests.

Umkehrung

Primzahlen sind die Umkehr: Sie erfüllen dieselbe Fermat-Kongruenz, sind aber tatsächlich prim; eine andere Umkehr sind zusammengesetzte Zahlen, die für einige teilerfremde Basen scheitern und daher leicht durch Fermat-Tests erkannt werden.

Abgrenzung

Definiert nur für zusammengesetzte ganze Zahlen; verlangt, dass die Kongruenz für jede zu n teilerfremde Zahl gilt. Schließt Fermat-Pseudoprimzahlen aus, die die Kongruenz nur für eine Teilmenge von Basen erfüllen, und schließt Primzahlen aus.

Semantische Spannung

Steht im Spannungsfeld zu Begriffen wie Fermat-Pseudoprimzahl, Euler-Pseudoprimzahl und starker Pseudoprimzahl; die Spannung besteht zwischen universeller Basen-Täuschung (Carmichael) und Täuschung für bestimmte Basen (Pseudoprimzahlen).

Synthese

Eine Carmichael-Zahl ist ein zusammengesetztes, quadratfreies n, dessen multiplikative Struktur die Fermat-Kongruenz für jede teilerfremde Basis erzwingt: ein universeller, basisunabhängiger Pseudoprimzahl-Beispiel, das einfache Primalitätstests entlarvt.