Pirminiai skaičiai

„Gal Dievas ir nežaidžia kauliukais Visatoje, tačiau kažkas keista vyksta su pirminiais skaičiais“, Paul Erdos (1913-1996).

Taip pat skaitykite: Naujas pirminių skaičių dėsningumas    

Pirminis skaičius – natūrinis (t.y. sveikas teigiamas) skaičius p, toks, kad p>1 ir neturi kitų sveikų teigiamų daliklių be 1 ir savęs paties (t.y. p). Pvz., 13 yra pirminis skaičius, nes dalijasi tik iš 1 ir 13, o 12 nėra pirminis, nes dalijasi ne tik iš 1 ir 12, bet ir iš 2, 3, 4, 6. Todėl 12 yra sudėtinis skaičius. Vienetas ( 1 ) yra specialus atvejis, nes jis nelaikomas nei pirminiu, nei sudėtiniu skaičiumi. Visi pirminiai skaičiai yra nelyginiai, išskyrus vienintelį atvejį – 2 yra pirminis skaičius (nors buvo metas, kai 2 nebuvo laikomas pirminiu skaičiumi).

Pirmieji pirminiai skaičiai yra 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... 2008 metais rugsėjo mėnesį Kalifornijos matematikai rado naują didžiausią, beveik 13 mln. skaitmenų ilgio pirminį skaičių 2^43 112 609 - 1, kuris yra Merseno skaičius. EFF^*) skyrė 100 tūkst. dolerių premiją už pirminio skaičiaus, didesnio nei 10⁷ suradimą.

Apie 300 m. pr.m.e. Euklidas parodė, kad pirminių skaičių yra begalinis skaičius (daugiau apie tai >>>>). Trumpai išdėstant, įrodymas būtų toksai:

Tarkim, kad jų skaičius baigtinis. Sudauginkime juos visus ir pridėkime 1. Gautas skaičius nesidalija nė iš vieno iš turimų pirminių skaičių. Vadinasi, privalo egzistuoti dar bent vienas pirminis skaičius, iš kurio jis dalintųsi.

Vėliau matematikai pateikė ir kitus begalinio pirminių skaičių kiekio įrodymus. Vienas jų, pateiktas Eulerio, parodo, kad visų skaičių, atvirkštinių pirminiams skaičiams, suma diverguoja. Teorema apie pirminių skaičių pasiskirstymą teigia, kad pirminių skaičių, mažesnių už n, kiekis (žymimas pi(n), auga pagal n / ln(n).

2 a. pr.m.e. graikų matematikas Eratostenas pasiūlė paprastą metodą pirminių skaičių nuo 2 iki n suradimui. Kitas būdas generuoti pirminius skaičius, tai imti laimingus skaičius (lucky numbers), kurie irgi yra atsijojami. Šie rodo kai kurias įdomias bendras su pirminiais skaičiais asimptotines savybes.

D. Zagier'as pakomentavo: „Yra du faktai apie pirminių skaičių pasiskirstymą < ... > Pirmasis, kad nepaisant jų elementaraus apibrėžimo ir statybinių blokų vaidmens natūriniams skaičiams, jie veši tarsi piktžolės tarp natūrinių skaičių ir atrodo, kad nėra jokio dėsningumo, o tik atsitiktinumas, todėl niekas negali nuspėti, kur išdygs kitas. Antrasis faktas dar labiau nustebina, nes teigia visiškai priešingai – kad pirminiai skaičiai pasirodo stebėtinai reguliariai, kad yra dėsniai, nusakantys jų elgseną, ir kad jie tų dėsningumų prisilaiko beveik kariška drausme“.

p_10ⁿ, kai n = 0, 1, 2, 3, .... turi skaitmenų: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... Tai pirminiai skaičiai: 2, 29, 541, 7919, 104729, 1299709, 15485863, 179424673, 2038074743, ....

Pirminiai skaičiai sudaryti iš eilės tvarka einančių skaitmenų (laikant, kad 0 eina po 9): 2, 3, 5, 7, 23, 67, 89, 4567, 78901, ...

Pirminiai, susidedantys iš skaitmenų, kurie yra pirminiais skaičiais: 23, 37, 53, 73, 223, 227, 233, 257, 277, 337, 353, 373, 523, 557, ... Tai viena iš Smarandache sekų.

Markas Daddon’as romane “Keistas šuns nutikimas naktį” (2003) protagonistas Christoferis skyrius numeravo pirminiais skaičiais. TV detektyviniame seriale „NUMB3RS” (Ska1č1a1) pirmojo sezono episode “Įtariamas pirminis skaičius” (2005) matematikos genijus Čarlis Epsas (Charlie Eppes) nustato, kad Etano dukra buvo pagrobta todėl, kad tasai buvo beįrodąs Rymano hipotezę, kas leistų nusikaltėliams „nulaužti“ Internete bet kokią apsaugą.

Bilas Geitsas „Kelias pirmyn“ rašė: „Kadangi tiek sistemos saugumas, tiek elektroninių pinigų saugumas priklauso nuo šifravimo, proveržis matematikoje ar kompiuterijoje, kuris pralaužtų kriptografijos sistemą būtų neganda. Akivaizdus matematinis proveržis galėtų būti lengvo didelių pirminių skaičių daugybos būdo sukūrimas“.

Kai kurios pirminių skaičių savybės

• Euklido lema: Jei p yra pirminis ir dalo ab, tai p dalo arba a, arba b;
• Mažoji Ferma teorema: Jei p - pirminis, o a - natūrinis, tai a^p - a dalosi iš p;
• Vilsono teorema: Natūrinis p > 1 yra pirminiu tada ir tik tada, kai p-1)! + 1 dalosi iš p;
• Bertrano postulatas: Natūriniam p > 1 egzistuoja pirminis p toks, kad n < p < 2n;
• Dirichlė teorema: Bet kuri aritmetinė progresija a, a+q, a+2q, ..., kai a, q > 1 - sveiki tarpusavyje pirminiai skaičiai, turi begalinį pirminių skaičių kiekį;
• Skaičių, atvirkštinių pirminiams, seka diverguoja. Daugiau apie tai >>>>>
• Bet kuris pirminis skaičius, didesnis už 3, pateikiamas pavidalu 6k+1 arba 6k-1, kur k tam tikras natūrinis skaičius;
• Jei p > 3 yra pirminis, tai p²-1 yra kartotinis 24;
• Žiedas Z_n yra lauku tik tada, kai n yra pirminis;
• Bet kurio lauko charakteristika – 0 arba pirminis skaičius;
• Jei G – baigtinė grupė iš pⁿ elementų, tai G turi p-osios eilės elementą;
• Jei G – baigtinė grupė ir pⁿ - maksimalus laipsnis p, kuris dalo |G|, tai G turi pⁿ laipsnio pogrupę, vadinamą jėgos pogrupe, be to jėgos pogrupių yra pk+1, tam tikram sveikam skaičiui k (Silovo teoremos).

