Prvočíslo je prirodzené číslo väčšie ako 1, ktoré má práve dva kladné delitele: 1 a seba samé. Inak povedané, prvočísla sú prirodzené čísla n > 1, ktoré sa nedajú vyjadriť ako m × n s oboma číslami väčšími ako 1. Číslo 1 nie je prvočíslo ani zložené číslo. Najmenším prvočíslom je 2 (jediné párne prvočíslo); ďalšie sú 3, 5, 7, 11, 13 a pod. Najmenšie zložené číslo je 4, pretože 2 × 2 = 4. Je dôležité rozlišovať tieto pojmy: zložené číslo má aspoň jedného netriviálneho deliteľa (iného než 1 a samo seba).

Vlastnosti prvočísel

  • 2 je jediné párne prvočíslo; všetky ostatné prvočísla sú nepárne.
  • Každé prirodzené číslo väčšie ako 1 sa dá jednoznačne zapísať ako súčin prvočísel (a to až na usporiadanie). Toto sa nazýva veta o prvočíselnej faktorizácii (Fundamentálna veta aritmetiky).
  • Najväčšie prvočíslo neexistuje — prvočísla sú nekonečné. Euclidov dôkaz tejto nekonečnosti ukazuje, že ak by existoval konečný zoznam prvočísel, konštrukciou čísla rovného súčinu všetkých týchto prvočísel plus 1 dostaneme nové číslo, ktoré má prvočíselného deliteľa, ktorý nie je v pôvodnom zozname, čo vedie ku sporu.
  • Prvočísla sú „rozmetané“ v číselnej rade: čím väčšie čísla, tým sú vzácnejšie. Asymptotické správanie ich počtu popisuje prvočíselná veta (Prime Number Theorem): počet prvočísel ≤ x sa približne rovná x / log x pre veľké x.

Príklady prvočísel

  • Prvočísla do 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
  • Špeciálne triedy prvočísel: Mersennove prvočísla (tvar 2^p − 1 pre prvočíslne p), Sophie Germain prvočísla, dvojčatá (twin primes) — páry prvočísel vzdialené o 2, napr. (11, 13).

Testovanie prvočíselnosti a faktorizácia

Určiť, či je veľké číslo prvočíslo, môže byť náročné, ale existuje viacero efektívnych metód:

  • Priamou metódou je skúška deliteľnosti (trial division): skúšame deliť n všetkými prvočíslami ≤ √n. Táto metóda je jednoduchá, ale pomalá pre veľké n.
  • Pre generovanie všetkých prvočísel do veľkého limitu sa používa Eratosthenovo sito, ktoré je veľmi efektívne pri hromadnej produkcii prvočísel.
  • Probabilistické testy, napr. Miller–Rabin, dokážu rýchlo určiť, že číslo je „pravdepodobne prvočíslo“ s veľmi vysokou istotou. Pre praktické použitie (napr. kryptografia) sú častokrát postačujúce.
  • Existujú aj deterministické polynomiálne algoritmy, napr. AKS test, ktorý dokáže rozhodnúť prvočíselnosť v deterministickom čase polynomiálnom v počte bitov vstupu.
  • Pre úplné dokazovanie prvočíselnosti sa používajú metódy ako ECPP (Elliptic Curve Primality Proving), ktoré vygenerujú formálny dôkaz.
  • Faktorizácia (rozloženie zloženého čísla na prvočísla) je naopak ťažký problém pri veľkých číslach; jeho ťažkosť využívajú kryptografické systémy ako RSA.

Význam v matematike a aplikácie

  • Prvočísla sú základom teórie čísel a aritmetiky — fundamentálna veta aritmetiky zabezpečuje jedinečnosť prvočíselnej faktorizácie.
  • Rozloženie prvočísel ovplyvňuje analytickú teóriu čísel (napr. vzťahy k Riemannovej zeta-funkcii a rozdeleniu prvočísel).
  • V informatike a kryptografii sú veľké prvočísla kľúčové: asymetrické šifrovanie a elektronický podpis často spočívajú na ťažkosti faktorizácie veľkých čísel alebo výpočtu diskrétnych logaritmov.
  • Prvočísla sa objavujú aj v teórii grafov, kódovaní, generovaní náhodných čísel a ďalších oblastiach aplikovanej matematiky.

Distribúcia a otvorené problémy

Aj keď vieme, že prvočísla sú nekonečné a priblížime ich hustotu pomocou prvočíselnej vety, mnoho otázok zostáva otvorených. Napríklad:

  • Domnienka o dvojčatách prvočísel (Twin Prime Conjecture): existuje nekonečne veľa dvojíc prvočísel vzdialených o 2? (Otázka zatiaľ nezodpovedaná.)
  • Goldbachova domnienka: každé párne číslo väčšie ako 2 je súčtom dvoch prvočísel — aj táto domnienka zostáva nevyriešená, hoci overená pre veľmi veľké dosiahnuté hranice.

Najväčšie známe prvočísla

Aj keď neexistuje „najväčšie prvočíslo“ teoreticky, v praxi sa pravidelne hľadajú veľmi veľké prvočísla. Mnohé z najväčších nájdených prvočísel sú Mersennove prvočísla. K významným rekordom patrí prvočíslo 2^82,589,933 − 1, objavené projektom GIMPS v roku 2018, ktoré má 24 862 048 číslic. Takéto rekordy sa môžu meniť, pretože prebiehajú nové výpočty.

Tipy na rýchlu kontrolu prvočíselnosti

  • Ak je číslo párne a nie je rovné 2, nie je prvočíslo.
  • Ak sú súčet číslic deliteľný 3 a číslo nie je 3, potom nie je prvočíslo.
  • Testujte deliteľnosť malými prvočíslami (5, 7, 11, …) predtým, než použijete náročnejšie metódy.
  • Pre veľmi veľké čísla používajte overené knižnice, ktoré kombinujú deterministické a probabilistické testy.

Prvočísla sú jednoduché na definíciu, no hlboké a bohaté na vlastnosti — tvoria jedno z najživších a najdôležitejších oblastí matematiky, spájajúce čistú teóriu s praktickými aplikáciami. Pre ďalšie súvisiace témy pozrite tiež vetu o prvočíslach a Goldbachovu domnienku.