Pirmskaitļi: definīcija, īpašības, piemēri un Goldbaha minējums
Atklāj pirmskaitļu definīciju, īpašības, piemērus un Goldbaha minējuma noslēpumu — skaidri izskaidrots raksts gan skolēniem, gan interesentiem.
Vienkāršais skaitlis jeb pirmskaitlis ir speciāls dabiskais skaitlis, kas >1 un nav dalāms ar nekādām citiem naturāliem skaitļiem, izņemot 1 un pašu sevi. Citiem vārdiem, pirmskaitlis nav izsakāms kā m × n, kur m un n ir lielāki par 1. Skaitlis 1 nav ne pirmskaitlis, ne salikts skaitlis. Mazākais pirmskaitlis ir 2 (vienīgais pāra pirmskaitlis). Pēc tam nāk 3, 5, 7, 11, 13 utt. Lielākā pirmskaitļa nav — pirmskaitļi ir bezgalīgi.
Vienkārši piemēri
- Daži mazāki pirmskaitļi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
- Piemērs, kas nav pirmskaitlis: 4 = 2 × 2 (salikts skaitlis).
- Skaitlis 1 nav pirmskaitlis un nav arī salikts — tas ir īpašs gadījums.
Galvenās īpašības
- Unikalitāte faktorizācijā: saskaņā ar aritmētikas pamattēzi jeb Galvenā aritmētikas teorēma, katru skaitli lielāku par 1 var viennozīmīgi izvietot kā pirmskaitļu reizinājumu (kārtības secība nav nozīmīga).
- Bezgalība: Eiklīds pierādīja, ka pirmskaitļu ir bezgalīgi. Īss pierādījuma skelets: pieņem, ka pirmskaitļu kopums ir beigts, reizinot tos visus kopā un pieskaitot 1, iegūst skaitli, kuram nav dalītāja starp sākotnējiem pirmskaitļiem, tātad jāeksistē jauns pirmskaitlis — pretruna.
- Pāra un nepāra: vienīgais pāra pirmskaitlis ir 2; visi citi pirmskaitļi ir nepāri.
- Densenes un sadalījums: pirmskaitļi kļūst retāki, pieaugot skaitļa lielumam. Matemātiski tas izpaužas caur pirmskaitļu teorēmu (Prime Number Theorem): skaitļu p(x), kas ir mazāki vai vienādi ar x, skaits asimptotiski uzvedas kā x / ln(x).
Kā pārbaudīt, vai skaitlis ir pirmskaitlis
- Vienkāršākais pamata paņēmiens — dalīšana (trial division): pārbaudīt dalāmību ar visiem pirmskaitļiem līdz kvadrātsaknei no skaitļa. Praktiski efektīvs maziem skaitļiem.
- Sitas (sievs): Sieve of Eratosthenes ir ātrs veids atrast visus pirmskaitļus līdz noteiktam robežskaitlim.
- Probabilistiskie testi: Miller–Rabin un citi ātri testi var ar ļoti mazu kļūdas varbūtību noteikt lielu skaitļu pirmskaitlību.
- Deterministiskie polinomiālā laika testi: AKS algoritms pierādāmi darbina polinomiālā laikā un nosaka, vai skaitlis ir pirmskaitlis bez nejaušības. Tomēr reālām pielietošanām bieži izmanto ātrākus heuristiskos un probabilistiskos algoritmus.
Pielietojumi
- Kriptogrāfijā (piem., RSA) lielu pirmskaitļu ģenerēšana un īpašības ir fundamentālas drošu atslēgu sistēmu darbībai.
- Algoritmi, teorētiskā datorzinātne un skaitļošanas problēmas bieži balstās uz pirmskaitļu īpašībām.
- Matemātiskajos pētījumos pirmskaitļi ir centrāla tēma ar gariem neatrisinātiem jautājumiem un aktīvu pētniecību.
Goldbaha minējums
Goldbaha minējums (Goldbach conjecture) ir slavenākā no klasiskajām neatrisinātajām problēmām saistībā ar pirmskaitļiem. Stāvoklis formulēts šādi:
- Spaida (stiprā) Goldbaha minējums: katrs pāra naturālais skaitlis lielāks par 2 ir izsakāms kā divu pirmskaitļu summa.
- Vāja (trīs) Goldbaha minējums: katrs nepāra naturālais skaitlis, kas ir lielāks par 5, ir izsakāms kā trīs pirmskaitļu summa. Šī vājā versija tika pilnībā pierādīta 2013. gadā (Haralds Helfgots).
Spēcīgā Goldbaha minējuma pilnīga pierādīšana joprojām nav atrisināta, tomēr to ir pārbaudījuši uz ļoti lieliem skaitļiem ar skaitļošanas palīdzību un iegūtas daudzas daļējas teorētiskas atziņas. Plašāku informāciju lasiet rakstā par Goldbaha minējumu.
Papildus piezīmes
- Ir daudzi speciāli klases pirmskaitļu pētījumi: Mersena pirmskaitļi, Fermā pirmskaitļi, Briesmas (Sophie Germain) pirmskaitļi u. c.
- Daudzas lielo pirmskaitļu meklēšanas iniciatīvas balstās uz sadarbības projektiem (piem., GIMPS), kas meklē arvien lielākus Mersena pirmskaitļus.
- Pirmskaitļu teorija joprojām ir aktīvs pētījumu lauks ar ciešu saikni uz analītisko teoriju, kombinatoriku un skaitļošanas matemātiku.
Šeit ir vēl viens veids, kā domāt par pirmskaitļiem. Skaitlis 12 nav pirmskaitlis, jo var izveidot taisnstūri, kura malas ir 4 un 3 garas. Šī taisnstūra laukums ir 12, jo ir izmantoti visi 12 klucīši. To nevar izdarīt ar 11. Neatkarīgi no tā, kā taisnstūris tiks sakārtots, vienmēr paliks pāri bloki, izņemot taisnstūri ar malu garumu 11 un 1. Tāpēc 11 ir jābūt pirmskaitlim.
Kā atrast mazus pirmskaitļus
Ir vienkārša metode, kā atrast pirmskaitļu sarakstu. To ir radījis Eratostēns. Tai ir nosaukums Eratostēna siets. Tajā tiek notverti skaitļi, kas nav pirmie (kā sietā), un caur to izlaiž pirmie skaitļi.
Metode darbojas ar skaitļu sarakstu un īpašu skaitli b, kas mainās metodes laikā. Metodes gaitā dažus skaitļus sarakstā apvelk ar aplīti, bet citus izsvītro. Katrs apvilktais skaitlis ir pirmskaitlis, un katrs svītrotais skaitlis ir salikts skaitlis. Sākumā visi skaitļi ir vienkārši: nav apvilkti un nav izsvītroti.
Metode vienmēr ir viena un tā pati:
- Uz papīra lapas uzraksti visus veselos skaitļus no 2 līdz pārbaudāmajam skaitlim. Nepierakstiet skaitli 1. Pārejiet uz nākamo soli.
- Sāciet ar b, kas vienāds ar 2. Pārejiet uz nākamo soli.
- Sarakstā apvelciet b. Pārejiet uz nākamo soli.
- Sākot no b, sarakstā saskaitiet vēl b un izsvītrojiet šo skaitli. Atkārtojiet vēl b skaitļu skaitīšanu un skaitļu svītrošanu līdz saraksta beigām. Pārejiet uz nākamo soli.
- (Piemēram: Ja b ir 2, apvelciet 2 un izsvītrojiet 4, 6, 8 un tā tālāk. Ja b ir 3, apvelciet 3 un izsvītrojiet 6, 9, 12 utt. 6 un 12 jau ir izsvītroti. Atkārtoti tos vēlreiz izsvītrojiet.)
- Palieliniet b par 1. Pārejiet uz nākamo soli.
- Ja b ir pārsvītrots, atgriezieties pie iepriekšējā soļa. Ja b ir sarakstā esošais numurs, kas nav svītrots, pārejiet uz 3. soli. Ja b nav sarakstā, pārejiet uz pēdējo soli.
- (Šis ir pēdējais solis.) Jūs esat gatavs. Visi pirmie skaitļi ir apvilkti un visi saliktie skaitļi ir pārsvītroti.
Piemēram, šo metodi var izmantot, izmantojot sarakstu ar skaitļiem no 2 līdz 10. Beigās tiks apvilkti skaitļi 2, 3, 5 un 7. Tie ir pirmie skaitļi. Savukārt 4, 6, 8, 9 un 10 tiks pārsvītroti. Tie ir saliktie skaitļi.
Lai atrastu ļoti lielus pirmskaitļus, šī metode vai algoritms aizņem pārāk daudz laika. Taču tā ir mazāk sarežģīta nekā metodes, ko izmanto ļoti lielu pirmskaitļu noteikšanai, piemēram, Fermata pirmskaitļa pārbaude (pārbaude, lai noteiktu, vai skaitlis ir vai nav pirmskaitlis) vai Millera-Rabina pirmskaitļa pārbaude.
Kādiem pirmskaitļiem izmanto pirmskaitļus
Pirmskaitļi ir ļoti svarīgi matemātikā un datorzinātnē. Tālāk ir sniegti daži reāli lietojumi. Ļoti garus skaitļus ir grūti atrisināt. Ir grūti atrast to pirmreizinātājus, tāpēc visbiežāk šifrēšanai un slepeniem kodiem izmanto tādus skaitļus, kas, iespējams, ir pirmreizēji.
- Lielākajai daļai cilvēku ir bankas karte, ar kuru viņi var saņemt naudu no sava konta, izmantojot bankomātu. Šī karte ir aizsargāta ar slepenu piekļuves kodu. Tā kā kods ir jāsaglabā slepenībā, to nevar saglabāt kartē atklātā tekstā. Lai kodu uzglabātu slepenā veidā, izmanto šifrēšanu. Šifrēšanā izmanto reizinājumus, dalījumus un lielu pirmskaitļu atlikumu atrašanu. Praksē bieži izmanto algoritmu, ko sauc par RSA. Tajā izmanto ķīniešu atlikuma teorēmu.
- Ja kādam e-pasta ziņojumam ir digitālais paraksts, tiek izmantots šifrēšana. Tādējādi tiek nodrošināts, ka neviens nevar viltot viņu e-pastu. Pirms parakstīšanas tiek izveidota ziņojuma hash vērtība. Pēc tam to apvieno ar digitālo parakstu, lai iegūtu parakstītu ziņojumu. Izmantotās metodes ir vairāk vai mazāk tādas pašas kā pirmajā gadījumā.
- Lielākās līdz šim zināmās pirmās vietas atrašana ir kļuvusi par sava veida sportu. Pārbaudīt, vai skaitlis ir pirmskaitlis, var būt sarežģīti, ja skaitlis ir liels. Lielākie zināmie pirmskaitļi parasti ir Mersena pirmskaitļi, jo visātrākais zināmais pirmskaitļa tests ir Lūkasa-Lehmera tests, kas balstās uz Mersena skaitļu īpašo formu. Grupa, kas meklē Mersena pirmskaitļus, ir šeit[1].
Jautājumi un atbildes
J: Kas ir pirmskaitlis?
A: Vienkāršais skaitlis ir dabiskais skaitlis, kuru nevar dalīt ar nevienu citu dabisko skaitli, izņemot 1 un sevi pašu.
J: Kāds ir mazākais saliktais skaitlis?
A: Mazākais saliktais skaitlis ir 4, jo 2 x 2 = 4.
J: Kādi ir nākamie pirmie skaitļi pēc 2?
A: Nākamie pirmie skaitļi pēc 2 ir 3, 5, 7, 11 un 13.
J: Vai ir lielākais pirmskaitlis?
A: Nē, nav lielākā pirmskaitļa. Vienkāršo skaitļu kopa ir bezgalīga.
J: Ko nosaka aritmētikas fundamentālā teorēma?
A: Aritmētikas fundamentālā teorēma nosaka, ka katru veselu pozitīvu skaitli var unikālā veidā ierakstīt kā pirmskaitļu reizinājumu.
J: Kas ir Goldbaha pieņēmums?
A: Goldbaha hipotēze ir neatrisināta problēma matemātikā, kas apgalvo, ka katru pāra skaitli, kas lielāks par divi, var izteikt kā divu pirmskaitļu summu.
J: Kurš pierakstīja pierādījumu, ka nav lielākā pirmskaitļa?
A.: Eiklīds ierakstīja pierādījumu, ka nav lielākā pirmskaitļa.
Meklēt