Tekst źródłowy strony Liczby pierwsze

[[Plik:Primencomposite0100.svg|thumb|Liczby naturalne od zera do stu – liczby pierwsze zaznaczone są na czerwono]]

'''Liczba pierwsza''' – [[liczby naturalne|liczba naturalna]] większa od [[1 (liczba)|1]], która ma dokładnie dwa [[dzielnik]]i naturalne: [[1 (liczba)|jedynkę]] i siebie samą<ref name="knuth_mk128">{{Cytuj książkę |autor = Ronald L. Graham, Donald E. Knuth, Oren Patashnik |tytuł = Matematyka konkretna |wydawca = PWN |data = 2001 |strony = 128 |isbn = 8301121246}}</ref><ref>{{Encyklopedia PWN | tytuł = Liczby pierwsze | id = 3932372 | data dostępu = 2021-07-24}}</ref>. Nie istnieje powszechnie przyjęty symbol zbioru wszystkich liczb pierwszych, czasami oznacza się ten zbiór symbolem <math>\mathbb{P}.</math>

Wykaz początkowych liczb pierwszych:
: [[2 (liczba)|2]], [[3 (liczba)|3]], [[5 (liczba)|5]], [[7 (liczba)|7]], [[11 (liczba)|11]], [[13 (liczba)|13]], [[17 (liczba)|17]], [[19 (liczba)|19]], [[23 (liczba)|23]], [[29 (liczba)|29]], [[31 (liczba)|31]], [[37 (liczba)|37]], [[41 (liczba)|41]], [[43 (liczba)|43]], [[47 (liczba)|47]], [[53 (liczba)|53]], [[59 (liczba)|59]], [[61 (liczba)|61]], [[67 (liczba)|67]], [[71 (liczba)|71]], [[73 (liczba)|73]], [[79 (liczba)|79]], [[83 (liczba)|83]], [[89 (liczba)|89]], [[97 (liczba)|97]] itd. {{OEIS|id=A000040}}.

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ę '''[[liczby złożone|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 (liczba)|1]] nie są ani pierwsze, ani złożone<ref group="uwaga">Zero 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.</ref>.

== Podstawowe własności ==
* Najmniejszy różny od jedynki dzielnik naturalny liczby naturalnej, większej od jedności, jest liczbą pierwszą.
* [[Euklides]] pokazał, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych:
*: Niech <math>X</math> będzie skończonym zbiorem liczb pierwszych. Niech <math>x</math> będzie iloczynem wszystkich liczb występujących w <math>X</math> (gdy <math>X</math> jest puste, to <math>x = 1</math>). Jedynym wspólnym dzielnikiem liczb <math>x</math> oraz <math>x + 1</math> jest 1. Zatem żadna liczba pierwsza, występująca w <math>X,</math> nie jest dzielnikiem liczby <math>x+1.</math> Ale <math>x + 1 > 1.</math> Więc <math>x + 1</math> ma dzielnik <math>p,</math> który jest liczbą pierwszą. Liczba pierwsza <math>p</math> nie należy do <math>X</math> (bo jest dzielnikiem liczby <math>x + 1</math>).
* Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych<ref name="knuth_mk128" />. Twierdzenie to był w stanie udowodnić już Euklides (stworzył niezbędne narzędzia), ale uczynił to dopiero [[Carl Friedrich Gauss|Gauss]]. Twierdzenie to oznacza, że liczby pierwsze są w pewnym sensie atomami, z których przy pomocy [[Mnożenie|mnożenia]] zbudowane są pozostałe liczby.

== Wyznaczanie ==
Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym, można posłużyć się algorytmem zwanym [[sito Eratostenesa|sitem Eratostenesa]]: jeśli liczba naturalna <math>N</math> większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z <math>N,</math> to <math>N</math> jest liczbą pierwszą.

[[Plik:Animacja liczb pierwszych.gif|Sito Eratostenesa – metoda znajdowania liczb pierwszych]]

Metoda dająca odpowiedź na pytanie, czy dana liczba naturalna jest pierwsza, czy nie, nosi nazwę [[test pierwszości|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 Millera-Rabina|test pierwszości Millera-Rabina]], [[test pierwszości Solovaya-Strassena]].

== Rozkład <math>n</math>! na czynniki pierwsze ==
Niech <math>\operatorname{ord}_p(n)</math> oznacza wykładnik, z którym liczba pierwsza <math>p</math> występuje w rozkładzie liczby naturalnej <math>n</math> (waluacja p-adyczna). Wtedy<ref name="knuth_mk135-139">{{Cytuj książkę |autor = Ronald L. Graham, Donald E. Knuth, Oren Patashnik |tytuł = Matematyka konkretna |wydawca = PWN |data = 2001 |strony = 135–139 |isbn = 8301121246}}</ref>:
: <math>\operatorname{ord}_p(n!) = \sum_{k=1}^\infty\left\lfloor \tfrac{n}{p^k}\right\rfloor</math> (wzór [[Adrien-Marie Legendre|Legendre’a]]),

gdzie <math>\lfloor x \rfloor</math> jest jedyną [[Liczby całkowite|liczbą całkowitą]], spełniającą nierówność
: <math>x-1 < \lfloor x \rfloor \leqslant x</math>

dla dowolnego rzeczywistego <math>x.</math> Liczbę <math>\lfloor x \rfloor</math> nazywamy ''[[podłoga i sufit|częścią całkowitą]]'' liczby rzeczywistej <math>x.</math> Powyższa suma jest skończona, gdyż tylko skończona liczba jej składników jest różna od 0 – mianowicie pierwsze <math>\left\lfloor \tfrac{\ln n}{\ln p}\right\rfloor</math> wyrazów.

<blockquote>Literatura: na przykład<ref name="SzLP">Lew G. Sznirelman, ''Liczby pierwsze'', PWN, Warszawa 1954.</ref> – rozdział 7.0<ref name="LV_Fnd">William J. LeVeque © 1977, ''Fundamentals of Number Theory'', Dover Publications 1996, {{ISBN|0-486-68906-9}}.</ref>; – rozdział 6.3, Twierdzenie 6.9.</blockquote>

== Rozkład środkowego współczynnika dwumianowego ==
Zbadajmy <math>o_p(n) := \operatorname{ord}_p \binom{2n}{n}.</math> <math>o_p(n) = 1,</math> gdy liczba pierwsza <math>p</math> należy do przedziału <math>n < p \leqslant 2n.</math> Ogólnie:
: <math>o_p(n) = \operatorname{ord}_p((2n)!) - 2\operatorname{ord}_p(n!).</math>

Ponieważ
: <math>0 \leqslant \lfloor 2x \rfloor - 2\lfloor x \rfloor \leqslant 1</math>

dla dowolnej liczby rzeczywistej <math>x,</math> to ze wzoru na <math>\operatorname{ord}_p(n!),</math> z poprzedniego fragmentu, wynika, że
: <math>o_p(n) \leqslant \left\lfloor \tfrac{\ln (2n)}{\ln p}\right\rfloor.</math>

Równość <math>p^{(\ln x)/(\ln p)} = x</math> pozwala powyższą nierówność wyrazić równoważnie jako
: <math>p^{o_p(n)} \leqslant 2n,</math>

czyli:

'''Twierdzenie.''' Jeżeli <math>p^k | \binom{2n}{n},</math> to <math>p^k \leqslant 2n.</math>

Prawdziwe jest także twierdzenie:

'''Twierdzenie.''' Jeżeli <math>n > 2</math> jest liczbą naturalną, oraz <math>p</math> – liczbą pierwszą z przedziału <math>\tfrac{2}{3}n < p \leqslant n,</math> to <math>p</math> nie jest dzielnikiem współczynnika <math>\binom{2n}{n}.</math>

== Rozmieszczenie ==
[[Plik:Ulps000-1.png|thumb|300px|Liczby pierwsze na [[Spirala Ulama|spirali Ulama]]]]
[[Plik:Visualization of the first 39131 primes.png|thumb|300px|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 [[oś liczbowa|osi liczbowej]].

=== Szereg odwrotności wszystkich liczb pierwszych ===
Niech <math>\mathbb{P}</math> oznacza zbiór liczb pierwszych. [[Leonhard Euler]] udowodnił, że [[Szereg (matematyka)|szereg liczbowy]] <math>\sum_{p \in \mathbb{P}} \tfrac{1}{p}</math> odwrotności wszystkich liczb pierwszych jest [[Szereg (matematyka)|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 <math>\sum_{p \in \mathbb{P}}\tfrac{1}{p}=\infty</math>'''

