Prvočísla

Prvočísla jsou čísla, která jsou dělitelná jen jedničkou a sama sebou. Vlastnosti prvočísel se často využívají například v kryptografii.

Definice a příklady

Pusťte si video verzi článku!

Prvočíslo je přirozené číslo, které je beze zbytku dělitelné pouze jedničkou a sebou samým, přičemž samotná jednička prvočíslo není. Nejmenší prvočíslo je dvojka — je dělitelná beze zbytku jedničkou a dvojkou. Je to zároveň jediné prvočíslo, které je sudé. Všechna ostatní prvočísla jsou lichá, protože jakékoliv jiné sudé číslo je dělitelné kromě jedničky a sebou samým ještě právě dvojkou.

Posloupnost několika prvních prvočísel: 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…

Prvočísel se týká základní věta aritmetiky, která říká, že každé celé číslo větší než 1 lze rozložit na součin prvočísel.

Otestujte si, zda je číslo prvočíslo

Vlastnosti prvočísel

• Prvočísel je nekonečně mnoho. Důkaz se nachází v článku o důkazu sporem.
• Pro každé celé číslo z>1 platí, že v intervalu (z, 2z) existuje alespoň jedno prvočíslo. Příklad: pro z = 2 máme interval (2, 4). Jediné celé číslo, které je v tomto intervalu, je trojka a to je prvočíslo. Pro z = 5 dostaneme interval (5, 10), tedy čísla 6, 7, 8, 9. Číslo 7 je prvočíslo. Podobně pro vyšší z.
• Mersennovo prvočíslo je prvočíslo, které je o jedna menší než nějaká celočíselná mocnina dvojky. Mersennovo prvočíslo M tak má tvar M = 2^z − 1, kde z je nějaké přirozené číslo. Příkladem může být prvočíslo 3, protože platí 2² − 1 = 3. Nebo 7, protože 2³ − 1 = 7.
• Největší známá prvočísla bývají právě Mersennova. Například 23. srpna 2008 bylo nalezeno Mersennovo prvočíslo M_43112609, kde spodní index určuje exponent z. Jedná se tak o prvočíslo 2^43112609−1, které má 12,978,189 číslic a v té době bylo největším známým prvočíslem.

Posloupnost bez prvočísel

Lze nalézt libovolně dlouhou konečnou posloupnost po sobě jdoucích přirozených čísel, mezi kterými se nevyskytuje ani jedno prvočíslo. Taková posloupnost může mít tvar k!+2, k!+3, …, k!+k a obsahuje k − 1 po sobě jdoucích složených čísel (vykřičník je faktoriál).

Například pro k = 6 dostaneme pět po sobě jdoucích složených čísel ve tvaru: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Tato čísla jsou postupně dělitelná dvěma, třemi, čtyřmi, pěti a šesti, protože číslo 6! = 720 je určitě dělitelné všemi těmito čísly, protože vzniklo jejich součinem: 6! = 6 · 5 · 4 · 3 · 2. Pokud je číslo 720 dělitelné třemi, pak i číslo 720 + 3 musí být dělitelné třemi. Podobně pro ostatní.

Malá Fermatova věta

Pro každé prvočíslo p a pro každé celé číslo z takové, že z není násobkem p, platí, že číslo z^p − z je dělitelné prvočíslem p.

Příklad: vezměme si prvočíslo p = 3 a celé číslo z = 4. Číslo čtyři není násobkem čísla tři, takže můžeme pokračovat. Vypočítáme hodnotu čísla 4³ − 4. To se rovná 60. Přitom ale platí, že 60/3 = 20, číslo tři tak dělí šedesátku beze zbytku, což odpovídá Fermatově větě. Jiný příklad: p = 7, z = 10. Vypočítáme mezivýsledek 10⁷ − 10 = 9999990 a toto číslo vydělíme sedmi: 9999990/7 = 1428570. Opět jsme dostali výsledek beze zbytku.

Nevyřešené otázky

Prvočísel se týká mnoho známých hypotéz, které se ještě (2011) nepovedlo dokázat ani vyvrátit. Mezi dvě nejznámější patří:

• Nekonečnost prvočíselných dvojic: prvočíselná dvojice je dvojice čísel (z, z + 2), přičemž obě tato čísla jsou prvočísla. Například (3, 5) nebo (29, 31). Otázkou je, zdali je těchto prvočíselných dvojic nekonečně mnoho. Předpokládá se, že ano, ale důkaz chybí.
• Riemannova hypotéza: Všechny netriviální nulové body Riemannovy zeta-funkce mají reálnou část rovnou $\frac12$. Věta souvisí s rozložením prvočísel a jedná se o jeden z tzv. problémů tisíciletí a za její vyřešení vás čeká odměna milion dolarů.