Prvočíslo

Prvočíslo je přirozené číslo větší než 1, které je dělitelné jen jedničkou a samo sebou. Má tedy přesně dva dělitele. Nejmenší prvočíslo je 2 a je zároveň jediné sudé prvočíslo. Prvočísla do 100 jsou:

2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97

Číslo, které má víc než dva dělitele, se nazývá složené číslo. Například 12 je složené, protože ho beze zbytku vydělí 1, 2, 3, 4, 6 i 12. Číslo 1 není ani prvočíslo, ani složené číslo: má jediného dělitele, sebe samo.

Co je prvočíslo a co ne

Nejnázornější je představit si čísla jako kostičky. Složené číslo jde poskládat do obdélníku s aspoň dvěma řadami a aspoň dvěma kostičkami v každé řadě: 12 kostiček dá obdélník 3 × 4 nebo 2 × 6. Prvočíslo takhle poskládat nejde, jde z něj jen jedna řada a jinak vždy zbude kostička navíc. U 11 kostiček to vyzkoušíte hned: 2 × 4 + 3, 2 × 5 + 1, 3 × 3 + 2.

Tři otázky, na které se ptá skoro každý:

• Je 1 prvočíslo? Není. Má jen jednoho dělitele a definice žádá přesně dva. Kdyby se jednička počítala, přestal by platit jednoznačný rozklad na prvočísla (viz níže), protože 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3...
• Je 0 prvočíslo? Není. Nulu vydělí beze zbytku každé nenulové číslo, takže má nekonečně mnoho dělitelů.
• Je 2 prvočíslo? Ano, a je to nejmenší prvočíslo. Každé jiné sudé číslo je dělitelné dvěma, a proto je složené. Všechna ostatní prvočísla jsou lichá.

Nejmenší prvočíslo a prvočísla do 20

Nejmenší prvočíslo je 2. Nejmenší liché prvočíslo je 3, nejmenší dvouciferné 11 a nejmenší trojciferné 101. Největší prvočíslo neexistuje, prvočísel je nekonečně mnoho (důkaz je níže).

Prvočísla do 20 jsou jen čtyři jednociferná a čtyři dvouciferná:

2, 3, 5, 7, 11, 13, 17, 19

Stojí za to je znát zpaměti, protože se pořád vracejí: při krácení zlomků, při hledání společného jmenovatele i při rozkladu na prvočinitele.

Prvočísla do 100: Eratosthenovo síto

Všechna prvočísla do nějaké hranice najdete nejsnáze Eratosthenovým sítem. Postup vymyslel řecký matematik Eratosthenés z Kyrény (asi 276 až 194 př. n. l.) a funguje takto:

1. Napište čísla od 2 do zvolené hranice, třeba do 100.
2. První neškrtnuté číslo je prvočíslo. Zakroužkujte ho a škrtněte všechny jeho další násobky.
3. Opakujte krok 2 s dalším neškrtnutým číslem.
4. Jakmile je další neškrtnuté číslo větší než odmocnina z hranice, můžete skončit. Všechno, co zbylo, jsou prvočísla.

Do 100 tedy stačí proškrtat násobky 2, 3, 5 a 7, protože `\sqrt{100}=10` a další prvočíslo 11 je už větší. Po čtyřech kolech zbude tahle tabulka:

Proč stačí jít jen do odmocniny? Každé složené číslo do 100 má dělitele, který není větší než 10. Kdyby totiž oba činitelé byli větší než 10, jejich součin by byl větší než 100. Takové číslo proto škrtneme už při některém z prvních čtyř kol.

Prvočísla do libovolné hranice vám vypíše kalkulačka Seznam prvočísel, která počítá právě Eratosthenovým sítem.

Tabulka prvočísel do 1000

Pod tisícem je celkem 168 prvočísel. V tabulce jsou rozdělená po stovkách a poslední sloupec ukazuje, kolik jich v dané stovce je. Prvočísla do 200 jsou první dva řádky, dohromady jich je 46.

S rostoucími čísly prvočísel pomalu ubývá: v první stovce jich je 25, v desáté už jen 14.

Jak poznat prvočíslo

O jednom konkrétním čísle `n` rozhodnete tak, že ho zkusíte vydělit prvočísly 2, 3, 5, 7, 11, ... Stačí jít do `\sqrt{n}`. Pokud žádné z nich `n` beze zbytku nevydělí, je `n` prvočíslo. Důvod je stejný jako u síta: kdyby `n=a\cdot b` a oba činitelé byli větší než `\sqrt{n}`, byl by jejich součin větší než `n`.

Dvojku, trojku, pětku a jedenáctku odbydete bez dělení, pomocí znaků dělitelnosti:

Na sedmičku, třináctku a další prvočísla žádný pohodlný trik není, ty je potřeba opravdu vydělit.

Příklad 1

Je 91 prvočíslo?

`\sqrt{91}\doteq 9{,}5`, stačí tedy zkusit 2, 3, 5 a 7. Číslo 91 je liché, ciferný součet 10 není dělitelný třemi a nekončí na 0 ani 5. Zbývá sedmička:

`91:7=13`

