Liczby pierwsze — jak je rozpoznać, rozkładać i dlaczego chronią internet

Liczba pierwsza ma dokładnie dwa dzielniki: 1 i samą siebie. Pierwsze z nich to 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Każda inna liczba większa od 1 jest iloczynem liczb pierwszych — są więc „cegiełkami”, z których zbudowane są wszystkie liczby naturalne.

Cechy podzielności

Liczba dzieli się przez	gdy
2	ostatnia cyfra jest parzysta
3	suma cyfr dzieli się przez 3 (471: 4+7+1 = 12 ✓)
5	kończy się na 0 lub 5
7	po odjęciu podwojonej ostatniej cyfry od reszty liczby wynik dzieli się przez 7 (343: 34 − 6 = 28 ✓)
11	naprzemienna suma cyfr dzieli się przez 11 (2 541: 2 − 5 + 4 − 1 = 0 ✓)

Wystarczy sprawdzać dzielniki nie większe niż pierwiastek z liczby: jeśli 221 miałoby dzielnik, to jeden z nich byłby ≤ √221 ≈ 14,9. Sprawdzamy 2, 3, 5, 7, 11, 13 — i okazuje się, że 221 = 13 · 17.

Rozkład na czynniki krok po kroku

360 : 2 = 180 180 : 2 = 90 90 : 2 = 45 45 : 3 = 15 15 : 3 = 5 5 : 5 = 1 → 360 = 2³ · 3² · 5

Z rozkładu wynika liczba dzielników: (3+1)·(2+1)·(1+1) = 24. Rozkład przydaje się też do skracania ułamków i szukania NWD oraz NWW (zob. kalkulator NWD i NWW i poradnik o działaniach na ułamkach).

Sito Eratostenesa

1. Wypisz liczby od 2 do N.
2. Weź najmniejszą nieskreśloną — to liczba pierwsza.
3. Skreśl wszystkie jej wielokrotności (zaczynając od jej kwadratu).
4. Powtarzaj, aż dojdziesz do √N. Nieskreślone liczby są pierwsze.

Do 100 jest 25 liczb pierwszych, do 1000 — 168, do miliona — 78 498. Im dalej, tym rzadziej występują: w okolicy liczby N średnio co ln N.

Ciekawostki

• Bliźniacze liczby pierwsze różnią się o 2: (11, 13), (17, 19), (41, 43). Nie wiadomo, czy jest ich nieskończenie wiele.
• Liczby Mersenne’a mają postać 2ᵖ − 1; największe znane liczby pierwsze to właśnie liczby Mersenne’a, mające dziesiątki milionów cyfr.
• Hipoteza Goldbacha: każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych (np. 28 = 5 + 23). Sprawdzona komputerowo dla ogromnych liczb, ale wciąż nieudowodniona.
• Liczby doskonałe (6, 28, 496, 8128) są związane z liczbami Mersenne’a: 28 = 2² · (2³ − 1).

Liczby pierwsze w internecie

Gdy łączysz się z bankiem, przeglądarka i serwer korzystają z szyfrowania opartego na matematyce liczb pierwszych. W klasycznym algorytmie RSA klucz publiczny zawiera iloczyn dwóch ogromnych liczb pierwszych. Pomnożenie ich jest łatwe, ale odtworzenie czynników z iloczynu (mającego setki cyfr) zajęłoby znanym metodom niewyobrażalnie długo.

Pierwszość dowolnej liczby (nawet szesnastocyfrowej), jej rozkład, dzielniki i listę liczb pierwszych do 100 000 sprawdzisz w kalkulatorze liczb pierwszych.