Prvočísel je nekonečně mnoho. Ať sepíšete jakkoli dlouhý seznam prvočísel, vždycky existuje další, které v něm chybí. Dokázal to už řecký matematik Eukleidés kolem roku 300 př. n. l. a jeho důkaz se vejde do čtyř řádků. A k čemu jsou prvočísla dobrá? Chrání vaši platební kartu a spojení s bankou, protože vynásobit dvě velká prvočísla je snadné, ale rozložit výsledek zpátky je i pro počítače skoro nemožné. A v přírodě je „používají“ americké cikády, které se z podzemí vynořují jednou za 13, nebo za 17 let.

Co prvočíslo je, jak ho poznat a tabulku prvočísel do 1000 najdete v článku Prvočíslo, jestli je konkrétní číslo prvočíslo, ověří kalkulačka Je číslo prvočíslo? Tady je to, na co se žáci ptají potom: proč prvočísla nikdy nedojdou, jak daleko od sebe mohou být, co jsou prvočíselná dvojčata, proč cikády čekají právě 13 a 17 let a jak na prvočíslech stojí šifra v platební kartě. Stačí k tomu násobení, dělení se zbytkem a nejmenší společný násobek, tedy učivo 6. a 7. třídy. Na konci jsou časté omyly a šest příkladů s řešením.

Proč je prvočísel nekonečně mnoho: Eukleidův důkaz

Eukleidův důkaz je ve čtyřech krocích:

  1. Vezmeme jakýkoli konečný seznam prvočísel.
  2. Všechna je vynásobíme a k součinu přičteme 1. Vznikne nové číslo `N`.
  3. Žádné prvočíslo ze seznamu `N` nedělí: při dělení kterýmkoli z nich vyjde zbytek 1.
  4. `N` je ale větší než 1, takže je buď samo prvočíslo, nebo ho dělí nějaké menší prvočíslo. To prvočíslo v seznamu není. Seznam tedy nebyl úplný.

Protože to platí pro každý seznam, žádný seznam všech prvočísel neexistuje a prvočísel je nekonečně mnoho. Dá se to říct i jako důkaz sporem: předpokládáme opak (prvočísel je jen konečně mnoho a dají se sepsat) a ukážeme, že vede k nesmyslu.

Příklad: seznam 2, 3, 5, 7

Kdyby prvočísla byla jen 2, 3, 5 a 7, vezmeme

`N=2\cdot 3\cdot 5\cdot 7+1=211`

Zkouška dělením: `211=2\cdot 105+1`, `211=3\cdot 70+1`, `211=5\cdot 42+1`, `211=7\cdot 30+1`. Pokaždé zbude 1, protože 210 je násobkem každého z těch čtyř čísel a 211 je o jedničku víc. Číslo, které dává zbytek 1, dělitelné není (viz Dělení se zbytkem). Tady je 211 dokonce samo prvočíslo, takže jsme našli prvočíslo, které v seznamu chybělo.

Důkaz ale nepotřebuje, aby nové číslo bylo prvočíslo. Vezměte seznam 3 a 5: `3\cdot 5+1=16`. Šestnáctka prvočíslo není, jenže `16=2\cdot 2\cdot 2\cdot 2` a dvojka v seznamu chyběla. Nové prvočíslo se najde vždycky, buď jako `N`, nebo v jeho prvočíselném rozkladu.

Pozor: součin prvočísel plus 1 nemusí být prvočíslo

Častý omyl je myslet si, že Eukleidés dal návod, jak vyrábět prvočísla. Když vezmeme po řadě první prvočísla, chvíli to opravdu vychází:

součin prvních prvočísel+ 1je prvočíslo?
23ano
2 · 3 = 67ano
2 · 3 · 5 = 3031ano
2 · 3 · 5 · 7 = 210211ano
2 · 3 · 5 · 7 · 11 = 2 3102 311ano
2 · 3 · 5 · 7 · 11 · 13 = 30 03030 031ne, 59 · 509
… · 17 = 510 510510 511ne, 19 · 97 · 277

