12
2. Prvočísla
Prvočíslo je jeden z nejdůležitějších pojmů elementární teorie čísel.
Jeho důležitost je dána především větou o jednoznačném rozkladu libovolného
přirozeného čísla na součin prvočísel, která je silným a účinným
nástrojem při řešení celé řady úloh z teorie čísel.
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.
V dalším textu budeme zpravidla prvočíslo značit písmenem p.
Nejmenší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, . . . .
Prvočísel je, jak brzy dokážeme, nekonečně mnoho, máme ovšem poměrně
limitované výpočetní prostředky na zjištění, zda je dané číslo
prvočíslem (největší známé prvočíslo 230 402 457
− 1 má pouze 9 152 052
cifer).
Věta 6. Přirozené číslo p ≥ 2 je prvočíslo, právě když platí: pro
každá celá čísla a, b z p | ab plyne p | a nebo p | b.
Důkaz. „⇒ Předpokládejme, že p je prvočíslo a p | ab, kde a, b ∈
Z. Protože (p, a) je kladný dělitel p, platí (p, a) = p nebo (p, a) = 1.
V prvním případě p | a, ve druhém p | b podle věty 5.
„⇐ Jestliže p není prvočíslo, musí existovat jeho kladný dělitel
různý od 1 a p. Označíme jej a; pak ovšem b = p
a
∈ N a platí p = ab,
odkud 1 < a < p, 1 < b < p. Našli jsme tedy celá čísla a, b tak, že p | ab
a přitom p nedělí ani a, ani b.
Příklad. Nalezněte všechna čísla k ∈ N0, pro která je mezi deseti
po sobě jdoucími čísly k + 1, k + 2, . . . , k + 10 nejvíce prvočísel.
Řešení. Pro k = 1 je mezi našimi čísly pět prvočísel: 2, 3, 5, 7,
11. Pro k = 0 a k = 2 pouze čtyři prvočísla. Jestliže k ≥ 3, není mezi
zkoumanými čísly číslo 3. Mezi deseti po sobě jdoucími celými čísly pět
sudých a pět lichých čísel, mezi kterými je zase aspoň jedno dělitelné
třemi. Našli jsme tedy mezi čísly k + 1, k + 2, . . . , k + 10 aspoň šest
složených, jsou tedy mezi nimi nejvýše čtyři prvočísla. Zadání proto
vyhovuje jediné číslo k = 1.
Příklad. Dokažte, že pro libovolné přirozené číslo n existuje n po
sobě jdoucích přirozených čísel, z nichž žádné není prvočíslo.
Řešení. Zkoumejme čísla (n + 1)! + 2, (n + 1)! + 3, . . . , (n + 1)! +
(n + 1). Mezi těmito n po sobě jdoucími čísly není žádné prvočíslo,
protože pro libovolné k ∈ {2, 3, . . ., n + 1} platí k | (n + 1)!, a tedy
k | (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo.
Příklad. Dokažte, že pro libovolné prvočíslo p a libovolné k ∈ N,
k < p, je kombinační číslo p
k
dělitelné p.
13
Řešení. Podle definice kombinačního čísla
p
k
=
p!
k!(p − k)!
=
p · (p − 1) · · · · · (p − k + 1)
1 · 2 · · · · · k
∈ N,
a tedy k! | p · a, kde jsme označili a = (p − 1) · · · · · (p − k + 1). Protože
k < p, není žádné z čísel 1, 2, . . ., k dělitelné prvočíslem p, a tedy podle
věty 6 není ani k! dělitelné prvočíslem p, odkud (k!, p) = 1. Podle věty
5 platí k! | a, a tedy b = a
k!
je celé číslo. Protože p
k
= pa
k!
= pb, je číslo
p
k
dělitelné číslem p.
Věta 7. Libovolné přirozené číslo n ≥ 2 je možné vyjádřit jako
součin prvočísel, přičemž je toto vyjádření jediné, nebereme-li v úvahu
pořadí činitelů. (Je-li n prvočíslo, pak jde o „součin jednoho prvo-
čísla.)
Poznámka. Dělitelnost je možné obdobným způsobem jako v 1.1
definovat v libovolném oboru integrity (zkuste si rozmyslet, proč se
omezujeme na obory integrity). V některých oborech integrity přitom
žádné prvky s vlastností prvočísla (říkáme jim ireducibilní) neexistují
(např. Q), v jiných sice ireducibilní prvky existují, ale zase tam neplatí
věta o jednoznačném rozkladu (např. v Z(
√
−5) máme následující rozklady:
6 = 2·3 = (1+
√
−5)·(1−
√
−5); zkuste si rozmyslet, že všichni
uvedení činitelé jsou skutečně v Z(
√
−5) ireducibilní).
Důkaz. Nejprve dokážeme indukcí, že každé n ≥ 2 je možné vyjádřit
jako součin prvočísel.
Je-li n = 2, je n součin jediného prvočísla 2.
Předpokládejme nyní, že n > 2 a že jsme již dokázali, že libovolné n′
,
2 ≤ n′
< n, je možné rozložit na součin prvočísel. Jestliže n je prvočíslo,
je součinem jediného prvočísla. Jestliže n prvočíslo není, pak existuje
jeho dělitel d, 1 < d < n. Označíme-li c = n
d
, platí také 1 < c < n.
Z indukčního předpokladu plyne, že c i d je možné vyjádřit jako součin
prvočísel, a proto je takto možné vyjádřit i jejich součin c · d = n.
Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost
součinů p1 · p2 · · · · · pm = q1 · q2 · · · · · qs, kde p1, . . . , pm, q1, . . . , qs
jsou prvočísla a navíc platí p1 ≤ p2 ≤ · · · ≤ pm, q1 ≤ q2 ≤ · · · ≤ qs
a 1 ≤ m ≤ s. Indukcí vzhledem k m dokážeme, že m = s, p1 =
q1, . . ., pm = qm.
Je-li m = 1, je p1 = q1 ·· · ··qs prvočíslo. Kdyby s > 1, mělo by číslo
p1 dělitele q1 takového, že 1 < q1 < p1 (neboť q2q3 . . . qs > 1), což není
možné. Je tedy s = 1 a platí p1 = q1.
Předpokládejme, že m ≥ 2 a že tvrzení platí pro m − 1. Protože
p1 ·p2·· · ··pm = q1 ·q2·· · ··qs, dělí pm součin q1 ·· · ··qs, což je podle věty 6
možné jen tehdy, jestliže pm dělí nějaké qi pro vhodné i ∈ {1, 2, . . ., s}.
Protože qi je prvočíslo, plyne odtud pm = qi (neboť pm > 1). Zcela
analogicky se dokáže, že qs = pj pro vhodné j ∈ {1, 2, . . ., m}. Odtud
14
plyne
qs = pj ≤ pm = qi ≤ qs,
takže pm = qs. Vydělením dostaneme p1 ·p2 ·· · ··pm−1 = q1 ·q2 ·· · ··qs−1,
a tedy z indukčního předpokladu m − 1 = s − 1, p1 = q1, . . . , pm−1 =
qm−1. Celkem tedy m = s a p1 = q1, . . . , pm−1 = qm−1, pm = qm.
Jednoznačnost, a proto i celá věta 7 je dokázána.
Poznámka. Již jsme se zmínili, že je složité o velkých číslech
s jistotou rozhodnout, jde-li o prvočíslo (na druhou stranu je o naprosté
většině složených čísel snadné prokázat, že jsou skutečně složená).
Přesto se v roce 2002 podařilo indickým matematikům (Agrawal,
Saxena, Kayal: http://www.cse.iitk.ac.in/users/manindra/
primality_v6.pdf) dokázat, že problém prvočíselnosti je možné rozhodnout
algoritmem s časovou složitostí polynomiálně závislou na počtu
cifer vstupního čísla. Nic podobného se zatím nepodařilo v otázce
rozkladu čísla na prvočísla (třebaže se obecně nevěří, že je to možné,
exaktní důkaz zatím nebyl podán).
Že je problém rozkladu přirozeného čísla na prvočísla výpočetně
složitý, o tom svědčí i výzva učiněná firmou RSA Security (viz http://
www.rsasecurity.com/rsalabs/node.asp?id=2093). Pokud se vám
podaří rozložit čísla označená podle počtu cifer jako RSA-704, RSA-
768, . . . , RSA-2048, obdržíte 30 000, 50 000, . . . , resp. 200 000 dolarů
(čísla RSA-576 a RSA-640 již byla rozložena v roce 2003, resp. 2005;
byla-li vyplacena slíbená odměna, mi není známo).
Důsledek. (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 .
Poznámka. S pojmem součet všech kladných dělitelů čísla a souvisí
pojem tzv. dokonalého čísla a, které splňuje podmínku σ(a) = 2a,
resp. slovně: „součet všech kladných dělitelů čísla a menších než a samotné
je roven číslu a .
15
Takovými čísly jsou např. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14,
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 a 8128 (jde o všechna
dokonalá čísla menší než 10 000).
Lze ukázat, že sudá dokonalá čísla jsou v úzkém vztahu s tzv. Mersenneho
prvočísly. Platí totiž: a je sudé dokonalé číslo, právě když je
tvaru a = 2q−1
· (2q
− 1), kde 2q
− 1 je prvočíslo. Mersenneho prvočísla
jsou právě prvočísla tvaru 2k
− 1. Bez zajímavosti není ani to,
že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe „vidět
– obecně je pro velká čísla, u kterých se nedaří nalézt netriviálního
dělitele, obtížné prokázat, že jsou prvočísla. Pro Mersenneho
prvočísla existuje poměrně jednoduchý a rychlý postup. Proto není náhodou,
že největší známá prvočísla jsou obvykle tvaru 2k
−1 (viz např.
http://www.utm.edu/research/primes/largest.html).
Na druhou stranu popsat lichá dokonalá čísla se dodnes nepodařilo,
resp. dodnes se neví, jestli vůbec nějaké liché dokonalé číslo
existuje
Příklad. Dokažte, že pro každé celé n > 2 existuje mezi čísly n a
n! alespoň jedno prvočíslo.
Řešení. Označme p libovolné prvočíslo dělící číslo n! − 1 (takové
existuje podle věty 7, protože n! − 1 > 1). Kdyby p ≤ n, muselo by p
dělit číslo n! a nedělilo by n! − 1. Je tedy n < p. Protože p | (n! − 1),
platí p ≤ n! − 1, tedy p < n!. Prvočíslo p splňuje podmínky úlohy.
Nyní uvedeme několik důkazů toho, že existuje nekonečně mnoho
prvočísel (i když tvrzení v podstatě vyplývá už z předchozího příkladu).
Věta 8. Mezi přirozenými čísly existuje nekonečně mnoho prvočí-
sel.
Důkaz. (Eukleides) Předpokládejme, že prvočísel je konečně mnoho
a označme je p1, p2, . . . , pn. Položme N = p1 · p2 . . . pn + 1. Toto číslo je
buď samo prvočíslem nebo je dělitelné nějakým prvočíslem různým od
p1, . . . , pn (čísla p1, . . . , pn totiž dělí číslo N − 1), což je spor.
(Kummer, 1878): Předpokládejme, že prvočísel je konečně mnoho
a označme je p1 < p2 < · · · < pn. Položme N = p1 · p2 · · · pn > 2.
Číslo N −1 je podle věty 7 dělitelné některým prvočíslem pi, které dělí
zároveň číslo N a tedy i N − (N − 1) = 1. Spor.
(Fürstenberg, 1955):
V této poznámce uvedeme elementární „topologický důkaz
existence nekonečně mnoha prvočísel. Zavedeme topologii
prostoru celých čísel pomocí báze tvořené aritmetickými
posloupnostmi (od −∞ do +∞). Lze snadno
ověřit, že jde skutečně o topologický prostor, navíc lze
ukázat, že je normální a tedy metrizovatelný. Každá aritmetická
posloupnost je uzavřená i otevřená množina (její
16
komplement je sjednocení ostatních aritmetických posloupností
se stejnou diferencí). Dostáváme, že sjednocení konečného
počtu aritmetických posloupností je uzavřená množina.
Uvažme množinu A = ∪Ap, kde Ap je tvořena všemi
násobky p a p probíhá všechna prvočísla. Jediná celá čísla
nepatřící do A jsou −1 a 1 a protože množina {−1, 1}
zřejmě není otevřená, množina A nemůže být uzavřená.
A tedy není konečným sjednocením uzavřených množin,
což znamená, že musí existovat nekonečně mnoho prvo-
čísel.
Příklad. Dokažte, že existuje nekonečně mnoho prvočísel tvaru
3k + 2, kde k ∈ N0.
Řešení. Předpokládejme naopak, že existuje pouze konečně mnoho
prvočísel tohoto tvaru a označme je p1 = 2, p2 = 5, p3 = 11, . . . , pn.
Položme N = 3p2 · p3 · · · · · pn + 2. Rozložíme-li N na součin prvočísel
podle věty 7, musí v tomto rozkladu vystupovat aspoň jedno prvočíslo
p tvaru 3k +2, neboť v opačném případě by bylo N součinem prvočísel
tvaru 3k + 1 (uvažte, že N není dělitelné třemi), a tedy podle příkladu
na str. 7 by bylo i N tvaru 3k+1, což neplatí. Prvočíslo p ovšem nemůže
být žádné z prvočísel p1, p2, . . . , pn, jak plyne z tvaru čísla N, a to je
spor.
Předchozí příklady je možné značně zobecnit. Platí totiž tvrzení,
které bývá nazýváno Bertrandovým postulátem nebo Čebyševovou vě-
tou:
Věta 9. (Čebyševova)
(1) 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.
Důkaz. Důkaz lze provést elementárními prostředky, je však poměrně
dlouhý, proto zde není uveden. Viz např. http://matholymp.
com/TUTORIALS/Bertrand.pdf
Z tvrzení uvedených v této kapitole je možné si udělat hrubou představu
o tom, jak „hustě se mezi přirozenými čísla prvočísla vyskytují.
Přesněji (i když „pouze asymptoticky) to popisuje tzv. „prime number
theorem :
Věta 10. (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
,
17
tj. podíl funkcí π(x) a x/ ln x se pro x → ∞ limitně blíží k nule.
Poznámka. To, jak jsou prvočísla hustě rozmístěna v množině přirozených
čísel, rovněž udává Eulerův výsledek
p prvočíslo
1
p
= ∞.
Přitom např.
n∈N
1
n2
=
π2
6
,
což znamená, že prvočísla jsou v N rozmístěna „hustěji než druhé
mozniny.
Použití v Pari-GP. O tom, jak odpovídá asymptotický odhad
π(x) ∼ x/ ln(x), v některých konkrétních příkladech vypovídá následující
tabulka (získáná s využitím funkce primepi(x) v Pari-GP.
? v=[100,1000,10000,100000,500000];
? for(k=1,5,print(v[k],„& ,primepi(v[k]),„& ,\
v[k]/log(v[k]),„& ,\
(primepi(v[k])-v[k]/log(v[k]))/primepi(v[k])))
x π(x) x/ ln(x) relativní chyba
100 25 21.71 0.13
1000 168 144.76 0.13
10000 1229 1085.73 0.11
100000 9592 8685.88 0.09
500000 41538 38102.89 0.08
Poslední příklad (o nekonečnosti počtu prvočísel tvaru 3k + 2) zobecňuje
Dirichletova věta o aritmetické posloupnosti:
Věta 11. (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.
Důkaz. Jde o hlubokou větu teorie čísel, k jejímuž důkazu je zapotřebí
aparát značně přesahující její elementární část. Viz např. [2,
kap. ???]
Označení. Pro libovolné prvočíslo p a libovolné přirozené číslo n
je podle věty 7 jednoznačně určen exponent, se kterým vystupuje p
v rozkladu čísla n na prvočinitele (pokud p nedělí číslo n, považujeme
tento exponent za nulový). Budeme jej označovat symbolem vp(n). Pro
záporné celé číslo n klademe vp(n) = vp(−n).
18
Podle důsledku 2 můžeme právě zavedené označení vp(n) charakterizovat
tím, že pvp(n)
je nejvyšší mocninou prvočísla p, která dělí číslo
n, nebo tím, že n = pvp(n)
· m, kde m je celé číslo, které není dělitelné
číslem p. Odtud snadno plyne, že pro libovolná nenulová celá čísla a, b
platí
vp(ab) = vp(a) + vp(b) (8)
vp(a) ≤ vp(b) ∧ a + b = 0 =⇒ vp(a + b) ≥ vp(a) (9)
vp(a) < vp(b) =⇒ vp(a + b) = vp(a) (10)
vp(a) ≤ vp(b) =⇒ vp((a, b)) = vp(a) ∧ vp([a, b]) = vp(b) (11)
Na následujícím příkladu demonstrujme užitečnost zavedeného ozna-
čení.
Příklad. Dokažte, že pro libovolná přirozená čísla a, b, c platí
([a, b], [a, c], [b, c]) = [(a, b), (a, c), (b, c)]
Řešení. Podle věty 7 budeme hotovi, ukážeme-li, že vp(L) = vp(P)
pro libovolné prvočíslo p, kde L, resp. P značí výraz na levé, resp.
pravé straně. Nechť je tedy p libovolné prvočíslo. Vzhledem k symetrii
obou výrazů můžeme bez újmy na obecnosti předpokládat, že vp(a) ≤
vp(b) ≤ vp(c). Podle (11) platí vp([a, b]) = vp(b), vp([a, c]) = vp([b, c]) =
vp(c); vp((a, b)) = vp((a, c)) = vp(a), vp((b, c)) = vp(b), odkud vp(L) =
vp(b) = vp(P), což jsme měli dokázat.