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

[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 apa 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 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 p1, p2, …, pn. Potom číslo x = p1 · p2 ··· pn + 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 / ln(n), kde ln(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 232 582 657 − 1, má 9 808 358 dekadických cifer. Je to 44. Mersennovo prvočíslo označované jako M32582657. 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

[editovat] Externí odkazy