Niech
: <math>P(x) := \sum_{p \in \mathbb{P}, p \leqslant x} \tfrac{1}{p},</math>
: <math>Q(x) := \sum_{p \in \mathbb{P}, p \leqslant x} \tfrac{1}{p-1}.</math>

Ponieważ
: <math>1 = \left(\tfrac{1}{1} - \tfrac{1}{2}\right) + \left(\tfrac{1}{2} - \tfrac{1}{3}\right) + \ldots,</math>

to
: <math>P(x) > Q(x) - 1</math>

dla dowolnego naturalnego <math>x.</math> Wystarczy zatem dowieść, że <math>Q(x)</math> może być dowolnie wielkie.

[[Szereg geometryczny]]:
: <math>1 + \tfrac{1}{p-1} = \tfrac{1}{1-\tfrac{1}{p}} = 1 + \tfrac{1}{p} + \tfrac{1}{p^2} + \ldots</math>

oraz rozkładalność liczb naturalnych na iloczyny liczb pierwszych, daje nierówność
: <math>\prod_{p \in \mathbb{P}, p \leqslant x} \left(1+\tfrac{1}{p-1}\right) = \prod_{p \in \mathbb{P}, p \leqslant x} \left(1 + \tfrac{1}{p} + \tfrac{1}{p^2} + \ldots\right) \geqslant \sum_{n=1}^x \tfrac{1}{n}.</math>

Ale <math>\tfrac{1}{p-1} > \ln\left(1 + \tfrac{1}{p-1}\right),</math> a więc:
: <math>Q(x) > \ln\left(\prod_{p \in \mathbb{P}, p \leqslant x} \left(1+\tfrac{1}{p-1}\right)\right) \geqslant \ln\left(\sum_{n=1}^x \tfrac{1}{n}\right) > \ln(\ln(x+1)) \to \infty,</math>

zatem
: <math>P(x) > \ln(\ln(x+1)) - 1 \to \infty,</math>

gdy <math>x \to \infty.</math> '''Koniec dowodu'''.

[[Franciszek Mertens|Franz Mertens]] uzyskał podobne oszacowanie <math>P(x)</math> także od góry.

=== Oszacowania iloczynu odcinka liczb pierwszych ===
Jasnym jest, że zachodzi podzielność
: <math>\prod_{p\in\mathbb{P}, n < p \leqslant 2n}p | \binom{2n}{n}</math> oraz równość <math>\binom{2n}{n} = 2\cdot \binom{2n - 1}{n-1}.</math>