Číslo 30 031 prvočíslo není, ale jeho dělitelé 59 a 509 v seznamu 2 až 13 opravdu nejsou. Důkaz tedy platí, jen nedává vzorec. Žádný jednoduchý vzorec, který by vyráběl jen prvočísla a žádné vynechal, dodnes nikdo nezná.

Prvočísla řídnou, ale nedojdou

Mezi prvními deseti čísly jsou čtyři prvočísla (2, 3, 5, 7), mezi prvními sto čísly 25, mezi prvním milionem už jen 78 498, tedy asi každé třinácté číslo. Čím dál, tím delší jsou mezery mezi sousedními prvočísly. Po 89 přijde až 97, mezi nimi je sedm složených čísel 90 až 96. Po 113 přijde až 127 a mezi nimi je třináct složených čísel.

Mezera může být dokonce libovolně dlouhá. Chceme pět složených čísel za sebou? Vezmeme `1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=720` (na střední škole se tomu říká faktoriál a píše se `6!`) a čísla za ním:

`\begin{gathered}722=720+2 \text{ je dělitelné } 2\\[4pt] 723=720+3 \text{ je dělitelné } 3\\[4pt] 724=720+4 \text{ je dělitelné } 4\\[4pt] 725=720+5 \text{ je dělitelné } 5\\[4pt] 726=720+6 \text{ je dělitelné } 6\end{gathered}`

Každé z nich je součet dvou násobků téhož čísla, třeba `720` i `4` jsou násobky čtyř, takže i 724 je násobek čtyř. Stejně se dá postavit milion složených čísel za sebou. Přesto se za každou takovou mezerou zase nějaké prvočíslo objeví, to zaručuje Eukleidés.

Prvočíselná dvojčata

Prvočíselná dvojčata (také prvočíselná dvojice) jsou dvě prvočísla, která se liší o 2. Pod stovkou jich je osm:

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)

Blíž k sobě dvě prvočísla být nemohou, s jedinou výjimkou dvojice 2 a 3: ze dvou sousedních čísel je jedno sudé a jediné sudé prvočíslo je 2.

Všimněte si, že mezi dvojčaty (kromě 3 a 5) leží vždy násobek šesti: 12 mezi 11 a 13, 18 mezi 17 a 19, 30 mezi 29 a 31. Není to náhoda. Každé prvočíslo větší než 3 leží hned vedle násobku šesti, je tvaru `6k-1` nebo `6k+1`. Ostatní čísla prvočísla být nemohou: `6k`, `6k+2` a `6k+4` jsou sudá, `6k+3` je dělitelné třemi. Dvojčata (kromě 3 a 5) jsou proto vždycky dvojice `6k-1` a `6k+1`. Opačně to neplatí: 25 a 35 také leží vedle násobku šesti, a prvočísla to nejsou.

Dvojčat s rostoucími čísly ubývá rychleji než prvočísel:

do1001 00010 000100 0001 000 000
prvočísel251681 2299 59278 498
dvojčat8352051 2248 169

Jestli jich je nekonečně mnoho, nikdo neví. Domněnka, že ano, je stará přes 150 let a patří k nejslavnějším nevyřešeným otázkám matematiky. V roce 2013 dokázal matematik Yitang Zhang, že existuje nekonečně mnoho dvojic prvočísel, které se liší nejvýš o 70 milionů. Zní to jako hodně, ale byl to první krok: o rok později matematici společně snížili hranici na 246. Do dvojky ovšem zbývá kus. Největší známá dvojčata (z roku 2016) mají 388 342 číslic.

Cikády, které počítají v prvočíslech

Ve východní části USA žijí periodické cikády. Jejich larvy prožijí 13, nebo 17 let pod zemí, kde sají šťávu z kořenů stromů. Pak všechny cikády ze stejné oblasti vylezou ve stejném roce, během několika týdnů, v miliardách. Spáří se, nakladou vajíčka a zemřou, a další generace je zase 13, nebo 17 let pod zemí. Mezi známými periodickými cikádami nejsou žádné s cyklem 12, 14, 15, 16 ani 18 let.

