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 jest liczbą Carmichaela wtedy i tylko wtedy, gdy:

  1. jest liczbą złożoną,
  2. dla każdej liczby naturalnej z przedziału względnie pierwszej z liczba jest podzielna przez

Każda liczba Carmichaela spełnia też ogólniejszy warunek[2]: dla każdego naturalnego liczba jest podzielna przez

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].

Związki z małym twierdzeniem Fermata

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 są nazywane liczbami pseudopierwszymi (przy podstawie ). 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 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.

Właściwości

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

  1. 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.

Rozmieszczenie

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

dla dostatecznie dużych ma miejsce nierówność gdzie jest pewną stałą.

Liczb Carmichaela mniejszych niż milion jest jedynie 43, a mniejszych niż bilion (1012) – 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 istnieje nieskończenie wiele liczb Carmichaela, które są iloczynem dokładnie czynników pierwszych?
  2. Czy istnieją liczby Carmichaela o dowolnie dużej liczbie czynników pierwszych?

Jak można je otrzymywać?

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

podstawiając kolejne liczby naturalne za wyznacza się Jeżeli dla pewnego wszystkie czynniki w nawiasach są liczbami pierwszymi, to jest liczbą Carmichaela. Istnieją uogólnienia tego algorytmu na większą liczbę czynników pierwszych[2].

Przykłady

Najmniejszą liczbą Carmichaela jest 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)

Przypisy

  1. Carmichaela liczby, [w:] Encyklopedia PWN [online] [dostęp 2021-09-30].
  2. a b c Paolo Ribenboim, Mała księga wielkich liczb pierwszych, WNT, Warszawa 1997, ISBN 83-204-2201-9.
  3. A. Korselt, Probleme chinois, „L’Intermediaire des mathematiciens” 1899, 6', s. 142–143.
  4. R.D. Carmichael: On composite numbers P which satisfy the Fermat congruence, „Amer. Math. Monthly”, 1912, 19, s. 22–27.
  5. Wacław Sierpiński: Wstęp do teorii liczb, wyd. 3 poprawione, WSiP, Warszawa 1987, ISBN 83-02-03150-X.
  6. a b W.R. Alford, A. Granville, C. Pomerance, There are infinitely many Carmichael numbers, „Annals of Math.” 1994, 140, s. 703–722.
  7. Paul Erdős: On pseudoprimes and Carmichael numbers, „Publ. Math. Debrecen”, 1956, 4, s. 201–206.
  8. J. Chernick: On Fermat’s simple theorem, „Bulletin of the American Mathematical Society” 45, 1939, s. 269–274.
  9. (ciąg publikacja w otwartym dostępie – możesz ją przeczytać A002997 w OEIS)

Linki zewnętrzne