Istnieją liczby złożone, które udają pierwsze przed całym testem Fermata
Małe twierdzenie Fermata daje własność spełnianą przez liczby pierwsze i prowadzi do prostych testów pierwszości. Problem w tym, że istnieją liczby złożone, które przechodzą taki test dla każdej podstawy względnie pierwszej z badaną liczbą. To liczby Carmichaela. Najmniejsza z nich to 561=3·11·17. Dla każdego a względnie pierwszego z 561 zachodzi a^560≡1 mod 561, dokładnie tak, jak oczekiwalibyśmy dla liczby pierwszej. Prawdziwe twierdzenie daje więc warunek konieczny, który nie jest warunkiem wystarczającym.
Skąd bierze się test Fermata
Jeśli p jest liczbą pierwszą, a a nie jest podzielne przez p, małe twierdzenie Fermata mówi, że a^(p−1)≡1 mod p. To kusi do odwrócenia rozumowania: skoro dla badanego n otrzymujemy a^(n−1)≡1 mod n, może n jest pierwsze. Niestety takie odwrócenie nie jest logicznie gwarantowane. Niektóre liczby złożone spełniają kongruencję dla wybranych podstaw i nazywa się je pseudopierwszymi Fermata.
561 oszukuje znacznie skuteczniej
Liczba 561 jest złożona, bo 561=3·11·17. Jednocześnie jest liczbą Carmichaela: dla każdej podstawy a względnie pierwszej z 561 przechodzi test Fermata. Nie wystarczy więc zmienić podstawy z 2 na 3, 5 czy wiele innych i liczyć, że w końcu test ujawni złożoność. W ramach samego kryterium Fermata 561 zachowuje się jak przypadek skrajnie mylący.
Kryterium Korselta odsłania strukturę
Liczby Carmichaela nie są przypadkowymi błędami numerycznymi. Kryterium Korselta charakteryzuje je strukturalnie: liczba złożona n jest liczbą Carmichaela wtedy i tylko wtedy, gdy jest bezkwadratowa oraz dla każdego pierwszego dzielnika p liczby n zachodzi p−1 | n−1. Dla 561 liczby 2, 10 i 16 — czyli odpowiednio 3−1, 11−1 i 17−1 — dzielą 560. Ta zgodność powoduje, że potęgowanie modulo każdego czynnika składa się w pozornie „pierwsze” zachowanie modulo całego 561.
Lekcja o warunkach koniecznych
To przykład uniwersalnej pułapki logicznej. Z twierdzenia „jeśli liczba jest pierwsza, to ma własność X” nie wynika automatycznie „jeśli ma X, to jest pierwsza”. Aby stworzyć poprawny test, trzeba zbadać również odwrotność albo znaleźć mocniejsze kryterium. W praktyce istnieją testy pierwszości i testy pseudopierwszości, które radzą sobie z liczbami Carmichaela znacznie lepiej. Sama historia pozostaje jednak świetną ilustracją, jak liczby złożone mogą naśladować bardzo charakterystyczną własność liczb pierwszych.
Dlaczego 561 przechodzi test dla wszystkich odpowiednich podstaw
Rozkład 561=3·11·17 i kryterium Korselta pozwalają zobaczyć mechanizm. Dla podstawy a względnie pierwszej z 561 twierdzenie Fermata zastosowane osobno do liczb pierwszych 3, 11 i 17 daje odpowiednie okresy potęg. Ponieważ 2, 10 i 16 wszystkie dzielą 560, otrzymujemy a^560≡1 modulo każdy z trzech czynników. Liczba 561 jest bezkwadratowa, więc zgodność modulo 3, 11 i 17 składa się w zgodność modulo ich iloczynu. To nie przypadkowa seria szczęśliwych trafień. Struktura czynników została dokładnie dopasowana do wykładnika 560. Dzięki temu liczba złożona imituje warunek Fermata systematycznie, a nie tylko dla jednej wybranej podstawy.
Późniejsze testy wykorzystują mocniejsze własności
Liczby Carmichaela nie oznaczają, że sprawdzanie pierwszości metodami modularnymi jest beznadziejne. Pokazują tylko granicę najprostszego testu Fermata. Mocniejsze testy probabilistyczne, takie jak test Millera–Rabina, wykorzystują dodatkową strukturę pierwiastków z jedności modulo liczby i potrafią wykrywać złożoność tam, gdzie goły test Fermata zawodzi. Matematyczna lekcja pozostaje cenna: gdy kontrprzykład obala prostą odwrotność twierdzenia, często prowadzi to nie do porzucenia pomysłu, lecz do znalezienia silniejszego kryterium.
Korselt opisał strukturę jeszcze przed nazwą Carmichaela
Kryterium charakteryzujące te liczby podał A. Korselt w 1899 roku, zanim Robert Carmichael opublikował swoje przykłady i systematyczne badania na początku XX wieku. To ciekawa kolejność historyczna: warunek strukturalny istniał wcześniej niż klasa liczb, która później otrzymała powszechną nazwę od Carmichaela. Sama 561 jest najmniejszym przykładem, ale zjawisko nie jest izolowane — istnieje nieskończenie wiele liczb Carmichaela, co pokazuje, że „fałszywe alarmy” dla testu Fermata tworzą rzeczywistą, bogatą rodzinę.