Prvočíslo

Prvočíslo je přirozené číslo, které je beze zbytku dělitelné právě dvěma různými čísly a to jedničkou a samo sebou (tedy 1 není prvočíslo). Celá čísla různá od jedné, která nejsou prvočísla, se nazývají složená čísla.

Začátek řady prvočísel:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

[editovat] Příklad

Číslo 13 má při dělení dvěma zbytek 1, při dělení 3 zbytek 1, při dělení pěti zbytek 3 atd. Beze zbytku je dělitelné pouze 1 a 13. Proto je 13 prvočíslo.

Číslo 24 je dělitelné čísly 1, 2, 3, 4, 6, 8, 12, 24 – proto není prvočíslem.

[editovat] Vlastnosti

• Pokud je p prvočíslo a p dělí součin čísel a a b, pak p dělí a nebo p dělí b.
• Každé složené číslo lze jednoznačně vyjádřit jako součin prvočísel. Proces rozkladu čísla na jeho prvočíselné činitele (prvočinitele) se nazývá faktorizace. Např. .
• Okruh Z/nZ (viz množina zbytkových tříd) je těleso, právě když n je prvočíslo. Jinak vyjádřeno: n je prvočíslo, právě když φ(n) = n − 1, kde φ(n) je počet invertovatelných prvků v Z/nZ.
• Pokud p je prvočíslo a 0<a<p je celé číslo, pak a^p − a je dělitelné p.
• Pokud n je kladné celé číslo, existuje prvočíslo p tak, že n < p ≤ 2n.
• Pokud G je konečná grupa a pⁿ je nejvyšší mocnina prvočísla p, která dělí řád grupy G, má grupa G podgrupu řádu pⁿ.
• Pokud p je prvočíslo a G je grupa s pⁿ prvky, obsahuje G prvek řádu p.
• Prvočísel je nekonečně mnoho. (Důkaz sporem: Nechť existuje jen konečně mnoho prvočísel. Označme je p₁, p₂, …, p_n. Potom číslo x = p₁ · p₂ ··· p_n + 1 není dělitelné žádným z těchto prvočísel, jelikož při dělení dostaneme vždy zbytek 1. Tím pádem číslo x musí být buď prvočíslo, nebo musí být dělitelné nějakým jiným prvočíslem. To ale znamená, že množina prvočísel z počátku důkazu nebyla úplná, což je spor s předpokladem). Tento důkaz předvedl Euklides.
• Suma převrácených hodnot prvočísel je nekonečná
• Hustota prvočísel je asymptoticky 1 / ln(n), kde ln(n) je přirozený logaritmus n. Přesněji, , kde π(n) je počet prvočísel menších než n.
• Největší dnes (2008) známé prvočíslo je 2^43 112 609 − 1, má 12 978 189 dekadických cifer. Je to 46. známé Mersennovo prvočíslo, označované jako M_43112609. Bylo nalezeno 23. srpna 2008.

Zkoumáním vlastností prvočísel se zabývá teorie čísel.

[editovat] Výskyt prvočísel

Podle Bertrándova postulátu lze nalézt vždy alespoň jedno prvočíslo mezi čísly n a 2n pro n > 1. Ve skutečnosti jich však existuje pro vyšší n daleko více. Z této věty ihned také plyne nekonečný počet prvočísel.

Naproti tomu lze nalézt libovolně dlouhé intervaly přirozených čísel, kde se nevyskytuje žádné prvočíslo. Například interval (k+1)!+2, (k+1)!+3, … (k+1)!+k+1 (vizte faktoriál) obsahuje k složených čísel. Tato čísla jsou totiž po řadě dělitelná dvěma, třemi, …, k+1.

Mnoho hypotéz o rozložení prvočísel je dodnes nevyřešených. K nejznámějším patří otázka, zda je nekonečně mnoho prvočíselných dvojčat, tj. dvojic prvočísel lišících se o 2 (např 5,7 nebo 41,43). Jiný otevřený problém je tzv. Riemannova hypotéza, která souvisí s pravidelností rozložení prvočísel a za jejíž důkaz je vypsána odměna milion dolarů.

[editovat] Využití

Velký praktický význam mají prvočísla v kryptografii.

Pro vytvoření seznamu prvočísel existují různé algoritmy, např. Eratosthenovo síto.

[editovat] Prvních sto 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, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541.

[editovat] Související články

• Mersennovo prvočíslo
• Emirp
• Prvočíselný rozklad
• Prvočíselná dvojice
• Wieferichovo prvočíslo

[editovat] Externí odkazy

• www.prime-numbers.org – Prvočísla do 10 miliard
• www.beda.cz/~jirkaj/primes.html - Přehledná tabulka prvočísel do miliónu
• primes.utm.edu - Vše o prvočíslech
• Prvočíslo: http://www.maths.cz/…

Tento matematický článek je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.