Liczby pierwsze

Z Wikipedii

Liczba pierwsza to liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i samą siebie. Zbiór wszystkich liczb pierwszych oznacza się symbolem $\mathbb{P}$ . Jeśli liczba naturalna jest większa od 1 i nie jest pierwsza, to nazywamy ją liczbą złożoną.

Oto dziesięć pierwszych w kolejności liczb pierwszych: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Więcej liczb pierwszych można znaleźć w tej tablicy.

Uwaga: Liczba 1 nie jest ani pierwsza ani złożona. Podobnie ma się rzecz z liczbą 0 (gdy jest traktowana jako liczba naturalna).

Spis treści

1 Podstawowe własności
2 Wyznaczanie liczb pierwszych
3 Rozkład n! na czynniki pierwsze
4 O rozkładzie środkowego współczynnika dwumianowego
5 Rozmieszczenie liczb pierwszych
6 Specjalne rodzaje i uogólnienia liczb pierwszych
7 Problemy
8 Największe znane liczby pierwsze
9 Przypisy
10 Bibliografia
11 Zobacz też
12 Linki zewnętrzne

[edytuj] Podstawowe własności

Najmniejszy dzielnik $d > 1$ liczby naturalnej $n > 1$ jest liczbą pierwszą.
Euklides pokazał, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych. Oto dowód Euklidesa (choć nie dosłownie): Niech X będzie skończonym zbiorem liczb pierwszych. Niech x będzie iloczynem wszystkich liczb występujących w X (gdy X jest puste, to x=1). Jedynym wspólnym dzielnikiem liczb x oraz x+1 jest 1. Zatem żadna liczba pierwsza, występująca w X, nie jest dzielnikiem liczby x+1. Ale x+1 > 1. Więc x+1 ma dzielnik p, który jest liczbą pierwszą. Liczba pierwsza p nie należy do X (bo jest dzielnikiem liczby x+1).
Każda liczba naturalna (ale nie zero!) daje się jednoznacznie zapisać w postaci iloczynu niemalejącego ciągu skończonego pewnych liczb pierwszych (w przypadku 1, ciąg jest pusty, ma zero wyrazów). Twierdzenie to mógł udowodnić Euklides (stworzył niezbędne narzędzia, lecz nie postawił kropki nad i), ale uczynił to Gauss. Twierdzenie Gaussa mówi, że liczby pierwsze są jakby multyplikatywnymi atomami, z których przy pomocy mnożenia zbudowane są pozostałe liczby.

[edytuj] Wyznaczanie liczb pierwszych

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

Natomiast metoda, która daje odpowiedź na pytanie czy dana liczba naturalna jest pierwsza, czy nie - nosi nazwę testu pierwszości. Wsró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 Solovay-Strassena.

[edytuj] Rozkład n! na czynniki pierwsze

Niech $\operatorname{ord}_p(n)\,$ oznacza wykładnik, z którym liczba pierwsza p występuje w rozkladzie liczby naturalnej n. Wtedy:

$\operatorname{ord}_p(n!) = \sum_{k=1}^{\infty}\,\left\lfloor \tfrac{n}{p^k}\right\rfloor$

gdzie $\lfloor x \rfloor$ jest jedyną liczbą całkowitą, spełniającą nierówność:

$x-1 < \lfloor x \rfloor \le x$

dla dowolnego rzeczywistego x. Liczbę $\lfloor x \rfloor$ nazywamy częścią calkowitą liczby rzeczywistej x. Powyższa suma jest skończona, gdyż tylko skończona liczba jej składników jest różna od 0 – mianowicie pierwsze $\left\lfloor \tfrac{\ln n}{\ln p}\right\rfloor$ wyrazów.

Literatura: na przykład ^[1] – rozdział 7.0; ^[2] – rozdział 6.3, Twierdzenie 6.9.

[edytuj] O rozkładzie środkowego współczynnika dwumianowego

Zbadajmy $o_p(n) := \operatorname{ord}_p \binom{2\cdot n}{n}$ . Oczywiście $\,o_p(n) = 1$ , gdy liczba pierwsza $p\,$ należy do przedziału $n < p \le 2\cdot n$ . Ogólnie:

$o_p(n) = \operatorname{ord}_p((2\cdot n)!) - 2\cdot \operatorname{ord}_p(n!)$

Ponieważ

$0 \le \lfloor 2\cdot x \rfloor - 2\cdot \lfloor x \rfloor \le 1$

