Twierdzenie Euklidesa: liczb pierwszych jest nieskończenie wiele

Q: Czy liczba N z dowodu jest zawsze pierwsza?

Nie. Najmniejszy kontrprzykład to 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031, które rozkłada się na 59 · 509. Dowód tego nie potrzebuje - wystarczy, że N ma dzielnik pierwszy spoza listy.

Q: Czy istnieje wzór na kolejne liczby pierwsze?

Nie ma prostego wzoru, który dla każdego n zwracałby n-tą liczbę pierwszą. Są wzory teoretyczne, ale nie nadają się do rachunków - w praktyce liczby pierwsze wyszukuje się sitem Eratostenesa i testami pierwszości.

Twierdzenie Euklidesa

Liczb pierwszych jest nieskończenie wiele. Kluczowy krok dowodu: dla dowolnego skończonego zbioru liczb pierwszych $p_1, p_2, \ldots, p_k$ rozważamy liczbę

$N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1,$

która przy dzieleniu przez każdą z liczb $p_i$ daje resztę $1$ .

Co mówi twierdzenie

Liczba pierwsza to liczba naturalna większa od $1$ , która dzieli się tylko przez $1$ i przez samą siebie: $2, 3, 5, 7, 11, 13, \ldots$ Twierdzenie Euklidesa mówi, że ten ciąg nigdy się nie kończy - nie istnieje „największa liczba pierwsza”.

To nie jest oczywiste. Liczby pierwsze robią się coraz rzadsze: wśród pierwszych dziesięciu liczb naturalnych są cztery pierwsze, wśród pierwszych stu - dwadzieścia pięć, wśród pierwszych miliona - około $78$ tysięcy. Gdyby ta gęstość spadała odpowiednio szybko, liczby pierwsze mogłyby się w pewnym momencie skończyć. Euklides pokazał, że tak się nie stanie.

Dowód

Pokaż dowódUkryj dowód

Krok 1. Zakładamy nie wprost, że liczb pierwszych jest skończenie wiele. Można je wtedy wypisać wszystkie:

$p_1, \ p_2, \ \ldots, \ p_k.$

Krok 2. Budujemy nową liczbę. Mnożymy je wszystkie i dodajemy jeden:

$N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1.$

Krok 3. Zauważamy, że $N > 1$ . Iloczyn liczb pierwszych jest co najmniej $2$ , więc $N \geq 3$ .

Krok 4. Każda liczba większa od 1 ma dzielnik pierwszy. Jeśli $N$ jest pierwsza - jest swoim własnym dzielnikiem pierwszym. Jeśli nie, to rozkłada się na czynniki mniejsze od siebie i po kilku krokach dochodzimy do czynnika pierwszego. Oznaczmy taki dzielnik przez $q$ .

Krok 5. Pokazujemy, że $q$ nie jest żadną z liczb $p_1, \ldots, p_k$ . Przypuśćmy, że $q = p_i$ dla pewnego $i$ . Wtedy $q$ dzieli $N$ oraz dzieli iloczyn $p_1 \cdot p_2 \cdot \ldots \cdot p_k$ . Skoro dzieli obie liczby, dzieli też ich różnicę:

$N - p_1 \cdot p_2 \cdot \ldots \cdot p_k = 1.$

Ale żadna liczba pierwsza nie dzieli jedynki - sprzeczność.

Krok 6. Wniosek. Otrzymaliśmy liczbę pierwszą $q$ spoza naszej listy, choć lista miała zawierać wszystkie liczby pierwsze. Założenie z kroku 1 jest więc fałszywe: liczb pierwszych jest nieskończenie wiele. $\blacksquare$

Najczęstsze nieporozumienie

Bardzo często dowód streszcza się (błędnie) tak: „mnożymy wszystkie liczby pierwsze, dodajemy jeden i dostajemy nową liczbę pierwszą”. To nieprawda - liczba $N$ wcale nie musi być pierwsza. Dowód mówi jedynie, że $N$ ma dzielnik pierwszy spoza listy.

Zobaczmy to na liczbach. Mnożąc kolejne liczby pierwsze i dodając jeden, dostajemy:

$2 + 1 = 3$ - liczba pierwsza;
$2 \cdot 3 + 1 = 7$ - liczba pierwsza;
$2 \cdot 3 \cdot 5 + 1 = 31$ - liczba pierwsza;
$2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211$ - liczba pierwsza;
$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 = 2311$ - liczba pierwsza;
$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ - złożona!

Ostatni przykład nie psuje dowodu: czynniki $59$ i $509$ też są liczbami pierwszymi spoza listy $\{2, 3, 5, 7, 11, 13\}$ - dokładnie tak, jak zapowiada krok 5.