Číslo 91 není prvočíslo, protože `91=7\cdot 13`. Zkouška: `7\cdot 13=70+21=91`. Tohle je nejčastější past. Číslo 91 vypadá jako prvočíslo, nedá se na něm použít žádný znak dělitelnosti a mnoho lidí ho do seznamu prvočísel zapíše.

Příklad 2

Je 97 prvočíslo?

`\sqrt{97}\doteq 9{,}8`, opět stačí 2, 3, 5 a 7. Číslo je liché, ciferný součet 16 není dělitelný třemi, nekončí na 0 ani 5 a `97=7\cdot 13+6`, dělení sedmi tedy dá zbytek 6. Žádné prvočíslo do 9,8 ho nedělí, takže 97 je prvočíslo. Je to největší prvočíslo menší než 100.

Příklad 3

Je 221 prvočíslo?

`\sqrt{221}\doteq 14{,}9`, zkoušíme prvočísla 2, 3, 5, 7, 11 a 13. Dvojka, trojka (ciferný součet 5) ani pětka nedělí. Dále:

`221=7\cdot 31+4`
`221=11\cdot 20+1`
`221=13\cdot 17`

Číslo 221 není prvočíslo. Příklad ukazuje, proč se nesmí skončit příliš brzy: kdo by přestal u sedmičky nebo jedenáctky, prohlásil by 221 za prvočíslo. Hranici určuje odmocnina, ne pocit, že už bylo vyzkoušeno dost.

Příklad 4

Je letopočet 2027 prvočíslo?

`\sqrt{2027}\doteq 45{,}02`, protože `45^2=2025`. Zkoušíme tedy prvočísla do 43: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Číslo je liché, ciferný součet 11 není dělitelný třemi a nekončí na 5. Zbytky po dělení ostatními prvočísly:

Žádný zbytek není nula, takže 2027 je prvočíslo. Další prvočíslo 47 už zkoušet nemusíme, protože `47^2=2209` je větší než 2027. Naproti tomu rok 2026 prvočíslo není, je sudý: `2026=2\cdot 1013`. Zbytky si můžete ověřit kalkulačkou dělení se zbytkem, celé rozhodnutí za vás udělá kalkulačka Je číslo prvočíslo?

Časté chyby

• Počítat jedničku mezi prvočísla. Seznam prvočísel začíná dvojkou.
• Myslet si, že liché číslo je prvočíslo. Pod stovkou je lichých složených čísel 25: 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95 a 99. Nejzrádnější jsou 51 = 3 · 17, 57 = 3 · 19 a 91 = 7 · 13.
• Soudit podle poslední číslice. Prvočísla větší než 5 končí na 1, 3, 7 nebo 9, ale neplatí to obráceně: 21, 33, 27 a 49 tak končí také.
• Skončit se zkoušením dřív než u odmocniny, jako v příkladu 3. Nebo naopak zbytečně pokračovat za ni.

Poznávání prvočísel si můžete vyzkoušet v procvičování prvočísel, kde se čísla dělitelná 2, 3 a 5 skoro nevyskytují a na nic se nedá hádat.

Prvočíselný rozklad

Základní věta aritmetiky říká, že každé přirozené číslo větší než 1 se dá zapsat jako součin prvočísel, a to jediným způsobem (až na pořadí činitelů). Prvočísla jsou tak stavební kameny, ze kterých se násobením poskládají všechna ostatní čísla. Jednotlivá prvočísla se přitom mohou opakovat:

`60=2^2\cdot 3\cdot 5`
`1001=7\cdot 11\cdot 13`
`23\,244=2^2\cdot 3\cdot 13\cdot 149`

Postup krok za krokem popisuje článek Prvočíselný rozklad, pro konkrétní číslo ho s celým postupem udělá kalkulačka Rozklad na prvočinitele. Rozklad je základ pro největší společný dělitel i nejmenší společný násobek.

Kolik je prvočísel

Prvočísel je nekonečně mnoho. Nejstarší důkaz pochází od Eukleida (asi 300 př. n. l.) a je tak krátký, že se vejde do odstavce:

Předpokládejme, že prvočísel je jen konečně mnoho. Vynásobme je všechna a přičtěme jedničku. Toto nové číslo nedělí žádné z našich prvočísel, protože dělení kterýmkoli z nich dá zbytek 1. Nové číslo je tedy buď samo prvočíslo, nebo je dělitelné nějakým prvočíslem, které v seznamu chybí. V obou případech seznam nebyl úplný, a to je spor.

Pozor na častou chybu v pochopení: výsledný součin plus jedna nemusí být prvočíslo. Nejmenší protipříklad:

`2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30\,031`
`30\,031=59\cdot 509`

Důkaz tvrdí jen to, že existuje nějaké prvočíslo mimo seznam, a tady jsou to 59 a 509.

Prvočísla s rostoucími čísly řídnou, ale nikdy nedojdou:

Rozmístění prvočísel

Žádný jednoduchý vzorec, který by vyráběl všechna prvočísla a nic jiného, neznáme. Leonhard Euler to komentoval slovy: Matematici se marně pokoušejí objevit nějaký zákon v rozmístění prvočísel a máme důvod se domnívat, že do tohoto tajemství naše mysl nikdy nepronikne. Přesto v nich jistá pravidelnost je a nejlépe ji ukazuje obrázek.

