Liczba pierwsza


Liczba pierwsza w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Spis treści

Liczba pierwszaliczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą. Zbiór wszystkich liczb pierwszych oznacza się symbolem P . {\displaystyle \mathbb {P} .}

Wykaz początkowych liczb pierwszych:

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. (ciąg A000040 w OEIS).

W wykazie brak np. liczby 4, bowiem 4 ma dzielniki 1, 2 i 4. Podobnie z liczbą 6, która ma 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[1].

Podstawowe własności | edytuj kod

  • 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 X {\displaystyle X} będzie skończonym zbiorem liczb pierwszych. Niech x {\displaystyle x} będzie iloczynem wszystkich liczb występujących w X {\displaystyle X} (gdy X {\displaystyle X} jest puste, to x = 1 {\displaystyle x=1} ). Jedynym wspólnym dzielnikiem liczb x {\displaystyle x} oraz x + 1 {\displaystyle x+1} jest 1. Zatem żadna liczba pierwsza, występująca w X , {\displaystyle X,} nie jest dzielnikiem liczby x + 1. {\displaystyle x+1.} Ale x + 1 > 1. {\displaystyle x+1>1.} Więc x + 1 {\displaystyle x+1} ma dzielnik p , {\displaystyle p,} który jest liczbą pierwszą. Liczba pierwsza p {\displaystyle p} nie należy do X {\displaystyle X} (bo jest dzielnikiem liczby x + 1 {\displaystyle x+1} ).
  • Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych. 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, z których przy pomocy mnożenia zbudowane są pozostałe liczby.

Wyznaczanie | edytuj kod

Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym, można posłużyć się algorytmem zwanym sitem Eratostenesa: jeśli liczba naturalna N {\displaystyle N} większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z N , {\displaystyle N,} to N {\displaystyle N} 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.

Rozkład n ! {\displaystyle n!} na czynniki pierwsze | edytuj kod

Niech ord p ( n ) {\displaystyle \operatorname {ord} _{p}(n)} oznacza wykładnik, z którym liczba pierwsza p {\displaystyle p} występuje w rozkładzie liczby naturalnej n {\displaystyle n} (waluacja p-adyczna). Wtedy:

ord p ( n ! ) = k = 1 n p k {\displaystyle \operatorname {ord} _{p}(n!)=\sum _{k=1}^{\infty }\left\lfloor {\tfrac {n}{p^{k}}}\right\rfloor } (wzór Legendre’a),

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

x 1 < x x {\displaystyle x-1<\lfloor x\rfloor \leqslant x}

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

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

Rozkład środkowego współczynnika dwumianowego | edytuj kod

Zbadajmy o p ( n ) := ord p ( 2 n n ) . {\displaystyle o_{p}(n):=\operatorname {ord} _{p}{\binom {2n}{n}}.} o p ( n ) = 1 , {\displaystyle o_{p}(n)=1,} gdy liczba pierwsza p {\displaystyle p} należy do przedziału n < p 2 n . {\displaystyle n<p\leqslant 2n.} Ogólnie:

o p ( n ) = ord p ( ( 2 n ) ! ) 2 ord p ( n ! ) . {\displaystyle o_{p}(n)=\operatorname {ord} _{p}((2n)!)-2\operatorname {ord} _{p}(n!).}

Ponieważ

0 2 x 2 x 1 {\displaystyle 0\leqslant \lfloor 2x\rfloor -2\lfloor x\rfloor \leqslant 1}

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

o p ( n ) ln ( 2 n ) ln p . {\displaystyle o_{p}(n)\leqslant \left\lfloor {\tfrac {\ln(2n)}{\ln p}}\right\rfloor .}

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

p o p ( n ) 2 n , {\displaystyle p^{o_{p}(n)}\leqslant 2n,}

czyli:

Twierdzenie. Jeżeli p k | ( 2 n n ) , {\displaystyle p^{k}|{\binom {2n}{n}},} to p k 2 n . {\displaystyle p^{k}\leqslant 2n.}

Prawdziwe jest także twierdzenie:

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

Rozmieszczenie | edytuj kod

Liczby pierwsze na spirali Ulama 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 | edytuj kod

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

Niech

P ( x ) := p P , p x 1 p , {\displaystyle P(x):=\sum _{p\in \mathbb {P} ,p\leqslant x}{\tfrac {1}{p}},} Q ( x ) := p P , p x 1 p 1 . {\displaystyle Q(x):=\sum _{p\in \mathbb {P} ,p\leqslant x}{\tfrac {1}{p-1}}.}

