~2026-24828-43: Die Referenz von Grandville/Pomerance ist auch die Quelle für die Aussage, dass Shanks sich überzeugen ließ.

2026-04-23T09:36:37Z

Die Referenz von Grandville/Pomerance ist auch die Quelle für die Aussage, dass Shanks sich überzeugen ließ.

Neue Seite

[[Datei:Robert Daniel Carmichael.gif|mini|alt=Robert Daniel Carmichael, circa 1920|Robert Daniel Carmichael, circa 1920]]
'''Carmichael-Zahlen''' sind [[Fermatsche Pseudoprimzahl|fermatsche Pseudoprimzahlen]] zu [[Teilerfremdheit|teilerfremden]] Basen. Fermatsche Pseudoprimzahlen sind natürliche Zahlen, die wie [[Primzahl]]en aussehen, aber keine sind, denn sie genügen dem lange Zeit gültigen [[Primzahltest]], dem 1640 aufgestellten [[Kleiner fermatscher Satz|kleinen fermatschen Satz]]. Carmichael-Zahlen sind das Produkt von mindestens drei Primzahlen ([[Primfaktorzerlegung]]), davon keine doppelt. Die kleinste Carmichael-Zahl ist die Zahl 561 = 3·11·17.

Carmichael-Zahlen spielen eine Rolle bei der Analyse von Primzahltests.

Sie sind benannt nach dem Mathematiker [[Robert Daniel Carmichael]], der sie 1910 beschrieben hat.

== Definition ==
'''Definition''' 
Eine zusammengesetzte natürliche Zahl <math>n</math> heißt '''Carmichael-Zahl''', falls für alle zu <math>n</math> teilerfremden Zahlen <math>a ,</math> hier „Basis“ genannt, die folgende Kongruenz erfüllt ist:
:<math> a^{n-1} \equiv 1 \pmod n</math> .

'''Beispiel''' 
<math>n := 561 = 3 \cdot 11 \cdot 17</math> ist die kleinste Carmichael-Zahl.
Für alle Basen <math>a ,</math> die keinen Primfaktor mit <math>n </math> gemeinsam haben, gilt nämlich <math> a^{n-1} \equiv 1 \pmod n</math>.

561 ist durch 3, 11, 17, 33, 51 und 187 teilbar. Für diese Teiler gilt die Kongruenz jedoch nicht:
3560 ≡ 375 mod 561, 11560 ≡ 154 mod 561, 17560 ≡ 34 mod 561 usw.

== Eigenschaften ==
Jede Carmichael-Zahl ist [[quadratfrei]] und das Produkt mindestens dreier Primzahlen.

Zwar gibt es Methoden zur Erzeugung von Carmichael-Zahlen, aber es ist problematisch – gerade bei großen Zahlen – zu erkennen, ob es sich bei einer Zahl um eine Carmichael-Zahl handelt. Diese Schwierigkeit haben die Carmichael-Zahlen mit den Primzahlen gemeinsam. In der Praxis wird das Unterscheiden einer unzerlegten Carmichael-Zahl von einer Primzahl dadurch erleichtert, dass es keine ''starken'' Carmichael-Zahlen gibt.<ref>{{Literatur |Autor=[[Derrick Henry Lehmer]] |Titel=Strong Carmichael numbers |Sammelwerk=Journal of the Australian Mathematical Society |Band=21 |Nummer=4 |Datum=1976 |Seiten=508–510 |DOI=10.1017/S1446788700019364}}</ref> Man kann zu jeder Carmichael-Zahl <math>n</math> stets eine teilerfremde Basis <math>a</math> finden, so dass die Primzahleigenschaft <math>a^{(n-1)/2} \equiv \left(\tfrac{a}{n}\right) \pmod n</math> (unter Verwendung des [[Jacobi-Symbol]]s und der Schreibweise für [[Kongruenz (Zahlentheorie)|Kongruenz]]) verletzt ist.

