Prvočíslo

Z Wikipedie, otevřené encyklopedie

Prvočíslo je přirozené číslo větší než 1, které je beze zbytku dělitelné pouze jedničkou a samo sebou. Celá čísla, která nejsou prvočíslem, se nazývají složená čísla (též neprvočísla).

Začátek řady prvočísel:

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

Obsah 1 Příklad 2 Vlastnosti 3 Využití 4 Podívejte se také na 5 Externí odkazy

[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.
• 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.
• Pokud p je prvočíslo a a je libovolné celé číslo, je ap − a dělitelné p.
• Pokud p je prvočíslo jiné než 2 a 5, 1/p má v desítkové soustavě nekonečný desetinný rozvoj.
• Pokud n je kladné celé číslo, existuje prvočíslo p tak, že n < p ≤ 2n.
• Pro každé prvočíslo p > 2 existuje přirozené číslo n tak, že p = 4n ± 1.
• Pro každé prvočíslo p > 3 existuje přirozené číslo n tak, že p = 6n ± 1.
• Pokud G je konečná grupa a pn je nejvyšší mocnina prvočísla p, která dělí řád grupy G, má grupa G podgrupu řádu pn.
• Pokud p je prvočíslo a G je grupa s pn 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 delitelné 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.)
• 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ř. 24 = 2³ ⋅ 3.
• Největší dnes (2006) známé prvočíslo je 2^32 582 657 − 1, má 9 808 358 dekadických cifer. Je to 44. Mersennovo prvočíslo označované jako M_32582657. Bylo nalezeno 4. září 2006.

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

[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] Podívejte se také na

• Mersennovo prvočíslo
• Emirp
• Prvočíselný rozklad

[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