Ponieważ

1 = ( 1 1 1 2 ) + ( 1 2 1 3 ) + , {\displaystyle 1=\left({\tfrac {1}{1}}-{\tfrac {1}{2}}\right)+\left({\tfrac {1}{2}}-{\tfrac {1}{3}}\right)+\dots ,}

to

P ( x ) > Q ( x ) 1 {\displaystyle P(x)>Q(x)-1}

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

Szereg geometryczny:

1 + 1 p 1 = 1 1 1 p = 1 + 1 p + 1 p 2 + {\displaystyle 1+{\tfrac {1}{p-1}}={\tfrac {1}{1-{\tfrac {1}{p}}}}=1+{\tfrac {1}{p}}+{\tfrac {1}{p^{2}}}+\dots }

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

p P , p x ( 1 + 1 p 1 ) = p P , p x ( 1 + 1 p + 1 p 2 + ) n = 1 x 1 n . {\displaystyle \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}}}+\dots \right)\geqslant \sum _{n=1}^{x}{\tfrac {1}{n}}.}

Ale 1 p 1 > ln ( 1 + 1 p 1 ) , {\displaystyle {\tfrac {1}{p-1}}>\ln \left(1+{\tfrac {1}{p-1}}\right),} a więc:

Q ( x ) > ln ( p P , p x ( 1 + 1 p 1 ) ) ln ( n = 1 x 1 n ) > ln ( ln ( x + 1 ) ) , {\displaystyle 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 ,}

zatem

P ( x ) > ln ( ln ( x + 1 ) ) 1 , {\displaystyle P(x)>\ln(\ln(x+1))-1\rightarrow \infty ,}

gdy x . {\displaystyle x\to \infty .} Koniec dowodu.

Franz Mertens uzyskał podobne oszacowanie P ( x ) {\displaystyle P(x)} także od góry.

Oszacowania iloczynu odcinka liczb pierwszych | edytuj kod

Jasnym jest, że zachodzi podzielność

p P , n < p 2 n p | ( 2 n n ) {\displaystyle \prod _{p\in \mathbb {P} ,n<p\leqslant 2n}p|{\binom {2n}{n}}} oraz równość ( 2 n n ) = 2 ( 2 n 1 n 1 ) . {\displaystyle {\binom {2n}{n}}=2\cdot {\binom {2n-1}{n-1}}.}

Więc dla n > 1 otrzymujemy:

p P , n < p 2 n p | ( 2 n 1 n 1 ) . {\displaystyle \prod _{p\in \mathbb {P} ,n<p\leqslant 2n}p|{\binom {2n-1}{n-1}}.} Wiemy także, że ( 2 n 1 n 1 ) = ( 2 n 1 n ) . {\displaystyle {\binom {2n-1}{n-1}}={\binom {2n-1}{n}}.}

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

p P , n < p 2 n p < 4 n 1 {\displaystyle \prod _{p\in \mathbb {P} ,n<p\leqslant 2n}p<4^{n-1}}

dla n > 2 , {\displaystyle n>2,} a nawet dla każdego n > 1. {\displaystyle n>1.} Bardziej atrakcyjne byłoby oszacowanie iloczynu początkowego odcinka liczb pierwszych

P ( x ) := { p P : p x } {\displaystyle \prod P(x):=\prod \{p\in \mathbb {P} :p\leqslant x\}}

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

P ( 2 n ) P ( n ) < 4 n 1 {\displaystyle {\frac {\prod P(2n)}{\prod P(n)}}<4^{n-1}}

dla każdego n > 1. {\displaystyle n>1.}

P ( 2 n 1 ) = P ( 2 n ) {\displaystyle \prod P(2n-1)=\prod P(2n)}

dla każdego naturalnego n > 1. {\displaystyle n>1.}

Twierdzenie
P ( x ) 1 2 4 x 1 {\displaystyle \prod P(x)\leqslant {\tfrac {1}{2}}4^{x-1}} dla każdej liczby całkowitej x > 1. {\displaystyle x>1.}
Dowód
Można sprawdzić bezpośrednio, że twierdzenie zachodzi dla x = 2 , 3. {\displaystyle x=2,3.}

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

