Carmichael-Zahl

Begriff und Bedeutung

Eine Carmichael-Zahl ist eine zusammengesetzte natürliche Zahl n, die sich beim kleinen fermatschen Satz für jede zu n teilerfremde Basis a wie eine Primzahl verhält. „Teilerfremd“ bedeutet, dass a und n keinen gemeinsamen Primfaktor besitzen. Genau dann gilt

a^(n−1) ≡ 1 (mod n).

Die Schreibweise „mod n“ bedeutet, dass a^(n−1) bei Division durch n den Rest 1 lässt. Carmichael-Zahlen sind damit fermatsche Pseudoprimzahlen zu allen teilerfremden Basen. Sie sind wichtig für die Untersuchung von Primzahltests, weil ein einfacher Test auf Grundlage des kleinen fermatschen Satzes sie fälschlich als Primzahlen einstufen kann.

Jede Carmichael-Zahl ist das Produkt von mindestens drei verschiedenen Primzahlen. Die kleinste ist 561 = 3·11·17. Für jede Basis a, die keinen Primfaktor mit 561 gemeinsam hat, gilt a^560 ≡ 1 (mod 561). Für nicht teilerfremde Basen muss die Kongruenz nicht gelten: Beispielsweise ist 3^560 ≡ 375 (mod 561), 11^560 ≡ 154 (mod 561) und 17^560 ≡ 34 (mod 561).

Kennzeichen und Prüfung

Jede Carmichael-Zahl ist quadratfrei, also durch kein Quadrat einer Primzahl teilbar, und besitzt mindestens drei Primfaktoren. Der 1899 von Alwin Reinhold Korselt bewiesene Satz liefert ein genaues Erkennungsmerkmal: Eine natürliche Zahl n ist genau dann eine Carmichael-Zahl, wenn sie nicht prim und quadratfrei ist und für jeden Primteiler p von n die Zahl p−1 ein Teiler von n−1 ist.

Wegen der Identität

n−1 = n/p − 1 + (p−1)·n/p

gilt für jeden Primteiler p außerdem

n−1 ≡ n/p − 1 (mod p−1).

Daher kann die Teilbarkeitsbedingung gleichwertig so formuliert werden: Für jeden Primteiler p von n teilt p−1 die Zahl n/p−1. Kennt man die Primfaktorzerlegung, lässt sich eine Carmichael-Zahl mit diesem Satz einfach erkennen.

Bei großen unzerlegten Zahlen ist die Entscheidung schwieriger. In der Praxis hilft, dass es keine starken Carmichael-Zahlen gibt: Zu jeder Carmichael-Zahl n lässt sich eine zu n teilerfremde Basis a finden, für die die bei Primzahlen geltende Beziehung a^((n−1)/2) ≡ (a/n) (mod n) verletzt ist; (a/n) bezeichnet dabei das Jacobi-Symbol. Zur Erkennung kann man deshalb entweder die Zahl faktorisieren oder den kleinen fermatschen Satz anwenden und bei auffälligen Basen zusätzlich Teilbarkeit prüfen.

Vorkommen und Anzahl

Es gibt unendlich viele Carmichael-Zahlen. Paul Erdős vermutete 1956 darüber hinaus ein sehr schnelles Wachstum ihrer Anzahl C(x) unterhalb einer Schranke x: Nach seiner Vermutung gibt es keinen Exponenten a < 1, für den C(x) < x^a bei beliebig großem x gilt.

William Robert Alford, Andrew Granville und Carl Pomerance bewiesen 1994 die Unendlichkeit und erhielten für alle hinreichend großen x die untere Schranke C(x) > x^(2/7). Glyn Harman verbesserte sie 2005 zu C(x) > x^0,33.

Berechnungen bis x = 10^15 deuteten dagegen auf ein Wachstum mit der unteren Abschätzung x^(1/3) hin. Daniel Shanks hielt deshalb x^(1/2) zunächst für eine sehr sichere obere Abschätzung, ließ sich später aber davon überzeugen, dass Erdős’ Vermutung die tatsächliche Asymptotik beschreiben könnte. Granville und Pomerance veröffentlichten 2002 auf Grundlage weiterer plausibler, aber nicht bewiesener Annahmen eine Analyse, die sowohl zu Erdős’ Argument als auch zu den Beobachtungen für kleine x passt.

Daniel Larsen zeigte 2021, dass für δ > 0 und hinreichend große x in jedem Intervall von x bis x + x/(log x)^(1/(2+δ)) mindestens e^(log x/(log log x)^(2+δ)) verschiedene Carmichael-Zahlen liegen.

Kleine Beispiele

Unter 100.000 gibt es 16 Carmichael-Zahlen:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973 und 75361.

Die meisten dieser Zahlen besitzen drei Primfaktoren. Beispiele sind 1105 = 5·13·17, 1729 = 7·13·19 und 29341 = 13·37·61. Es kommen aber auch Zahlen mit vier Primfaktoren vor, etwa 41041 = 7·11·13·41, 62745 = 3·5·47·89, 63973 = 7·13·19·37 und 75361 = 11·13·17·31.

Die im Artikel aufgeführte Tabelle setzt diese Zahlen außerdem zur Carmichael-Funktion λ und zur eulerschen φ-Funktion in Beziehung. Für 561 gilt beispielsweise λ(561) = 80, (561−1)/λ(561) = 7, φ(561) = 320 und φ(561)/λ(561) = 4. Bei 1729 lauten die entsprechenden Werte 36, 48, 1296 und 36.

Konstruktionsmethoden

Jack Chernick beschrieb 1939 eine einfache Konstruktion: Sind 6m+1, 12m+1 und 18m+1 sämtlich Primzahlen, dann ist

(6m+1)(12m+1)(18m+1)

eine Carmichael-Zahl. Für m = 1 entsteht 1729 = 7·13·19. Die Zahl 172081 = 31·61·91 erfüllt das Schema nur beinahe, weil 91 nicht prim ist, sondern eine fermatsche Pseudoprimzahl zur Basis 3.

Eine Gérard Michon zugeschriebene ähnliche Methode lautet: Falls m ≡ 326 (mod 616) gilt und 7m+1, 8m+1 sowie 11m+1 Primzahlen sind, ist ihr Produkt eine Carmichael-Zahl. Dabei muss m durch 3 teilbar sein, da andernfalls einer der drei Faktoren durch 3 teilbar wäre. Für m = 24966 sind 174763, 199729 und 274627 prim; ihr Produkt ist daher eine Carmichael-Zahl. Der Artikel kennzeichnet diese Zuschreibung und Methode jedoch als nicht hinreichend durch Publikationen belegt und merkt an, dass sie möglicherweise nicht von Michon allein stammt.

Als Beispiel für diese Methode wird außerdem eine Carmichael-Zahl mit 1000 Stellen angegeben:

(12936·10^329−59827428149)·(14784·10^329−68374203599)·(20328·10^329−94014529949).

Neuere Konstruktionen beruhen auf einer Idee von Paul Erdős und verbinden gruppentheoretische Überlegungen mit modernen Computer-Algorithmen. Im Juli 2012 wurde nach weitgehendem Ausreizen bereits bekannter Verfahren eine Carmichael-Zahl mit mehr als 10 Milliarden Primfaktoren und fast 300 Milliarden Dezimalstellen vorgestellt.