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.
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\cdot 3$ .
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 n$ je nejvyšší mocnina prvočísla p, která dělí řád grupy G, má grupa G podgrupu řádu $p n$ .
Pokud p je prvočíslo a G je grupa s $p n$ 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.)
Suma převrácených hodnot prvočísel je nekonečná
Hustota prvočísel je asymptoticky $1 / l n (n)$ , kde $l n (n)$ je přirozený logaritmus n. Přesněji, $\pi(n)\simeq n/ln(n)$ , kde $π(n)$ je počet prvočísel menších než n.
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.