Teoria liczb 2010, sem.IV,
B.Bajorska, O.Macedońska
Wykład 5. Liczby pierwsze
1 Podstawowe własności liczb pierwszych
Definicja 1. Liczbę naturalną n większą od 1 nazywamy liczbą pierwszą,
jeśli ma ona tylko dwa dzielniki naturalne 1 oraz n. Każdą liczbę naturalną n
większą od 1, która nie jest pierwsza, nazywamy liczbą złożoną. Zbiór liczb
pierwszych oznaczamy przez P.
Przykład 2, 5, 7 " P, 4 " P, bo 2|4.
/
Wniosek 1. Liczba n jest złożona wtedy i tylko wtedy, gdy istnieją liczby
całkowite a, b takie, że
n = ab przy czym 1 < a d" b < n.
Lemat 1. Każda liczba naturalna większa od 1 ma dzielnik pierwszy.
Dowód. Jeśli n jest liczbą pierwszą, to sama jest swoim dzielnikiem pierw-
szym. Załóżmy teraz, że n jest liczbą złożoną. Wtedy na podstawie definicji
n ma dzielnik naturalny m taki, że 1 < m < n. Niech teraz D oznacza zbiór
wszystkich naturalnych dzielników liczby n. Zbiór ten jest niepusty, ponie-
waż m " D. Wobec Zasady minimum (Wykład 2, Tw.1) istnieje w D element
najmniejszy, powiedzmy p. Pokażemy, że jest to szukany dzielnik pierwszy
liczby n. Z definicji zbioru D mamy p|n, a więc wystarczy pokazać, że p jest
liczbą pierwszą. Załóżmy nie wprost, że p " P. Ponieważ p jest liczbą natu-
/
ralną większą od 1, to p jest liczbą złożoną, więc z definicji istnieje dzielnik
d liczby p (d = p). Ponieważ p|n, to z Własności 6 (Wykład 2, Tw.1) d jest

