Liczby pierwsze — definicja i sposoby sprawdzania
Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: jedynkę i samą siebie. Najmniejszą liczbą pierwszą jest 2, jedyna parzysta w całym zbiorze.
Liczby pierwsze są podstawowymi cegiełkami arytmetyki — każda liczba naturalna rozkłada się na ich iloczyn. Poniżej definicja, sposoby sprawdzania i zastosowania praktyczne.
Definicja
Liczba pierwsza to liczba naturalna większa od 1, mająca dokładnie dwa dzielniki naturalne: 1 i samą siebie.
Pierwsze liczby pierwsze: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Liczby mające więcej dzielników nazywamy złożonymi. Liczba 1 nie należy do żadnej z tych grup — ma tylko jeden dzielnik.
Dlaczego 1 nie jest pierwsza
To pytanie wraca regularnie. Definicja wymaga dokładnie dwóch dzielników, a jedynka ma jeden. Ale za tym stoi głębszy powód.
Gdyby uznać 1 za pierwszą, przestałoby działać twierdzenie o jednoznaczności rozkładu: każda liczba rozkłada się na czynniki pierwsze na dokładnie jeden sposób. Liczba 12 to 2 · 2 · 3 i nic innego. Z jedynką w zbiorze mielibyśmy 1 · 2 · 2 · 3, 1 · 1 · 2 · 2 · 3 i nieskończenie wiele wariantów.
Wykluczenie jedynki nie jest więc arbitralne, lecz konieczne dla spójności całej arytmetyki.
Jak sprawdzić, czy liczba jest pierwsza
Wystarczy szukać dzielników do pierwiastka kwadratowego z badanej liczby. Gdyby istniał dzielnik większy, jego para musiałaby być mniejsza od pierwiastka — a tę już byśmy znaleźli.
Przykład: czy 97 jest pierwsza? Pierwiastek z 97 to około 9,8, więc sprawdzamy dzielniki do 9: liczby 2, 3, 5 i 7. Żadna nie dzieli 97, więc 97 jest liczbą pierwszą.
To skraca pracę drastycznie — zamiast 96 sprawdzeń wystarczą cztery.
Sito Eratostenesa
Metoda znajdowania wszystkich liczb pierwszych do zadanej granicy, opisana ponad dwa tysiące lat temu:
- Wypisz liczby od 2 do wybranej granicy
- Zaznacz 2 jako pierwszą i wykreśl wszystkie jej wielokrotności
- Przejdź do kolejnej niewykreślonej liczby i powtórz
- Pozostałe niewykreślone liczby są pierwsze
Ile jest liczb pierwszych
Nieskończenie wiele — udowodnił to Euklides około 300 roku p.n.e., a jego dowód jest do dziś uważany za wzór eleganckiego rozumowania.
Zakłada się, że liczb pierwszych jest skończenie wiele, mnoży wszystkie i dodaje jeden. Otrzymana liczba nie dzieli się przez żadną z listy — zawsze zostaje reszta 1. Musi więc być pierwsza albo mieć dzielnik pierwszy spoza listy. W obu przypadkach lista była niepełna, co przeczy założeniu.
Do czego służą
Liczby pierwsze są podstawą współczesnej kryptografii. Szyfrowanie danych w bankowości i internecie opiera się na prostej asymetrii: pomnożenie dwóch dużych liczb pierwszych jest łatwe, a rozłożenie wyniku z powrotem na czynniki — praktycznie niewykonalne w rozsądnym czasie.
Przy liczbach kilkusetcyfrowych rozkład zająłby najszybszym komputerom miliony lat. Na tej różnicy trudności opiera się bezpieczeństwo przelewów i połączeń szyfrowanych.