Liczby Carmichaela

Liczby Carmichaela

Liczby Carmichaela to złożone liczby naturalne, które spełniają warunki małego twierdzenia Fermata. Liczba naturalna $n$ jest liczbą Carmichaela, jeśli:

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

Nazwa tych liczb pochodzi od Roberta Daniela Carmichaela, który zdefiniował je w 1910 roku.

Związki z małym twierdzeniem Fermata

Małe twierdzenie Fermata dotyczy liczb pierwszych, jednak istnieją także liczby złożone, które spełniają jego warunki. Liczby te, które spełniają kongruencję dla pewnej podstawy $a$, nazywane są liczbami pseudopierwszymi. Liczby Carmichaela są szczególnym przypadkiem i są pseudopierwsze dla każdej podstawy. Oznacza to, że są liczbami pseudopierwszymi, ale nie są jedynym przypadkiem.

Fakt istnienia liczb Carmichaela podważa możliwość stosowania małego twierdzenia Fermata jako deterministycznego testu pierwszości, co skutkuje koniecznością korzystania z testów probabilistycznych.

Właściwości

Liczby Carmichaela mają kilka charakterystycznych właściwoś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, że istnieje nieskończona ilość liczb Carmichaela. Dla dużych wartości $x$ istnieje nierówność:

$operatorname\{CN\}(x)\; leqslant\; xcdot\; expleft(frac\{-kcdotlog\; xcdotlogloglog\; x\}\{loglog\; x\}right),$

gdzie $k$ jest stałą. Liczby Carmichaela mniejsze niż milion to tylko 43, a mniejsze niż bilion – 8238. Wciąż pozostają otwarte pytania, takie jak:

• Czy dla każdego $k\; geqslant\; 3$ istnieje nieskończona ilość liczb Carmichaela z dokładnie $k$ czynnikami pierwszymi?
• Czy istnieją liczby Carmichaela o dowolnie dużej liczbie czynników pierwszych?

Jak można je otrzymywać?

Algorytm J. Chernicka dla liczb Carmichaela o trzech czynnikach pierwszych polega na podstawieniu liczb naturalnych za $m$ w równaniu $M(m)=(6m+1)(12m+1)(18m+1)$. Gdy wszystkie czynniki są liczbami pierwszymi, $M(m)$ jest liczbą Carmichaela. Przykłady liczb Carmichaela to:

• 1105 = 5 · 13 · 17
• 1729 = 7 · 13 · 19
• 2465 = 5 · 17 · 29
• 2821 = 7 · 13 · 31
• 6601 = 7 · 23 · 41
• 8911 = 7 · 19 · 67