Ulamova spirála

V roce 1963 si matematik Stanisław Ulam na nudné přednášce kreslil přirozená čísla do spirály s jedničkou uprostřed:

Když v ní nechal jen prvočísla, všiml si, že se řadí do úhlopříčných čar:

Na spirále o rozměrech 200 × 200 čísel jsou úhlopříčky vidět ještě lépe. Každá tečka je jedno prvočíslo:

Prvočíselné dvojice

Prvočíselná dvojice (také prvočíselná dvojčata) jsou dvě prvočísla, která se liší o 2, například 11 a 13. Blíž k sobě dvě prvočísla být nemohou, s jedinou výjimkou dvojice 2 a 3: ze dvou sousedních čísel je vždy jedno sudé. Pod tisícem je 35 prvočíselných dvojic:

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139), (149, 151), (179, 181), (191, 193), (197, 199), (227, 229), (239, 241), (269, 271), (281, 283), (311, 313), (347, 349), (419, 421), (431, 433), (461, 463), (521, 523), (569, 571), (599, 601), (617, 619), (641, 643), (659, 661), (809, 811), (821, 823), (827, 829), (857, 859), (881, 883)

Předpokládá se, že prvočíselných dvojic je nekonečně mnoho, ale dokázat se to zatím nepodařilo.

Emirp

Emirp je anglické prime (prvočíslo) napsané pozpátku. Tak se říká prvočíslu, které po přečtení odzadu dá jiné prvočíslo. Palindromy jako 11 nebo 101 se nepočítají, protože pozpátku dají samy sebe. Emirpy do 200:

13, 17, 31, 37, 71,
73, 79, 97, 107, 113,
149, 157, 167, 179, 199

Goldbachova hypotéza

Jeden z nejstarších nevyřešených problémů matematiky, z roku 1742: Každé sudé číslo větší než 2 lze zapsat jako součet dvou prvočísel.

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
14 = 3 + 11 = 7 + 7

Čím větší číslo, tím víc takových zápisů obvykle má: 30 = 7 + 23 = 11 + 19 = 13 + 17. Počítače hypotézu ověřily pro všechna sudá čísla do `4\cdot 10^{18}`, obecný důkaz ale dodnes chybí.

Podobná Lemoinova hypotéza tvrdí, že každé liché číslo větší než 5 je součtem prvočísla a dvojnásobku prvočísla, tedy `2n+1=p+2q` pro `n\gt 2`. Například:

47 = 43 + 2 · 2
47 = 41 + 2 · 3
47 = 37 + 2 · 5
47 = 13 + 2 · 17

Počítače ji ověřily pro obrovská čísla, dokázaná ale také není.

Největší známé prvočíslo a trocha historie

Největší známé prvočíslo (stav k roku 2026) je

`2^{136\,279\,841}-1`

Má 41 024 320 číslic. Našel ho v říjnu 2024 Luke Durant v rámci projektu GIMPS (Great Internet Mersenne Prime Search), ve kterém dobrovolníci po celém světě nechávají své počítače prověřovat obří kandidáty.

Prvočísla tvaru `2^p-1` se jmenují Mersennova, po francouzském mnichovi Marinu Mersennovi, který je v 17. století zkoumal. Aby `2^p-1` mohlo být prvočíslo, musí být prvočíslem i exponent `p`. To ale nestačí: `2^7-1=127` prvočíslo je, `2^{11}-1=2047=23\cdot 89` není. Mersennova čísla se dají testovat mnohem rychleji než jiná čísla stejné velikosti, a proto téměř všechna rekordní prvočísla mají tento tvar.

Pierre de Fermat v 17. století předpokládal, že prvočísla jsou všechna čísla tvaru `2^{2^n}+1`. Pro `n=0` až `4` to platí (3, 5, 17, 257, 65 537), jenže Leonhard Euler v roce 1732 ukázal, že už další z nich prvočíslo není:

`2^{32}+1=4\,294\,967\,297=641\cdot 6\,700\,417`

Dlouho se zdálo, že prvočísla nemají mimo matematiku žádné využití. To se změnilo v 70. letech 20. století se vznikem šifry RSA. Ta stojí na tom, že vynásobit dvě velká prvočísla je snadné, ale rozložit jejich součin zpátky je pro dnešní počítače prakticky nemožné. Na tom dodnes závisí třeba zabezpečené spojení s bankou.

Příklady k procvičení

Kam dál

Poznávání prvočísel si procvičte v procvičování prvočísel, rozklad na prvočinitele a počet dělitelů v procvičování Dělitelé a prvočinitelé a znaky dělitelnosti v procvičování znaků dělitelnosti.

Na výpočty s postupem jsou tu kalkulačky Je číslo prvočíslo?, Seznam prvočísel, Rozklad na prvočinitele a Všichni dělitelé čísla, všechny najdete v přehledu Dělitelnost a prvočísla.

Na tento článek navazují Prvočíselný rozklad, Největší společný dělitel a Nejmenší společný násobek.