Pirminiai skaičiai: apibrėžimas, savybės ir pagrindinės teoremos
Pirminiai skaičiai: aiškus apibrėžimas, svarbiausios savybės ir pagrindinės teoremos — nuo 2 iki didžiųjų teoremų ir neišspręstų problemų.
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.
Štai dar vienas būdas galvoti apie pirminius skaičius. Skaičius 12 nėra pirminis, nes galima sudaryti stačiakampį, kurio kraštinių ilgiai yra 4 ir 3. Šio stačiakampio plotas yra 12, nes naudojami visi 12 blokų. To negalima padaryti su 11. Kad ir kaip stačiakampis būtų sudėliotas, visada liks blokų, išskyrus stačiakampį, kurio kraštinių ilgiai 11 ir 1. Todėl 11 turi būti pirminis skaičius.
Kaip rasti mažus pirminius skaičius
Yra paprastas būdas rasti pirminių skaičių sąrašą. Jį sukūrė Eratostenas. Jis pavadintas Eratosteno sietu. Jis sugauna skaičius, kurie nėra pirminiai (kaip sietas), ir praleidžia pirminius skaičius.
Metodas veikia su skaičių sąrašu ir specialiu skaičiumi, vadinamu b, kuris metodo metu kinta. Atliekant metodą, kai kurie skaičiai sąraše apvedami apskritimu, o kiti išbraukiami. Kiekvienas apvestas skaičius yra pirminis, o kiekvienas išbrauktas skaičius yra sudėtinis. Pradžioje visi skaičiai yra paprasti: neapibrėžti ir neperbraukti.
Metodas visada tas pats:
- Ant popieriaus lapo užrašykite visus sveikuosius skaičius nuo 2 iki tikrinamo skaičiaus. Nerašykite skaičiaus 1. Pereikite prie kito žingsnio.
- Pradėkite nuo skaičiaus b, lygaus 2. Pereikite prie kito žingsnio.
- Sąraše apveskite ratuką b. Pereikite prie kito žingsnio.
- Pradėdami nuo b, sąraše suskaičiuokite dar b ir tą skaičių išbraukite. Pakartokite skaičiuodami dar b skaičių ir išbraukdami skaičius iki sąrašo pabaigos. Pereikite prie kito žingsnio.
- (Pavyzdžiui: Kai b yra 2, apveskite 2 ir išbraukite 4, 6, 8 ir t. t. Kai b yra 3, apvesite 3 ir išbrauksite 6, 9, 12 ir t. t. 6 ir 12 jau buvo išbraukti. Perbraukite juos dar kartą.)
- Padidinkite b 1. Pereikite prie kito veiksmo.
- Jei b buvo perbraukta, grįžkite prie ankstesnio veiksmo. Jei b yra neišbrauktas sąrašo numeris, pereikite prie 3 žingsnio. Jei b nėra sąraše, pereikite prie paskutinio žingsnio.
- (Tai paskutinis žingsnis.) Baigta. Visi pirminiai skaičiai apvedžioti, o visi sudėtiniai skaičiai perbraukti.
Pavyzdžiui, šį metodą galite taikyti skaičių nuo 2 iki 10 sąrašui. Galiausiai skaičiai 2, 3, 5 ir 7 bus apvesti. Jie yra pirminiai skaičiai. 4, 6, 8, 9 ir 10 bus perbraukti. Tai sudėtiniai skaičiai.
Šis metodas arba algoritmas užtrunka pernelyg ilgai, kad būtų galima rasti labai didelius pirminius skaičius. Tačiau jis nėra toks sudėtingas kaip labai dideliems pirminiams skaičiams rasti naudojami metodai, pavyzdžiui, Fermat'o pirmumo testas (testas, kuriuo nustatoma, ar skaičius yra pirminis, ar ne) arba Millerio-Rabino pirmumo testas.
Kam naudojami pirminiai skaičiai
Pirminiai skaičiai labai svarbūs matematikoje ir informatikoje. Toliau pateikiama keletas realaus naudojimo pavyzdžių. Labai ilgus skaičius sunku išspręsti. Sunku rasti jų pirminius veiksnius, todėl dažniausiai šifravimui ir slaptiems kodams naudojami skaičiai, kurie tikriausiai yra pirminiai.
- Dauguma žmonių turi banko kortelę, kuria naudodamiesi bankomatu gali pasiimti pinigų iš savo sąskaitos. Ši kortelė yra apsaugota slaptu prieigos kodu. Kadangi kodas turi būti slaptas, jis negali būti saugomas atviru tekstu kortelėje. Kodui slapta saugoti naudojamas šifravimas. Šifravimui naudojamos daugybos, dalybos ir didelių pirminių skaičių liekanų radimas. Praktikoje dažnai naudojamas algoritmas, vadinamas RSA. Jame naudojama kinų liekanų teorema.
- Jei el. laiškas pasirašytas skaitmeniniu parašu, naudojamas šifravimas. Taip užtikrinama, kad niekas negalėtų suklastoti jų elektroninio laiško. Prieš pasirašant sukuriama pranešimo hash vertė. Tuomet ji sujungiama su skaitmeniniu parašu ir gaunamas pasirašytas pranešimas. Naudojami daugiau ar mažiau tokie patys metodai kaip ir pirmuoju pirmiau minėtu atveju.
- Didžiausio iki šiol žinomo pirminio skaičiaus paieška tapo savotišku sportu. Patikrinti, ar skaičius yra pirminis, gali būti sunku, jei skaičius yra didelis. Didžiausi bet kuriuo metu žinomi pirminiai skaičiai paprastai yra Merseno pirminiai skaičiai, nes greičiausias žinomas pirmumo testas yra Lucaso-Lehmerio testas, kuris remiasi specialia Merseno skaičių forma. Grupė, kuri ieško Merseno pirminių skaičių, yra čia[1].
Klausimai ir atsakymai
K: Kas yra pirminis skaičius?
Atsakymas: Pirminis skaičius - tai natūralusis skaičius, kurio negalima dalyti iš jokio kito natūraliojo skaičiaus, išskyrus 1 ir jį patį.
K: Koks yra mažiausias sudėtinis skaičius?
A: Mažiausias sudėtinis skaičius yra 4, nes 2 x 2 = 4.
K: Kokie yra kiti pirminiai skaičiai po 2?
A: Po 2 einantys pirminiai skaičiai yra 3, 5, 7, 11 ir 13.
K: Ar yra didžiausias pirminis skaičius?
Atsakymas: Ne, nėra didžiausio pirminio skaičiaus. Pirminių skaičių aibė yra begalinė.
K: Ką teigia pagrindinė aritmetikos teorema?
A: Pagrindinė aritmetikos teorema teigia, kad kiekvienas teigiamas sveikasis skaičius gali būti užrašytas kaip pirminių skaičių sandauga unikaliu būdu.
K: Kas yra Goldbacho spėjimas?
A: Goldbacho spėjimas yra neišspręsta matematikos problema, teigianti, kad kiekvienas lyginis sveikasis skaičius, didesnis už du, gali būti išreikštas kaip dviejų pirminių skaičių suma.
K: Kas užrašė įrodymą, kad nėra didžiausio pirminio skaičiaus?
A: Euklidas užrašė įrodymą, kad nėra didžiausio pirminio skaičiaus.
Ieškoti