również dzielnikiem liczby n, a zatem d " D. Z Własności 1, d < p, więc
mamy sprzeczność z minimalnością p. Zatem n ma dzielnik pierwszy p.
"
Lemat 2. Każda liczba złożona n ma dzielnik pierwszy p taki, że p d" n.
Dowód. Na podstawie Wniosku 1 istnieją liczby naturalne a, b takie, że
"
1 <" d" b < n oraz n = ab. Gdyby a byÅ‚o wiÄ™ksze" n, to także
a niż
b > n i wtedy n = ab > n, sprzeczność. Tak więc a d" n i na podstawie
Lematu 1, a ma dzielnik pierwszy p. Ponadto, z Własności 1 (Wykład 2,
"
Tw.1) p d" a d" n, a z Własności 6 (Wykład 2, Tw.1) p|n.
Uwaga 1 Z powyższego Lematu wynika elementarna metoda sprawdzania,
czy dana liczba n jest pierwsza: wystarczy sprawdzić, czy dzieli się przez
"
którąkolwiek liczbę pierwszą nie większą niż n.
Uwaga 2 Definicję liczby złożonej można rozszerzyć na liczby ujemne. Liczbą
złożoną nazywalibyśmy wówczas każdą liczbę całkowitą różną od -1, 0 oraz
1, która nie jest liczbą pierwszą ani liczbą przeciwną do pierwszej. Dla tak
zmodyfikowanej definicji Wniosek 1 oraz Lematy 1 i 2 po odpowiednim prze-
formułowaniu pozostają prawdziwe.
1
2 Nieskończoność zbioru liczb pierwszych
W czasach Euklidesa unikano pojęcia tzw. nieskończoności aktualnej, czyli
istnienia nieskończonego bytu1. Używano natomiast tzw. nieskończoności
potencjalnej, czyli nieustającej możliwości powiększania2. Dlatego też twier-
dzenie o nieskończoności zbioru liczb pierwszych zostało sformułowane przez
Euklidesa jak niżej.
Twierdzenie 1 (Euklides). Dla każdej liczby pierwszej istnieje liczba pierw-
sza większa od niej.
Dowód. Załóżmy nie wprost, że liczba pierwsza pn jest ostatnia, tzn. że
zbiór wszystkich liczb pierwszych ma postać P = {p1, p2, ..., pn} i rozpatrzmy
liczbÄ™ naturalnÄ… m = p1p2 · · · pn + 1. Na mocy Lematu 1 liczba m dzieli siÄ™
przez pewną liczbę pierwszą q ze zbioru P. Wobec tego liczba q dzieli też
iloczyn wszystkich liczb z P. Na podstawie Własności 8 (Wykład 2, Tw.1),
q|m - p1 · · · pn, czyli q|1, a stÄ…d q = 1, co daje sprzeczność z zaÅ‚ożeniem,
że q jest liczbą pierwszą. Wobec tego założenie, że istnieje ostatnia liczba
pierwsza nie jest prawdziwe, co kończy dowód.
Z Twierdzenia Euklidesa otrzymujemy natychmiast żądany
Wniosek 2. Zbiór liczb pierwszych jest nieskończony.
Lemat 3. Dla każdego n " N istnieje n kolejnych liczb złożonych.
Dowód. Jest to ciąg liczb (n + 1)!+2, (n + 1)!+3, ... (n + 1)!+(n + 1).
Lemat 4. Dla każdego naturalnego n takiego, że n e" 3, pomiędzy n i n!
istnieje liczba pierwsza.
Dowód. Najmniejszym n dla którego istnieje liczba pomiędzy n i n! jest
3. Teraz, jeśli n! - 1 jest liczbą pierwszą, to mamy tezę. Jeśli nie, to na
podstawie Lematu 1 ma ona dzielnik pierwszy p. Gdyby p d" n, to p byłoby
jednym z czynników w n!, czyli p|n!. Ponieważ także p|n! - 1, to z Własnoś-
ci 8 (Wykład 2, Tw.1) mielibyśmy p|n! - (n! - 1), czyli p|1, a więc p = 1, co
jest sprzeczne z założeniem, że p " P. Tak więc n < p < n!. Zatem liczba
pierwsza w danym przedziale zawsze istnieje.
Uwaga Z dowodu powyższego Lematu wynika ciekawa własność - mianowi-
cie, wszystkie dzielniki pierwsze liczby n!-1 są większe niż n. Oznacza to, że
wszystkie dzielniki naturalne (różne od 1) są większe niż n - bo gdyby istniał
jakiś dzielnik mniejszy lub równy n, to miałby on dzielnik pierwszy mniejszy
lub równy n, który byłby dzielnikiem liczby n! - 1, co przeczy własności tej
liczby. Zatem, jeśli n! - 1 jest liczbą złożoną oraz p jest jej dowolnym dziel-
nikiem pierwszym, to z Wniosku 1 istnieje naturalne k takie, że n! - 1 = pk,
1
Badaniem nieskończoności jako samodzielnego bytu zajął się dopiero Cantor (XIX w)
2
Na tym rozumieniu nieskończoności oparta jest cała analiza matematyczna, jak rów-
nież teoria liczb
2
(n-1)!n-1
n!-1
przy czym n < k d" p < n! - 1, a więc p = < < (n - 1)!.
k n
Ostatecznie mamy, że jeśli p jest dzielnikiem pierwszym liczby n! - 1, to
n < p < (n - 1)!.
Z każdego z poniższych 2 twierdzeń (które przytaczamy bez dowodów)
także wynika nieskończoność zbioru P.
Twierdzenie 2 (Dirichlet3). Niech a, b " N. Jeśli NW D(a, b) = 1 to ciąg
arytmetyczny (a + nb)n"N zawiera nieskończenie wiele liczb pierwszych.
Twierdzenie 3 (Czebyszew4). Dla każdej liczby naturalnej n większej niż 1
pomiędzy n i 2n istnieje co najmniej jedna liczba pierwsza.
2.1 Sito Eratostenesa
Eratostenes5 wymyślił elementarną metodę znajdowania wszystkich liczb pierw-
szych mniejszych od danej liczby naturalnej n, zwanÄ… sitem Eratostenesa.
Procedura wygląda następująco:
(1) Wypisujemy wszystkie liczby naturalne od 2 do n - 1.
(2) Najmniejszą nieskreśloną liczbą jest 2 i jest to liczba pierwsza. Wobec
tego z ciągu wykreślamy co drugą liczbę (liczenie rozpoczynamy od 3). W ten
sposób wyeliminujemy wszystkie liczby podzielne 2.
(3) Najmniejszą nieskreśloną liczbą jest teraz 3 i jest to kolejna liczba
pierwsza. Wobec tego z ciągu wykreślamy co trzecią liczbę (liczenie rozpo-
czynamy od 4). Niektóre liczby zostaną wykreślone dwa razy (np 6). W ten
sposób wyeliminujemy liczby podzielne przez 3. Oznacza to, ze wyelimino-
waliśmy wszystkie liczby podzielne przez 2 lub 3.
(4) Powtarzamy proces dla kolejnych nieskreślonych liczb. Algorytm się
"
kończy wtedy, gdy najmniejsza nieskreślona liczba jest większa niż n - 1.
Liczby, które pozostaną nieskreślone to wszystkie możliwe liczby pierwsze
mniejsze niż n, co wynika z metody wykreślania oraz Lematu 2.
Uwaga Sito jest metodą pracochłonną, przez co nieefektywną, ale skuteczną
dla małych liczb. Szukaniem dużych liczb pierwszych w postaci Mersenne a
zajmuje się od 1996 roku zespół ochotników w ramach projektu GIMPS6
(Great Internet Mersenne Prime Search). Największa znana obecnie liczba
pierwsza to 243112609-1, ma prawie 13 milionów cyfr. Została znaleziona przez
zespół GIMPS w sierpniu 2008 roku i jest to najprawdopodobniej czterdziesta
szósta liczba Mersenne a, czyli liczba pierwsza postaci 2p - 1.
3
Peter Gustav Lejeune Dirichlet 1805-1859
4
Pafnutij Lwowicz Czebyszew 1821-1894
5
Eratostenes 276-194 p.n.e.
6
Strona www projektu: http://www.mersenne.org/
3