Więc dla n > 1 otrzymujemy:
: <math>\prod_{p\in\mathbb{P}, n < p \leqslant 2n}p | \binom{2n - 1}{n-1}.</math> Wiemy także, że <math>\binom{2n - 1}{n - 1} = \binom{2n - 1}{n}.</math>

Powyższe współczynniki dwumianowe są składnikami sumy ze wzoru Newtona na <math>(1+1)^{2n -1}.</math> Są więc one mniejsze od <math>2^{2n - 2} = 4^{n-1}</math> (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:
: <math>\prod_{p\in\mathbb{P}, n < p \leqslant 2n}p < 4^{n-1}</math>

dla <math>n > 2,</math> a nawet dla każdego <math>n > 1.</math> Bardziej atrakcyjne byłoby oszacowanie iloczynu początkowego odcinka liczb pierwszych
: <math>\prod P(x) := \prod \{p \in \mathbb{P} : p \leqslant x\}</math>

Ale przynajmniej możemy powyższą nierówność przepisać w postaci:
: <math>\frac{\prod P(2n)}{\prod P(n)} < 4^{n-1}</math>

dla każdego <math>n > 1.</math>
: <math>\prod P(2n -1) = \prod P(2n)</math>

dla każdego naturalnego <math>n > 1.</math>

; Twierdzenie
:: <math>\prod P(x) \leqslant \tfrac{1}{2} 4^{x-1}</math>
: dla każdej liczby całkowitej <math>x > 1.</math>
; Dowód: Można sprawdzić bezpośrednio, że twierdzenie zachodzi dla <math>x=2,3.</math>
Rozpatrzmy parzyste <math>x > 3.</math> Wtedy <math>1 < x/2 <x.</math> Możemy więc indukcyjnie założyć, że twierdzenie zachodzi dla <math>x/2.</math> Zatem korzystając ze wcześniejszego oszacowania iloczynu odcinka (niepoczątkowego), które zachodziło dla każdego <math>x := 2n > 2,</math> otrzymujemy:
: <math>\prod P(x) < \prod P\left(\tfrac{x}{2}\right) 4^{\tfrac{x}{2}-1} \leqslant \tfrac{1}{2} 4^{\tfrac{x}{2}-1} 4^{\tfrac{x}{2}-1} = \tfrac{1}{2} 4^{x-2}.</math>

Więc indukcja zachodzi dla parzystego przypadku. Dla nieparzystego <math>x > 3</math> mamy <math>1 < \tfrac{x+1}{2} < x,</math> co pozwala nam stosować założenie indukcyjne dla <math>\tfrac{x+1}{2}</math> (oraz znowu wcześniejsze oszacowanie):
: <math>\prod P(x) < \prod P\left(\tfrac{x+1}{2}\right) 4^{\tfrac{x-1}{2}} \leqslant \tfrac{1}{2} 4^{\tfrac{x-1}{2}} 4^{\tfrac{x-1}{2}} = \tfrac{1}{2} 4^{x-1}</math>

'''Koniec dowodu'''

'''Uwaga.''' Twierdzenie zachodzi dla każdej liczby rzeczywistej <math>x \geqslant 2,</math> a nie tylko dla całkowitych.

=== Postulat Bertranda – twierdzenie Czebyszewa ===
{{Osobny artykuł|Postulat Bertranda}}
[[Pafnutij Czebyszew|Czebyszew]] udowodnił następujące twierdzenie (patrz<ref name="SzLP" /> – rozdział 9<ref name="LV_Fnd" />, – rozdział 6.9):
; Twierdzenie
Dla dowolnej liczby naturalnej <math>n</math> większej od 1, między liczbami <math>n</math> a <math>2n</math> istnieje co najmniej jedna liczba pierwsza.

; Dowód
Wyżej zdefiniowaliśmy <math>o_p(n)</math> i odnotowaliśmy następujące trzy twierdzenia:
* Jeżeli <math>p^k | \binom{2n}{n},</math> to <math>p^k \leqslant 2n;</math> albo krótko: <math>p^{o_p(n)} \leqslant 2n.</math>
* Jeżeli <math>n > 2</math> jest liczbą naturalną, oraz <math>p</math> – liczbą pierwszą z przedziału <math>\tfrac{2}{3} n < p \leqslant n,</math> to <math>p</math> nie jest dzielnikiem współczynnika <math>\binom{2n}{n}.</math>
* <math>\prod P(x) \leqslant \tfrac{1}{2} 4^{x-1}</math> dla każdego rzeczywistego <math>x > 1.</math>

Zdefiniujmy:
: <math>L(n) := \prod_{p\in\mathbb{P}, p \leqslant n} p^{o_p(n)}.</math>

Twierdzenia dowiedziemy, pokazując, że <math>L(n) < \binom{2n}{n}.</math>

Otóż <math>L(n) = M(n) N(n),</math> gdzie:
: <math>M(n) := \prod\left\{p^{o_p(n)} : p \leqslant \sqrt{2n}, p\in \mathbb{P}\right\}</math>
: <math>N(n) := \prod\left\{p\in \mathbb{P} : \sqrt{2n} < p \leqslant \tfrac{2}{3} n\right\}</math>

Dla <math>x > 8</math> liczba liczb pierwszych nie większych od <math>x</math> jest mniejsza od <math>\tfrac{x}{2}.</math> Zatem gdy <math>n>32,</math> <math>M(n)</math> ma nie więcej, niż <math>\sqrt\tfrac{n}{2}</math> czynników, z których każdy jest ograniczony od góry przez <math>2n.</math> Zatem:
: <math>M(n) \leqslant (2n)^{\sqrt\tfrac{n}{2}}</math>

oraz
: <math>N(n) \leqslant \prod\left\{p\in \mathbb{P} : p \leqslant \tfrac{2}{3} n\right\} \leqslant \tfrac{1}{2} 4^{\tfrac{2}{3} n - 1}.</math>

Z drugiej strony <math>\binom{2n}{n}</math> jest największym z <math>2n + 1</math> składników sumy Newtona przedstawiającej <math>(1+1)^{2n} = 4^n,</math> przy czym dwa składniki równe są 1, więc:
: <math>\binom{2n}{n} \geqslant \tfrac{4^n - 2}{2n - 1} \geqslant \tfrac{4^n}{2n}</math>

Przy tym nierówność jest ostra dla <math>n > 1,</math> a co dopiero dla <math>n > 32.</math> Dla takich <math>n,</math> nierówność <math>M(n) N(n) < \binom{2n}{n},</math> po obustronnym pomnożeniu przez <math>2n,</math> wyniknie z
: <math>n (2n)^{\sqrt\tfrac{n}{2}} 4^{\tfrac{2}{3} n - 1} < 4^n,</math>

czyli
: <math>n (2n)^{\sqrt\tfrac{n}{2}} < 4^{\tfrac{n}{3} + 1}</math>

czyli, po zlogarytmowaniu:
: <math>\left(1+\sqrt\tfrac{n}{2}\right) \tfrac{\ln(n)}{\ln(4)} < \left(\tfrac{n}{3} + 1\right) - \frac{\sqrt\tfrac{n}{2}}{2}</math>

Z tego, że dla <math>x > 1</math> zachodzi <math>\ln(x) < x-1,</math> otrzymujemy dla <math>n > 32,</math> że:
: <math>\ln(n) = \ln(32) + 2\ln\left(\sqrt\tfrac{n}{32}\right) < \ln(32)+2\left(\sqrt\tfrac{n}{32}-1\right) < 2+\sqrt\tfrac{n}{8}</math>

Wystarczy zatem dowieść
: <math>\left(1+\sqrt\tfrac{n}{2}\right)\left(2+\sqrt\tfrac{n}{8}\right) < \left(\tfrac{n}{3} + 1 - \sqrt\tfrac{n}{8}\right) \ln(4),</math>

czyli
: <math>\sqrt{2n} + \left(1+\ln(4)\right) \sqrt\tfrac{n}{8} < \left(\tfrac{\ln(4)}{3}-\tfrac{1}{4}\right) n - 2 + \ln(4).</math>

Ponieważ <math>\tfrac{138}{100} < \ln(4) < \tfrac{7}{5},</math> to wystarczy dowieść, że:
: <math>8\sqrt{2n} < n-4,</math>

co dla <math>n\geqslant 4</math> jest równoważne z:
: <math>n^2 - 136n + 16 > 0.</math>

Nierówność ta zachodzi dla każdego <math>n \geqslant 136.</math> Więc twierdzenie zachodzi dla każdego <math>n \geqslant 136.</math> Dla <math>n \leqslant 135</math> twierdzenie zachodzi, gdyż kolejne liczby pierwsze w następującym ciągu są mniejsze od podwojonego poprzednika:
: <math>2,\ 3,\ 5,\ 7,\ 13,\ 23,\ 43,\ 83,\ 163.</math>

'''Koniec dowodu.'''

Dla dowolnej, nieujemnej liczby całkowitej <math>k</math> bez większego trudu można by dowieść nierówności:
: <math>(2n)^k L(n) < \binom{2n}{n}</math>

lub słabszej
: <math>\left(\prod_{s=1}^k (2n - 2s + 1)\right) L(n) < \binom{2n}{n}</math>

dla wszystkich <math>n \geqslant C,</math> gdzie stała C zależałaby od <math>k.</math> Nierówność ta zapewniłaby <math>k+1</math> liczb pierwszych pomiędzy <math>n</math> i <math>2n,</math> dla wszystkich, dostatecznie dużych <math>n</math> (dla <math>n \geqslant C</math>).

=== 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]]<ref name="SzLP" />), który skupił się na środkowym współczynniku dwumianowym, czyli na <math>(2n)!,</math> podzielonym dwukrotnie przez <math>n!.</math> 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<ref name="LV_Fnd" />). 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 <math>n > 6,</math> między liczbami <math>n,</math> a <math>2n,</math> znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci <math>4k + 1,</math> oraz co najmniej jedna postaci <math>4m + 3.</math>

