Carmichael-Zahl

Paul Erdős vermutete bereits 1956, dass es unendlich viele Carmichael-Zahlen gibt, und dass für ihre Anzahl ${\displaystyle C(x)}$ unterhalb einer Schranke ${\displaystyle x}$ kein Exponent ${\displaystyle a<1}$ existiert mit ${\displaystyle C(x)<x^{a}}$ bei beliebig großem ${\displaystyle x}$. Das haben jedoch erst Carl Pomerance, William Robert Alford und Andrew Granville im Jahr 1994 bewiesen.[2] Ihr Beweis liefert die untere Abschätzung der Anzahlfunktion ${\displaystyle C(x)>x^{2/7}}$ für alle hinreichend großen ${\displaystyle x}$. Die Anzahl der Carmichael-Zahlen wächst also asymptotisch.

Glyn Harman verbesserte dieses Ergebnis im Jahr 2005 zu ${\displaystyle C(x)>x^{0.33}}$ für hinreichend große ${\displaystyle x}$.[3] Rechnungen bis ${\displaystyle x=10^{15}}$ legen ein Wachstum mit der unteren Abschätzung ${\displaystyle x^{1/3}}$ nahe, so dass Daniel Shanks überzeugt war, ${\displaystyle x^{1/2}}$ sei eine sehr sichere obere Abschätzung für die Anzahlfunktion. Er ließ sich jedoch durch Diskussion mit den genannten Autoren davon überzeugen, dass die Vermutung von Erdös der wahren Asymptotik entsprechen könnte.

Im Jahre 2002 publizierten Granville und Pomerance eine Analyse der Verteilung der Carmichael-Zahlen anhand weiterer plausibler und begründeter Vermutungen, die ein Ergebnis (keinen Beweis) sowohl entsprechend dem Argument von Erdős als auch im Einklang mit den empirischen Resultaten für kleine ${\displaystyle x}$ lieferte und so den von Shanks hervorgehobenen scheinbaren Widerspruch auflöste.[4]

2021 hat der Jugendliche Daniel Larsen gezeigt, dass in jedem Intervall zwischen ${\displaystyle x}$ und ${\displaystyle x+{\frac {x}{(\log x)^{\frac {1}{2+\delta }}}}}$ mindestens ${\displaystyle e^{\frac {\log x}{(\log \log x)^{2+\delta }}}}$ für ${\displaystyle \delta >0}$ und hinreiched große ${\displaystyle x}$ verschiedene Carmichael-Zahlen existieren.[5]

Die Tabelle zeigt die Carmichael-Zahlen (Folge A002997 in OEIS) unterhalb 100.000 und bringt sie mit der Carmichael-Funktion ${\displaystyle \lambda }$ und der Eulerschen ${\displaystyle \varphi }$-Funktion in Beziehung.

Carmichael-Zahl ${\displaystyle n}$	Primfaktoren	${\displaystyle \lambda (n)}$	${\displaystyle (n-1)/\lambda (n)}$	${\displaystyle \varphi (n)}$	${\displaystyle \varphi (n)/\lambda (n)}$
561	3⋅11⋅17	80	7	320	4
1105	5⋅13⋅17	48	23	768	16
1729	7⋅13⋅19	36	48	1296	36
2465	5⋅17⋅29	112	22	1792	16
2821	7⋅13⋅31	60	47	2160	36
6601	7⋅23⋅41	1320	5	5280	4
8911	7⋅19⋅67	198	45	7128	36
10585	5⋅29⋅73	504	21	8064	16
15841	7⋅31⋅73	360	44	12960	36
29341	13⋅37⋅61	180	163	25920	144
41041	7⋅11⋅13⋅41	120	342	28800	240
46657	13⋅37⋅97	288	162	41472	144
52633	7⋅73⋅103	1224	43	44064	36
62745	3⋅5⋅47⋅89	2024	31	32384	16
63973	7⋅13⋅19⋅37	36	1777	46656	1296
75361	11⋅13⋅17⋅31	240	314	57600	240

Der böhmische Mathematiker Václav Šimerka hat die ersten 6 Carmichael-Zahlen bereits 1885 gefunden, was jedoch unbemerkt geblieben ist.[6][7]

Um eine Carmichael-Zahl zu erkennen, führt man entweder eine Faktorisierung durch, oder man wendet den kleinen fermatschen Satz auf die Zahl an, wobei man für die Basen, die nicht auf eine Primalität weisen und die bei Primzahlen nicht vorkommen, auf Teilbarkeit testen muss.

Jack Chernick fand 1939 ein relativ einfaches System, um Carmichael-Zahlen zu konstruieren:[8]

Falls die drei Zahlen ${\displaystyle 6m+1,12m+1}$ und ${\displaystyle 18m+1}$ Primzahlen sind, so ist ihr Produkt ${\displaystyle (6m+1)(12m+1)(18m+1)}$ eine Carmichael-Zahl.[9]

Beispielsweise hat 1729 = 7·13·19 diese Struktur. Interessant ist, dass die Carmichael-Zahl 172081 = 31·61·91 die Bedingung „fast erfüllt“: 91 ist nicht prim, aber fermatsche Pseudoprimzahl zur Basis 3.

Gérard Michon fand eine ähnliche Methode, um Carmichael-Zahlen zu konstruieren:

Wenn ${\displaystyle m\equiv 326{\pmod {616}}}$ und die drei Zahlen ${\displaystyle 7m+1,8m+1}$ und ${\displaystyle 11m+1}$ Primzahlen sind, so ist ihr Produkt ${\displaystyle (7m+1)(8m+1)(11m+1)}$ eine Carmichael-Zahl.

${\displaystyle m}$ muss dann durch 3 teilbar sein, da sonst einer der drei Faktoren durch 3 teilbar ist.
Beispiel: für ${\displaystyle m=24966}$ sind die drei Zahlen ${\displaystyle 174763,199729}$ und ${\displaystyle 274627}$ prim und ihr Produkt ist eine Carmichael-Zahl.
Eine mit dieser Methode erzeugte Carmichael-Zahl mit 1000 Stellen ist

${\displaystyle (12936\cdot 10^{329}-59827428149)\cdot (14784\cdot 10^{329}-68374203599)\cdot (20328\cdot 10^{329}-94014529949).}$

Basierend auf einer Idee von Paul Erdős können mit Hilfe gruppentheoretischer Überlegungen und moderner Computer-Algorithmen weitaus größere Carmichael-Zahlen konstruiert werden. 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.[10]