Krótko o liczbach pierwszych :: Artykuły / Polski Serwis Naukowy

Polecamy również:

Szczegóły pierwszych projektów IMI ujawnione

20. rocznica pierwszych powszechnych wyborów prezydenckich w Polsce

Archeolodzy zbadali osadę pierwszych rolników w Szewnie

Naukowcy odsłaniają tajemnicę pierwszych eksploratorów na świecie

Resort nauki sfinansuje budowę pierwszych polskich satelitów

20 lat od odkrycia przez Polaka pierwszych planet pozasłonecznych

Liczby pierwsze, choć znane od wczesnych lat szkolnej edukacji, są bardzo ciekawymi obiektami matematycznymi. Kryją w sobie wiele tajemnic, których odkrycie nie udało się dotychczas nawet najtęższym umysłom świata.

Dla porządku przypomnijmy, że liczbą pierwszą nazywamy każdą liczbę naturalną $\fs2 n>1$ , która ma dokładnie dwa dzielniki: $\fs2 1$ oraz $\fs2 n$ . Przyjrzyjmy się nieco bliżej zbiorowi liczb pierwszych. Na pewno każdy potrafi wypisać kilka liczb pierwszych. Gdybyśmy chcieli wypisać kilka liczb pierwszych zaczynając od największej, to mielibyśmy spory problem. Tak naprawdę jest to niemożliwe, ponieważ liczb pierwszych jest nieskończenie wiele, a co za tym idzie nie możemy wskazać największej. Nie ma problemu z wyznaczeniem jednak najmniejszej liczby pierwszej, czyli $\fs2 2$ . Wtedy kolejnymi liczbami pierwszymi są: $\fs2 3,\, 5,\, 7,\, 11,\, 13,\, 17,\, 19,\, 23,\, 29,\,...$ . Przy okazji zauważmy, że $\fs2 2$ jest jedyną wypisaną dotychczas liczbą parzystą, która jest pierwsza. Czy na pewno nie ma więcej?

Nie, ponieważ gdyby takowa istniała – na przykład liczba $\fs2 s$ – to dzieliłaby się oprócz $\fs2 1$ oraz $\fs2 s$ również przez $\fs2 2$ , co przeczyłoby warunkowi definicji.

1. Ile jest liczb pierwszych?

Odpowiedź na to pytanie padła już powyżej, a znana jest już od dosyć dawna, bo od ok 300 r. przed Chrystusem. Wówczas to Euklides, jako jeden z pierwszych (choć w literaturze przyjmuje się raczej, że jako pierwszy) udowodnił matematycznie niemożliwość istnienia największej liczby pierwszej, a co jest równoważne stwierdzeniu, że zbiór liczb pierwszych jest nieskończony.

Zanim spróbujemy uzasadnić dlaczego liczb pierwszych jest nieskończenie wiele, przywołam jedno ważne twierdzenie. Nosi ono nazwę Podstawowego twierdzenia arytmetyki. Chociaż w nazwie wyczuwa się, że jest ono rzeczywiście kluczowe dla całej arytmetyki, to w szkole raczej się o nim nie wspomina.

Podstawowe twierdzenie arytmetyki
Każda liczba naturalna większa od 1 ma jednoznaczne (z dokładnością do kolejności czynników) przedstawienie w postaci iloczynu liczb pierwszych.

Jednoznaczność trzeba rozumieć w ten sposób, że jeśli dowolna liczba np. $\fs2 9177$ będąca iloczynem liczb pierwszych $\fs2 3, 7, 19, 23$ innego rozkładu już nie ma z dokładnością do kolejności czynników, to znaczy mówimy, że $\fs2 3\cdot 7\cdot 19\cdot 23 = 9177 = 7\cdot 3 \cdot 19 \cdot 23$ .

Podstawowe twierdzenie arytmetyki pomoże w uzasadnieniu twierdzenia Euklidesa.
Aby łatwiej się pisało o zbiorze liczb pierwszych ustalmy raz na zawsze (czyli do końca artykułu), że przez $\fs2 \mathbb{P}$ oznaczać będziemy zbiór (wszystkich, nie tylko wybranych) liczb pierwszych.

Przypuśćmy, że zbiór $\fs2 \mathbb{P}$ jest skończony i składa się z dokładnie $\fs2 k$ liczb pierwszych:

$\mathbb{P}\,=\,{p_1,p_2,\dots, p_k}$

Utwórzmy liczbę naturalną

postaci:

$n=p_1\cdot p_2\cdot \cdots \cdot p_k+1$

Z podstawowego twierdzenia arytmetyki wynika, że n ma jednoznaczny rozkład na czynniki pierwsze. Zauważmy przy tym, że żadna ze zbioru $\fs2 \mathbb{P}$ nie dzieli $\fs2 n$ . Wynika stąd, że istnieją inne liczby pierwsze występujące w rozkładzie liczby $\fs2 n$ . A zatem zbiór $\fs2 \mathbb{P}$ nie zawiera wszystkich liczb pierwszych.

Wniosek: zbiór $\mathbb{P}$ nie jest zbiorem skończonym.

Liczby pierwsze mają swoje zastosowanie w naszej codzienności. To właśnie liczby pierwsze wykorzystywane w pomysłach matematyków oraz przekute klawiaturami informatyków w programy komputerowe zapewniają bezpieczne szyfrowanie informacji w Internecie.

