Impresja o liczbach pierwszych

Teoria liczb jest dziedziną matematyki zajmującą się liczbami naturalnymi. Nazwano ją królową nauk matematycznych ze względu na (jak sądzono) największą czystość czyli zupełny brak związków z praktyką. Dziś teoria liczb utraciła to dziewictwo, albowiem rozkład liczby naturalnej na czynniki pierwsze stanowi podstawę algorytmu szyfrowania z kluczem publicznym. Ale nie o tym chcę dziś mówić — cofnę się do absolutnych podstaw. Zapraszam więc do lektury.


Liczby pierwsze

Liczba naturalna jest pierwsza, jeśli ma dokładnie dwa dzielniki. Stąd od razu wynika, że jedynka nie jest liczbą pierwszą. Czemu o tym mówię? Bo w szkole podstawowej uczono mnie, że liczba pierwsza to taka, która dzieli się tylko przez $1$ i przez samą siebie, a jedynka ten warunek spełnia.

Jasnym jest, że każdą liczbę naturalną większą niż $1$ można przedstawić w postaci iloczynu liczb pierwszych. Dlaczego jasne? Niech $n>1$ będzie liczbą naturalną. Jeśli nie da się jej przez nic podzielić (mówię tu kolokwialnie, mając na myśli dzielniki właściwe, czyli większe niż $1$ i mniejsze niż $n$), to jest pierwsza. Jeśli się da, to zabawę w szukanie dzielników powtarzamy dla każdego dzielnika z osobna. W końcu dojdziemy do podstaw: niczego już nie będzie się dało przez nic podzielić i otrzymamy liczbę $n$ w postaci iloczynu liczb pierwszych.

Istnieje nieskończenie wiele liczb pierwszych i jest to podstawowe twierdzenie w teorii liczb. Dowodów jest co niemiara. Ale najprostszy jest dowód Euklidesa. Niech $\{p_1,\dots,p_n\}$ będzie zbiorem skończonym złożonym z liczb pierwszych, nawet niekoniecznie kolejnych. Niech $p=p_1\cdot p_2\cdot\ldots\cdot p_n+1$. Łatwo zauważyć, że liczba $p$ nie jest podzielna przez żadną z liczb $p_1,\dots,p_n$ (bo resztą z takiego dzielenia jest $1$). Dlatego istnieje liczba pierwsza inna niż wszystkie te liczby. Jest nią albo sama liczba $p$, albo, jeśli $p$ jest złożona, jakikolwiek jej dzielnik pierwszy. Wykazaliśmy więc, że dla każdego zbioru skończonego złożonego z liczb pierwszych istnieje liczba pierwsza, która do niego nie należy. Tym samym rzeczywiście zbiór wszystkich liczb pierwszych jest nieskończony.

Podzielę się pewnym spostrzeżeniem związanym z powyższym dowodem. Przypuśćmy, że będziemy rozważać kolejne skończone zbiory początkowych liczb pierwszych takie jak $\{2\}$, $\{2,3\}$, $\{2,3,5\}$ itd. Niech ogólnie $\{p_1,\dots,p_n\}$ będzie takim podzbiorem. Gdy sam poznawałem dowód nieskończoności zbioru liczb pierwszych, wydawało mi się, że już liczba $p=p_1\cdot p_2\cdot\ldots\cdot p_n+1$ jest pierwsza, bo przecież żadna z liczb $p_1,\dots,p_n$ nie jest jej dzielnikiem. To ewidentna nieprawda, gdyż liczby postaci $p$ mogą być złożone, o czym nietrudno się przekonać. Pierwsza taka możliwość zachodzi dla zbioru $\{2,3,5,7,11,13\}$, dla którego\[2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509\,.\] Dalej złożone są liczby $p$ dla wszystkich kolejnych zbiorów aż do liczby $29$ (jako końcowej) włącznie. Dla $p_n=31$ znów $p$ jest liczba pierwszą, potem dla $p_n=37$ bądź $p_n=41$ znów liczby $p$ są złożone. Rozpoznanie pierwszości czy złożoności dalszych liczb $p$ pozostawiam eksperymentom Czytelników (jeśli tylko dysponują odpowiednim oprogramowaniem).

7 komentarzy

  1. Dawno temu mówiono, że jeżeli Pan Bóg miał czas by zajmować się matematyką to uprawia geometrię, później że zajmuje się algebrą, a obecnie teorią liczb.

  2. Z tą jedynką i definicją widzę jeden istotny problem – jeśli tłumaczenie jest takie, że 1 nie jest pierwsze z definicji, to skąd się w takim razie wzięła definicja?

    1. A dlaczego czasem umawiamy się, że 0 jest liczbą naturalną, a czasem, że nie jest? Proponuję przejrzeć dostępne w sieci dyskusje.

Dodaj komentarz