P ( x ) < P ( x 2 ) 4 x 2 1 1 2 4 x 2 1 4 x 2 1 = 1 2 4 x 2 . {\displaystyle \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}.}

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

P ( x ) < P ( x + 1 2 ) 4 x 1 2 1 2 4 x 1 2 4 x 1 2 = 1 2 4 x 1 {\displaystyle \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}}

Koniec dowodu

Uwaga. Twierdzenie zachodzi dla każdej liczby rzeczywistej x 2 , {\displaystyle x\geqslant 2,} a nie tylko dla całkowitych.

Postulat Bertranda – Twierdzenie Czebyszewa | edytuj kod

 Osobny artykuł: Postulat Bertranda.

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

Twierdzenie

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

Dowód

Wyżej zdefiniowaliśmy o p ( n ) {\displaystyle o_{p}(n)} i odnotowaliśmy następujące trzy twierdzenia:

  • Jeżeli p k | ( 2 n n ) , {\displaystyle p^{k}|{\binom {2n}{n}},} to p k 2 n ; {\displaystyle p^{k}\leqslant 2n;} albo krótko: p o p ( n ) 2 n . {\displaystyle p^{o_{p}(n)}\leqslant 2n.}
  • Jeżeli n > 2 {\displaystyle n>2} jest liczbą naturalną, oraz p {\displaystyle p} – liczbą pierwszą z przedziału 2 3 n < p n , {\displaystyle {\tfrac {2}{3}}n<p\leqslant n,} to p {\displaystyle p} nie jest dzielnikiem współczynnika ( 2 n n ) . {\displaystyle {\binom {2n}{n}}.}
  • P ( x ) 1 2 4 x 1 {\displaystyle \prod P(x)\leqslant {\tfrac {1}{2}}4^{x-1}} dla każdego rzeczywistego x > 1. {\displaystyle x>1.}

Zdefiniujmy:

L ( n ) := p P , p n p o p ( n ) . {\displaystyle L(n):=\prod _{p\in \mathbb {P} ,p\leqslant n}p^{o_{p}(n)}.}

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

Otóż L ( n ) = M ( n ) N ( n ) , {\displaystyle L(n)=M(n)N(n),} gdzie:

M ( n ) := { p o p ( n ) : p 2 n , p P } {\displaystyle M(n):=\prod \left\{p^{o_{p}(n)}:p\leqslant {\sqrt {2n}},p\in \mathbb {P} \right\}} N ( n ) := { p P : 2 n < p 2 3 n } {\displaystyle N(n):=\prod \left\{p\in \mathbb {P} :{\sqrt {2n}}<p\leqslant {\tfrac {2}{3}}n\right\}}

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

M ( n ) ( 2 n ) n 2 {\displaystyle M(n)\leqslant (2n)^{\sqrt {\tfrac {n}{2}}}}

oraz

N ( n ) { p P : p 2 3 n } 1 2 4 2 3 n 1 . {\displaystyle 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}.}

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

( 2 n n ) 4 n 2 2 n 1 4 n 2 n {\displaystyle {\binom {2n}{n}}\geqslant {\tfrac {4^{n}-2}{2n-1}}\geqslant {\tfrac {4^{n}}{2n}}}

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

n ( 2 n ) n 2 4 2 3 n 1 < 4 n , {\displaystyle n(2n)^{\sqrt {\tfrac {n}{2}}}4^{{\tfrac {2}{3}}n-1}<4^{n},}

czyli

n ( 2 n ) n 2 < 4 n 3 + 1 {\displaystyle n(2n)^{\sqrt {\tfrac {n}{2}}}<4^{{\tfrac {n}{3}}+1}}

czyli, po zlogarytmowaniu:

( 1 + n 2 ) ln ( n ) ln ( 4 ) < ( n 3 + 1 ) n 2 2 {\displaystyle \left(1+{\sqrt {\tfrac {n}{2}}}\right){\tfrac {\ln(n)}{\ln(4)}}<\left({\tfrac {n}{3}}+1\right)-{\frac {\sqrt {\tfrac {n}{2}}}{2}}}

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

ln ( n ) = ln ( 32 ) + 2 ln ( n 32 ) < ln ( 32 ) + 2 ( n 32 1 ) < 2 + n 8 {\displaystyle \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}}}}

Wystarczy zatem dowieść

( 1 + n 2 ) ( 2 + n 8 ) < ( n 3 + 1 n 8 ) ln ( 4 ) , {\displaystyle \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),}

czyli

