Kontrola prvočísla

Prvočíslo je prirodzené číslo väčšie ako 1, ktoré nemá iných kladných deliteľov ako 1 a samo seba. Prvočísla sú 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Nie, 1 sa nepovažuje za prvočíslo. Podľa definície musí byť prvočíslo väčšie ako 1 a musí mať presne dva rôzne kladné delitele (1 a seba samého). Číslo 1 má len jedného deliteľa.

Áno, 2 je jediné párne prvočíslo. Je deliteľné len číslami 1 a 2. Všetky ostatné párne čísla sú deliteľné 2, takže nemôžu byť prvočíslami.

Prvočísla sú základom matematiky a majú zásadný význam pre modernú kryptografiu. Šifrovanie RSA, ktoré sa používa na zabezpečenie online transakcií, sa spolieha na náročnosť faktoringu veľkých čísel na ich prvočíselné zložky.

Prvočísiel je nekonečne veľa, čo dokázal Euklides okolo roku 300 pred Kristom. Bez ohľadu na to, aké veľké prvočíslo nájdete, vždy existuje väčšie. Prvočísla sú však s rastúcim počtom čísel čoraz vzácnejšie - len asi 4 % čísel blízkych miliónu sú prvočísla.

K dátumu 2024 je najväčším známym prvočíslom číslo 2^82,589,933 - 1, objavené v roku 2018. Toto Mersennovo prvočíslo má 24,862,048 číslic. Nové rekordné prvočísla sa objavujú vďaka projektu Great Internet Mersenne Prime Search (GIMPS), ktorý využíva distribuované výpočty.

Pri malých číslach skontrolujte deliteľnosť prvočíslami až po druhú odmocninu. Napríklad, ak chcete overiť, či je 97 prvočíslo, otestujte prvočísla do √97 ≈ 9,8 (teda otestujte 2, 3, 5, 7). Keďže 97 nie je deliteľné žiadnym z nich, je prvočíslo.

Dvojčatá sú dvojice prvočísiel, ktoré sa líšia o 2, napríklad (3,5), (5,7), (11,13), (17,19) a (29,31). Podľa domnienky o existencii dvojčiat ich je nekonečne veľa, ale napriek stáročiam matematického výskumu sa to stále nepodarilo dokázať.

Každé zložené číslo možno jednoznačne vyjadriť ako súčin prvočísel (Základná veta aritmetiky). Prvočíselná faktorizácia sa používa pri zjednodušovaní zlomkov, hľadaní GCD/LCM, kryptografii a riešení mnohých matematických problémov. Napríklad 60 = 2^2 × 3 × 5.

Mersennove prvočísla majú tvar 2^p - 1, kde p je tiež prvočíslo. Príkladmi sú 3 (2^2-1), 7 (2^3-1) a 31 (2^5-1). Sú významné pri hľadaní veľkých prvočísel a majú súvislosť s dokonalými číslami. Známych je len 51 Mersennových prvočísel.