11
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: lan. 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. Nej menší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (zejména číslo 1 za prvočíslo ani za číslo složené nepovažujeme, je totiž inver-tibilní, neboli jednotkou okruhu celých čísel). 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; číslo 282589933 —
I, které bylo v roce 2018 největším známým prvočíslem, má pouze 24 862 048 cifer a jeho dekadické vyjádření by se tak vešlo na kdejaký prehistorický datový nosič, při tisku knihy o 60 řádcích na stránku a 80 znacích na řádek by nicméně i tak zabralo 5 180 stran.
Uveďme nyní větu, která udává ekvivalentní podmínku prvočíselnosti a je základní ingrediencí při důkazu jednoznačnosti rozkladu na prvočísla.
VĚTA 6 (Euklidova o prvočíslech). 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 g 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 = - g N a platí p = ab, odkud l<a<p, l<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 g No, 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,
II. 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é prvočíslo p a libovolné k g N, k < p, je kombinační číslo (^) dělitelné p.  
12
řešení. Podle definice kombinačního čísla
ÍP\ =      p!      = p-jp-l).....(p-k + 1)
\kj    k\(p-k)\ 1-2.....k
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, & tedy b = |j je celé číslo. Protože (f) = ff = pb, je číslo (^) dělitelné číslem p. □
věta 7. Libovolné přirozené číslo n je možné vyjádřit jako součin prvočísel, přičemž je toto vyjádřeni jediné, nebereme-li v úvahu pořadí činitelů. (Je-li n prvočíslo, pak jde o „součin" jednoho prvočísla, n = 1 je součinem prázdné množiny1 prvočísel)
poznámka. Dělitelnost je možné obdobným způsobem jako v 1.2 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 + y/—5) • (1 — yj—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 = ^, 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ů pi • p2.....pm = 9i-929s, kde pi,... ,pm, q1,...,qs
jsou prvočísla a navíc platí p\ < p2 < • • • < pm, q± < q2 < • • • < qs a 1 < m < s. Indukcí vzhledem k m dokážeme, že m = s, pi =
Ql i ■ ■ ■ i Pm      Qm ■
Je-li m = 1, je p! = q±.....qs prvočíslo. Kdyby s > 1, mělo by číslo
Pi dělitele q± takového, že 1 < q± < p\ (neboť q2qz ... qs > 1), což není možné. Je tedy s = 1 a platí p± = q±.
Předpokládejme, že m > 2 a že tvrzení platí pro m — 1. Protože
Pi-P2Pm = qi-q2qs, dělípm součin qľ.....qs, což je podle věty 6
možné jen tehdy, jestliže pm dělí nějaké g« pro vhodné i G {1,2,..., s}. Protože qi je prvočíslo, plyne odtud pm = qi (neboť pm > 1). Zcela
1V řeči teorie okruhů jde o jedničku okruhu celých čísel, která je dle obvyklé konvence součinem prázdné množiny prvků okruhu.
13
analogicky se dokáže, že qs = pj pro vhodné j g {1,2,..., m}. Odtud plyne
qs =Pj <Pm = Qí< qa,
takže pm = qs. Vydělením dostaneme p\ -p2.....pm-i = Qi'Q2Qs-i,
a tedy z indukčního předpokladu m — 1 = s — 1, p\ = q1}... ,pm-i = gm_i. Celkem tedy m = s a px = q1,...,pm_1 = qm_x, 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, Ka-yal: http: //www. cse. iitk. ac. in/users/manindra/algebra/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). Nejrychlejší obecně použitelný faktorizační
algoritmus, tzv. síto v číselném tělese, je sub-exponenciální časové složitosti q ^el.9(logAr)1/3(iogiogAr)2/3^
Peter Shor v roce 1994 vymyslel algoritmus, který číslo n faktorizuje v kubickém čase (tento algoritmus je tedy časové složitosti O (log3 iV)) na kvantovém počítači. Je k tomu nicméně třeba sestrojit počítače s dostatečným počtem kvantových bitů (tzv. qubits) - jak je to obtížné, lze vysledovat z toho, ze v roce 2001 se IBM podařilo pomocí kvantového počítače rozložit číslo 15, v roce 2012 byl dosažen další faktorizační rekord rozkladem čísla 21, následovali čínští fyzikové (s využitím jistého triku jim stačil NMR kvantový počítač s pouhými čtyřmi qubity k rozkladu čísla 143) a v závěru roku 2014 bylo ukázáno, že tentýž počítač je schopný rozložit i číslo 56153 (viz https://en. wikipedia.org/wiki/Timeline_of_quantum_computing).
Ze je problém rozkladu přirozeného čísla na prvočísla výpočetně složitý, o tom svědčí i (již neplatná) výzva učiněná v roce 1991 firmou RSA Security (viz http: //www. rsasecurity. com/rsalabs/node. asp? id=2093). Pokud se komukoliv podařilo rozložit čísla označená podle počtu cifer jako RSA-100, ..., RSA-704, RSA-768, ..., RSA-2048, mohl obdržet 1 000,..., 30 000, 50 000, ..., resp. 200 000 dolarů (číslo RSA-100 rozložil v temže roce Arjen Lenstra, číslo RSA-704 bylo rozloženo v roce 2012, některá další ale dosud rozložena nebyla).
Díky jednoznačnosti rozkladu na prvočísla jsme schopni (se znalostí tohoto rozkladu) snadno odpovědět i na otázky ohledně počtu či součtu dělitelů konkrétního čísla. Stejně snadno dostaneme i (z dřívějška intuitivně známý) postup na výpočet největšího společného dělitele dvou čísel ze znalosti jejich rozkladu na prvočísla.
14
DŮSLEDEK.        (1) Jsou-li pi,... ,pk navzájem různá prvočísla a
ni,... ,nk G N0; je kažáý klaáný áělitel čísla a = p"1.....p^h
tvaru p"11.....Pkk j káe nii,..., mk G No a ni\ < n\, ni2 < ri2,
nik < nk. Číslo a má teáy právč
r (a) = (ni + l)(n2 + l).....(nk + 1)
klaáných áčlitelů, jejichž součet je
m+i _ i nk+l _ ,
*(a) = *---±.
Pi ~ 1 Pk ~ 1
(2) Jsou-li pi,... ,Pk navzájem různá prvočísla a n\, . . ., nk,
. . ., nik G No a označíme-liľi = min{ni,nii}, ti = max{rij,mj} pro kažáé i = 1,2,..., k, platí
{pT.....Pk\pT.....pľk)=p?.....Plh,
[pT.....pT,pi11.....Pľk]=Pi.....Pu-
2.1. Dokonalá čísla a jejich vztah k prvočíslům. Se součtem všech kladných dělitelů daného čísla souvisí pojem tzv. áokonalého čísla. Řekneme, že a je dokonalé, pokud splňuje podmínku a(a) = 2a, resp. slovně, pokud součet všech klaáných áčlitelů čísla a menších než a samotné je roven číslu a.
Takovými čísly jsou např. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7+14, 496 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. Mer-senneho prvočísly. Platí totiž následující fakt.
TVRZENÍ 2.1. Přirozené číslo a je suáé áokonalé číslo, pravé káyž je tvaru a = 29~1(29 — 1), káe 2q — 1 je prvočíslo.
DŮKAZ. Je-li a = 2q~1(2q - 1), kde p = 2q - 1 je prvočíslo, pak z předchozího tvrzení plyne
2q - 1
= —- ■ (p + 1) = (2q -l)-2q = 2a.
Takové číslo a je tedy dokonalé.
Pro důkaz opačného směru uvažme libovolné sudé dokonalé číslo a a pišme
a = 2k ■ m, kde m, k G N a 2 f m.
Protože je funkce a multiplikativní (viz 3.2), je a(a) = cr{2k) • a{m) = (2k+1 — 1) • a(m). Přitom ale z dokonalosti čísla a plyne a(a) = 2a = 2k+1 ■ m, odkud
2k+1 -ni = (2k+1 - 1) -a(m).
Protože je 2k+1 — 1 liché, nutně 2k+1 — 1 | ni a můžeme položit ni = (2k+1 — 1) • n pro vhodné n G N. Úpravou dostáváme 2k+1 ■
15
n = a (m). Mezi dělitele čísla m přitom patří čísla m i n (a protože »22 _ 2k+1 — 1 > 1? jsou tato čísla nutně různá), proto
2k+1 ■ n = a (m) >m + n = 2k+1 ■ n,
a tedy o~(m) = m + n. To znamená, že m je prvočíslo s jedinými děliteli m a n = 1, odkud a = 2k ■ (2k+1 — 1), kde 2k+1 — 1 = m je prvočíslo. □
poznámka. Na druhou stranu, popsat lichá dokonalá čísla se dodnes nepodařilo, dokonce se ani neví, jestli vůbec nějaké liché dokonalé číslo existuje.
Mersenneho prvočísla jsou právě prvočísla tvaru 2k — 1. Není bez zajímavosti, že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe „vidět" - pro Mersenneho čísla existuje poměrně jednoduchý a rychlý postup, jak ověřit, že jde o prvočísla. Proto není náhodou, že největší známá prvočísla jsou obvykle tvaru 2k — 1.
Jakkoliv může být hledání největšího známého prvočísla chápáno jako pochybná zábava bez valného praktického užitku2, jednak posunuje hranice matematického poznání a zdokonaluje použité metody (a často i hardware), navíc může přinést benefit i samotným objevitelům (Electronic Frontier Foundation vypsala odměny EFF Cooperative Computing Awards za nalezení prvočísla majícího alespoň 106,107,108 a 109 číslic - odměny 50, resp. 100 tisíc dolarů za první dvě kategorie byly vyplaceny v letech 2000, resp. 2009 - v obou případech projektu GIMPS - na další odměny si ještě zřejmě nějaký čas počkáme).
2.2. Rozložení prvočísel.
There are two facts about the distribution of prime numbers. The first is that, [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision.
Don Zagier
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 g {2,3,... ,n + 1} platí k | (n + 1)!, a tedy k I (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. □
2Viz např. titulek iDnes z 6.února 2013: Největší známé prvočíslo na světě má 17 milionů číslic a je k ničemu