2. Jak sprawdzić czy liczba jest pierwsza?

Odpowiedź na to pytanie jest dość prosta – należy tylko sprawdzić czy nie ma podzielników większych różnych od

i samej tej liczby. Powstaje jednak pytanie, jak długo sprawdzać podzielność. Na pewno nie trzeba sprawdzać większych niż n-1

, co wynika wprost z definicji. Jeśli przypatrzymy się, jak układają się pary liczb, których iloczyn jest równy

, to łatwo wywnioskować, że wystarczy jednak sprawdzić liczby od

do

.

Podamy stwierdzenie, które pozwoli jeszcze bardziej ograniczyć liczbę sprawdzeń:

$\bigg(\forall_{n\in N}\; \forall_{k\in[2,\sqrt{n}]\cap\mathbb{N}}\qquad k\not | n \bigg)\; \Rightarrow\; n\in\mathbb{P}$

Dowód:
Przypuśćmy, że żadna liczba naturalna $\fs2 k\leq\sqrt{n}$ nie jest podzielnikiem liczby $\fs2 n$ oraz $\fs2 n$ jest liczbą złożoną. Zatem $\fs2 n=x\cdot y$ , gdzie $\fs2 x,y\in\mathbb{N}$ .
Wówczas są możliwe dwie wykluczające się wypadki:
(1) x=y

;
(2)

.
Z dowolności

i

nie musimy rozważać sytuacji, gdy $\fs2 x>y$ (ponieważ albo obie liczby są równe albo jedna jest większa). Jeśli zachodzi (1), to $\fs2 x=y=\sqrt{n}$ . Ale zakładaliśmy, że $\sqrt{n}$ nie jest podzielnikiem liczby $\fs2 n$ , więc otrzymujemy sprzeczność. Zatem warunek (1) nie może zachodzić.
Jeśli zachodzi (2), to $\fs2 x|n$ i $\fs2 x<\sqrt{n}$ , co jest sprzeczne z założeniem. Zatem warunek (2) również nigdy nie zachodzi. Stąd niemożliwym jest aby n było liczbą złożoną, więc $\fs2 n$ jest liczbą pierwszą.

3. Jak znaleźć wszystkie liczby pierwsze?

Pytanie jest oczywiście nieco na wyrost. Nie da się znaleźć wszystkich liczb pierwszych, ale potrafimy znaleźć wszystkie liczby pierwsze mniejsze od pewnej, ustalonej liczby $\fs2 n$ . Można posłużyć się ciekawym z punktu widzenia informatyki algorytmem, który nazywany jest sitem Erastotenesa i pochodzi z czasów starożytnych. Polega ona na usuwaniu (przesiewaniu przez sito) krotności kolejnych liczb pierwszych. Pozostają wówczas wyłącznie liczby pierwsze nie większe niż $\fs2 n$ .

Przeanalizujmy działanie sita dla liczb naturalnych z przedziału [2, 30]:

Załączony film prezentuje działanie algorytmu, który zaproponował Eratostenes. Zauważmy, że potrzebowaliśmy aż 10 kroków (czyli kolorowań dziewięciu liczb) żeby wyznaczyć wszystkie liczby pierwsze z tego przedziału. Powstaje naturale pytanie, czy można szybciej. Okazuje się, że tak. Zauważmy, że od pewnego momentu nie wykreślamy już żadnych liczb, tylko kolorujemy (tzn. uznajemy za pierwsze) te, które pozostały. Z pomocą przychodzi stwierdzenie z punktu 2. Zastosowanie go do sita Eratostenesa pozwala ograniczyć liczbę wykreśleń (a tym samym sprawdzeń) do liczb nie większych niż $\fs2 \sqrt{n}$ .
Na załączonym filmie widać, że jako ostatnią wykreślamy krotność liczby 5. Zauważmy przy tym, że $\fs2 5<\sqrt{30}<6$ , co potwierdza naszą obserwację. Dzięki temu wystarczyłoby wykreślać krotności tylko trzech kolejnych liczb a resztę, która pozostała uznać za liczby pierwsze. Jest to znaczne uproszczenie w stosunku do początkowych 10 kroków.

Dowód naszej obserwacji pozostawiamy czytelnikowi.

komentuj publikację

Czy wiesz że...?

wersja BETA

Funkcja multiplikatywna W teorii liczb, funkcję arytmetyczną f określoną na zbiorze liczb naturalnych nazywamy multiplikatywną, jeżeli dla wszystkich względnie pierwszych liczb m, n spełniony jest warunek pełny tekst

Słaba hipoteza Goldbacha to przypuszczenie w teorii liczb, które mówi, że każda liczba naturalna nieparzysta i większa od 7 jest sumą trzech nieparzystych liczb pierwszych (niekoniecznie różnych). pełny tekst

Moduł "Czy wiesz że...?" (wersja testowa, beta): definicje/pojęcia wygenerowane w obrębie tego modułu pochodzą z Wikipedii i udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Dostęp do pełnej wersji każdego hasła (oraz dokładnch informacji na temat licencji, autora oraz edycji) możliwy jest po kliknięciu w odnośnik opisany jako "pełny tekst".