Liczby Carmichaela
![](http://upload.wikimedia.org/wikipedia/commons/9/92/Robert_Daniel_Carmichael.gif)
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:
- jest liczbą złożoną,
- 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:
- są nieparzyste;
- przy rozkładzie na czynniki pierwsze, żaden czynnik nie występuje w potędze wyższej niż pierwsza;
- 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):
- Czy dla każdego istnieje nieskończenie wiele liczb Carmichaela, które są iloczynem dokładnie 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[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].
- 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 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
- ↑ Carmichaela liczby, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-09-30] .
- ↑ a b c Paolo Ribenboim, Mała księga wielkich liczb pierwszych, WNT, Warszawa 1997, ISBN 83-204-2201-9.
- ↑ A. Korselt, Probleme chinois, „L’Intermediaire des mathematiciens” 1899, 6', s. 142–143.
- ↑ R.D. Carmichael: On composite numbers P which satisfy the Fermat congruence, „Amer. Math. Monthly”, 1912, 19, s. 22–27.
- ↑ Wacław Sierpiński: Wstęp do teorii liczb, wyd. 3 poprawione, WSiP, Warszawa 1987, ISBN 83-02-03150-X.
- ↑ a b W.R. Alford, A. Granville, C. Pomerance, There are infinitely many Carmichael numbers, „Annals of Math.” 1994, 140, s. 703–722.
- ↑ Paul Erdős: On pseudoprimes and Carmichael numbers, „Publ. Math. Debrecen”, 1956, 4, s. 201–206.
- ↑ J. Chernick: On Fermat’s simple theorem, „Bulletin of the American Mathematical Society” 45, 1939, s. 269–274.
- ↑ (ciąg
A002997 w OEIS)
Linki zewnętrzne
- 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
- p
- d
- e
ogólne typy liczb | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
relacje |
| ||||||||||
działania | |||||||||||
liczby pierwsze |
| ||||||||||
równania diofantyczne |
| ||||||||||
twierdzenia arytmetyki modularnej |
| ||||||||||
inne zagadnienia | |||||||||||
twierdzenia limitacyjne |
- p
- d
- e
pojęcia definiujące |
| ||||
---|---|---|---|---|---|
typy ciągów |
| ||||
przykłady ciągów liczb naturalnych | |||||
inne przykłady ciągów liczb | |||||
twierdzenia |
| ||||
powiązane pojęcia |
- Britannica: topic/Carmichael-number