Prvočísla
Prvočíslo je velmi důležitým pojmem v aritmetice, zvláště proto, že každé celé číslo lze
jednoznačně zapsat jako součin prvočísel. Existuje také hodně problémů, týkajících se prvočísel,
které je jednoduché vyslovit, ale obtížné vyřešit.
Definice. Každé přirozené číslo n  2 má aspoň dva kladné dělitele: 1 a n. Pokud kromě
těchto dvou jiné kladné dělitele nemá, nazývá se prvočíslo. V opačném případě hovoříme
o složeném čísle.
Pro nalezení všech prvočísel nepřevyšující dané číslo n existuje jednoduchá metoda
zvaná Eratosthenovo síto (viz např. [??], kapitola 1.5).
Věta. Přirozené číslo p  2 je prvočíslo, právě když platí: pro všechna celá čísla a, b z p|ab
plyne p|a nebo p|b.
Věta (Základní věta aritmetiky). Každé přirozené číslo je možné vyjádřit jako součin
prvočísel. Toto vyjádření je jednoznačné, nebereme-li v úvahu pařadí činitelů.
Prázdný součin je roven číslu jedna (1 = p0
i , i  N), každé prvočíslo je pak součin
jednoho prvočísla. Pomocí rozkladu na součin prvočísel lze určit i údaje týkající se dělitelů
daného čísla.
Věta. 1. Jsou-li p1, . . . , pk navzájem různá prvočísla a n1, . . ., nk  N0, je každý kladný
dělitel čísla a = pn1
1      pnk
k tvaru pm1
1      pmk
k , kde m1, . . ., mk  N0 a m1  n1,
m2  n2, . . . , mk  nk.
Číslo a má tedy právě
(a) = (n1 + 1)(n2 + 1)      (nk + 1)
kladných dělitelů, jejichž součet je
(a) =
pn1+1
1 - 1
p1 - 1
. . .
pnk+1
k - 1
pk - 1
.
2. Jsou-li p1, . . . , pk navzájem různá prvočísla a n1, . . . , nk, m1, . . . , mk  N0 a
označíme-li ri = min{ni, mi}, ti = max{ni, mi} pro každé i = 1, 2, . . ., k, platí
(pn1
1      pnk
k , pm1
1      pmk
k ) = pr1
1      prk
k ,
[pn1
1      pnk
k , pm1
1      pmk
k ] = pt1
1      ptk
k .
1
Věta. Mezi přirozenými čísly existuje nekonečně mnoho prvočísel.
O rozmístění prvočísel existuje mnoho tvrzení, zde však budeme používat pouze následující
tři.
Věta. (Čebyševova)
1. Pro libovolné přirozené číslo n > 5 existují mezi čísly n a 2n alespoň dvě prvočísla.
2. Pro každé číslo n > 3 existuje mezi čísly n a 2n - 2 alespoň jedno prvočíslo.
Věta. (Dirichletova) Jsou-li a, m nesoudělná přirozená čísla, existuje nekonečně mnoho
přirozených čísel k tak, že mk + a je prvočíslo. Jinými slovy, mezi čísly 1  m + a, 2  m +
a, 3  m + a, . . . existuje nekonečně mnoho prvočísel.
Třetí tvrzení lze využít i při odhadu počtu prvočísel, nepřevyšující zadané číslo x.
Věta. (o hustotě prvočísel) Nechť (x) udává počet prvočísel menších nebo rovných číslu
x  R. Pak
(x) 
x
ln x
,
tj. podíl funkcí (x) a x/ ln x se pro x   limitně blíží k nule.
2