Liczby pierwsze

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Liczby pierwsze to te liczby naturalne większe od 1, które mają tylko dwa dzielniki naturalne – jedynkę i samą siebie.

$\forall _{x \in N} (P(x) \iff x > 1 \and \forall _y (y | x \rightarrow y = 1 \or y = x))$ , gdzie "P" znaczy tyle, co "jest liczbą pierwszą".

Liczbę naturalną (z wyjątkiem 1 i 0), która nie jest liczbą pierwszą, nazywamy liczbą złożoną. 1 oraz 0 nie są ani liczbami pierwszymi, ani złożonymi.

[edytuj] Własności ogólne

Już od czasów Euklidesa wiedziano, że liczb pierwszych jest nieskończenie wiele. Poniższy dowód tego faktu jest modyfikacją oryginalnego dowodu Euklidesa i oparty jest na obserwacji, że każda liczba naturalna jest albo pierwsza, albo ma dzielnik pierwszy. Załóżmy więc, że liczb pierwszych jest tylko skończona liczba i są to: p₁, p₂, ...,p_n. Wtedy jednak liczba $\begin{matrix} \prod_{i=1}^n p_i +1\end{matrix}$ w dzieleniu przez każdą z nich daje resztę 1, czyli nie dzieli się przez żadną z wypisanych liczb pierwszych. A więc albo sama musi być pierwsza lub musi istnieć jakaś liczba pierwsza inna niż p₁, p₂, ..., p_n.

Każda liczba naturalna większa od 1 jest albo pierwsza, albo daje się jednoznacznie zapisać w postaci iloczynu swych czynników pierwszych. W tym sensie można powiedzieć, że liczby pierwsze są elementarnymi cegiełkami, z których zbudowane są pozostałe liczby i to decyduje o ich ważności.

[edytuj] Wyznaczanie liczb pierwszych

Prostą, choć mało wydajną, metodę znajdowania liczb pierwszych stanowi 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ą.

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.

Przykładowy program w języku C oparty na sicie Eratostenesa, znajdujący pierwszych 15000 liczb pierwszych:

#include <stdio.h>
int main()
{
   int tab[15000] = { 2 };   // znalezione liczby pierwsze
   int lim = 0;        // numer kolejnej liczby pierwszej
   int sq = 4;         // kwadrat liczby tab[lim]
   int i, j, f;

   printf("%d", tab[0]);

   for(i=3, j=1; j<15000; i+=2)
   {
       if(i >= sq)
           ++lim, sq = tab[lim] * tab[lim];

       for(f=1; f<lim; f++)
           if(i % tab[f] == 0)
               break;

       if(f >= lim)
       {
           tab[j++] = i;
           printf(",%d", i);
       }
   }

   return 0;
}

Wartościami zmiennej i są kolejne liczby "kandydatki", które program sprawdza. Te z nich, które okażą się pierwszymi, umieszczane są w tablicy tab. Zmienna j przechowuje długość wypełnionego fragmentu tablicy (liczbę znalezionych liczb pierwszych).
Program bada tylko liczby nieparzyste, poczynając od 3. Liczba 2, jedyna parzysta liczba pierwsza, jest umieszczona w tablicy w fazie inicjalizowania danych.
Pętla wewnętrzna przegląda początkowy fragment tablicy (indeks f) i sprawdza podzielność liczby-kandydatki i przez już znalezione liczby pierwsze. Zmienna lim wraz z sq pozwalają ograniczyć zakres sprawdzeń wykonywanych w wewnętrznej pętli do potencjalnych dzielników nie większych od pierwiastka z badanej liczby.
Każda znaleziona liczba pierwsza jest natychmiast wypisywana na standardowe wyjście programu.

Program w języku Python, który pozwala wyliczyć dość "szybko" liczby pierwsze do podanej liczby.

def pierwsze(zakres):
 liczby_pierwsze=[2]
 if zakres==2:
         print liczby_pierwsze[0]
 else:
         for n in range(3,zakres):
                 for x in range(len(liczby_pierwsze)):
                         liczba1=n
                         liczba2=liczby_pierwsze[x]
                         while liczba2:
                                 liczba1, liczba2 = liczba2, liczba1%liczba2
                         if liczba1!=1:
                                 break
                 else:
                         liczby_pierwsze.append(n)
                         print n,

Program działa na podstawie Algorytmu Euklidesa.

[edytuj] Rozmieszczenie liczb pierwszych

Rozmieszczenie liczb pierwszych wśród liczb naturalnych wydaje się nie podlegać żadnym prawidłowościom. W szczególności 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 ∑ 1/p

Leonhard Euler udowodnił, że szereg liczbowy ∑ _i 1/p_i 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.

[edytuj] Twierdzenie Czebyszewa

Czebyszew udowodnił następujące twierdzenie:

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

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

Dla dowolnej liczby naturalnej n większej od 6, między liczbami n a 2n znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci 4k + 1 oraz co najmniej jedna postaci 4l + 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.

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

[edytuj] 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że O.

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

[edytuj] Liczby pierwsze Mersenne'a

Są to liczby pierwsze będące jednocześnie liczbami Mersenne'a (tj. są postaci 2ⁿ - 1 dla pewnego n będącego również liczbą pierwszą). Przykłady: 3, 7, 31, 127, 8191...

We wrześniu 2006 roku największą znaną liczbą pierwszą była właśnie 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.

[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

F5 = 641 x 6700417

F6 = 274177 x 67280421310721

[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ą z próbami udowodnienia wielkiego twierdzenia Fermata.

[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 liczba pierwsza (2 759 677 cyfr), która nie jest liczbą Mersenne'a:

$27653\cdot 2^{9167433} + 1$