Liczby Carmichaela

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Liczby Carmichaela to w teorii liczb takie złożone liczby naturalne, dla których teza Małego Twierdzenia Fermata jest prawdziwa.

Dokładniej[1], liczba naturalna n jest liczbą Carmichaela wtedy i tylko wtedy, gdy:

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

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

Pierwszy liczby te zdefiniował (inaczej, ale w sposób równoważny) i badał ich własności A. Korselt[2] 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[3].

Związki z Małym Twierdzeniem Fermata[edytuj | edytuj kod]

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

Właściwości[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

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

Liczb Carmichaela mniejszych niż milion jest jedynie 43, a mniejszych niż bilion (10^{12}) – jedynie 8238.

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 k \geqslant 3 istnieje nieskończenie wiele liczb Carmichaela, które są iloczynem dokładnie k czynników pierwszych?
  2. czy istnieją liczby Carmichaela o dowolnie dużej liczbie czynników pierwszych?

Jak można je otrzymywać?[edytuj | edytuj kod]

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

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

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

Przykłady[edytuj | edytuj kod]

Najmniejszą liczbą Carmichaela jest 561=3 \cdot 11 \cdot 17. Następne kilka z nich to[8]:

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. 1,0 1,1 1,2 Ribenboim, Paolo "Mała księga wielkich liczb pierwszych", WNT, Warszawa 1997, ISBN 83-204-2201-9
  2. Korselt, A. "Probleme chinois", L'Intermediaire des mathematiciens, 1899,6, 142-143.
  3. Carmichael,R. D.: "On composite numbers P which satisfy the Fermat congruence". Amer. Math. Monthly, 1912, 19, 22-27.
  4. Sierpiński, Wacław: "Wstęp do teorii liczb", wyd. 3 poprawione, WSiP, Warszawa 1987, ISBN 83-02-03150-X
  5. 5,0 5,1 Alford, W. R., Granville, A., Pomerance, C. "There are infinitely many Carmichael numbers", Annals of Math., 1994, 140, 703-722.
  6. Erdős, Paul: "On pseudoprimes and Carmichael numbers", Publ. Math. Debrecen, 1956, 4, 201–206
  7. Chernick, J.: "On Fermat's simple theorem", Bulletin of the American Mathematical Society 45, 1939, ss. 269-274
  8. (ciąg A002997 w OEIS)

Linki zewnętrzne[edytuj | edytuj kod]