=== Twierdzenie Dirichleta ===
Poniższe twierdzenie zostało udowodnione przez [[Peter Gustav Lejeune Dirichlet|Dirichleta]]
; Twierdzenie
W dowolnym [[ciąg arytmetyczny|ciągu arytmetycznym]] liczb naturalnych: <math>a,</math> <math>a + q,</math> <math>a + 2q,</math> <math>a + 3q,\dots</math> takim, że <math>a</math> i <math>q</math> są [[liczby względnie pierwsze|względnie pierwsze]], występuje nieskończenie wiele liczb pierwszych. (Przy ustalonym <math>q,</math> ilość liczb pierwszych dla różnych a, względnie pierwszych z liczbą <math>q,</math> jest w pewnym asymptotycznym sensie taka sama).

==== Przypadki szczególne ====
* Ciąg arytmetyczny <math>5, 11, 17, \dots</math> liczb naturalnych <math>n\equiv -1\mod 6{:}</math>
*: Niech <math>A</math> będzie niepustym [[Zbiór skończony|zbiorem skończonym]] liczb naszego ciągu. Niech <math>X</math> będzie ich iloczynem. Wtedy <math>6X-1</math> nie może mieć wyłącznie dzielników pierwszych dających resztę <math>1</math> z dzielenia przez <math>6</math> (ich iloczyn dałby resztę <math>1</math>). Zatem istnieje taki dzielnik pierwszy <math>p | 6X-1,</math> że <math>p\equiv -1\mod 6.</math> Dzielnik ten nie należy do <math>A,</math> 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 <math>2, 5, 8, \dots</math> liczb naturalnych <math>n\equiv -1\mod 3</math> zawiera powyższy, ale ma tylko jedną więcej liczbę pierwszą, mianowicie <math>2.</math>

