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 libovolné 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ší dosud známé prvočíslo je tak právě Mersennovo prvočíslo, označuje se M_43112609, kde spodní index určuje exponent z. Jedná se tak o prvočíslo 2^43112609−1. Bylo nalezeno 23. srpna 2008 a má 12,978,189 číslic. (Wikipedie)

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/4 = 15, číslo čtyř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í. (Wikipedie)
• Riemannova hypotéza: Všechny netriviální nulové body Riemannovy zeta-funkce mají reálnou část rovnou $\frac12$. (Wikipedie) Věta souvisí s rozložením prvočísel a jedná se o jeden tzv. Problémů tisíciletí a za její vyřešení vás čeká odměna milion dolarů.