Tekst źródłowy strony Liczby Carmichaela

[[Plik:Robert Daniel Carmichael.gif|mały|Robert Daniel Carmichael (1879-1967), amerykański matematyk]]
'''Liczby Carmichaela''' to w [[Teoria liczb|teorii liczb]] takie [[Liczby złożone|złożone]] [[liczby naturalne]], dla których teza [[Małe twierdzenie Fermata|małego twierdzenia Fermata]] jest prawdziwa<ref name="epwn">{{Encyklopedia PWN | id = 3883275 | tytuł = Carmichaela liczby | data dostępu = 2021-09-30 }}</ref>.

Dokładniej<ref name="Ribenboim">Paolo Ribenboim, ''Mała księga wielkich liczb pierwszych'', WNT, Warszawa 1997, {{ISBN|83-204-2201-9}}.</ref>, liczba naturalna <math>n</math> jest liczbą Carmichaela wtedy i tylko wtedy, gdy:
# jest liczbą złożoną,
# dla każdej liczby naturalnej <math>a</math> z przedziału <math>1<a<n,</math> [[liczby względnie pierwsze|względnie pierwszej]] z <math>n,</math> liczba <math>(a^{n-1}-1)</math> jest podzielna przez <math>n.</math>

Każda liczba Carmichaela <math>n</math> spełnia też ogólniejszy warunek<ref name="Ribenboim" />: dla każdego naturalnego <math>a\geqslant1</math> liczba <math>(a^n-a)</math> jest podzielna przez <math>n.</math>

Jako pierwszy liczby te zdefiniował (inaczej, ale w sposób równoważny) i badał ich własności A. Korselt<ref>A. Korselt, ''Probleme chinois'', „L’Intermediaire des mathematiciens” 1899, ''6''', s. 142–143.</ref> w roku [[1899]], nie podał on jednak żadnego przykładu takiej liczby.

Nazwa tych liczb pochodzi od nazwiska [[Robert Daniel Carmichael|Roberta Daniela Carmichaela]] (właściwie [[Robert Daniel Carmichael|Carmichaëla]]), który zdefiniował je niezależnie w [[1910]] roku, dokładniej zbadał ich własności oraz podał kilka przykładów takich liczb<ref>R.D. Carmichael: ''On composite numbers P which satisfy the Fermat congruence'', „Amer. Math. Monthly”, 1912, '''19''', s. 22–27.</ref>.

== Związki z małym twierdzeniem Fermata ==
[[Małe twierdzenie Fermata]] charakteryzuje [[liczby pierwsze]], natomiast nie wyklucza istnienia [[Liczby złożone|liczb złożonych]], dla których wskazana w jego tezie [[kongruencja]] jest również spełniona. Liczby złożone, które spełniają tę [[kongruencja|kongruencję]] dla pewnej podstawy <math>a</math> są nazywane [[liczby pseudopierwsze|liczbami pseudopierwszymi]] (przy podstawie <math>a</math>). ''Liczby Carmichaela są zatem liczbami pseudopierwszymi przy każdej podstawie''.

Wynika stąd, że każda liczba Carmichaela jest liczbą pseudopierwszą, ale nie na odwrót. Z uwagi na ten fakt, liczby Carmichaela są czasem (w starszej literaturze<ref>Wacław Sierpiński: ''Wstęp do teorii liczb'', wyd. 3 poprawione, WSiP, Warszawa 1987, {{ISBN|83-02-03150-X}}.</ref>) nazywane liczbami bezwzględnie pseudopierwszymi. Nie należy ich mylić z innymi podzbiorami zbioru liczb pseudopierwszych: [[liczby silnie pseudopierwsze|liczbami silnie pseudopierwszymi]] lub [[liczby pseudopierwsze Eulera|liczbami pseudopierwszymi Eulera]].

Istnienie liczb Carmichaela wskazuje, że odwrócenie małego twierdzenia Fermata jest nieprawdziwe, dlatego [[test pierwszości]], czyli test do badania, czy dana liczba <math>n</math> jest pierwsza, oparty na tym twierdzeniu, zwany [[Test pierwszości Fermata|testem Fermata]], nie może być deterministycznym testem pierwszości. Na zasadzie małego twierdzenia Fermata można oprzeć jedynie [[algorytm probabilistyczny|test probabilistyczny]], który będzie działał tym skuteczniej, im rzadziej w zbiorze liczb naturalnych pojawiają się liczby pseudopierwsze i liczby Carmichaela.

== Właściwości ==
Można dowieść, że liczby Carmichaela mają, między innymi, następujące własności:
# są [[Parzystość liczb|nieparzyste]];
# przy rozkładzie na [[Czynnik pierwszy|czynniki pierwsze]], żaden czynnik nie występuje w potędze wyższej niż pierwsza;
# każda z nich jest [[Iloczyn skalarny|iloczynem]] przynajmniej trzech [[Liczby pierwsze|liczb pierwszych]].

== Rozmieszczenie ==
Udowodniono (w [[1992]] roku<ref name="AGP">W.R. Alford, A. Granville, C. Pomerance, ''There are infinitely many Carmichael numbers'', „Annals of Math.” 1994, '''140''', s. 703–722.</ref>), że liczb Carmichaela jest nieskończenie wiele. Dokładniej, jeżeli przez <math>\operatorname{CN}(x)</math> oznaczymy ilość liczb Carmichaela mniejszych od danej liczby <math>x,</math> to w pracy<ref name="AGP" /> uzyskano dla dostatecznie dużych liczb oszacowanie: <math>x^{\frac{2}{7}} \leqslant \operatorname{CN}(x).</math> Znane jest też oszacowanie funkcji <math>\operatorname{CN}(x)</math> od góry, podane przez [[Paul Erdős|Paula Erdősa]]<ref>Paul Erdős: ''On pseudoprimes and Carmichael numbers'', „Publ. Math. Debrecen”, 1956, '''4''', s. 201–206.</ref>:

dla dostatecznie dużych <math>x</math> ma miejsce nierówność <math>\operatorname{CN}(x) \leqslant x\cdot \exp\left(\frac{-k\cdot\log x\cdot\log\log\log x}{\log\log x}\right),</math> gdzie <math>k</math> jest pewną stałą.

Liczb Carmichaela mniejszych niż milion jest jedynie 43, a mniejszych niż bilion (10<sup>12</sup>) – jedynie 8238. Jednak wiele pytań dotyczących liczb Carmichaela pozostaje otwartych. Nie wiadomo na przykład do dziś (pierwsza połowa roku 2007):
# Czy dla każdego <math>k \geqslant 3</math> istnieje nieskończenie wiele liczb Carmichaela, które są iloczynem dokładnie <math>k</math> czynników pierwszych?
# Czy istnieją liczby Carmichaela o dowolnie dużej liczbie czynników pierwszych?

== Jak można je otrzymywać? ==
Oto [[algorytm]] podany przez J.Chernicka<ref>J. Chernick: ''On Fermat’s simple theorem'', „[[Bulletin of the American Mathematical Society]]” 45, 1939, s. 269–274.</ref> dla liczb Carmichaela o trzech czynnikach pierwszych:

podstawiając kolejne liczby naturalne za <math>m</math> wyznacza się <math>M(m)=(6m+1)(12m+1)(18m+1).</math> Jeżeli dla pewnego <math>m</math> wszystkie czynniki w nawiasach są liczbami pierwszymi, to <math>M(m)</math> jest liczbą Carmichaela. Istnieją uogólnienia tego algorytmu na większą liczbę czynników pierwszych<ref name="Ribenboim" />.

* [http://web.archive.org/web/20030425040718/http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf Algorytm znajdowania bardzo dużych liczb Carmichaela] o wielkiej liczbie czynników pierwszych opisali G. Löh i W. Niebuhr.

== Przykłady ==
Najmniejszą liczbą Carmichaela jest <math>561=3 \cdot 11 \cdot 17.</math> Następne kilka z nich to<ref>{{OEIS|id=A002997}}</ref>:
: 1105 = 5 · 13 · 17 &nbsp;&nbsp; (4 | 1104, 12 | 1104, 16 | 1104)
: 1729 = 7 · 13 · 19 &nbsp;&nbsp; (6 | 1728, 12 | 1728, 18 | 1728)
: 2465 = 5 · 17 · 29 &nbsp;&nbsp; (4 | 2464, 16 | 2464, 28 | 2464)
: 2821 = 7 · 13 · 31 &nbsp;&nbsp; (6 | 2820, 12 | 2820, 30 | 2820)
: 6601 = 7 · 23 · 41 &nbsp;&nbsp; (6 | 6600, 22 | 6600, 40 | 6600)
: 8911 = 7 · 19 · 67 &nbsp;&nbsp; (6 | 8910, 18 | 8910, 66 | 8910)

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{MathWorld | adres = CarmichaelNumber | tytuł = Carmichael Number }} [dostęp 2022-07-02].
* [http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen Tablica liczb Carmichaela (po niemiecku)]
* Löh, Günter and Niebuhr, Wolfgang: „A new algorithm for constructing large Carmichael numbers”, '''Math.of Comp.''' (1996), ''65'', s. 823–836, [http://web.archive.org/web/20030425040718/http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf algorytm znajdowania bardzo dużych liczb Carmichaela]

{{Typy liczb naturalnych}}
{{Ciągi liczbowe}}
{{Teoria liczb}}

{{Kontrola autorytatywna}}

[[Kategoria:Rodzaje liczb naturalnych|C]]