dla dowolnej liczby rzeczywistej $\,x$ , to ze wzoru na $\operatorname{ord}_p(n!)$ , z poprzedniego fragmentu, wynika, że

$o_p(n) \le \left\lfloor \tfrac{\ln (2\cdot n)}{\ln p}\right\rfloor$

Równość $p ^{(\ln x)/(\ln p)} = x\,$ pozwala nam powyższą nierówność wyrazić równoważnie jako:

$p^{o_p(n)} \le 2\cdot n$

czyli

Twierdzenie Jeżeli $p^k\, | \binom{2\cdot n}{n}$ , to $p^k \le 2\cdot n$ .

Zachodzi także następujące, łatwe

Twierdzenie Jeżeli $n > 2\,$ jest liczbą naturalną, oraz $p\,$ – liczbą pierwszą z przedziału $\frac{2}{3}\cdot n < p \le n$ , to $p\,$ nie jest dzielnikiem wspólczynnika $\binom{2\cdot n}{n}$ .

[edytuj] Rozmieszczenie 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.

[edytuj] Szereg odwrotności wszystkich liczb pierwszych

Niech $\mathbb{P}$ oznacza zbiór liczb pierwszych. Leonhard Euler udowodnił, że szereg liczbowy $\sum_{p \in \mathbb{P}} \frac{1}{p}$ 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 $\sum_{p \in \mathbb{P}}\frac{1}{p}=\infty$

Niech

$P(x) := \sum_{p \in \mathbb{P}, p \le x}\, \frac{1}{p}$

$Q(x) := \sum_{p \in \mathbb{P}, p \le x}\, \frac{1}{p-1}$

Ponieważ:

$1 = \left(\frac{1}{1} - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \dots$

$P(x) > Q(x) - 1\,$

dla dowolnego naturalnego $x\,$ . Wystarczy zatem dowieść, że $Q(x)\,$ może być dowolnie wielkie.

Szereg geometryczny:

$1 + \frac{1}{p-1} = \frac{1}{1-\frac{1}{p}} = 1 + \frac{1}{p} + \frac{1}{p^2} + \dots$

oraz rozkładalność liczb naturalnych na iloczyny liczb pierwszych, daje nierówność:

$\prod_{p \in \mathbb{P}, p \le x}\, \left(1+\frac{1}{p-1}\right)\ =\ \prod_{p \in \mathbb{P}, p \le x}\, \left(1 + \frac{1}{p} + \frac{1}{p^2} + \dots\right) \ \geq\ \sum_{n=1}^{x}\, \frac{1}{n}$

Ale $\frac{1}{p-1} > \ln\left(1 + \frac{1}{p-1}\right)$ Więc:

$Q(x)\ >\ \ln\left(\prod_{p \in \mathbb{P}, p \le x}\, \left(1+\frac{1}{p-1}\right)\right) \ \geq\ \ln\left(\sum_{n=1}^{x}\, \frac{1}{n}\right) \ >\ \ln(\ln(x+1))\ \rightarrow \infty,$

zatem

$P(x)\ >\ \ln(\ln(x+1)) - 1\ \rightarrow \infty,$

gdy x dąży do nieskończoności. Koniec dowodu.

Franz Mertens uzyskał podobne oszacowanie $P(x)\,$ także od góry.

[edytuj] Oszacowania iloczynu odcinka liczb pierwszych

Jasnym jest, że zachodzi podzielność:

$\prod_{p\in\mathbb{P},\ n < p \le 2\cdot n}p\ |\ \binom{2\cdot n}{n}\ =\ 2\cdot\binom{2\cdot n - 1}{n-1}$

Więc dla n > 2 otrzymujemy:

$\prod_{p\in\mathbb{P},\ n < p \le 2\cdot n}p\ |\ \binom{2\cdot n - 1}{n-1}\ =\ \binom{2\cdot n - 1}{n}$

Powyższe wspólczynniki dwumianowe są składnikami sumy ze wzoru Newtona na $(1+1)^{2\cdot n -1}$ . Są więc one mniejsze od $2^{2\cdot n - 2} = 4^{n-1}$ (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:

$\prod_{p\in\mathbb{P},\ n < p \le 2\cdot n}p\ <\ 4^{n-1}$

dla $\,n > 2$ , a nawet dla każdego $\,n > 1$ . Atrakcyjnieszym byłoby oszacowanie iloczynu początkowego odcinka liczb pierwszych:

$\prod\! P(x)\ :=\ \prod\, \{p \in \mathbb{P} : p \le x\}$

Ale przynajmniej możemy powyższą nierówność przepisać w postaci:

$\frac{\prod\! P(2\cdot n)}{\prod\! P(n)}\ <\ 4^{n-1}$

dla każdego $\,n > 1$ . Oczywiście:

$\prod\! P(2\cdot n -1)\ =\ \prod\! P(2\cdot n)$

dla każdego naturalnego $\,n > 1$ .

Twierdzenie

$\prod\! P(x)\ \le\ \frac{1}{2}\cdot 4^{x-1}$

dla każdej liczby całkowitej $\,x > 1$ .

Dowód Twierdzenie zachodzi dla $\,x=2,3$ . Rozpatrzmy parzyste $\,x > 3$ . Wtedy $\,1 < x/2 <x$ . Możemy więc indukcyjnie założyć, że twierdzenie zachodzi dla $\,x/2$ . Zatem, korzystając ze wcześniejszego oszacowania iloczynu odcinka (niepoczątkowego), które zachodziło dla każdego $x := 2\cdot n > 2$ , otrzymujemy:

$\prod\! P(x)\ <\ \prod\! P(\frac{x}{2}) \cdot 4^{\frac{x}{2}-1}\ \le\ \frac{1}{2}\cdot 4^{\frac{x}{2}-1} \cdot 4^{\frac{x}{2}-1}\ =\ \frac{1}{2}\cdot 4^{x-2}$

Więc indukcja zachodzi dla parzystego przypadku. Dla nieparzystego $\,x > 3$ mamy $1 < \frac{x+1}{2} < x$ , co pozwala nam stosować założenie indukcyjne dla $\frac{x+1}{2}$ (oraz znowu wcześniejsze oszacowanie):

$\prod\! P(x)\ <\ \prod\! P(\frac{x+1}{2}) \cdot 4^{\frac{x-1}{2}}\ \le\ \frac{1}{2}\cdot 4^{\frac{x-1}{2}} \cdot 4^{\frac{x-1}{2}}\ =\ \frac{1}{2}\cdot 4^{x-1}$

Koniec dowodu

Uwaga Twierdzenie zachodzi dla każdej liczby rzeczywistej $\,x \geq 2$ , a nie tylko dla całkowitych.

[edytuj] Postulat Bertranda – Twierdzenie Czebyszewa

Zobacz więcej w osobnym artykule: Postulat Bertranda.

Czebyszew udowodnił następujące twierdzenie (patrz ^[1] – rozdział 9, ^[2] – rozdział 6.9):

Dla dowolnej liczby naturalnej n większej od 1, między liczbami $n\,$ a $2\cdot n\,$ istnieje co najmniej jedna liczba pierwsza.

Dowód Wyżej zdefiniowaliśmy $o_p(n)\,$ i odnotowaliśmy następujące 3 twierdzenia:

Jeżeli $p^k\, | \binom{2\cdot n}{n}$ , to $p^k \le 2\cdot n$ ; albo krótko: $p^{o_p(n)} \le 2\cdot n$ .

Jeżeli $n > 2\,$ jest liczbą naturalną, oraz $p\,$ – liczbą pierwszą z przedziału $\frac{2}{3}\cdot n < p \le n$ , to $p\,$ nie jest dzielnikiem wspólczynnika $\binom{2\cdot n}{n}$ .

$\prod\! P(x)\ \le\ \frac{1}{2}\cdot 4^{x-1}$ dla każdego rzeczywistego $\,x > 1$ .

Zdefiniujmy: $L(n) := \prod_{p\in\mathbb{P}, p \le n} p^{o_p(n)}$ . Twierdzenie dokażemy, pokazując, że $L(n) < \binom{2\cdot n}{n}$ :

otóż $\,L(n) = M(n)\cdot N(n)$ , gdzie:

$M(n) := \prod\{p^{o_p(n)} : p \le \sqrt{2\cdot n},\ p\in \mathbb{P}\}$

$N(n) := \prod\{p\in \mathbb{P} : \sqrt{2\cdot n} < p \le \frac{2}{3}\cdot n\}$

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

$M(n) \le (2\cdot n)^{\sqrt{\frac{n}{2}}}$

oraz:

$N(n) \le \prod\{p\in \mathbb{P} : p \le \frac{2}{3}\cdot n\} \le \frac{1}{2}\cdot 4^{\frac{2}{3}\cdot n - 1}$

Z drugiej strony $\binom{2\cdot n}{n}$ jest największym z $2\cdot n + 1$ składników sumy Newtona przedstawiającej $(1+1)^{2\cdot n} = 4^n$ , przy czym dwa składniki równe są 1. Więc:

$\binom{2\cdot n}{n} \geq \frac{4^n - 2}{2\cdot n - 1} \geq \frac{4^n}{2\cdot n}$

Przy tym nierówność jest ostra dla $\,n > 1$ , a co dopiero dla $\,n > 32$ . Dla takich $\,n$ , nierówność $M(n)\cdot N(n) < \binom{2\cdot n}{n}$ , po obustronnym pomnożeniu przez $2\cdot n$ , wyniknie z

$n\ \cdot\ (2\cdot n)^{\sqrt{\frac{n}{2}}}\ \cdot\ 4^{\frac{2}{3}\cdot n - 1}\ <\ 4^n$

czyli

$n\ \cdot\ (2\cdot n)^{\sqrt{\frac{n}{2}}}\ <\ 4^{\frac{n}{3} + 1}$

czyli, po zlogarytmowaniu:

$(1+\sqrt{\frac{n}{2}})\cdot\frac{\ln(n)}{\ln(4)}\ <\ (\frac{n}{3} + 1) - \frac{\sqrt{\frac{n}{2}}}{2}$

Z tego, że dla $x > 1\,$ zachodzi $\,\ln(x) < x-1$ , otrzymujemy dla $\,n > 32$ , że:

$\ln(n) = \ln(32) + 2\cdot\ln(\sqrt{\frac{n}{32}}) < \ln(32)+2\cdot(\sqrt{\frac{n}{32}}-1) < 2+\sqrt{\frac{n}{8}}$

Wystarczy zatem dowieść:

$(1+\sqrt{\frac{n}{2}})\cdot (2+\sqrt{\frac{n}{8}})\ <\ (\frac{n}{3} + 1 - \sqrt{\frac{n}{8}})\cdot ln(4)$

czyli

$\sqrt{2\cdot n}\ +\ (1+\ln(4))\cdot \sqrt{\frac{n}{8}}\ \ <\ \ (\frac{\ln(4)}{3}-\frac{1}{4})\cdot n\ -\ 2\ +\ \ln(4)$

Ponieważ $\frac{138}{100} < \ln(4) < \frac{7}{5}$ , to wystarczy dowieść, że:

$8\cdot\sqrt{2\cdot n}\ <\ n-4$

co dla $\,n\geq 4$ jest równoważne z:

$n^2 - 136\cdot n + 16\ >\ 0$

Nierówność ta oczywiście zachodzi dla każdego $\,n \geq 136$ . Więc twierdzenie zachodzi dla każdego $\,n \geq 136$ . Dla $\,n \le 135$ twierdzenie zachodzi, gdyż kolejne liczby pierwsze w następującym ciągu są mniejsze od podwojonego poprzednika:

$2,\ 3,\ 5,\ 7,\ 13,\ 23,\ 43,\ 83,\ 163$

Koniec dowodu.

Uwaga W powyższym dowodzie, argument ogólny dał twierdzenie dla każdego $\,n \geq 136$ . Gdyby zadowolić się dowolną stałą zamiast 136, to druga część dowodu uprościłaby się. Co więcej, dla dowolnej, nieujemnej liczby całkowitej k bez większego trudu można by dowieść nierówności:

$(2\cdot n)^k \cdot L(n) < \binom{2\cdot n}{n}$

lub słabszej:

$(\prod_{s=1}^k (2\cdot n - 2\cdot s + 1)) \cdot L(n) < \binom{2\cdot n}{n}$

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

[edytuj] Metoda Czebyszewa

Jak w przedstawionym powyżej dowodzie, 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ł (patrz Sznirelmana ^[1]) Srinivasa Ramanujan, który skupił się na środkowym współczynniku dwumianowym, czyli na (2·n)!, podzielonym dwukrotnie przez n!. 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 ^[2]). Udowodnione po Czebyszewie twierdzenie o rozmieszczeniu liczb pierwszych natychmiast daje podobny wynik dla wszelkich proporcji ustalonych powyżej 1.

[edytuj] Wariacja Erdősa

Paul Erdős wzmocnił twierdzenie Czebyszewa dowodząc, że:

Dla dowolnej liczby naturalnej $\,n > 6$ , między liczbami $\,n$ , a $\,2\cdot n$ , znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci $\,4\cdot k + 1$ , oraz co najmniej jedna postaci $\,4\cdot m + 3$ .

[edytuj] Twierdzenie Dirichleta

Poniższe twierdzenie zostało udowodnione przez Dirichleta:

W dowolnym ciągu arytmetycznym liczb naturalnych: a, a + q, a + 2q, a + 3q, ... takim, że a i q są względnie pierwsze, występuje nieskończenie wiele liczb pierwszych. (Przy ustalonym q, ilość liczb pierwszych dla różnych a, względnie pierwszych z liczbą q, jest w pewnym asymptotycznym sensie taka sama.)

[edytuj] Przypadki szczególne

Ciąg arytmetyczny $5, 11, 17, \dots$ liczb naturalnych $n\equiv -1\mod 6$ :

Niech $A\,$ będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech $X\,$ będzie ich iloczynem. Wtedy $6 \cdot X-1\,$ nie może mieć dzielniki pierwsze wyłącznie dające resztę $1\,$ z dzielenia przez $\,6$ (ich iloczyn dałby resztę $\,1$ ). Zatem istnieje taki dzielnik pierwszy $p\, |\, 6 \cdot X-1\,$ , że $p\equiv -1\mod 6$ . Dzielnik ten nie należy do $A\,$ , 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 $2, 5, 8, \dots$ liczb naturalnych $n\equiv -1\mod 3$ zawiera powyższy, ale ma tylko jedną więcej liczbę pierwszą, mianowicie $\,2$ .

Ciąg arytmetyczny $3, 7, 11, \dots$ liczb naturalnych $n\equiv -1\mod 4$ :

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 $1, 5, 9, \dots$ liczb naturalnych $n\equiv 1\mod 4$ :

Euler pokazał, że nieparzysty dzielnik pierwszy liczby naturalnej postaci $a^2+1\,$ musi dać resztę 1 z dzielenia przez 4. Niech więc $A\,$ będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech $X\,$ będzie ich iloczynem. Wtedy $(2 \cdot X)^2+1$ musi mieć dzielnik pierwszy z naszego ciągu. Ale dzielnik taki nie może należeć do $A\,$ , co oznacza, że zbôr wszystkich liczb pierwszych w naszym ciągu jest nieskończony.

[edytuj] 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 [1, n] opisana jest zależnością:

$\pi(n)\sim\mathrm{Li}(n)$

gdzie symbol Li(n) oznacza resztę logarytmu całkowego, a "~" oznacza równość asymptotyczną rozumianą jako:

$\lim_{n\to\infty}\frac{\pi(n)}{\mathrm{Li}(n)}=1$

Rozwinięcie logarytmu całkowego w szereg daje oszacowanie:

$\pi(n)\approx\frac{n}{\ln n}+\frac{n}{\ln^2 n}+\frac{2n}{\ln^3 n}+\cdots=\sum_{i=1}^\infty\frac{(i-1)!n}{\ln^i n}$

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:

$\pi (n)\approx \frac{n}{\ln n}$

W tym wypadku także zachodzi asymptotyczna równość:

$\lim_{n\to\infty}\frac{\pi(n)}{\frac{n}{\ln n}}=1$

[edytuj] Hipoteza Riemanna

Zobacz więcej w osobnym artykule: hipoteza Riemanna.

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 [1, n] wyraża się wzorem:

$\pi(n) = \mathrm{Li}(n) + O\left(\sqrt{n} \ln n\right)$

gdzie użyto notacji dużego O.

[edytuj] Hipoteza liczb pierwszych bliźniaczych

Zobacz więcej w osobnym artykule: hipoteza liczb pierwszych bliźniaczych.

Ta hipoteza sugeruje, że liczb pierwszych bliźniaczych jest nieskończenie wiele.

[edytuj] Specjalne rodzaje i uogólnienia liczb pierwszych

[edytuj] Liczby pierwsze bliźniacze

Liczby pierwsze p i q nazywamy bliźniaczymi jeśli p = q + 2. 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... Zauważmy, że 5 jest bliźniacza zarówno z 3 jak i z 7.

Nie wiemy, czy istnieje nieskończenie wiele bliźniaczych liczb pierwszych.

Największa znana para liczb pierwszych bliźniaczych (stan na listopad 2007) to $2003663613\cdot 2^{195000}\pm 1.$ Liczby te, znalezione w 2007 roku, posiadają 58711 cyfr w zapisie dziesiętnym^[3].

[edytuj] Liczby pierwsze Mersenne'a

Liczbę:

M(n) := 2ⁿ - 1

nazywamy n-tą liczbą Mersenne'a (dla n=0, 1, ...). Tak otrzymana funkcja M jest homomorfizmem ze względu na największy wspólny dzielnik NWD:

M(NWD(k, n)) = NWD(M(k), M(n)).

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 M(n) była pierwsza jest pierwszość liczby n. Jednak nie dla każdej liczby pierwszej p, liczba M(p) jest pierwsza; na przykład

2¹¹ - 1 = 23·89

Dlatego ciekawe są także dzielniki Mersenne'a, a mianowicie dzielniki liczb Mersenne'a M(p), dla p pierwszego, zwłaszcza dzielniki pierwsze.

We wrześniu 2006 roku największą znaną liczbą pierwszą była liczba Mersenne'a 2^{32 582 657} - 1 – do jej zapisania w układzie dziesiętnym trzeba użyć 9 808 358 cyfr. Została ona znaleziona przez projekt GIMPS w wrześniu 2006 roku. Electronic Frontier Foundation ufundowało nagrodę w wysokości 100,000$ za znalezienie liczby pierwszej o co najmniej 10 milionach cyfr.

Największymi znanymi liczbami pierwszy mi były na ogół liczby Mersenne'a, gdyż istnieje dla nich efektywna metoda sprawdzenia, czy są pierwszymi, tak zwany test Lucasa-Lehmera.

[edytuj] Liczby złożone Mersenne'a

Chodzi o liczby Mersenne'a M(p), które są złożone, gdy liczba p jest pierwsza (gdy p jest złożone, to M(p) jest zawsze złożone).

Zachodzi proste twierdzenie, które rzuca światło na ten problem:

Niech p oraz q := 2·p+1 będą liczbami pierwszymi, przy czym 2 jest resztą kwadratową mod q (t.zn. $x^2 \equiv 2 \mod q\,$ dla pewnej liczby całkowitej $x\,$ ). Wtedy q | M(p), więc liczba Mersenne'a M(p) jest wtedy złożona dla p > 3.

Dowód Przy założeniach twierdzenia, niech $x^2 \equiv 2 \mod q\,$ dla pewnej liczby całkowitej $x\,$ . Wtedy na mocy Małego Twierdzenia Fermata:

$M(p) := 2^p - 1 \equiv x^{q-1} - 1\equiv 0 \mod q$

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

Koniec dowodu.

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

(p, q) := (12·k - 1, 24·k - 1)

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

[edytuj] Liczby pierwsze Fermata

Są to liczby pierwsze postaci $2^{2^n}+1$ . Jak dotąd znanych jest jedynie pięć liczb Fermata, które są pierwsze: 3, 5, 17, 257 i 65537

a oto przykładowe faktoryzacje liczb Fermata

F₅ = 641 × 6700417

F₆ = 274177 × 67280421310721

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

[edytuj] Liczby pierwsze Sophie Germain

Liczbę pierwszą p nazywamy liczbą pierwszą Sophie Germain jeżeli liczba 2p + 1 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.

Widzieliśmy też powyżej, że liczby pierwsze Germain występują w kontekście liczb złożonych Mersenne'a.

[edytuj] Liczby pomiędzy pierwsze

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ą oczywiście liczbami złożonymi, ponieważ analizie poddajemy kolejne liczby pierwsze.

[edytuj] Liczby pseudopierwsze

Liczby złożone n, które spełniają warunek: $n | 2 n - 2$ . Istnieje nieskończenie wiele liczb pseudopierwszych parzystych, jak i nieparzystych. Co więcej, dla każdej liczby pierwszej p istnieje nieskończenie wiele liczb pseudopierwszych podzielnych przez p. 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 a równym 2.

[edytuj] Liczby lustrzane

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,...

[edytuj] Liczby palindromiczne pierwsze

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

[edytuj] Problemy

Zagadnienia dotyczące liczb pierwszych należą do teorii liczb. W tej dyscyplinie ciekawe problemy formułuje się w sposób zrozumiały nawet dla laika, a na ich rozwiązanie trzeba czekać niekiedy wiele lat – przykładem jest tu wielkie twierdzenie Fermata. Oto kilka podobnych i jak dotąd nie rozwiązanych problemów:

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 liczb pierwszych Fermata jest nieskończenie wiele?
czy liczb pierwszych bliźniaczych jest nieskończenie wiele?
czy liczb pierwszych Mersenne'a jest nieskończenie wiele?
czy liczb pierwszych Germain jest nieskończenie wiele?
czy istnieje nieskończenie wiele liczb pierwszych postaci n² + 1?
czy dla dowolnego n pomiędzy liczbami n² i (n + 1)² istnieje liczba pierwsza?

[edytuj] Największe znane liczby pierwsze

Największa odkryta dotąd liczba pierwsza to 44 liczba Mersenne'a: 2^32582657−1 i liczy sobie 9808358 cyfr w zapisie dziesiętnym. Została ona odkryta 4 września 2006 roku przez Curtisa Coopera i Stevena Boone'a - uczestników projektu GIMPS. Poprzednia największa liczba pierwsza, 43 liczba Mersenne'a, została odkryta w grudniu 2005. Electronic Frontier Foundation ustanowiła nagrodę 100 tysięcy dolarów dla odkrywcy liczby pierwszej o więcej niż 10 milionach cyfr.[1]

Największa znana liczba pierwsza (3 918 990 cyfr), która nie jest liczbą Mersenne'a to:

$19249\cdot 2^{13018586} + 1$

Liczba ta jest jednocześnie siódmą największą znaną liczbą pierwszą. Została odkryta 26 marca 2007 roku w ramach projektu Seventeen or Bust.

Największą liczbą pierwszą poznaną przed erą elektroniki jest 44-cyfrowa tzw. liczba Ferriera:

$\frac{2^{148} + 1}{17} = 20 988 936 657 440 586 486 151 264 256 610 222 593 863 921$

znaleziona za pomocą mechanicznego kalkulatora.

Przypisy

↑ ^1,0 ^1,1 ^1,2 Lew G. Sznirelman,Liczby Pierwsze,PWN, Warszawa 1954
↑ http://primes.utm.edu/largest.html#biggest

[edytuj] Bibliografia

Istnieje bardzo wiele książek o teorii liczb i liczbach pierwszych; między innymi:

Lew G. Sznirelman, Liczby pierwsze, PWN, Warszawa 1954;

[edytuj] Zobacz też

Zobacz w Wikiźródłach tekst
Liczby pierwsze

Zobacz w Wikiźródłach tekst
Tablica liczb pierwszych i rozkładów na czynniki pierwsze

Zobacz w Wikiźródłach tekst
Tablica rozkładów na sumę dwóch liczb pierwszych

[edytuj] Linki zewnętrzne

Kategorie: Teoria liczb • Liczby pierwsze

We provide Linux to the World

Liczby pierwsze

Z Wikipedii

Spis treści

[edytuj] Podstawowe własności

[edytuj] Wyznaczanie liczb pierwszych

[edytuj] Rozkład n! na czynniki pierwsze

[edytuj] O rozkładzie środkowego współczynnika dwumianowego

[edytuj] Rozmieszczenie liczb pierwszych

[edytuj] Szereg odwrotności wszystkich liczb pierwszych

[edytuj] Oszacowania iloczynu odcinka liczb pierwszych

[edytuj] Postulat Bertranda – Twierdzenie Czebyszewa

[edytuj] Metoda Czebyszewa

[edytuj] Wariacja Erdősa

[edytuj] Twierdzenie Dirichleta

[edytuj] Przypadki szczególne

[edytuj] Twierdzenie o liczbach pierwszych

[edytuj] Hipoteza Riemanna

[edytuj] Hipoteza liczb pierwszych bliźniaczych

[edytuj] Specjalne rodzaje i uogólnienia liczb pierwszych

[edytuj] Liczby pierwsze bliźniacze

[edytuj] Liczby pierwsze Mersenne'a

[edytuj] Liczby złożone Mersenne'a

[edytuj] Liczby pierwsze Fermata

[edytuj] Liczby pierwsze Sophie Germain

[edytuj] Liczby pomiędzy pierwsze

[edytuj] Liczby pseudopierwsze

[edytuj] Liczby lustrzane

[edytuj] Liczby palindromiczne pierwsze

[edytuj] Problemy

[edytuj] Największe znane liczby pierwsze

Przypisy

[edytuj] Bibliografia

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach