Liczba pierwsza to liczba naturalna większa niż 1, która ma dokładnie dwa dzielniki: 1 i siebie samą. Innymi słowy, liczba pierwsza nie da się zapisać w postaci iloczynu dwóch liczb naturalnych większych od 1. Liczby, które można tak zapisać, nazywamy złożonymi (np. najmniejszą liczbą złożoną jest 4, bo 2 × 2 = 4). Liczba 1 nie jest ani pierwsza, ani złożona. Najmniejszą liczbą pierwszą jest 2 (to jedyna parzysta liczba pierwsza); kolejne to 3, 5, 7, 11, 13, 17, 19 itd. Nie istnieje największa liczba pierwsza — zbiór liczb pierwszych jest nieskończony.

Własności i przykłady

  • Każda liczba pierwsza p ma dokładnie dwa dzielniki: 1 i p.
  • Z wyjątkiem 2 wszystkie liczby pierwsze są nieparzyste (bo parzyste liczby większe niż 2 dzielą się przez 2).
  • Fundamentalne twierdzenie arytmetyki: każda liczba naturalna większa od 1 da się jednoznacznie (z dokładnością do kolejności czynników) rozłożyć na iloczyn liczb pierwszych.
  • Są specjalne rodzaje liczb pierwszych: bliźniacze (np. 11 i 13), Mersenne'a (postaci 2^p − 1 dla pewnych p), Fermata, bezpieczne i inne.

Dowód nieskończoności liczb pierwszych

Klasyczny dowód Euklidesa jest prosty i elegancki: przyjmijmy, że istnieje skończony zbiór liczb pierwszych p1, p2, ..., pn. Rozważ liczbę P = p1·p2·...·pn + 1. Liczba P nie dzieli się przez żadną z pi (bo dzielenie daje resztę 1), więc albo P jest pierwsza, albo ma dzielnik pierwszy spoza zbioru {p1,...,pn}. W obu przypadkach otrzymujemy nową liczbę pierwszą, sprzeczną z założeniem skończoności.

Rozkład i twierdzenia

Sposób, w jaki rozmieszczone są liczby pierwsze wśród liczb naturalnych, jest przedmiotem głębokich badań. Jednym z najważniejszych rezultatów jest twierdzenie o liczbach pierwszych, które opisuje asymptotyczny rozkład liczb pierwszych i mówi w przybliżeniu, ile liczb pierwszych znajduje się poniżej danej wartości (liczba pierwsza około n ma gęstość odwrotnie proporcjonalną do logarytmu n). Istnieje też wiele nierozwiązanych problemów — jednym z najsłynniejszych jest przypuszczenie Goldbacha (każda liczba parzysta większa niż 2 jest sumą dwóch liczb pierwszych).

Jak sprawdzić, czy liczba jest pierwsza

  • Najprostsza metoda: dzielenie próbne — sprawdzamy podzielność przez wszystkie liczby pierwsze mniejsze lub równe √n. Jeśli żadna nie dzieli n, to n jest pierwsza.
  • Optymalizacje: pominięcie parzystych dzielników (po sprawdzeniu 2), sprawdzanie tylko liczb postaci 6k ± 1, użycie sita Eratostenesa do wyznaczenia wszystkich liczb pierwszych do pewnego progu.
  • Metody probabilistyczne: testy Fermata, Miller–Rabin — szybkie, dają dużą pewność, ale mogą dać wynik fałszywie pozytywny dla rzadkich liczb zwanych pseudopierwszymi.
  • Metody deterministyczne dla dużych liczb: test AKS daje deterministyczny algorytm wielomianowy, ale jest praktycznie wolniejszy od dobrze zoptymalizowanych testów probabilistycznych dla zastosowań praktycznych.

Sito Eratostenesa — prosty sposób na listę pierwszych

Sito Eratostenesa to skuteczna metoda wyznaczania wszystkich liczb pierwszych mniejszych od pewnej granicy N. Polega na kolejnych eliminacjach wielokrotności liczb pierwszych: zaczynając od 2, skreślamy wszystkie jego wielokrotności, potem przechodzimy do następnej nieskreślonej liczby (3) i skreślamy jej wielokrotności, i tak dalej do √N. Złożoność obliczeniowa można zoptymalizować, a metoda jest bardzo użyteczna w praktyce.

Zastosowania liczb pierwszych

  • Teoria kodowania i kryptografia — np. system RSA opiera się na trudności rozkładu dużych liczb złożonych na czynniki pierwsze.
  • Generator liczb losowych, protokoły zabezpieczeń, testy integralności danych.
  • Badania matematyczne: teoria liczb, badania nad rozkładem, konjektury (np. Goldbacha, bliźniaczych pierwszych).

Zagadki i przykłady do rozwiązania

  • Znajdź wszystkie liczby pierwsze mniejsze niż 100 (można użyć sita Eratostenesa).
  • Sprawdź, czy liczba 1 000 003 jest pierwsza (spróbuj dzielenia próbnego do √(1 000 003) lub testu Miller–Rabin).
  • Zagadka: udowodnij, że wśród kolejnych n! + 2, n! + 3, ..., n! + n każdy składnik jest złożony — co to pokazuje o rozmieszczeniu liczb złożonych?

Sposób, w jaki występują liczby pierwsze, pozostaje wciąż pełen wyzwań i niespodzianek dla matematyków. W miarę jak rozmiary badanych liczb rosną, wykrywanie pierwszości staje się trudniejsze, ale jednocześnie rozwijane są coraz skuteczniejsze algorytmy i techniki badawcze. Wspomniane powyżej twierdzenie o liczbach pierwszych i przypuszczenie Goldbacha to tylko dwa przykłady zagadnień, które łączą teorię z praktycznymi zastosowaniami.