* Ciąg arytmetyczny <math>3, 7, 11, \dots</math> liczb naturalnych <math>n\equiv -1\mod 4{:}</math>
*: 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 <math>1, 5, 9, \dots</math> liczb naturalnych <math>n\equiv 1\mod 4{:}</math>
*: Euler pokazał, że nieparzysty dzielnik pierwszy liczby naturalnej postaci <math>a^2+1</math> musi dać resztę 1 z dzielenia przez 4. Niech więc <math>A</math> będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech <math>X</math> będzie ich iloczynem. Wtedy <math>(2X)^2+1</math> musi mieć dzielnik pierwszy z naszego ciągu. Ale dzielnik taki nie może należeć do <math>A,</math> co oznacza, że zbiór wszystkich liczb pierwszych w naszym ciągu jest nieskończony.

=== Twierdzenie o liczbach pierwszych ===
{{główny artykuł|Twierdzenie o liczbach pierwszych}}

Podstawowe twierdzenie o rozmieszczeniu liczb pierwszych wśród liczb naturalnych sformułował [[Carl Friedrich Gauss|Gauss]], który na podstawie badań empirycznych zasugerował, że liczba π(n) liczb pierwszych w [[Przedział (matematyka)|przedziale]] <math>[1, n]</math> opisana jest zależnością:
: <math>\pi(n)\sim\mathrm{Li}(n),</math>

gdzie symbol <math>\mathrm{Li}(n)</math> oznacza [[logarytm całkowy|resztę logarytmu całkowego]], a „~” oznacza '''równość asymptotyczną''' rozumianą jako
: <math>\lim_{n\to\infty}\frac{\pi(n)}{\mathrm{Li}(n)}=1.</math>

Rozwinięcie logarytmu całkowego w szereg daje oszacowanie:
: <math>\pi(n)\approx\frac{n}{\ln n}+\frac{n}{\ln^2 n}+\frac{2n}{\ln^3 n}+\ldots=\sum_{i=1}^\infty\frac{(i-1)!n}{\ln^i n}.</math>

Gauss nie udowodnił tego twierdzenia – dopiero pod koniec XIX wieku zostało ono udowodnione przez [[Jacques Salomon Hadamard|Hadamarda]] i [[Nicolas de la Vallee Poussin|de la Vallee Poussina]].

Najprostszą postacią przybliżenia funkcji π jest pierwszy element tego szeregu:
: <math>\pi (n)\approx \frac{n}{\ln n}.</math>

W tym wypadku także zachodzi asymptotyczna równość:
: <math>\lim_{n\to\infty}\frac{\pi(n)}{\frac{n}{\ln n}}=1.</math>

=== Hipoteza Riemanna ===
{{Osobny artykuł|hipoteza Riemanna}}
Rozmieszczenie liczb pierwszych na osi jest też związane bezpośrednio z hipotezą Riemanna. Mianowicie, jest ona równoważna stwierdzeniu, że [[Funkcja licząca liczby pierwsze|liczba <code>π</code>(n)]] liczb pierwszych w przedziale <math>[1, n]</math> wyraża się wzorem:
: <math>\pi(n) = \mathrm{Li}(n) + O\left(\sqrt{n} \ln n\right),</math>

gdzie użyto [[Asymptotyczne tempo wzrostu|notacji dużego O]].

=== Hipoteza liczb pierwszych bliźniaczych ===
{{Osobny artykuł|hipoteza liczb pierwszych bliźniaczych}}
Według tej teorii [[liczby bliźniacze|liczb pierwszych bliźniaczych]] jest nieskończenie wiele.