2 n + ( 1 + ln ( 4 ) ) n 8 < ( ln ( 4 ) 3 1 4 ) n 2 + ln ( 4 ) . {\displaystyle {\sqrt {2n}}+\left(1+\ln(4)\right){\sqrt {\tfrac {n}{8}}}<\left({\tfrac {\ln(4)}{3}}-{\tfrac {1}{4}}\right)n-2+\ln(4).}

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

8 2 n < n 4 {\displaystyle 8{\sqrt {2n}}<n-4}

co dla n 4 {\displaystyle n\geqslant 4} jest równoważne z:

n 2 136 n + 16 > 0 {\displaystyle n^{2}-136n+16>0}

Nierówność ta zachodzi dla każdego n 136. {\displaystyle n\geqslant 136.} Więc twierdzenie zachodzi dla każdego n 136. {\displaystyle n\geqslant 136.} Dla n 135 {\displaystyle n\leqslant 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 {\displaystyle 2,\ 3,\ 5,\ 7,\ 13,\ 23,\ 43,\ 83,\ 163}

Koniec dowodu.

Dla dowolnej, nieujemnej liczby całkowitej k {\displaystyle k} bez większego trudu można by dowieść nierówności:

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

lub słabszej

( s = 1 k ( 2 n 2 s + 1 ) ) L ( n ) < ( 2 n n ) {\displaystyle \left(\prod _{s=1}^{k}(2n-2s+1)\right)L(n)<{\binom {2n}{n}}}

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

Metoda Czebyszewa | edytuj kod

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[2]), który skupił się na środkowym współczynniku dwumianowym, czyli na ( 2 n ) ! , {\displaystyle (2n)!,} podzielonym dwukrotnie przez n ! . {\displaystyle 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[3]). Udowodnione po Czebyszewie twierdzenie o rozmieszczeniu liczb pierwszych natychmiast daje podobny wynik dla wszelkich proporcji ustalonych powyżej 1.

Wariacja Erdősa | edytuj kod

Paul Erdős wzmocnił twierdzenie Czebyszewa dowodząc

Twierdzenie

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

Twierdzenie Dirichleta | edytuj kod

Poniższe twierdzenie zostało udowodnione przez Dirichleta

Twierdzenie

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

Przypadki szczególne | edytuj kod

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

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

Twierdzenie o liczbach pierwszych | edytuj kod

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

π ( n ) L i ( n ) , {\displaystyle \pi (n)\sim \mathrm {Li} (n),}

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

lim n π ( n ) L i ( n ) = 1. {\displaystyle \lim _{n\to \infty }{\frac {\pi (n)}{\mathrm {Li} (n)}}=1.}

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

