thumb|Liczby naturalne od zera do stu – liczby pierwsze zaznaczone są na czerwono
Liczba pierwsza – dowolna liczba naturalna z dokładnie dwoma różnymi dzielnikami naturalnymi: jedynką () i nią samą.
Zbiór wszystkich liczb pierwszych bywa najczęściej oznaczany, symbolem :
Początek ciągu liczb pierwszych to: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 itd. .
Na liście nie ma np. liczby cztery (4), bo ma ona trzy (3) różne dzielniki naturalne, mianowicie: 1, 2 i 4. Podobnie jest z liczbą sześć (6), która ma cztery (4) dzielniki: 1, 2, 3 i 6. O takich liczbach – które mają więcej niż dwa (2) dzielniki – mówi się, że są złożone (że są liczbami złożonymi). Z podanych definicji wynika, że liczby 0 i 1 nie są ani pierwsze, ani złożoneZero nie jest liczbą pierwszą, bo ma nieskończoną liczbę dzielników, a nie dokładnie dwa. Jeden nie jest liczbą pierwszą, bo ma tylko jeden dzielnik (siebie), a nie dokładnie dwa. Zero i jeden nie są liczbami złożonymi, bo nie są większe od 1..
Liczby pierwsze są badane od antyku, a w XXI wieku te badania dalej trwają. Jednym z powodów są zastosowania tych liczb – między innymi do szyfrowania, czyli w kryptografii. Korzystają z nich niektóre znane algorytmy jak RSA. Rozwój tych algorytmów zapewnia ewolucję projektów wyszukiwania ogromnych liczb pierwszych, takich jak GIMPS.
Podstawowe własności mały|Euklides z Aleksandrii (IV–III w. p.n.e.) – badał między innymi liczby pierwsze
Najmniejszy różny od jedynki dzielnik naturalny, dla każdej liczby naturalnej, większej od jedności; jest liczbą pierwszą. Euklides z Aleksandrii pokazał, że liczb pierwszych jest nieskończenie wiele: Dowód Euklidesa. Niech będzie skończonym zbiorem liczb pierwszych. Niech będzie iloczynem wszystkich liczb występujących w (gdy jest puste, to ). Jedynym wspólnym dzielnikiem liczb oraz jest 1. Zatem żadna liczba pierwsza, występująca w nie jest dzielnikiem liczby Ale Więc ma dzielnik który jest liczbą pierwszą. Liczba pierwsza nie należy do (bo jest dzielnikiem liczby ). Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych (to jest tak zwane twierdzenie o jednoznaczności rozkładu na czynniki pierwsze). Twierdzenie to był w stanie udowodnić już Euklides (stworzył niezbędne narzędzia), ale uczynił to dopiero Gauss. Twierdzenie to oznacza, że liczby pierwsze są w pewnym sensie atomami (dla liczb naturalnych w ogóle), z których przy pomocy mnożenia zbudowane są pozostałe liczby.
Wyznaczanie Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym, można posłużyć się algorytmem, nazywanym często sitem Eratostenesa.
Algorytm ten przebiega w sposób następujący: jeśli liczba naturalna większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z to z tego wnioskujemy, że samo jest liczbą pierwszą.
Sito Eratostenesa – metoda znajdowania liczb pierwszych
Metoda dająca odpowiedź na pytanie, czy dana liczba naturalna jest pierwsza, czy nie, nosi nazwę testu pierwszości. Wśród takich metod praktyczne zastosowanie mają testy probabilistyczne, to znaczy takie, które pozwalają określić pierwszość liczby z dostatecznie dużym prawdopodobieństwem, np.: test pierwszości Millera-Rabina, test pierwszości Solovaya-Strassena.
Rozkład ! na czynniki pierwsze Niech oznacza wykładnik, z którym liczba pierwsza występuje w rozkładzie liczby naturalnej (waluacja p-adyczna). Wtedy: (wzór Legendre’a),
gdzie jest jedyną liczbą całkowitą, spełniającą nierówność
dla dowolnego rzeczywistego Liczbę nazywamy częścią całkowitą liczby rzeczywistej Powyższa suma jest skończona, gdyż tylko skończona liczba jej składników jest różna od 0 – mianowicie pierwsze wyrazów.
Literatura: na przykładLew G. Sznirelman, Liczby pierwsze, PWN, Warszawa 1954. – rozdział 7.0William J. LeVeque © 1977, Fundamentals of Number Theory, Dover Publications 1996, .; – rozdział 6.3, Twierdzenie 6.9.
Rozkład środkowego współczynnika dwumianowego Zbadajmy gdy liczba pierwsza należy do przedziału Ogólnie:
Ponieważ
dla dowolnej liczby rzeczywistej to ze wzoru na z poprzedniego fragmentu, wynika, że
Równość pozwala powyższą nierówność wyrazić równoważnie jako
czyli:
Twierdzenie. Jeżeli to
Prawdziwe jest także twierdzenie:
Twierdzenie. Jeżeli jest liczbą naturalną, oraz – liczbą pierwszą z przedziału to nie jest dzielnikiem współczynnika
Rozmieszczenie thumb|Liczby pierwsze na spirali Ulama thumb|Rozmieszczenie pierwszych 39131 liczb pierwszych Rozmieszczenie liczb pierwszych wśród liczb naturalnych spełnia pewne prawidłowości statystyczne, ale nie jest znany żaden wzór, który pozwalałby wyznaczać liczby pierwsze w sposób bardziej efektywny niż metoda Eratostenesa.
Kilka poniższych twierdzeń przybliża zagadnienia związane z badaniem rozmieszczenia liczb pierwszych na osi liczbowej.
Szereg odwrotności wszystkich liczb pierwszych Niech oznacza zbiór liczb pierwszych. Leonhard Euler udowodnił, że szereg liczbowy odwrotności wszystkich liczb pierwszych jest rozbieżny. Sugeruje to, że liczby pierwsze nie mogą być rozłożone zbyt „rzadko” na osi liczbowej. Rozbieżność tego szeregu daje też nowy dowód na istnienie nieskończenie wielu liczb pierwszych.
Dowód twierdzenia Eulera
Niech
Ponieważ
to
dla dowolnego naturalnego Wystarczy zatem dowieść, że może być dowolnie wielkie.
Szereg geometryczny:
oraz rozkładalność liczb naturalnych na iloczyny liczb pierwszych, daje nierówność
Ale a więc:
zatem
gdy Koniec dowodu.
Franz Mertens uzyskał podobne oszacowanie także od góry.
Oszacowania iloczynu odcinka liczb pierwszych Jasne jest, że zachodzi podzielność oraz równość
Więc dla n > 1 otrzymujemy: Wiemy także, że
Powyższe współczynniki dwumianowe są składnikami sumy ze wzoru Newtona na Są więc one mniejsze od (ostro, bo w sumie Newtona występują też inne składniki). Tak więc mamy nasze pierwsze oszacowanie (od góry) iloczynu odcinka liczb pierwszych:
dla a nawet dla każdego Bardziej atrakcyjne byłoby oszacowanie iloczynu początkowego odcinka liczb pierwszych
Ale przynajmniej możemy powyższą nierówność przepisać w postaci:
dla każdego
dla każdego naturalnego
Twierdzenie
dla każdej liczby całkowitej Dowód Można sprawdzić bezpośrednio, że twierdzenie zachodzi dla Rozpatrzmy parzyste Wtedy Możemy więc indukcyjnie założyć, że twierdzenie zachodzi dla Zatem korzystając ze wcześniejszego oszacowania iloczynu odcinka (niepoczątkowego), które zachodziło dla każdego otrzymujemy:
Więc indukcja zachodzi dla parzystego przypadku. Dla nieparzystego mamy co pozwala nam stosować założenie indukcyjne dla (oraz znowu wcześniejsze oszacowanie):
Koniec dowodu
Uwaga. Twierdzenie zachodzi dla każdej liczby rzeczywistej a nie tylko dla całkowitych.
Postulat Bertranda – twierdzenie Czebyszewa
Czebyszew udowodnił następujące twierdzenie (patrz – rozdział 9, – rozdział 6.9): Twierdzenie Dla dowolnej liczby naturalnej większej od 1, między liczbami a istnieje co najmniej jedna liczba pierwsza.
Dowód Wyżej zdefiniowaliśmy i odnotowaliśmy następujące trzy twierdzenia: Jeżeli to albo krótko: Jeżeli jest liczbą naturalną, oraz – liczbą pierwszą z przedziału to nie jest dzielnikiem współczynnika dla każdego rzeczywistego
Zdefiniujmy:
Twierdzenia dowiedziemy, pokazując, że
Otóż gdzie:
Dla liczba liczb pierwszych nie większych od jest mniejsza od Zatem gdy ma nie więcej, niż czynników, z których każdy jest ograniczony od góry przez Zatem:
oraz
Z drugiej strony jest największym z składników sumy Newtona przedstawiającej przy czym dwa składniki równe są 1, więc:
Przy tym nierówność jest ostra dla a co dopiero dla Dla takich nierówność po obustronnym pomnożeniu przez wyniknie z
czyli
czyli, po zlogarytmowaniu:
Z tego, że dla zachodzi otrzymujemy dla że:
Wystarczy zatem dowieść
czyli
Ponieważ to wystarczy dowieść, że:
co dla jest równoważne z:
Nierówność ta zachodzi dla każdego Więc twierdzenie zachodzi dla każdego Dla twierdzenie zachodzi, gdyż kolejne liczby pierwsze w następującym ciągu są mniejsze od podwojonego poprzednika:
Koniec dowodu.
Dla dowolnej, nieujemnej liczby całkowitej bez większego trudu można by dowieść nierówności:
lub słabszej
dla wszystkich gdzie stała C zależałaby od Nierówność ta zapewniłaby liczb pierwszych pomiędzy i dla wszystkich, dostatecznie dużych (dla ).
Metoda Czebyszewa Czebyszew wprowadził iloczyny odcinków kolejnych liczb naturalnych, i ich kombinacje iloczynowo-ilorazowe. Z jednej strony takie iloczyny dają się dokładnie szacować, a z drugiej, dobierając starannie ich kombinacje, uzyskuje się iloczyny w których gęsto jest od kolejnych liczb pierwszych w potędze 1.
Metodę Czebyszewa uprościł Srinivasa Ramanujan (patrz: Lew Sznirelman), który skupił się na środkowym współczynniku dwumianowym, czyli na podzielonym dwukrotnie przez Działa to dobrze w przypadku postulatu Bertranda, ze względu na odcinek pomiędzy daną liczbą naturalną i dwukrotnie większą. Jednak Czebyszew uzyskał mocniejszy wynik, gdyż zamiast proporcji 2 wystarczyła mu dowolnie ustalona powyżej 6/5 (patrz). Udowodnione po Czebyszewie twierdzenie o rozmieszczeniu liczb pierwszych natychmiast daje podobny wynik dla wszelkich proporcji ustalonych powyżej 1.
Wariacja Erdősa Paul Erdős wzmocnił twierdzenie Czebyszewa dowodząc Twierdzenie Dla dowolnej liczby naturalnej między liczbami a znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci oraz co najmniej jedna postaci
Twierdzenie Dirichleta Poniższe twierdzenie zostało udowodnione przez Dirichleta Twierdzenie W dowolnym ciągu arytmetycznym liczb naturalnych: takim, że i są względnie pierwsze, występuje nieskończenie wiele liczb pierwszych. (Przy ustalonym ilość liczb pierwszych dla różnych a, względnie pierwszych z liczbą jest w pewnym asymptotycznym sensie taka sama).
Przypadki szczególne Ciąg arytmetyczny liczb naturalnych Niech będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech będzie ich iloczynem. Wtedy nie może mieć wyłącznie dzielników pierwszych dających resztę z dzielenia przez (ich iloczyn dałby resztę ). Zatem istnieje taki dzielnik pierwszy że Dzielnik ten nie należy do czyli żaden taki zbiór skończony nie zawiera wszystkich liczb pierwszych z naszego ciągu arytmetycznego, a więc takich liczb pierwszych jest nieskończenie wiele.
Uwaga. Ciąg arytmetyczny liczb naturalnych zawiera powyższy, ale ma tylko jedną więcej liczbę pierwszą, mianowicie
Ciąg arytmetyczny liczb naturalnych Dowód, że ten ciąg zawiera nieskończenie wiele liczb pierwszych podobny jest do wcześniejszego, powyżej, dla przypadku mod 6. Taki prosty dowód działa tylko dla reszty -1, i tylko mod n: =3 lub 4 lub 6, kiedy to jedynymi resztami mod n, względnie pierwszymi z n, są liczby -1 oraz 1 (mod n). Ciąg arytmetyczny liczb naturalnych Euler pokazał, że nieparzysty dzielnik pierwszy liczby naturalnej postaci musi dać resztę 1 z dzielenia przez 4. Niech więc będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech będzie ich iloczynem. Wtedy musi mieć dzielnik pierwszy z naszego ciągu. Ale dzielnik taki nie może należeć do co oznacza, że zbiór wszystkich liczb pierwszych w naszym ciągu jest nieskończony.
Twierdzenie o liczbach pierwszych
Podstawowe twierdzenie o rozmieszczeniu liczb pierwszych wśród liczb naturalnych sformułował Gauss, który na podstawie badań empirycznych zasugerował, że liczba π(n) liczb pierwszych w przedziale opisana jest zależnością:
gdzie symbol oznacza resztę logarytmu całkowego, a „~” oznacza równość asymptotyczną rozumianą jako
Rozwinięcie logarytmu całkowego w szereg daje oszacowanie:
Gauss nie udowodnił tego twierdzenia – dopiero pod koniec XIX wieku zostało ono udowodnione przez Hadamarda i de la Vallee Poussina.
Najprostszą postacią przybliżenia funkcji π jest pierwszy element tego szeregu:
W tym wypadku także zachodzi asymptotyczna równość:
Hipoteza Riemanna