Neišspręsti klausimai

Žinomiausius 5-ame tarptautiniame matematikų kongrese išvardijo Edmundas Landau.

1. Goldbacho problema: bet kuris lyginis skaičius didesnis už 2 gali būti pateiktas dviejų pirminių skaičių suma, o bet kuris nelyginis skaičius, didesnis už 5, gali būti pateiktas trijų pirminių skaičių suma;

2. Ar begalinė „pirminių dvynių“ (tokių, tarp kurių skirtumas lygus 2) aibė?

3. Ležandro hipotezė: Ar teisinga, kad tarp n² ir (n+1)² visada bus pirminis skaičius?

4. Ar begalinė pirminių skaičių, kurių pavidalas yra n² + 1, aibė?

Taip pat tebėra atviras klausimas apie pirminių skaičių begalinį skaičių daugelyje skaičių sekų: Fibonačio, Ferma ir t.t.

Pagrindinė aritmetikos teorema

Kiekvienas natūrinis skaičius, didesnis už 1, gali būti pateikiamas pirminių skaičių sandauga, beje, vieninteliu būdu.

Taigi, pirminiai skaičiai yra natūrinių skaičių „statybiniai blokai“. Skaičiaus išskaidymas į pirminių skaičių sandaugą vadinama faktorizacija. Šiuo metu dar nežinomi polinominiai faktorizacijos algoritmai, nors ir neįrodyta, kad toks algoritmas neegzistuoja. Faktorizacijos nustatymo sudėtingumu remiasi RSA šifravimo sistema.

Daugiau Pagrindinė aritmetikos teorema...

Ar skaičius pirminis?

Eratosteno, Sundaramo ir Atkino sietai pateikia paprastus metodus pradiniams pirminiams skaičiams surasti, tačiau praktikoje dažnai reikia patikrinti, ar žinomas skaičius yra pirminis. Yra daugybė polinomialinių metodų (testų), tačiau dauguma jų yra tikimybiniais (pvz., Milerio-Rabino testas) ir naudojami kriptografijos reikmėms. Tik 2002 m. buvo įrodyta, kad patikra polinomiškai įmanoma, tačiau pasiūlytas algoritmas pernelyg sudėtingas praktinėms reikmėms (Agrawal-Kayal-Saxena AKS testas).