== Satz von Korselt ==
Bereits im Jahr 1899 bewies [[Alwin Reinhold Korselt]] folgenden Satz:
:Eine natürliche Zahl <math>n</math> ist genau dann eine Carmichael-Zahl, wenn sie nicht prim und quadratfrei ist und für alle ihre Primteiler <math>p</math> gilt, dass <math>p - 1</math> die Zahl <math>n - 1</math> teilt.


'''Verschärfung''' 
Aufgrund der Identität <math>n-1 = \frac{n}{p} - 1 + (p-1)\frac{n}{p}</math> gilt für jeden Primteiler <math>p</math> einer natürlichen Zahl <math>n</math>:
:<math>n-1\equiv \frac{n}{p} - 1\pmod {p-1} .</math>

Somit lässt sich der zweite Teil von Korselts Satz auch formulieren als:
Eine Zahl <math>n</math> ist genau dann eine Carmichael-Zahl, wenn für jeden ihrer Primteiler gilt: <math>p-1</math> teilt <math>\frac{n}{p} - 1</math>.

Dank dem ''Satz von Korselt'' ist es einfach, eine Carmichael-Zahl zu erkennen, wenn man ihre [[Primfaktorzerlegung]] kennt. Carmichael hat dann 1910 mit 561 die erste Zahl gefunden, die den Eigenschaften des ''Satzes von Korselt'' entspricht.

== Menge der Carmichael-Zahlen ==
=== Unendliche Anzahl ===
[[Paul Erdős]] vermutete bereits 1956, dass es unendlich viele Carmichael-Zahlen gibt, und dass für ihre Anzahl <math>C(x)</math> unterhalb einer Schranke <math>x</math> kein Exponent <math>a < 1</math> existiert mit <math>C(x) < x^a</math> bei beliebig großem <math>x</math>. Das haben jedoch erst [[William Robert Alford]], [[Andrew Granville]] und [[Carl Pomerance]] im Jahr 1994 bewiesen.<ref>{{Literatur |Autor=[[William Robert Alford|W. R. Alford]], [[Andrew Granville]], [[Carl Pomerance]] |Titel=There are Infinitely Many Carmichael Numbers |Sammelwerk=Annals of Mathematics |Band=139 |Nummer=3 |Datum=1994 |Seiten=703-722 |DOI=10.2307/2118576}}</ref> Ihr Beweis liefert die untere Abschätzung der Anzahlfunktion <math>C(x) > x^{2/7}</math> für alle hinreichend großen <math>x</math>. Die Anzahl der Carmichael-Zahlen wächst also asymptotisch.
[[Glyn Harman]] verbesserte dieses Ergebnis im Jahr 2005 zu <math>C(x) > x^{0.33}</math> für hinreichend große <math>x</math>.<ref>{{Literatur |Autor=[[Glyn Harman]] |Titel=On the Number of Carmichael Numbers up to x |Sammelwerk=Bulletin of the London Mathematical Society |Band=37 |Nummer=5 |Datum=2005 |Seiten=641-650 |DOI=10.1112/S0024609305004686}}</ref>

Rechnungen bis <math>x=10^{15}</math> legen ein Wachstum mit der unteren Abschätzung <math>x^{1/3}</math> nahe, so dass [[Daniel Shanks]] überzeugt war, <math>x^{1/2}</math> sei eine sehr sichere obere Abschätzung für die Anzahlfunktion<ref>{{Literatur |Autor=[[Daniel Shanks]] |Titel= Solved and Unsolved Problems in Number Theory |Verlag= AMS Chelsea Publishing |Band=297 |Datum=1985}}</ref>. 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 <math>x</math> lieferte und so den von Shanks hervorgehobenen scheinbaren Widerspruch auflöste.<ref>{{Literatur |Autor=[[Andrew Granville]], [[Carl Pomerance]] |Titel=Two contradictory conjectures concerning Carmichael numbers |Sammelwerk=Mathematics of Computation |Band=71 |Datum=2002 |Seiten=883-908 |DOI=10.1090/S0025-5718-01-01355-2}}</ref>

