Liczby Carmichaela

Z Wikipedii

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. a ponadto, 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 liczba (aⁿ − 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].

Spis treści 1 Związki z Małym Twierdzeniem Fermata 2 Właściwości 3 Rozmieszczenie 4 Jak można je otrzymywać? 5 Przykłady 6 Bibliografia

[edytuj] 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 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, np.^[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.

[edytuj] Właściwości

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

[edytuj] Rozmieszczenie

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

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

Liczb Carmichaela mniejszych niż milion jest jedynie 43, a mniejszych niż bilion (10¹²) – 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 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?

[edytuj] Jak można je otrzymywać?

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.

[edytuj] Przykłady

Najmniejszą liczbą Carmichaela jest . Następne kilka z nich to:

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)

[edytuj] Bibliografia

Źródła

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-0315-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", Bull. Amer. Math. Soc., 1939, 45, str. 269-274

Linki zewnętrzne

• 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, 823-836 algorytm znajdowania bardzo dużych liczb Carmichaela