liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i siebie samą Z Wikipedii, wolnej encyklopedii
Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą[1][2]. Nie istnieje powszechnie przyjęty symbol zbioru wszystkich liczb pierwszych, czasami oznacza się ten zbiór symbolem
Wykaz początkowych liczb pierwszych:
W wykazie brak np. liczby 4, bowiem ma ona 3 dzielniki: 1, 2 i 4. Podobnie z liczbą 6, która ma 4 dzielniki: 1, 2, 3 i 6.
Liczby naturalne większe od 1, które nie są pierwsze, nazywa się liczbami złożonymi. Liczby 4 i 6 są więc przykładami liczb złożonych.
Z podanych definicji wynika, że liczby 0 i 1 nie są ani pierwsze, ani złożone[a].
Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym, można posłużyć się algorytmem zwanym sitem Eratostenesa: jeśli liczba naturalna większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z to jest liczbą pierwszą.
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.
Niech oznacza wykładnik, z którym liczba pierwsza występuje w rozkładzie liczby naturalnej (waluacja p-adyczna). Wtedy[3]:
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ład[4] – rozdział 7.0[5]; – rozdział 6.3, Twierdzenie 6.9.
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 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.
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.
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.
Jasnym jest, że zachodzi podzielność
Więc dla n > 1 otrzymujemy:
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
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.
Czebyszew udowodnił następujące twierdzenie (patrz[4] – rozdział 9[5], – rozdział 6.9):
Dla dowolnej liczby naturalnej większej od 1, między liczbami a istnieje co najmniej jedna liczba pierwsza.
Wyżej zdefiniowaliśmy i odnotowaliśmy następujące trzy twierdzenia:
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 ).
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[4]), 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[5]). Udowodnione po Czebyszewie twierdzenie o rozmieszczeniu liczb pierwszych natychmiast daje podobny wynik dla wszelkich proporcji ustalonych powyżej 1.
Paul Erdős wzmocnił twierdzenie Czebyszewa dowodząc
Dla dowolnej liczby naturalnej między liczbami a znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci oraz co najmniej jedna postaci
Poniższe twierdzenie zostało udowodnione przez Dirichleta
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).
Uwaga. Ciąg arytmetyczny liczb naturalnych zawiera powyższy, ale ma tylko jedną więcej liczbę pierwszą, mianowicie
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ść:
Rozmieszczenie liczb pierwszych na osi jest też związane bezpośrednio z hipotezą Riemanna. Mianowicie, jest ona równoważna stwierdzeniu, że liczba π
(n) liczb pierwszych w przedziale wyraża się wzorem:
gdzie użyto notacji dużego O.
Według tej teorii liczb pierwszych bliźniaczych jest nieskończenie wiele.
Dla każdej liczby naturalnej istnieją takie dwie kolejne liczby pierwsze, że ich różnica wynosi nie mniej niż Można to udowodnić poprzez wykazanie, że istnieje ciąg kolejnych liczb naturalnych, z których żadna nie jest pierwsza (tj. każda jest złożona)[6].
Dowód
Dla każdej liczby naturalnej istnieją niezerowe liczby podzielne przez wszystkie liczby naturalne od do przykładowo Możemy utworzyć ciąg kolejnych liczb: Każda z nich jest podzielna odpowiednio przez Oznacza to, że istnieje ciąg kolejnych liczb naturalnych, z których żadna nie jest pierwsza.
Koniec dowodu
Dwie liczby pierwsze są bliźniacze, jeśli ich różnica jest równa Przykłady: 3 i 5, 5 i 7, 11 i 13, 17 i 19, 29 i 31, 41 i 43, 59 i 61, 71 i 73...
5 jest bliźniacza zarówno z 3, jak i z 7.
Nie wiadomo, czy istnieje nieskończenie wiele bliźniaczych liczb pierwszych.
Największa znana para liczb pierwszych bliźniaczych (stan na listopad 2024) to Liczby te, znalezione we wrześniu 2016, mają 388342 cyfry w zapisie dziesiętnym[7].
Cztery liczby pierwsze są czworacze, jeśli są postaci np. 5, 7, 11 i 13 lub 101, 103, 107 i 109. Są to dwie pary liczb bliźniaczych w najbliższym możliwym sąsiedztwie. Największe znane liczby czworacze to:
Liczby te, znalezione w lutym 2019, mają po 10132 cyfry w zapisie dziesiętnym[8].
Liczba pierwsza jest izolowana, jeśli najbliższa jej liczba pierwsza różni się od co najmniej o 4. Przykłady: 23, 89, 157, 173.
Liczbę
nazywamy -tą liczbą Mersenne’a (dla ). Tak otrzymana funkcja jest homomorfizmem ze względu na największy wspólny dzielnik NWD:
Liczby pierwsze Mersenna są to liczby pierwsze, będące jednocześnie liczbami Mersenne’a. Przykłady: 3, 7, 31, 127, 8191...
Warunkiem koniecznym, żeby liczba Mersenne’a była pierwsza jest pierwszość liczby Jednak nie dla każdej liczby pierwszej liczba jest pierwsza; na przykład:
Dlatego bada się także dzielniki Mersenne’a, a mianowicie dzielniki liczb Mersenne’a dla pierwszego, zwłaszcza dzielniki pierwsze.
W sierpniu 2008 roku największą znaną liczbą pierwszą była liczba Mersenne’a – do jej zapisania w układzie dziesiętnym trzeba użyć 12978189 cyfr. Wygrano w ten sposób 100 tysięcy dolarów ufundowane przez Electronic Frontier Foundation dla odkrywcy liczby pierwszej o co najmniej 10 milionach cyfr[9]. Obecnie największą znaną, 52. liczbą pierwszą Mersenne’a jest która w zapisie dziesiętnym ma 41 024 320 cyfr. Odkrył ją 12 października 2024 roku Luke Durant w ramach projektu GIMPS[10]. Test Lucasa-Lehmera jest efektywną metodą sprawdzenia, czy liczba Mersenne’a jest liczbą pierwszą.
Liczby złożone Mersenne’a mogą być liczbami złożonymi, gdy liczba jest liczbą pierwszą lub gdy jest liczbą złożoną, to jest także liczbą złożoną.
Niech oraz będą liczbami pierwszymi, przy czym 2 jest resztą kwadratową (tzn. dla pewnej liczby całkowitej ). Wtedy więc liczba Mersenne’a jest wtedy złożona dla
Przy założeniach twierdzenia, niech dla pewnej liczby całkowitej Wtedy na mocy małego twierdzenia Fermata:
czyli Ponieważ dla zachodzi to jest dzielnikiem właściwym, więc jest złożone dla (przy pozostałych założeniach).
Przykłady: 2 jest resztą kwadratową nieparzystej liczby pierwszej wtedy i tylko wtedy, gdy daje resztę -1 lub 1 z dzielenia przez 8. Ponadto chcemy, żeby było liczbą pierwszą. Zatem przykładów ilustrujących powyższe twierdzenie, należy szukać wyłącznie wśród dających resztę -1 z dzielenia przez 8, czyli wśród liczb postaci: Wtedy Więc nie powinno dawać reszty 1 z dzielenia przez 3, by uniknąć podzielności oraz nie powinno dawać reszty -1, by uniknąć Zatem należy ograniczyć się do podzielnych przez 3, czyli do
Stąd najmniejszym przykładem, ilustrującym powyższe twierdzenie jest Otrzymujemy podzielność Następnym jest czyli podzielność
Są to liczby pierwsze postaci Jak dotąd znanych jest pięć liczb Fermata, które są pierwsze: 3, 5, 17, 257 i 65537.
A oto przykładowe faktoryzacje liczb Fermata
Skoro liczby Fermata nie muszą być pierwsze, to bada się dzielniki Fermata, czyli dzielniki liczb Fermata, zwłaszcza dzielniki pierwsze.
Liczbę pierwszą nazywamy liczbą pierwszą Sophie Germain jeżeli liczba również jest pierwsza. Oto kilka liczb tego rodzaju: 2, 3, 5, 11, 23, 29, 41, 53, 83... Liczby pierwsze Germain związane są ze szczególnymi przypadkami wielkiego twierdzenia Fermata. Liczby pierwsze Germain są związane z liczbami złożonymi Mersenne’a.
Liczby będące średnią kolejnych dwóch liczb pierwszych większych od 2 (ang. interprime numbers). Początkowe liczby pomiędzy pierwsze to: 4, 6, 9, 12, 15, 18, 21, 26, 30, 34,…
Liczby te są liczbami złożonymi, ponieważ analizie poddajemy kolejne liczby pierwsze.
Liczby złożone które spełniają warunek:
Istnieje nieskończenie wiele liczb pseudopierwszych parzystych, jak i nieparzystych. Co więcej, dla każdej liczby pierwszej istnieje nieskończenie wiele liczb pseudopierwszych podzielnych przez Liczbami pseudopierwszymi dla danego testu pierwszości nazywamy liczby złożone, których ten test nie rozpoznaje (powyższy przykład to liczby pseudopierwsze dla testu Fermata przy równym 2).
To pary liczb pierwszych, z których jedna powstaje przez zapisanie cyfr dziesiętnych drugiej w odwrotnej kolejności.
Przykłady: 13 i 31, 17 i 71, 37 i 73, 79 i 97, 107 i 701,...
To liczby pierwsze, które nie zmieniają się, gdy ich cyfry dziesiętne zapiszemy w odwrotnej kolejności.
Przykłady: 11, 101, 131, 151, 181, 191, 929.
Zagadnienia dotyczące liczb pierwszych należą do teorii liczb. Istnieją w niej dotąd nierozstrzygnięte problemy:
Największa znana dotąd liczba pierwsza to 52. liczba pierwsza Mersenne’a: , która ma 41 024 320 cyfr w zapisie dziesiętnym[11]