Proč právě prvočísla? Jedno z vysvětlení, které biologové navrhli, se dá spočítat. Představte si dravce nebo parazita (ptáka, vosu nebo houbu), kterému se daří jednou za pár let. Cikády s dravcem se potkají v roce, který je násobkem obou cyklů. Poprvé tedy po tolika letech, kolik je jejich nejmenší společný násobek:

`\begin{gathered}\text{NSN}(12,\ 4)=12\\[4pt] \text{NSN}(13,\ 4)=52\end{gathered}`

Cikáda s cyklem 12 let by na dravce s cyklem 4 roky narazila při každém výletu z podzemí, protože 12 je násobek čtyř. Cikáda s cyklem 13 let ho potká poprvé až za 52 let:

Dravec: každé 4 rokyCikáda, 12 let: dravec čeká pokaždé1224364860728496Cikáda, 13 let: poprvé až za 52 let52104020406080100 let

Tabulka ukazuje, kolikrát za 100 let se cikáda potká s dravci s cykly 2 až 6 let (počítáme, že všichni vylezli poprvé ve stejném roce):

cyklus cikády2 roky3 roky4 roky5 let6 letcelkem
12 let8881833
13 let321118
14 let7231215
15 let3616319
16 let6261217
17 let211105
18 let5521518

Cykly 13 a 17 let vycházejí nejlépe, protože prvočíslo nemá žádného dělitele mezi 2 a 6. S cyklem 12 let, který se dělí dvěma, třemi, čtyřmi i šesti, by cikády dravce krmily skoro pokaždé. NSN dvou čísel si spočítáte kalkulačkou Nejmenší společný násobek.

Prvočísla oddělují i oba druhy cikád navzájem. Jedna populace třináctiletých cikád a sousední populace sedmnáctiletých vylezou ve stejném roce jen jednou za `\text{NSN}(13,\ 17)=13\cdot 17=221` let. Dvěma takovým populacím se to stalo v roce 2024 ve státě Illinois, předtím naposledy v roce 1803.

Biologové se dodnes přou, jestli je důvodem opravdu útěk před dravci, nebo něco jiného (třeba to, aby se dva cykly nekřížily). Jisté je jen to, že americké periodické cikády mají cykly 13 a 17 let, a to jsou prvočísla.

Proč je platební karta v bezpečí

Dlouho se zdálo, že prvočísla nemají mimo matematiku žádné využití. Pak v roce 1977 trojice matematiků Rivest, Shamir a Adleman vymyslela šifru RSA (podle jejich příjmení). Ta stojí na jednoduchém pozorování:

  • Vynásobit dvě prvočísla je snadné. `61\cdot 53=3\,233` spočítáte zpaměti nebo písemně za půl minuty.
  • Rozložit výsledek zpátky je těžké. Kdo dostane jen číslo 3 233, musí zkoušet dělit prvočísly 2, 3, 5, 7, 11, … a teprve 53 vyjde. To je šestnáct pokusů.

U čtyřmístného čísla je to práce na chvíli, s kalkulačkou na rozklad na zlomek vteřiny. Šifra RSA ale pracuje s čísly, která mají kolem 600 číslic a jsou součinem dvou prvočísel s asi 300 číslicemi. Vynásobit je zvládne počítač okamžitě. Na jejich rozklad by žádnému dnešnímu počítači nestačily ani tisíce let. Největší takové číslo, které se zatím podařilo rozložit, má 250 číslic. Povedlo se to v roce 2020 a všechny použité počítače na tom dohromady pracovaly tak dlouho, jako by jeden procesor počítal asi 2 700 let.

Čip na platební kartě v sobě nosí tajný klíč šifry RSA. Při placení jím terminálu prokáže, že je to pravá karta, a ne kopie. Podobně se ověřuje, že web banky je opravdu web banky. Kdo by uměl rychle rozkládat obří čísla na prvočísla, uměl by tajný klíč spočítat.

Šifra RSA v malém (pro zvídavé, 8.-9. třída)

Celou šifru si můžete vyzkoušet s malými prvočísly 3 a 11. Jejich součin `3\cdot 11=33` je veřejný, zná ho každý. Písmena převedeme na čísla podle abecedy, A = 1, B = 2, … (jako v šifře čísla místo písmen). Zašifrujeme písmeno H = 8:

Šifrování (postup zná každý): číslo umocníme na třetí a vydělíme 33. Zašifrovaná zpráva je zbytek.

`\begin{gathered}8^3=512\\[4pt] 512:33=15 \text{ (zb. 17)}\end{gathered}`

Odešleme 17. Kdo zprávu zachytí, vidí jen 17.

Dešifrování (postup zná jen příjemce): číslo 17 umocníme na sedmou, tedy vezmeme sedm sedmnáctek a vynásobíme je. Aby čísla nebyla obří, po každém násobení necháme jen zbytek po dělení 33.

kroknásobímedělíme 33pokračujeme s
1.1717
2.17 · 17 = 289289 : 33 = 8 (zb. 25)25
3.25 · 17 = 425425 : 33 = 12 (zb. 29)29
4.29 · 17 = 493493 : 33 = 14 (zb. 31)31
5.31 · 17 = 527527 : 33 = 15 (zb. 32)32
6.32 · 17 = 544544 : 33 = 16 (zb. 16)16
7.16 · 17 = 272272 : 33 = 8 (zb. 8)8

Vyšlo 8, tedy H. Zpráva je zpátky. (Že výsledek nezávisí na tom, jestli zbytky bereme průběžně, nebo až na konci, se dá dokázat; zbytky po dělení si ověříte kalkulačkou Dělení se zbytkem.)

Kde se vzala sedmička? Příjemce zná prvočísla 3 a 11, a tak spočítá `(3-1)\cdot(11-1)=20` a hledá číslo, které po vynásobení třemi dá o jedna víc než násobek dvacítky: `3\cdot 7=21=20+1`. Kdo zná jen 33, musí nejdřív 33 rozložit na `3\cdot 11`. U čísla 33 je to hračka, u čísla se 600 číslicemi to nejde. To je celé tajemství karty.

Šifru RSA by mohl prolomit dostatečně velký kvantový počítač. Ty dnešní jsou na to zatím příliš malé, ale banky a prohlížeče už pro jistotu zavádějí šifry, které na rozkladu na prvočísla nestojí.

Časté omyly

  • „Součin prvočísel plus 1 je vždycky prvočíslo.“ Není: `2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30\,031=59\cdot 509`. Eukleidův důkaz tvrdí jen to, že nové číslo nedělí žádné prvočíslo ze seznamu.
  • „Největší prvočíslo je to rekordní, co našly počítače.“ To je jen největší známé prvočíslo (najdete ho v článku Prvočíslo). Za ním jsou další, jen je zatím nikdo nenašel.
  • „Prvočísla jednou dojdou, protože řídnou.“ Řídnou, ale nikdy nedojdou. Řídnutí a konec jsou dvě různé věci.
  • „Každé číslo tvaru 6k ± 1 je prvočíslo.“ Platí to jen opačně: každé prvočíslo větší než 3 má tento tvar. Číslo `25=6\cdot 4+1` prvočíslo není.
  • „Šifra je bezpečná, protože prvočísla jsou tajná.“ Prvočísel je nekonečně mnoho a znát je může každý. Tajné je jen to, která dvě prvočísla dala dohromady veřejný součin.

Příklady k procvičení

1. Vynásobte prvočísla ze seznamu 2, 7 a přičtěte 1. Totéž udělejte pro seznam 3, 7. Jaká prvočísla, která v seznamu chybějí, z toho dostanete?

2. Napište pět po sobě jdoucích složených čísel, aniž byste hledali v tabulce prvočísel.

3. Čísla 3, 5, 7 jsou tři prvočísla, každé o 2 větší než předchozí. Proč žádná jiná taková trojice neexistuje?

4. Dravec se objevuje každých 6 let. Za kolik let se s ním poprvé potká cikáda s cyklem 12 let a za kolik cikáda s cyklem 13 let, když všichni vylezli poprvé ve stejném roce?

5. Číslo 221 je součin dvou prvočísel. Najděte je. Kde v tomto článku jste se s ním už potkali?

6. Zašifrujte malou šifrou RSA z článku (umocnit na třetí, nechat zbytek po dělení 33) písmeno D = 4. Pak zprávu dešifrujte.

Kam dál