Pirminis skaičius yra tam tikros rūšies natūralusis skaičius. Apibrėžimas: pirminis skaičius yra skaičius, didesnis už 1, turintis tik du teigiamus dalininkus — 1 ir patį save. Skaičius, kurį galima užrašyti kaip dviejų mažesnių natūraliųjų skaičių sandaugą, vadinamas sudėtiniu. Mažiausias sudėtinis skaičius yra 4, nes 2 × 2 = 4. Skaičius 1 nėra nei pirminis, nei sudėtinis. Mažiausias pirminis skaičius yra 2 — tai vienintelis lyginis pirminis; visi kiti pirminiai skaičiai yra nelyginiai. Pavyzdžiai: 2, 3, 5, 7, 11, 13. Didžiausio pirminio skaičiaus nėra — pirminių skaičių visada atsiranda daugiau (apie tai žemiau).

Savybės ir pagrindinės savybės

  • Dalijimasis ir testavimas: jei skaičius n turi daliklį d kur 1 < d < n, tuomet n yra sudėtinis; priešingu atveju n yra pirminis.
  • Unikali faktorizacija: pagal aritmetikos pagrindinį teoremą (Fundamental Theorem of Arithmetic) kiekvienas natūralusis skaičius >1 gali būti užrašytas kaip pirminių sandauga vienareikšmiškai (išskyrus faktorių eiliškumą).
  • 2 kaip vienintelis lyginis pirminis: visi kiti pirminiai yra nelyginiai, nes jei skaičius yra lyginis ir didesnis už 2, jis dalinasi iš 2.
  • Modulinės savybės: pirminiai skaičiai lemia struktūras moduliuose, pvz., grupes U(p) moduliu pirminiu p.

Kodėl pirminių skaičių daugėja neribotai

Seniausias paprastas įrodymas, kad pirminių yra begalybė, priklauso Euklidui. Idėja trumpai: tarkime, pirminių yra baigtinai p1, p2, …, pn. Sudarykime skaičių Q = p1·p2·…·pn + 1. Joks iš p1,…,pn nepadalina Q (lieka liekana 1), tad Q turi būti pirminis arba turėti pirminį daliklį, kuris nėra tarp p1,…,pn. Tai prieštarauja prielaidai, taigi pirminių yra begalybė.

Pirminių skaičių pasiskirstymas ir teoremos

  • Pirminių skaičių teorema: aprašo, kaip pirminių skaičių skaičius mažesnių už x reikšmių, pažymimas π(x), elgiasi kai x → ∞: π(x) ~ x / ln(x). Daugiau apie tai: pirminių skaičių teorema.
  • Riemano hipotezė: nors tai nėra nei patvirtinta, nei paneigta, ji susijusi su labai tiksliomis pirminių pasiskirstymo savybėmis.

Praktiniai metodai, kaip nustatyti, ar skaičius yra pirminis

  • Paprastas tikrinimas (trial division): tikriname dalinimą iš pirminių iki √n. Veiksminga mažiems skaičiams, tačiau lėta labai dideliems.
  • Probabilistiniai testai: pvz., Miller–Rabin — greiti ir praktiškai patikimi, bet grąžina tik tikimybę, kad skaičius yra pirminis.
  • Deterministiniai testai: egzistuoja deterministinis AKS algoritmas, kuris poliominiu laiku nusprendžia pirminumą — tačiau praktikoje dažnai naudojami optimizuoti variantai ir suderinimas su probabilistiniais testais.
  • Specializuoti testai: Mersenne pirminiams (forma 2^p − 1) naudojami ypatingi metodai — tai leidžia rasti labai didelius pirminius, pvz., per GIMPS projektą.

Pritaikymai

  • Kryptografija: daug šifravimo sistemų (pvz., RSA) remiasi didžiųjų pirminių savybėmis ir tuo, kad faktorizacija į pirminius veikia lėtai.
  • Matematinės struktūros: pirminiai lemia paprastų ir sudėtingų algebraicinių bei kombinatorinių struktūrų savybes.
  • Skaičiavimai ir kompiuterija: pirminių paieška skatina algoritmų ir paskirstytų skaičiavimų tobulinimą.

Atviros problemos ir spėliojimai

  • Twin prime conjecture: ar egzistuoja begalinis skaičius pirminių porų p ir p+2?
  • Goldbacho spėjimas: kiekvieną pakankamai didelį lyginį skaičių galima užrašyti kaip dviejų pirminių sumą; tai vis dar neįrodyta — daugiau apie tai: Goldbacho spėjimas.
  • Didžiausių pirminių paieška: nors pirminių yra begalybė, atrasti labai didelius pirminius teikia techninių iššūkių; daugiausia rastų didžiųjų pirminių yra Mersenne tipo.

Praktiniai pavyzdžiai ir pastebėjimai

  • 2 — vienintelis lyginis pirminis.
  • 3, 5, 7, 11, 13 — pirmosios keletas pirminių.
  • Skaičius 1 nėra pirminis; jis neturi reikšmės aritmetikos pagrindinėje teoremoje dėl unikalios faktorizacijos.

Apibendrinant: pirminiai skaičiai yra matematikos kertinis elementas — jie sudaro natūraliųjų skaičių „atomas“ ir turi tiek gilų teorinį, tiek praktinį (pvz., saugumo) pritaikymą. Tyrimai apie jų pasiskirstymą, greitus nustatymo metodus ir susijusias atviras problemas tebėra intensyvi matematinių tyrimų sritis.