Liczby pierwsze

Definicja:

Liczba pierwsza to liczba naturalna, która ma dokładnie dwa dzielniki: 1 oraz samą siebie.
Zbiór liczb pierwszych w powyższym sensie oznacza się często przez $P$.

Ponieważ podzielność można rozpatrywać również w zbiorze liczb całkowitych, więc czasami przyjmuje się definicję: liczbę całkowitą nazwiemy pierwszą, gdy w każdym jej przedstawieniu w postaci iloczynu dwóch liczb całkowitych dokładnie jeden z czynników ma wartość bezwzględną równą 1.
W dalszej części artykułu ograniczymy się jednak do liczb naturalnych.

Własności:

• najmniejszą i jedyną parzystą liczbą pierwszą jest liczba 2;
• istnieje nieskończenie wiele liczb pierwszych;
• jeżeli liczba pierwsza dzieli iloczyn dwóch liczb, to dzieli co najmniej jeden z czynników (zasadnicze twierdzenie arytmetyki);
• każda liczba naturalna większa od 1 jest albo liczbą pierwszą, albo iloczynem liczb pierwszych (przedstawienie liczby w postaci iloczynu liczb pierwszych jest jednoznaczne z dokładnością do kolejności czynników);
• jeżeli p jest liczbą pierwszą i nie jest dzielnikiem liczby b, to p dzieli liczbę $b^{p-1}$ (małe twierdzenie Fermata);
• p jest liczbą pierwszą dokładnie wtedy, gdy p dzieli liczbę (p-1)!+1 (kryterium Wilsona-Waringa pierwszości liczb);
• p jest liczbą pierwszą dokładnie wtedy, gdy p dzieli liczbę (p-2)!-1 (kryterium Leibniza pierwszości liczb);
• szereg odwrotności liczb pierwszych jest zbieżny (suma odwrotności liczb pierwszych jest liczbą skończoną);
• istnieją dowolnie długie (ale skończone) ciągi arytmetyczne liczb pierwszych.

Liczby związane z liczbami pierwszymi:

• liczby złożone -liczby naturalne wieksze od 1, które posiadają więcej niż dwa różne dzielniki;
• liczby bliźniacze - dwie liczby pierwsze różniące się o 2, np. 3 i 5;
• liczby Mersenne'a; (podlinkować)
• liczby Fermata;
• liczby Carmichaela - liczby złożone spełniające małe twierdzenie Fermata;
• liczby doskonałe - (czytaj wpis: liczby Mersenne'a);
• długie liczby pierwsze - to takie liczby pierwsze p, których okres w rozwinięciu ich odwrotności ma długość p-1;

Rozmieszczenie liczb pierwszych:

Logarytmiczne prawo Legendre'a: liczb pierwszych nieprzekraczających N jest w przybliżeniu $N/\ln N$.

Przybliżenie Gaussa: liczba liczb pierwszych nieprzekraczających N jest równa w przybliżeniu polu obszaru ograniczonego przez proste x=2, x=N, oś odciętych oraz wykres funkcji $1/\ln N$ (całka oznaczona z tej funkcji po odpowiednim przedziale). Oszacowaną w ten sposób liczbę liczb pierwszych nie wiekszą niż N oznaczmy przez $Li(N)$.

Oszacowanie Riemanna: liczba $R(N) liczb pierwszych nie większych niż N jest w przybliżeniu równa:

$$ R(N)= \mu(1)\cdot\frac{1}{1}\cdot Li(N)+ \mu(2)\cdot\frac{1}{2}\cdot Li(N^{\frac{1}{2}})+ \mu(3)\cdot\frac{1}{3}\cdot Li(N^{\frac{1}{3}})+... $$

gdzie $\mu$ jest funkcją Möbiusa i jest równa odpowiednio:

• 0, gdy n jest podzielne przez kwadrat pewnej liczby naturalnej różnej od 1;
• 1, gdy n jest iloczynem parzystej liczby różnych czynników pierwszych;
• -1, gdy n jest iloczynem nieparzystej liczby różnych czynników pierwszych.

Historia:

• Euklides w IV wieku p.n.e. udowodnił, że istnieje nieskończenie wiele liczb pierwszych;
• Eratostenes w III wieku p.n.e. wskazał pierwszy algorytm wyszukiwania liczb pierwszych zwany sitem Eratostenesa. Opis metody: pierwszą liczbą pierwszą jest liczba 2, wykreślmy wszystkie jej wielokrotności; pierwsza niewykreślona liczba (w tym kroku tą liczbą będzie 3) jest również liczbą pierwszą, którą należy pozostawić, a wykreślić jej wszystkie wielokrotności, itd...; w ten sposób wykreślimy wszystkie liczby złożone, pozostaną więc liczby pierwsze;
• później znaczące osiągnięcia w teorii liczb miał dopiero Pierre de Fermat. Sformułował na przykład twierdzenie: jeżeli p jest liczbą pierwszą postaci 4k+1 (gdzie k jest liczbą naturalną), to jest ona sumą dwóch kwadratów; (zobacz też liczby pierwsze Fermata);
• twierdzeń Fermata (nie wszystkich) dowiódł dopiero Leonhard Euler około 100 lat po ich powstaniu. Euler jako pierwszy użył metod analitycznych do badania zagadnień teorii liczb;
• dopiero pod koniec XIX wieku Hadamard i (niezależnie) Poussin udowodnili, że przy x dążącym do nieskończoności stosunek $\frac{\pi(x) \cdot \ln x}{x}$ zbliża się do 1, gdzie $\pi(x)$ oznacza liczbę liczb pierwszych nie większych od x, a $\ln(x)$ jest logarytmem naturalnym (przy podstawie e) liczby x.

Bibligrafia:

• Księga liczb. J.H. Conway, R.K.Guy. Wydawnictwo Naukowo-Techniczne. Warszawa 1999.
• Matematyka i jej historia. W. Więsław. Wydawnictwo Nowik. Opole 1997.
• Encyklopedia szkolna. Matematyka. Wydawnictwa Szkolne i Pedagogiczne. Warszawa 1989.