2021 hat der Jugendliche [[Daniel Larsen]] gezeigt, dass in jedem Intervall zwischen <math>x</math> und <math>x+\frac{x}{(\log x)^{\frac{1}{2+\delta}}}</math> mindestens <math>e^\frac{\log x}{(\log \log x)^{2 + \delta}}</math> für <math>\delta > 0</math> und hinreichend große <math>x</math> verschiedene Carmichael-Zahlen existieren.<ref>{{Literatur |Autor=[[Daniel Larsen]] |Titel=Bertrand’s Postulate for Carmichael Numbers |Sammelwerk=International Mathematics Research Notices |Datum= |DOI=10.1093/imrn/rnac203}}</ref>

=== Carmichael-Zahlen unter 100.000 ===
Die Tabelle zeigt die Carmichael-Zahlen ({{OEIS|A002997}}) unterhalb 100.000 und bringt sie mit der [[Carmichael-Funktion]] <math>\lambda</math> und der [[Eulersche φ-Funktion|Eulerschen {{nowrap|<math>\varphi</math>-Funktion}}]] in Beziehung.
:

{| class="wikitable" style="text-align:right"
! Carmichael-Zahl <math>n</math>|| Primfaktoren||<math>\lambda(n)</math>||<math>(n-1)/\lambda(n)</math>||<math>\varphi(n)</math>||<math>\varphi(n)/\lambda(n)</math>
|-
|561 ||style="text-align:left"| 3⋅11⋅17 ||80 ||7 ||320 ||4
|-
|1105 ||style="text-align:left"| 5⋅13⋅17 ||48 ||23 ||768 ||16
|-
|1729 ||style="text-align:left"| 7⋅13⋅19 ||36 ||48 ||1296 ||36
|-
|2465 ||style="text-align:left"| 5⋅17⋅29 ||112 ||22 ||1792 ||16
|-
|2821 ||style="text-align:left"| 7⋅13⋅31 ||60 ||47 ||2160 ||36
|-
|6601 ||style="text-align:left"| 7⋅23⋅41 ||1320 ||5 ||5280 ||4
|-
|8911 ||style="text-align:left"| 7⋅19⋅67 ||198 ||45 ||7128 ||36
|-
|10585 ||style="text-align:left"| 5⋅29⋅73 ||504 ||21 ||8064 ||16
|-
|15841 ||style="text-align:left"| 7⋅31⋅73 ||360 ||44 ||12960 ||36
|-
|29341 ||style="text-align:left"| 13⋅37⋅61 ||180 ||163 ||25920 ||144
|-
|41041 ||style="text-align:left"| 7⋅11⋅13⋅41 ||120 ||342 ||28800 ||240
|-
|46657 ||style="text-align:left"| 13⋅37⋅97 ||288 ||162 ||41472 ||144
|-
|52633 ||style="text-align:left"| 7⋅73⋅103 ||1224 ||43 ||44064 ||36
|-
|62745 ||style="text-align:left"| 3⋅5⋅47⋅89 ||2024 ||31 ||32384 ||16
|-
|63973 ||style="text-align:left"| 7⋅13⋅19⋅37 ||36 ||1777 ||46656 ||1296
|-
|75361 ||style="text-align:left"| 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.<ref>{{Literatur |Autor=[[Václav Šimerka]] |Titel=Zbytky z arithmetické posloupnosti. [On reminders from arithmetical sequence] |Sammelwerk=Časopis Pro Pěstování Matematiky a Fysiky |Band=14 |Nummer=5 |Datum=1885 |Seiten=221-225 |DOI=}}</ref><ref>{{Internetquelle |url=https://dml.cz/bitstream/handle/10338.dmlcz/122245/CasPestMatFys_014-1885-5_3.pdf |titel=Zbytky z arithmetické posloupnosti |format=PDF |abruf=2023-02-05}}</ref>

Um eine Carmichael-Zahl zu erkennen, führt man entweder eine [[Faktorisierung]] durch, oder man wendet den [[Kleiner fermatscher Satz|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.

== Erzeugung von Carmichael-Zahlen ==
=== Methode von Chernick ===
[[Jack Chernick]] fand 1939 ein relativ einfaches System, um Carmichael-Zahlen zu konstruieren:<ref>{{Literatur |Autor=[[Jack Chernick]] |Titel=On Fermat’s simple theorem |Sammelwerk=Bulletin of the American Mathematical Society |Band=45 |Datum=1939 |Seiten=269-274 |DOI=10.1090/S0002-9904-1939-06953-X}}</ref>

:Falls die drei Zahlen <math>6m + 1, 12m + 1</math> und <math>18m + 1</math> Primzahlen sind, so ist ihr Produkt <math>(6m + 1)(12m + 1)(18m + 1)</math> eine Carmichael-Zahl.<ref>Zum (einfachen) Beweis siehe Eric W. Weisstein: "Carmichael number" (→ Weblinks).</ref>
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.

=== Methode von Michon ===
[[Gérard Michon]] fand eine ähnliche Methode, um Carmichael-Zahlen zu konstruieren:
{{Belege fehlen|Nicht belegt durch Publikationen, ggf. nicht von Michon alleine}}

:Wenn <math>m\equiv 326 \pmod {616}</math> und die drei Zahlen <math>7m + 1, 8m + 1</math> und <math>11m + 1</math> Primzahlen sind, so ist ihr Produkt <math>(7m+1)(8m+1)(11m+1)</math> eine Carmichael-Zahl.
<math>m</math> muss dann durch 3 teilbar sein, da sonst einer der drei Faktoren durch 3 teilbar ist. 
Beispiel: für <math>m = 24966</math> sind die drei Zahlen <math>174763, 199729</math> und <math>274627</math> prim und ihr Produkt ist eine Carmichael-Zahl. 
Eine mit dieser Methode erzeugte Carmichael-Zahl mit 1000 Stellen ist
:<math>(12936\cdot 10^{329} - 59827428149)\cdot(14784\cdot 10^{329} - 68374203599)\cdot(20328\cdot 10^{329} - 94014529949).</math>

=== Neuere Konstruktionen ===
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.<ref>[[Steven Hayman]], [[Andrew Shallue]]: [http://math.ucsd.edu/~kedlaya/ants10/poster-hayman.pdf Constructing a ten billion factor Carmichael number] (PDF-Datei; 91 kB) Poster auf der ANTS X-Konferenz, San Diego, Juli 2012</ref>

== Einzelnachweise ==
<references />

== Literatur ==
* [[Paulo Ribenboim]]: ''The New Book of Prime Number Records.'' 3rd edition. Springer, New York NY u. a. 1996, ISBN 0-387-94457-5.
* [[Richard Crandall]], [[Carl Pomerance]]: ''Prime Numbers. A Computational Perspective.'' Springer, New York NY u. a. 2001, ISBN 0-387-94777-9.

== Siehe auch ==
* [[Lucas-Carmichael-Zahl]]
* [[Knödel-Zahl]]

== Weblinks ==
{{Wikibooks|Pseudoprimzahlen: Tabelle Carmichael-Zahlen|Tabelle von Carmichael-Zahlen}}
* [https://encyclopediaofmath.org/wiki/Carmichael_number Encyclopedia of Mathematics]
* [https://web.archive.org/web/20090906105152/http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen Table of Carmichael numbers]
* [https://github.com/drazioti/Carmichael/tree/master/Tables Tables of Carmichael numbers with many prime factors]
* [http://www.s369624816.websitehome.co.uk/rgep/cartable.html Tables of Carmichael numbers below <math>10^{18}</math>]
* {{MathWorld | id=CarmichaelNumber | title=Carmichael Number}}
* [http://www.numericana.com/answer/modular.htm#carmichael Final Answers Modular Arithmetic: Carmichael Numbers (Absolute Pseudoprimes)]
* [https://www.faz.net/aktuell/wissen/daniel-larsen-findet-einen-mathebeweis-zu-carmichael-zahlen-18583248.html TEENAGER FINDET MATHEBEWEIS : Simpel und mysteriös zugleich]
{{Navigationsleiste Primzahlklassen}}

[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl]]
[[Kategorie:Zahlentheorie]]

Carmichael-Zahl - Versionsgeschichte

~2026-24828-43: Die Referenz von Grandville/Pomerance ist auch die Quelle für die Aussage, dass Shanks sich überzeugen ließ.