Prvočíslo: definícia, vlastnosti, príklady a význam v matematike

Komplexný sprievodca prvočíslam: definícia, vlastnosti, príklady, význam v matematike a nevyriešené otázky (Goldbachova domnienka). Naučte sa rozpoznať prvočísla rýchlejšie.

Autor: Leandro Alegsa

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.

Tu je ďalší spôsob, ako uvažovať o prvočíslach. Číslo 12 nie je prvočíslo, pretože z neho možno vytvoriť obdĺžnik so stranami dlhými 4 a 3. Tento obdĺžnik má plochu 12, pretože je použitých všetkých 12 kvádrov. To sa nedá urobiť s 11. Bez ohľadu na to, ako je obdĺžnik usporiadaný, vždy zostanú kvádre, okrem obdĺžnika so stranami dĺžok 11 a 1. 11 teda musí byť prvočíslo.Zoom
Tu je ďalší spôsob, ako uvažovať o prvočíslach. Číslo 12 nie je prvočíslo, pretože z neho možno vytvoriť obdĺžnik so stranami dlhými 4 a 3. Tento obdĺžnik má plochu 12, pretože je použitých všetkých 12 kvádrov. To sa nedá urobiť s 11. Bez ohľadu na to, ako je obdĺžnik usporiadaný, vždy zostanú kvádre, okrem obdĺžnika so stranami dĺžok 11 a 1. 11 teda musí byť prvočíslo.

Ako nájsť malé prvočísla

Existuje jednoduchá metóda na nájdenie zoznamu prvočísiel. Vytvoril ju Eratosthenes. Má názov Eratosthenovo sito. Zachytáva čísla, ktoré nie sú prvočíslami (ako sito), a prvočísla necháva prejsť.

Metóda pracuje so zoznamom čísel a špeciálnym číslom b, ktoré sa počas metódy mení. Pri postupe metódou niektoré čísla v zozname zakrúžkujete a iné vyškrtnete. Každé zakrúžkované číslo je prvočíslo a každé prečiarknuté číslo je zložené. Na začiatku sú všetky čísla jednoduché: nie sú zakrúžkované ani prečiarknuté.

Metóda je vždy rovnaká:

  1. Na hárok papiera napíšte všetky celé čísla od 2 až po testované číslo. Číslo 1 nezapisujte. Prejdite na ďalší krok.
  2. Začnite s b rovným 2. Prejdite na ďalší krok.
  3. V zozname zakrúžkujte b. Prejdite na ďalší krok.
  4. Počínajúc číslom b napočítajte v zozname ďalšie b a toto číslo prečiarknite. Opakujte počítanie ďalších b čísel a vyškrtávanie čísel až do konca zoznamu. Prejdite na ďalší krok.
    • (Napríklad: Ak je b 2, zakrúžkujete 2 a prečiarknete 4, 6, 8 atď. Keď je b 3, zakrúžkujete 3 a prečiarknete 6, 9, 12 atď. Hodnoty 6 a 12 už boli prečiarknuté. Prečiarknite ich ešte raz.)
  5. Zvýšte b o 1. Prejdite na ďalší krok.
  6. Ak bolo b prečiarknuté, vráťte sa k predchádzajúcemu kroku. Ak je b číslo v zozname, ktoré nebolo prečiarknuté, prejdite na 3. krok. Ak b nie je v zozname, prejdite na posledný krok.
  7. (Toto je posledný krok.) Hotovo. Všetky prvočísla sú zakrúžkované a všetky zložené čísla sú prečiarknuté

Ako príklad môžete použiť túto metódu na zozname čísel od 2 do 10. Na konci budú zakrúžkované čísla 2, 3, 5 a 7. Sú to prvočísla. Čísla 4, 6, 8, 9 a 10 budú prečiarknuté. Sú to zložené čísla.

Táto metóda alebo algoritmus trvá príliš dlho na nájdenie veľmi veľkých prvočísel. Je však menej komplikovaný ako metódy používané pri veľmi veľkých prvočíslach, ako je Fermatov test prvočíselnosti (test na zistenie, či je číslo prvočíslo alebo nie) alebo Millerov-Rabinov test prvočíselnosti.

Na čo sa používajú prvočísla

Prvočísla sú veľmi dôležité v matematike a informatike. Nižšie sú uvedené niektoré reálne použitia. Veľmi dlhé čísla sa ťažko riešia. Je ťažké nájsť ich prvočinitele, preto sa na šifrovanie a tajné kódy väčšinou používajú čísla, ktoré sú pravdepodobne prvočíselné.

  • Väčšina ľudí má bankovú kartu, ktorou si môžu vybrať peniaze zo svojho účtu prostredníctvom bankomatu. Táto karta je chránená tajným prístupovým kódom. Keďže tento kód musí byť tajný, nemôže byť na karte uložený v otvorenom texte. Na tajné uloženie kódu sa používa šifrovanie. Toto šifrovanie využíva násobenie, delenie a hľadanie zvyškov veľkých prvočísel. V praxi sa často používa algoritmus s názvom RSA. Využíva čínsku vetu o zvyšku.
  • Ak má niekto digitálny podpis pre svoj e-mail, používa sa šifrovanie. Tým sa zabezpečí, že nikto nemôže sfalšovať e-mail od neho. Pred podpísaním sa vytvorí hash hodnota správy. Tá sa potom skombinuje s digitálnym podpisom a vytvorí sa podpísaná správa. Používané metódy sú viac-menej rovnaké ako v prvom uvedenom prípade.
  • Hľadanie najväčšieho doteraz známeho prvočísla sa stalo akýmsi športom. Testovanie, či je číslo prvočíslo, môže byť ťažké, ak je číslo veľké. Najväčšie známe prvočísla sú zvyčajne Mersennove prvočísla, pretože najrýchlejším známym testom prvočíselnosti je Lucasov-Lehmerov test, ktorý sa opiera o špeciálnu formu Mersennových čísel. Skupina, ktorá hľadá Mersennove prvočísla, sa nachádza tu[1].

Otázky a odpovede

Otázka: Čo je to prvočíslo?


Odpoveď: Prvočíslo je prirodzené číslo, ktoré nemožno deliť žiadnym iným prirodzeným číslom okrem 1 a seba samého.

Otázka: Aké je najmenšie zložené číslo?


Odpoveď: Najmenšie zložené číslo je 4, pretože 2 x 2 = 4.

Otázka: Aké sú ďalšie prvočísla po čísle 2?


Odpoveď: Ďalšie prvočísla po 2 sú 3, 5, 7, 11 a 13.

Otázka: Existuje najväčšie prvočíslo?


Odpoveď: Nie, neexistuje žiadne najväčšie prvočíslo. Množina prvočísiel je nekonečná.

Otázka: Čo hovorí základná veta aritmetiky?


Odpoveď: Základná veta aritmetiky hovorí, že každé kladné celé číslo sa dá zapísať ako súčin prvočísel jedinečným spôsobom.

Otázka: Čo je Goldbachova domnienka?


Odpoveď: Goldbachova domnienka je nevyriešený problém v matematike, ktorý hovorí, že každé párne celé číslo väčšie ako dve možno vyjadriť ako súčet dvoch prvočísel.

Otázka: Kto zaznamenal dôkaz, že neexistuje najväčšie prvočíslo?


Odpoveď: Euklides zaznamenal dôkaz, že neexistuje najväčšie prvočíslo.


Prehľadať
AlegsaOnline.com - 2020 / 2025 - License CC3