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 ≤ 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 6= 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 ≤

√

n.

Dowód. Na podstawie Wniosku 1 istnieją liczby naturalne a, b takie, że
1 < a ≤ b < n oraz n = ab. Gdyby a było większe niż

√

n, to także

b >

√

n i wtedy n = ab > n, sprzeczność. Tak więc a ≤

√

n i na podstawie

Lematu 1, a ma dzielnik pierwszy p. Ponadto, z Własności 1 (Wykład 2,
Tw.1) p ≤ a ≤

√

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 bytu

1

. Używano natomiast tzw. nieskończoności

potencjalnej, czyli nieustającej możliwości powiększania

2

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

n

jest ostatnia, tzn. że

zbiór wszystkich liczb pierwszych ma postać P = {p

1

, p

2

, ..., p

n

} i rozpatrzmy

liczbę naturalną m = p

1

p

2

· · · p

n

+ 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 − p

1

· · · p

n

, 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 ≥ 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 ≤ 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

przy czym n < k ≤ p < n! − 1, a więc p =

n!−1

k

<

(n−1)!n−1

n

< (n − 1)!.

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 (Dirichlet

3

). 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 (Czebyszew

4

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

Eratostenes

5

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 GIMPS

6

(Great Internet Mersenne Prime Search). Największa znana obecnie liczba
pierwsza to 2

43112609

−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 2

p

− 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