=== Różnice między kolejnymi liczbami pierwszymi ===
Dla każdej liczby naturalnej <math>n</math> istnieją takie dwie kolejne liczby pierwsze, że ich różnica wynosi nie mniej niż <math>n.</math> Można to udowodnić poprzez wykazanie, że istnieje ciąg kolejnych <math>n</math> liczb naturalnych, z których żadna nie jest pierwsza (tj. każda jest złożona)<ref>{{Cytuj |tytuł = mathschallenge.net |data dostępu = 2024-09-25 |opublikowany = mathschallenge.net |url = https://mathschallenge.net/full/consecutive_composites}}</ref>.

'''Dowód'''

Dla każdej liczby naturalnej <math>n</math> istnieją niezerowe liczby podzielne przez wszystkie liczby naturalne od <math>2</math> do <math>n + 1,</math> przykładowo <math>(n + 1)!.</math> Możemy utworzyć ciąg kolejnych liczb: <math>(n + 1)! + 2,\ (n + 1)! + 3,\ (n + 1)! + 4,\dots,\ (n + 1)! + n + 1.</math> Każda z nich jest podzielna odpowiednio przez <math>2, 3, 4, \dots, (n + 1).</math> Oznacza to, że istnieje ciąg <math>n</math> kolejnych liczb naturalnych, z których żadna nie jest pierwsza.

'''Koniec dowodu'''

== Szczególne rodzaje liczb pierwszych ==
=== Liczby pierwsze bliźniacze ===
Dwie liczby pierwsze są [[Liczby bliźniacze|bliźniacze]], jeśli ich różnica jest równa <math>2.</math> 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 <math>2996863034895\cdot 2^{1290000}\pm 1.</math> Liczby te, znalezione we wrześniu 2016, mają 388342 cyfry w zapisie dziesiętnym<ref name="LKTP">{{Cytuj |tytuł = Twin Primes |data dostępu = 2024-11-06 |opublikowany = t5k.org |url = https://t5k.org/top20/page.php?id=1 |język = en}}</ref>.

=== Liczby pierwsze czworacze ===
Cztery liczby pierwsze są [[Liczby czworacze|czworacze]], jeśli są postaci <math>p,p+2,p+6,p+8</math> 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:
: <math>667674063382677 \cdot 2^{33608}-1,</math> <math>667674063382677 \cdot 2^{33608}+1,</math> <math>667674063382677 \cdot 2^{33608}+5,</math> oraz <math>667674063382677 \cdot 2^{33608}+7</math>
Liczby te, znalezione w lutym 2019, mają po 10132 cyfry w zapisie dziesiętnym<ref name="LKQP">{{Cytuj |tytuł = Quadruplet |data dostępu = 2024-11-06 |opublikowany = t5k.org |url = https://t5k.org/top20/page.php?id=55 |język = en}}</ref>.

=== Liczby pierwsze izolowane ===
Liczba pierwsza <math>p</math> jest izolowana, jeśli najbliższa jej liczba pierwsza różni się od <math>p</math> co najmniej o 4. Przykłady: 23, 89, 157, 173.

=== Liczby pierwsze Mersenne’a ===
Liczbę
: <math>M(n) := 2^n - 1</math>

nazywamy <math>n</math>-tą [[Liczby Mersenne’a|liczbą Mersenne’a]] (dla <math>n = 0, 1, \dots</math>). Tak otrzymana funkcja <math>M</math> jest homomorfizmem ze względu na [[największy wspólny dzielnik]] NWD:
: <math>M(NWD(k, n)) = NWD(M(k), M(n)).</math>

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 <math>M(n)</math> była pierwsza jest pierwszość liczby <math>n.</math> Jednak nie dla każdej liczby pierwszej <math>p,</math> liczba <math>M(p)</math> jest pierwsza; na przykład:
: <math>2^{11} - 1 = 23\cdot 89.</math>

Dlatego bada się także [[dzielniki Mersenne’a]], a mianowicie dzielniki liczb Mersenne’a <math>M(p),</math> dla <math>p</math> pierwszego, zwłaszcza dzielniki pierwsze.

W sierpniu 2008 roku największą znaną liczbą pierwszą była liczba Mersenne’a <math>2^{43 112 609} - 1</math> – 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<ref name="largest">{{cytuj stronę |url = http://www.mersenne.org/primes/?press=M74207281 |tytuł = GIMPS Project Discovers Largest Known Prime Number, 2<sup>74,207,281</sup>-1 |opublikowany = mersenne.org |język = en |data dostępu = 2016-01-07}}</ref>. Obecnie największą znaną, 52. liczbą pierwszą Mersenne’a jest <math>2^{136279841} - 1,</math> która w zapisie dziesiętnym ma {{nowrap|41 024 320}} cyfr. Odkrył ją 12 października 2024 roku Luke Durant w ramach projektu [[Great Internet Mersenne Prime Search|GIMPS]]<ref name="MP52">{{Cytuj stronę |url = https://www.mersenne.org/primes/?press=M136279841 |tytuł = GIMPS Discovers Largest Known Prime Number: <math>2^{136279841}-1</math> |data = 2024-10-21 |opublikowany = mersenne.org |język = en |data dostępu = 2024-10-21}}</ref>.
[[Test Lucasa-Lehmera]] jest efektywną metodą sprawdzenia, czy liczba Mersenne’a jest liczbą pierwszą.

==== Liczby złożone Mersenne’a ====
Liczby złożone Mersenne’a <math>M(p),</math> mogą być liczbami złożonymi, gdy liczba <math>p</math> jest liczbą pierwszą lub gdy <math>n</math> jest liczbą złożoną, to <math>M(n)</math> jest także liczbą złożoną.

; Stwierdzenie
Niech <math>p</math> oraz <math>q := 2\cdot p + 1</math> będą liczbami pierwszymi, przy czym 2 jest resztą kwadratową <math>\mod q</math> (tzn. <math>x^2 \equiv 2 \mod q</math> dla pewnej liczby całkowitej <math>x</math>). Wtedy <math>q | M(p),</math> więc liczba Mersenne’a <math>M(p)</math> jest wtedy złożona dla <math>p > 3.</math>
; Dowód
Przy założeniach twierdzenia, niech <math>x^2\equiv 2\mod q</math> dla pewnej liczby całkowitej <math>x.</math> Wtedy na mocy [[Małe twierdzenie Fermata|małego twierdzenia Fermata]]:
: <math>M(p) := 2^p - 1\equiv x^{q-1} - 1\equiv 0\mod q,</math>

czyli <math>q | M(p).</math> Ponieważ dla <math>p > 3</math> zachodzi <math>q := 2\cdot p + 1 < M(p),</math> to <math>q</math> jest dzielnikiem właściwym, więc <math>M(p)</math> jest złożone dla <math>p > 3</math> (przy pozostałych założeniach).
; Koniec dowodu.

Przykłady: 2 jest resztą kwadratową nieparzystej liczby pierwszej <math>q</math> wtedy i tylko wtedy, gdy <math>q^2</math> daje resztę -1 lub 1 z dzielenia przez 8. Ponadto chcemy, żeby <math>p := (q - 1)/2</math> było liczbą pierwszą. Zatem przykładów <math>q,</math> ilustrujących powyższe twierdzenie, należy szukać wyłącznie wśród <math>q</math> dających resztę -1 z dzielenia przez 8, czyli wśród liczb postaci: <math>q = 8\cdot n - 1.</math> Wtedy <math>p = 4\cdot n - 1.</math> Więc <math>n</math> nie powinno dawać reszty 1 z dzielenia przez 3, by uniknąć podzielności <math>3 | p,</math> oraz nie powinno dawać reszty -1, by uniknąć <math>3 | q.</math> Zatem należy ograniczyć się do <math>n</math> podzielnych przez 3, czyli do
: <math>(p, q) := (12\cdot k - 1, 24\cdot k - 1).</math>

Stąd najmniejszym przykładem, ilustrującym powyższe twierdzenie jest <math>(p, q) := (11, 23).</math> Otrzymujemy podzielność <math>23 | M(11).</math> Następnym jest <math>(p, q) := (23, 47),</math> czyli podzielność <math>47 | M(23).</math>

=== Liczby pierwsze Fermata ===
Są to liczby pierwsze postaci <math>2^{2^n}+1.</math> Jak dotąd znanych jest pięć [[liczby Fermata|liczb Fermata]], które są pierwsze: 3, 5, 17, 257 i 65537.

A oto przykładowe [[rozkład na czynniki|faktoryzacje]] liczb Fermata
: <math>F_5 = 641\cdot 6700417,</math>
: <math>F_6 = 274177 \cdot 67280421310721.</math>

Skoro liczby Fermata nie muszą być pierwsze, to bada się dzielniki Fermata, czyli dzielniki [[liczby Fermata|liczb Fermata]], zwłaszcza dzielniki pierwsze.

=== Liczby pierwsze Germain ===
{{Osobny artykuł|Liczby pierwsze Germain}}

Liczbę pierwszą <math>p</math> nazywamy '''liczbą pierwszą [[Sophie Germain]]''' jeżeli liczba <math>2p + 1</math> 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 [[wielkie twierdzenie Fermata|wielkiego twierdzenia Fermata]]. Liczby pierwsze Germain są związane z liczbami złożonymi Mersenne’a.

=== Liczby pomiędzy pierwsze ===
Liczby będące [[średnia arytmetyczna|średnią]] kolejnych dwóch liczb pierwszych większych od 2 ([[język angielski|ang.]] ''interprime numbers''). Początkowe liczby pomiędzy pierwsze to: '''4, 6, 9, 12, 15, 18, 21, 26, 30, 34,…'''

Liczby te są [[Liczby złożone|liczbami złożonymi]], ponieważ analizie poddajemy '''kolejne''' liczby pierwsze.

=== Liczby pseudopierwsze ===
Liczby złożone <math>n,</math> które spełniają warunek:
: <math>n|2^n -2.</math>

Istnieje nieskończenie wiele [[Liczby pseudopierwsze|liczb pseudopierwszych]] parzystych, jak i nieparzystych. Co więcej, dla każdej liczby pierwszej <math>p</math> istnieje nieskończenie wiele liczb pseudopierwszych podzielnych przez <math>p.</math> Liczbami pseudopierwszymi dla danego [[test pierwszości|testu pierwszości]] nazywamy liczby złożone, których ten test nie rozpoznaje (powyższy przykład to liczby pseudopierwsze dla [[Małe twierdzenie Fermata|testu Fermata]] przy <math>a</math> równym 2).

=== Liczby lustrzane pierwsze ===
To pary liczb pierwszych, z których jedna powstaje przez zapisanie cyfr dziesiętnych drugiej w odwrotnej kolejności.<br>
Przykłady: 13 i 31, 17 i 71, 37 i 73, 79 i 97, 107 i 701,...

=== Liczby palindromiczne pierwsze ===
To liczby pierwsze, które nie zmieniają się, gdy ich cyfry dziesiętne zapiszemy w odwrotnej kolejności.<br>
Przykłady: 11, 101, 131, 151, 181, 191, 929.

== Problemy ==
Zagadnienia dotyczące liczb pierwszych należą do [[teoria liczb|teorii liczb]]. Istnieją w niej dotąd nierozstrzygnięte problemy:
* [[hipoteza Goldbacha]]: czy każda liczba parzysta większa od 2 może być przedstawiona w postaci sumy dwóch liczb pierwszych?
* czy [[ciąg Fibonacciego]] zawiera nieskończenie wiele liczb pierwszych?
* czy [[Liczby Fermata|liczb pierwszych Fermata]] jest nieskończenie wiele?
* czy [[Liczby bliźniacze|liczb pierwszych bliźniaczych]] jest nieskończenie wiele?
* czy liczb [[liczby Mersenne’a|pierwszych Mersenne’a]] jest nieskończenie wiele?
* czy [[Liczby pierwsze Germain|liczb pierwszych Germain]] jest nieskończenie wiele?
* czy istnieje nieskończenie wiele liczb pierwszych postaci <math>n^2 + 1</math>?
* czy dla dowolnego <math>n</math> pomiędzy liczbami <math>n^2</math> i <math>(n + 1)^2</math> istnieje liczba pierwsza?

== Największe znane liczby pierwsze ==
Największa znana dotąd liczba pierwsza to 52. [[liczby Mersenne’a|liczba pierwsza Mersenne’a]]: <math>2^{136279841} - 1</math>, która ma 41 024 320 cyfr w zapisie dziesiętnym<ref name="LKP" />. Odkrył ją Luke Durant 12 października 2024 w ramach projektu [[Great Internet Mersenne Prime Search|GIMPS]]<ref name="MP52" />.

W listopadzie 2024 siedem największych znanych liczb pierwszych to liczby pierwsze Mersenne’a<ref name="LKP">{{Cytuj |tytuł = Largest Known Primes |data dostępu = 2024-11-06 |opublikowany = t5k.org |url = https://t5k.org/top20/page.php?id=3 |język = en}}</ref>. Największą znaną liczbą pierwszą, która nie jest liczbą Mersenne’a, jest:
: <math>516693^{2097152} - 516693^{1048576} + 1,</math>

która w zapisie dziesiętnym ma 11 981 518 cyfr i została odkryta w październiku 2023<ref name="LKP" />.

Największą liczbą pierwszą poznaną przed erą elektroniki jest 44-cyfrowa tzw. [[liczba Ferriera]]:
: <math>\frac{2^{148} + 1}{17} = 20\,988\,936\,657\,440\,586\,486\,151\,264\,256\,610\,222\,593\,863\,921</math>

znaleziona za pomocą mechanicznego kalkulatora.

== Odpowiedniki w innych strukturach algebraicznych ==
Najbliższym odpowiednikiem liczb pierwszych w [[pierścień (matematyka)|pierścieniach]] są [[element pierwszy|elementy pierwsze]]. Liczby pierwsze nie są jednak tym samym, co elementy pierwsze pierścienia liczb całkowitych – elementami pierwszymi są także liczby ujemne <math>(-2, -3, -5, \dots),</math> a według niektórych źródeł także zero<ref>Na podstawie definicji w {{cytuj książkę |nazwisko = Reinhardt |imię = Fritz |nazwisko2 = Soeder |imię2 = Heinrich |tytuł = Atlas matematyki |strony = 121 |wydawca = Prószyński i S-ka |isbn = 9788374691895}} W podręczniku Algebry Białynickiego-Biruli zero jest jednak z definicji elementu pierwszego wykluczone.</ref>, które zostały z definicji wykluczone ze zbioru liczb pierwszych.

W pierścieniach bez jednoznaczności rozkładu pierwszość elementu nie jest równoważna jego nierozkładalności na czynniki (istnieją elementy nierozkładalne, które nie są pierwsze). Również pojęcie [[ideał pierwszy|ideału pierwszego]] nawiązuje do tych intuicji.

== Zastosowanie ==
Liczby pierwsze są stosowane w niektórych znanych [[algorytm]]ach [[kryptologia|kryptograficznych]]; jednym z nich jest [[RSA (kryptografia)|RSA]]. Rozwój tych algorytmów zapewnia ewolucję projektów wyszukiwania ogromnych liczb pierwszych, takich jak [[Great Internet Mersenne Prime Search|GIMPS]].

== Uwagi ==
{{Wikiźródła|Liczby pierwsze|Liczby pierwsze}}
{{Wikiźródła|Tablica liczb pierwszych i rozkładów na czynniki pierwsze|Tablica liczb pierwszych i rozkładów na czynniki pierwsze}}
{{Wikiźródła|Tablica rozkładów na sumę dwóch liczb pierwszych|Tablica rozkładów na sumę dwóch liczb pierwszych}}
{{wikisłownik|liczba pierwsza}}
{{Uwagi}}

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
Istnieje bardzo wiele książek o teorii liczb i liczbach pierwszych; między innymi:
* [[Lew Sznirelman|Lew G. Sznirelman]], ''Liczby pierwsze'', [[Wydawnictwo Naukowe PWN|Państwowe Wydawnictwo Naukowe]], Warszawa 1954.
* [[William LeVeque|William J. LeVeque]] © 1977, ''Fundamentals of Number Theory'', Dover Publications 1996, {{ISBN|0-486-68906-9}}.
* [[Jean-Pierre Serre]], ''A Course in Arithmetic'', Springer-Verlag © 1973, {{ISBN|0-387-90040-3}}, {{ISBN|3-540-90040-3}}.

== Linki zewnętrzne ==
; Polskojęzyczne
* [http://www.math.us.edu.pl/~pgladki/faq/node46.html Dlaczego 1 nie jest liczbą pierwszą w FAQ grupy pl.sci.matematyka]
* [https://obliczone.pl/kalkulatory/867-liczby-pierwsze Kalkulator liczb pierwszych]

; Anglojęzyczne
* {{MathWorld | adres = PrimeNumber | tytuł = Prime Number}} [dostęp 2024-05-12].
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/Prime_number Prime number]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-12].
* [http://www.had2know.com/academics/prime-composite.html Sprawdzanie czy dana liczba jest liczbą pierwszą]
* [http://www.mersenne.org/ Projekt GIMPS poszukiwania największych liczb pierwszych]
* [https://archive.is/20070626173551/http://primes.utm.edu/largest.html Największe znane liczby pierwsze]
* [http://www.primegrid.com/ PrimeGrid – projekt tworzący publicznie dostępne listy liczb pierwszych] (bazuje na platformie [[Berkeley Open Infrastructure for Network Computing|BOINC]])
* [https://numberworld.info/primeCheck Kalkulator sprawdzający czy dana liczba jest pierwsza]

{{Typy liczb naturalnych}}
{{Ciągi liczbowe}}
{{Teoria liczb}}

{{Kontrola autorytatywna}}

[[Kategoria:Liczby pierwsze| ]]