Jak rzadkie są liczby pierwsze

Skoro jest ich nieskończenie wiele, naturalne jest pytanie: jak gęsto występują? Odpowiada na to twierdzenie o liczbach pierwszych (Hadamard i de la Vallée Poussin, 1896): liczba liczb pierwszych nie większych od $x$ , oznaczana $\pi(x)$ , spełnia

$\pi(x) \approx \frac{x}{\ln x}.$

Dla $x = 10^6$ daje to około $72\,382$ , a naprawdę jest ich $78\,498$ - przybliżenie z błędem około $8\%$ , poprawiające się wraz ze wzrostem $x$ .

Jednocześnie w ciągu liczb naturalnych istnieją dowolnie długie przerwy bez liczb pierwszych. Dla dowolnego $n$ liczby

$n! + 2, \quad n! + 3, \quad \ldots, \quad n! + n$

są kolejno podzielne przez $2, 3, \ldots, n$ , więc żadna z nich nie jest pierwsza. To ciąg $n - 1$ kolejnych liczb złożonych - i można go zbudować dla dowolnie dużego $n$ .

Po co to komu

Cała współczesna kryptografia z kluczem publicznym opiera się na liczbach pierwszych. Algorytm RSA potrzebuje dwóch dużych liczb pierwszych (dziś zwykle po $1024$ bity, czyli ponad $300$ cyfr) - i musi mieć pewność, że takich liczb nie zabraknie oraz że da się je losowo znajdować.

Twierdzenie Euklidesa gwarantuje pierwsze, a twierdzenie o liczbach pierwszych - drugie: skoro wśród liczb $300$ -cyfrowych mniej więcej jedna na $700$ jest pierwsza, wystarczy losować i testować, by w rozsądnym czasie trafić na liczbę pierwszą.

Kto i kiedy

Dowód pochodzi z Elementów Euklidesa (księga IX, twierdzenie 20), spisanych około $300$ roku p.n.e. w Aleksandrii. Sam Euklides sformułował go ostrożniej niż my dzisiaj - starożytni Grecy unikali pojęcia nieskończoności i mówili raczej: „liczb pierwszych jest więcej niż jakakolwiek zadana ich ilość”.

Rozumowanie przetrwało ponad dwa tysiące lat bez jednej poprawki i do dziś jest podręcznikowym przykładem dowodu nie wprost. Więcej o autorze: Euklides.

Najczęstsze pytania

Czy liczba $N$ z dowodu jest zawsze pierwsza? Nie. Najmniejszy kontrprzykład to $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$ , które rozkłada się na $59 \cdot 509$ . Dowód tego nie potrzebuje - wystarczy, że $N$ ma dzielnik pierwszy spoza listy.

Czy znamy największą liczbę pierwszą? Nie i nigdy nie poznamy - twierdzenie Euklidesa właśnie to wyklucza. Znamy natomiast największą odkrytą dotąd liczbę pierwszą; rekordy padają co kilka lat i są to zwykle liczby Mersenne’a postaci $2^p - 1$ .

Czy jedynka jest liczbą pierwszą? Nie. Gdyby była, rozkład na czynniki pierwsze przestałby być jednoznaczny (można by dopisywać dowolnie wiele jedynek), a to zepsułoby podstawowe twierdzenie arytmetyki.

Dlaczego to dowód „nie wprost”? Bo zaczynamy od zaprzeczenia tezy („liczb pierwszych jest skończenie wiele”) i doprowadzamy do sprzeczności. Skoro założenie prowadzi do fałszu, musi być fałszywe - a więc teza jest prawdziwa.

Czy istnieje wzór na kolejne liczby pierwsze? Nie ma prostego wzoru, który dla każdego $n$ zwracałby $n$ -tą liczbę pierwszą. Są wzory teoretyczne, ale nie nadają się do rachunków - w praktyce liczby pierwsze wyszukuje się sitem Eratostenesa i testami pierwszości.

Podsumowanie

Liczb pierwszych jest nieskończenie wiele - to twierdzenie Euklidesa sprzed ponad $2300$ lat.
Dowód jest nie wprost: z założenia o skończonej liście budujemy liczbę $N = p_1 \cdots p_k + 1$ i pokazujemy, że jej dzielnik pierwszy nie może należeć do listy.
Liczba $N$ nie musi być pierwsza (np. $30031 = 59 \cdot 509$ ) - to najczęstszy błąd w streszczeniach tego dowodu.
Liczby pierwsze rzedną jak $\tfrac{x}{\ln x}$ , ale nigdy się nie kończą; istnieją za to dowolnie długie przerwy między nimi.
Bez tego twierdzenia nie byłoby kryptografii RSA, na której opiera się bezpieczeństwo internetu.