Kai kurioms skaičių klasėms egzistuoja specializuoti testai, pvz., Marseno skaičiams patikrinti naudojamas Liuko-Lemero testas, o Ferma skaičių patikrinimui – Pepino testas.

Daugianario 
teigiamų reikšmių aibė sutampa su pirminių skaičių aibe, kai daugianario kintamieji perbėga per visus teigiamus sveikus skaičius. Tai Jurijaus Matiasevičiaus įrodyto bet kokios efektyviai išvardijamos aibės diofantiškumo atskiras atvejis.

---

Priedai

Donas Zagieras

Donas Zagieras (g. 1951 m., Don Zagier) – JAV matematikas, daugiausia dėmesio skiriantis skaičių teorijai, vienas iš Makso Planko Matematikos instituto Bonoje direktorių, Paryžiaus „College de France“ profesorius. 1987 m gavo Cole premiją.

Gimė Heidelberge, Vokietijoje, užaugo JAV, aukštąją mokyklą baigė būdamas 13 m., o po to 3 m. studijavo MIT, 16 m. gaudamas magistro laipsnį. Vadovaujamas F. Nirzebruch‘o iš Oksfordo parašė daktarinę disertaciją apie charakteristiškas klases (būdamas 21 m. amžiaus) ir vėliau bendradarbiavo su F. Nirzebruch‘u tyrinėdamas Hilberto modularinius paviršius.

Vienas žymesnių pasiekimų padarytas kartu su B. Gross. Jų formulė susieja sudėtingos elipsinės kreivės taške 1 L-serijos pirmąją išvestinę su tam tikru Heegner‘io tašku. Ši teorema daug kur pritaikoma. Tame tarpe ir Biirch ir Swinnerton-Dyer teiginiui bei yra pagrindas klasės skaičiaus uždavinio D. Goldfeld‘o sprendime.

Taip pat atrado trumpą ir elementarų Ferma teoremos apie dviejų kvadratų sumą įrodymą.

---

^*) EFF (Electronic Frontier Foundation) – 1990 m. John Perry Barlow ir Mitch Kapor JAV įkurta nekomercinė pilietinių laisvių grupė, siekianti apginti žmogaus teises atsižvelgiant į elektroninių priemonių naudojimą. Jos veikla apima žmogaus teises saugančių įstatymų palaikymą ir kūrimą, bendrą strategiją cenzūrai, bendruomenių įvairovę ir pan., suteikia gynybos paslaugas teismuose, organizuoja politines akcijas bei skleidžia informaciją. Išsilaiko iš narių ir korporacijų aukų. Įsikūrusi San Franciske; 2007 m. atsidarė EFF atstovybė Europoje. EFF yra įsteigusi premijas už pirminių skaičių, turinčių per 1 mln. (įteikta 2000 m. Nayan Hajratwala, GIMPS projekto dalyviui), 10 mln. (įteikta 2009 m. Kalifornijos universiteto Matematikos fakultetui, GIMPS dalyviui), 100 mln. ir 1 mlrd. skaitmenų, suradimą.

Literatūra:

1. B.C. Berndt. Ramanujan’s Theory of Prime Numbers// Ramanujan’s Notebooks, part IV, 1994
2. J. R. Chen. On the Distribution of Almost Primes in an Interval II// Sci. Sinica, 22, 1979
3. R. Ceandall, C. Pomerance. Prime Numbers, 2001
4. J. Derbyshire. Prime Obsession..., 2004
5. E.J. Ellison, F. Ellison. Prime Numbers, 1985
6. P.J. Giblin. Primes and Programming..., 1994
7. K. Ramachandra. Many Famous Conjectures on Primes...// Proc. Indian Nat. Sci. Acad., part A, 64, 1998
8. P. Ribenboim. The Little Book of Big Primes, 1994

Pirminiai dvyniai
Harmoninės eilutės
Hipatija – pirmoji matematikė
Pagrindinė aritmetikos teorema
Didžiausias bendras daliklis
Kaip supakuoti standžiau?
Didžioji Ferma teorema
Euklidas iš Aleksandrijos
Alef paslaptis: begalybės paieškos
A. Puankarė. Mokslas ir hipotezė
Naujas pirminių skaičių dėsningumas
Kaip išgyventi aukštesnius matavimus?
Iniciatyva: Matematikos keliu
Pagrindinės algebrinės struktūros
J. Tate: Abelio premijos laureatas
Surasta trilijonas trikampių
Puankarė problemos įrodymas
Matematika Egipte: Rindo papirusas ir kt.
Matematikai: Pjeras Ferma
Matematikai: Davidas Hilbertas
Revoliucija mazgų teorijoje
Hiparchas iš Rodo
Dalyba iš nulio
Pitagoro teorema
Algebros istorija
Erdvės formos
Vartiklio naujienos