π ( n ) n ln n + n ln 2 n + 2 n ln 3 n + = i = 1 ( i 1 ) ! n ln i n . {\displaystyle \pi (n)\approx {\frac {n}{\ln n}}+{\frac {n}{\ln ^{2}n}}+{\frac {2n}{\ln ^{3}n}}+\dots =\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:

π ( n ) n ln n . {\displaystyle \pi (n)\approx {\frac {n}{\ln n}}.}

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

lim n π ( n ) n ln n = 1. {\displaystyle \lim _{n\to \infty }{\frac {\pi (n)}{\frac {n}{\ln n}}}=1.}

Hipoteza Riemanna | edytuj kod

 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 liczba π(n) liczb pierwszych w przedziale 1 , n {\displaystyle [1,n]} wyraża się wzorem:

π ( n ) = L i ( n ) + O ( n ln n ) , {\displaystyle \pi (n)=\mathrm {Li} (n)+O\left({\sqrt {n}}\ln n\right),}

gdzie użyto notacji dużego O.

Hipoteza liczb pierwszych bliźniaczych | edytuj kod

 Osobny artykuł: hipoteza liczb pierwszych bliźniaczych.

Według tej teorii liczb pierwszych bliźniaczych jest nieskończenie wiele.

Szczególne rodzaje liczb pierwszych | edytuj kod

Liczby pierwsze bliźniacze | edytuj kod

Liczby pierwsze p {\displaystyle p} i q {\displaystyle q} bliźniacze, jeśli p = q + 2. {\displaystyle 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...

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 luty 2019) to 2996863034895 2 1290000 ± 1. {\displaystyle 2996863034895\cdot 2^{1290000}\pm 1.} Liczby te, znalezione w 2016 roku, mają 388342 cyfr w zapisie dziesiętnym. [4]

Liczby pierwsze czworacze | edytuj kod

Liczby czworacze – liczby pierwsze mające postać p , {\displaystyle p,} p + 2 , {\displaystyle p+2,} p + 6 , {\displaystyle p+6,} p + 8 , {\displaystyle p+8,} np. 5, 7, 11 i 13 lub 101, 103, 107 i 109, czyli dwie pary liczb bliźniaczych w najbliższym możliwym sąsiedztwie. Największe znane liczby czworacze to:

667674063382677 2 33608 1 , {\displaystyle 667674063382677\cdot 2^{33608}-1,} 667674063382677 2 33608 + 1 , {\displaystyle 667674063382677\cdot 2^{33608}+1,} 667674063382677 2 33608 + 5 , {\displaystyle 667674063382677\cdot 2^{33608}+5,} oraz 667674063382677 2 33608 + 7 {\displaystyle 667674063382677\cdot 2^{33608}+7} Liczby te, znalezione w 2019 roku, mają po 10132 cyfry w zapisie dziesiętnym. [4]

Liczby pierwsze izolowane | edytuj kod

Liczba pierwsza p {\displaystyle p} jest izolowana, jeśli najbliższa jej liczba pierwsza różni się od p {\displaystyle p} co najmniej o 4. Przykłady: 23, 89, 157, 173.

Liczby pierwsze Mersenne’a | edytuj kod

Liczbę

M ( n ) := 2 n 1 {\displaystyle M(n):=2^{n}-1}

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

M ( N W D ( k , n ) ) = N W D ( M ( k ) , M ( n ) ) . {\displaystyle 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 ) {\displaystyle M(n)} była pierwsza jest pierwszość liczby n . {\displaystyle n.} Jednak nie dla każdej liczby pierwszej p , {\displaystyle p,} liczba M ( p ) {\displaystyle M(p)} jest pierwsza; na przykład:

2 11 1 = 23 89. {\displaystyle 2^{11}-1=23\cdot 89.}

Dlatego bada się także dzielniki Mersenne’a, a mianowicie dzielniki liczb Mersenne’a M ( p ) , {\displaystyle M(p),} dla p {\displaystyle p} pierwszego, zwłaszcza dzielniki pierwsze.

W sierpniu 2008 roku największą znaną liczbą pierwszą była liczba Mersenne’a 2 43112609 1 {\displaystyle 2^{43112609}-1} – 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[5]. Obecnie największą znaną, 51. liczbą pierwszą Mersenne’a jest 2 82589933 1 , {\displaystyle 2^{82589933}-1,} która w zapisie dziesiętnym ma 24 862 048 cyfr. Została ona odkryta 7 grudnia 2018 roku przez Patricka Laroche’a w ramach projektu GIMPS[6].

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

Liczby złożone Mersenne’a | edytuj kod

Liczby złożone Mersenne’a to liczby Mersenne’a M ( p ) , {\displaystyle M(p),} które są złożone, gdy liczba p {\displaystyle p} jest pierwsza (gdy p {\displaystyle p} jest złożone, to M ( p ) {\displaystyle M(p)} jest zawsze złożone).

Stwierdzenie

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

Dowód

Przy założeniach twierdzenia, niech x 2 2 mod q {\displaystyle x^{2}\equiv 2\mod q} dla pewnej liczby całkowitej x . {\displaystyle x.} Wtedy na mocy małego twierdzenia Fermata:

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

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

Koniec dowodu.

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

( p , q ) := ( 12 k 1 , 24 k 1 ) . {\displaystyle (p,q):=(12\cdot k-1,24\cdot k-1).}

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

Liczby pierwsze Fermata | edytuj kod

Są to liczby pierwsze postaci 2 2 n + 1. {\displaystyle 2^{2^{n}}+1.} 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

F 5 = 641 6700417 , {\displaystyle F_{5}=641\cdot 6700417,} F 6 = 274177 67280421310721. {\displaystyle F_{6}=274177\cdot 67280421310721.}

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

Liczby pierwsze Germain | edytuj kod

 Osobny artykuł: Liczba pierwsza Sophie Germain.

Liczbę pierwszą p {\displaystyle p} nazywamy liczbą pierwszą Sophie Germain jeżeli liczba 2 p + 1 {\displaystyle 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. Liczby pierwsze Germain są związane z liczbami złożonymi Mersenne’a.

Liczby pomiędzy pierwsze | edytuj kod

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 pseudopierwsze | edytuj kod

Liczby złożone n , {\displaystyle n,} które spełniają warunek:

n | 2 n 2. {\displaystyle n|2^{n}-2.}

Istnieje nieskończenie wiele liczb pseudopierwszych parzystych, jak i nieparzystych. Co więcej, dla każdej liczby pierwszej p {\displaystyle p} istnieje nieskończenie wiele liczb pseudopierwszych podzielnych przez p . {\displaystyle 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 {\displaystyle a} równym 2).

Liczby lustrzane pierwsze | edytuj kod

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

Liczby palindromiczne pierwsze | edytuj kod

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.

Problemy | edytuj kod

Zagadnienia dotyczące liczb pierwszych należą do 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 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 2 + 1 {\displaystyle n^{2}+1} ?
  • czy dla dowolnego n {\displaystyle n} pomiędzy liczbami n 2 {\displaystyle n^{2}} i ( n + 1 ) 2 {\displaystyle (n+1)^{2}} istnieje liczba pierwsza?

Największe znane liczby pierwsze | edytuj kod

Największa odkryta dotąd liczba pierwsza to 51. (znana) liczba pierwsza Mersenne’a: 2 82589933 1 {\displaystyle 2^{82589933}-1} i liczy sobie 24 862 048 cyfr w zapisie dziesiętnym.

W grudniu 2018 roku osiem największych znanych liczb pierwszych to liczby pierwsze Mersenne’a[7]. Największą znaną liczbą pierwszą, która nie jest liczbą Mersenne’a, jest:

10223 2 31172165 + 1 , {\displaystyle 10223\cdot 2^{31172165}+1,}

która w zapisie dziesiętnym liczy 9 383 761 cyfr. Liczba ta jest dziewiątą co do wielkości znaną liczbą pierwszą i została odkryta 31 października 2016 roku w ramach projektu PrimeGrid[8].

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

2 148 + 1 17 = 20 988 936 657 440 586 486 151 264 256 610 222 593 863 921 {\displaystyle {\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.

Odpowiedniki w innych strukturach algebraicznych | edytuj kod

Najbliższym odpowiednikiem liczb pierwszych w pierścieniachelementy pierwsze. Liczby pierwsze nie są jednak tym samym, co elementy pierwsze pierścienia liczb całkowitych – elementami pierwszymi są także liczby ujemne ( 2 , 3 , 5 , ) , {\displaystyle (-2,-3,-5,\dots ),} a według niektórych źródeł także zero[9], 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łu pierwszego nawiązuje do tych intuicji.

Zastosowanie | edytuj kod

Liczby pierwsze są stosowane w niektórych znanych algorytmach kryptograficznych; jednym z nich jest RSA. Rozwój tych algorytmów zapewnia ewolucję projektów wyszukiwania ogromnych liczb pierwszych, takich jak GIMPS.

Zobacz też | edytuj kod

Przypisy | edytuj kod

  1. 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.
  2. a b c Lew G. Sznirelman, Liczby pierwsze, PWN, Warszawa 1954.
  3. a b c William J. LeVeque © 1977, Fundamentals of Number Theory, Dover Publications 1996, ​ISBN 0-486-68906-9​.
  4. a b The Largest Known Primes.
  5. GIMPS Project Discovers Largest Known Prime Number, 274,207,281-1 (ang.). mersenne.org. [dostęp 2016-01-07].
  6. Mersenne Prime Discovery - 2^82589933-1 is Prime!, www.mersenne.org [dostęp 2018-12-21] .
  7. Chris K.Ch.K. Caldwell Chris K.Ch.K., The Prime Database: Database Search Output, primes.utm.edu [dostęp 2018-01-05]  (ang.).
  8. PrimeGrid official announcement http://www.primegrid.com/download/SOB-31172165.pdf.
  9. Na podstawie definicji w Fritz Reinhardt, Heinrich Soeder: Atlas matematyki. Prószyński i S-ka, s. 121. ISBN 978-83-7469-189-5. W podręczniku Algebry Białynickiego-Biruli zero jest jednak z definicji elementu pierwszego wykluczone.

Bibliografia | edytuj kod

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

Linki zewnętrzne | edytuj kod

Kontrola autorytatywna (rodzaj liczby):
Na podstawie artykułu: "Liczba pierwsza" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy