Liczby Carmichaela

Liczby Carmichaela to w teorii liczb takie złożone liczby naturalne, dla których teza małego twierdzenia Fermata jest prawdziwa^[1].

Dokładniej^[2], liczba naturalna ${\displaystyle n}$ jest liczbą Carmichaela wtedy i tylko wtedy, gdy:

1. jest liczbą złożoną,
2. dla każdej liczby naturalnej ${\displaystyle a}$ z przedziału ${\displaystyle 1<a<n,}$ względnie pierwszej z ${\displaystyle n,}$ liczba ${\displaystyle (a^{n-1}-1)}$ jest podzielna przez ${\displaystyle n.}$

Każda liczba Carmichaela ${\displaystyle n}$ spełnia też ogólniejszy warunek^[2]: dla każdego naturalnego ${\displaystyle a\geqslant 1}$ liczba ${\displaystyle (a^{n}-a)}$ jest podzielna przez ${\displaystyle n.}$

Jako pierwszy liczby te zdefiniował (inaczej, ale w sposób równoważny) i badał ich własności A. Korselt^[3] w roku 1899, nie podał on jednak żadnego przykładu takiej liczby.

Nazwa tych liczb pochodzi od nazwiska Roberta Daniela Carmichaela (właściwie 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^[4].

Małe twierdzenie Fermata charakteryzuje liczby pierwsze, natomiast nie wyklucza istnienia 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ę kongruencję dla pewnej podstawy ${\displaystyle a}$ są nazywane liczbami pseudopierwszymi (przy podstawie ${\displaystyle a}$). 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^[5]) nazywane liczbami bezwzględnie pseudopierwszymi. Nie należy ich mylić z innymi podzbiorami zbioru liczb pseudopierwszych: liczbami silnie pseudopierwszymi lub 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 ${\displaystyle n}$ jest pierwsza, oparty na tym twierdzeniu, zwany testem Fermata, nie może być deterministycznym testem pierwszości. Na zasadzie małego twierdzenia Fermata można oprzeć jedynie test probabilistyczny, który będzie działał tym skuteczniej, im rzadziej w zbiorze liczb naturalnych pojawiają się liczby pseudopierwsze i liczby Carmichaela.

Można dowieść, że liczby Carmichaela mają, między innymi, następujące własności:

1. są nieparzyste;
2. przy rozkładzie na czynniki pierwsze, żaden czynnik nie występuje w potędze wyższej niż pierwsza;
3. każda z nich jest iloczynem przynajmniej trzech liczb pierwszych.

Udowodniono (w 1992 roku^[6]), że liczb Carmichaela jest nieskończenie wiele. Dokładniej, jeżeli przez ${\displaystyle \operatorname {CN} (x)}$ oznaczymy ilość liczb Carmichaela mniejszych od danej liczby ${\displaystyle x,}$ to w pracy^[6] uzyskano dla dostatecznie dużych liczb oszacowanie: ${\displaystyle x^{\frac {2}{7}}\leqslant \operatorname {CN} (x).}$ Znane jest też oszacowanie funkcji ${\displaystyle \operatorname {CN} (x)}$ od góry, podane przez Paula Erdősa^[7]:

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

Liczb Carmichaela mniejszych niż milion jest jedynie 43, a mniejszych niż bilion (10¹²) – jedynie 8238. Jednak wiele pytań dotyczących liczb Carmichaela pozostaje otwartych. Nie wiadomo na przykład do dziś (pierwsza połowa roku 2007):

1. Czy dla każdego ${\displaystyle k\geqslant 3}$ istnieje nieskończenie wiele liczb Carmichaela, które są iloczynem dokładnie ${\displaystyle k}$ czynników pierwszych?
2. Czy istnieją liczby Carmichaela o dowolnie dużej liczbie czynników pierwszych?

Oto algorytm podany przez J.Chernicka^[8] dla liczb Carmichaela o trzech czynnikach pierwszych:

podstawiając kolejne liczby naturalne za ${\displaystyle m}$ wyznacza się ${\displaystyle M(m)=(6m+1)(12m+1)(18m+1).}$ Jeżeli dla pewnego ${\displaystyle m}$ wszystkie czynniki w nawiasach są liczbami pierwszymi, to ${\displaystyle M(m)}$ jest liczbą Carmichaela. Istnieją uogólnienia tego algorytmu na większą liczbę czynników pierwszych^[2].

• Algorytm znajdowania bardzo dużych liczb Carmichaela o wielkiej liczbie czynników pierwszych opisali G. Löh i W. Niebuhr.

Najmniejszą liczbą Carmichaela jest ${\displaystyle 561=3\cdot 11\cdot 17.}$ Następne kilka z nich to^[9]:

1105 = 5 · 13 · 17    (4 | 1104, 12 | 1104, 16 | 1104)

1729 = 7 · 13 · 19    (6 | 1728, 12 | 1728, 18 | 1728)

2465 = 5 · 17 · 29    (4 | 2464, 16 | 2464, 28 | 2464)

2821 = 7 · 13 · 31    (6 | 2820, 12 | 2820, 30 | 2820)

6601 = 7 · 23 · 41    (6 | 6600, 22 | 6600, 40 | 6600)

8911 = 7 · 19 · 67    (6 | 8910, 18 | 8910, 66 | 8910)

• Eric W.E.W. Weisstein Eric W.E.W., Carmichael Number, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2022-07-02].
• 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, algorytm znajdowania bardzo dużych liczb Carmichaela