Kai kurios pirminių skaičių formos. Vartiklis

Pirminiai skaičiai yra sveiki teigiami skaičiai, kurie nesidalija iš jokių kitų skaičių, išskyrus save ir 1. Dėl daugelio teiginių formulavimo paprastumo, 1 taip pat nelaikomas pirminiu skaičiumi. Vieninteliu lyginiu pirminiu skaičiumi yra 2. Pagal Euklido teoremą, yra begalinis kiekis pirminių skaičių. Jir yra tarsi „plytos“, iš kurių formuojami visi kiti sveikieji skaičiai.

Pirmieji pirminiai skaičiai yra 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, ... Golbacho teiginio patikrinimo projektas praneša, kad suskaičiavo visus pirminius skaičius, mažesnius už 4 × 10¹⁸, t.y. rado 95 676 260 903 887 607 pirminius skaičius (skaitykite apie teigiamą jo įrodymą).
Dabar didžiausias žinomas skaičius yra 2^57885161 - 1, kurį sudaro .17 425 170 skaitmenys. Jis yra Mersenne pirminis skaičius ir buvo atrastas GIMPS projekte 2013 m. vasarį.

Kai kuriuos pirminius skaičius galime išreikšti tam tikromis formomis. Tokie jų poaibiai sudaro atskiras sekas. Pvz., 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 skaičiai, 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ų.
p_10ⁿskaičiai, kai n = 0, 1, 2, 3, .... turi tokį kiekį 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, ....

Viena įdomi pirminių skaičių rūšis yra pirminiai dvyniai. Kitas specialias formas aprašysime šiame puslapyje.

Praimorialiniai pirminiai skaičiai

Tai pirminiai skaičiai, turintys p_n# Q 1 formą, kur p_n# yra p_n praimorialas^**).

Jie skirstomi į dvi sekas: A057704, skirtą p_n# - 1 ir A014545 - p_n# + 1. Dar nėra įrodyta, ar praimorialinių pirminių skaičių yra begalinis skaičius.

Didžiausias p_n# - 1 skaičius 3267113#-1 (1418398 skaitmenų ilgio) surastas 2021 m. rugsėjį – praėjus beveik 10 m. nuo ankstesnio (1098133#-1) suradimo ir jo patikrinimas truko beveik 1 mėn.. Tuo tarpu p_n# + 1 naujo didžiausio skaičiaus nerandama jau 20 m. (paskutinis, 392113#+1 iš 169966 skaitmenų) buvo rastas 2001 m. rugsėjį.

Beje, p_n# + 1 skaičiai (nebūtinai pirminiai; pvz., E₆ = 13#+1 = 30031 = 59*509) vadinami Euklido skaičiais. Beje, visiems n > 3, E_n paskutinis skaitmuo lygus 1, nes E_n dalosi iš 2 ir 5.

Tai pirminiai skaičiai p tokie, kad 2p+1 taip pat pirminis. Pirminiai skaičiai 2p+1 vadinami „saugiais“, nes jie susiję su „stipriais“ pirminiais skaičiais. Stiprūs pirminiai skaičiai q kriptografijoje yra tokie, kuriems q-1 ir q+1 turi didelius pirminius daliklius (tačiau skaičių teorijoje stiprių pirminių skaičių apibrėžimas kitoks: jai laikomi tokie, kurie didesni už aritmetinį vidurkį artimiausių jam pirminių – prieš ir po). „Saugiam“ q=2p+1 automatiškai q-1 turi didelį pirminį daliklį p.

Šie skaičiai pavadinti prancūzės matematikės Sofijos Žermen (Sophie Germain, 1776-1831) garbei. Ji juos panaudojo Ferma Didžiosios teoremos tyrinėjimuose. Ji ją (apie 1825 m.) įrodė laipsniams, esantiems pirminiais ir turintiems tokią formą (tam atvejui, kai laipsnis nedalo nė vieno iš lygties kintamųjų). Pirmieji Sophie Germain pirminiai skaičiai: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, ...

Teigiama, kad Sophie Germain pirminių skaičių yra begalinis kiekis, tačiau šis teiginys dar neįrodytas.

Jie panaudojami kriptografijoje bei pirminių skaičių požymio patikrinimui (AKS testas). Taip pat jie gali būti panaudoti pseudo-atsitiktinių skaičių generavimui.
Jie buvo paminėti filme „Įrodymas“ (2005), pagal David Auburn’o pjesę (1998), kuris yra apie mirusį protinės negalios kamuotą matematikos genijų, kurio studentas jo užrašuose randa neįtikėtiną įrodymą apie pirminius skaičius.

Pastaba: Redaktorius yra radęs Sophie Germain pirminį skaičių 3898169142525*2^1290000-1 (388342 skaitmenų). Atradimo metu (2018 m. vasario 20 d.) jis buvo didžiausias iš žinomų. Ir jūs galite prisijungti prie pirminių skaičių paieškos paskirstytų skaičiavimų projektuose.

Viferiko pirminiai skaičiai

p yra Viferiko pirminiu skaičiumi, jei p² dalija 2^p-1-1. Taip šie skaičiai susiejami su P. Ferma mažąja teorema, teigiančia, kad bet kuris nelyginis pirminis skaičius p dalija 2^p-1-1.
Vėliau buvo nustatyti ir kiti šių skaičių sąryšiai su pirminiais skaičiais ir kitais matematiniais objektais, tame tarpe ir kitų grupių pirminiais skaičiai (Marseno, Ferma), ypatingais pseudopirminių skaičių tipais ir kai kuriais Viferiko pirminių skaičių apibendrinimais. Ryšiai buvo išplėsti kai kurioms pirminių skaičių savybėms, skaičių laukui, abc hipotezei.

Arthur Wieferich’as 1909 m. įrodė, kad jei Ferma teoremos pirmasis atvejis (kai p nedalija x, y ir z) turi sprendinių nelyginiam laipsniui p, tai p tenkina kriterijų a^p-1=1 (mod p²), kai a=2. Kitaip sakant, jei x^p+^p+z^p=0 turi sprendinį, tai p tenkina sąlygą 2^p-1=1 (mod p²).

Nepaisant intensyvių paieškų, kol kas tėra žinomi tik du Viferiko pirminiai skaičiai: 1093 (atrastas 1913 m.) ir 3511 (atrastas 1922 m.) – tai A001220 seka. Įdomu, kad vienu mažesnis skaičius leidžia įtarti juos turint pasikartojančias dvejetaines sekas:
1092 = 10001000100₂
3510 = 110110110110₂

Jų retumas sukėlė susidomėjimą ir jiems „artimiems“ skaičiams, kurie apibrėžiami (su mažu |A|) kaip 2^(p-1)/2 º ±1 + Ap (mod p²).

Jūs irgi galite prisidėti prie jų paieškos prisijungę prie paskirstytų skaičiavimų PrimeGrid projekto (apie tai daugiau skaitykite >>>>>).

Tai pirminiai skaičiai p, tokie, kad p=k × 2ⁿ+1, kur n teigiamas sveikasis skaičius toks, kad 2ⁿ>k.

Šie skaičiai pavadinti Fransua Proto (Francois Proth, 1852 – 1879) garbei. Jų patikrinimas galimas remiantis Proto teorema. Pirmieji Proth pirminiai skaičiai: 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, … Didžiausias žinomas yra 19249 × 2^13018586 1 (iš 3 918 990 skaitmenų, atrastas Seventeen or Bust projekte 2007 m.).

Tai pirminiai skaičiai, kuris nelygūs jokio mažesnio pirminius skaičiaus ir dvigubo sveiko skaičiaus kvadrato sumai, t.y. jų forma nėra p+b². Pirmieji tokie skaičiai yra 2, 3, 17, 137, 227, 977, 1187, … Pavadinti M.A. Šterno (1807-1894), kuris domėjosi tokiais skaičiais, garbei.

Kuleno ir Vudalo skaičiai

Kuleno skaičiai – natūriniai skaičiai, turintys pavidalą n x 2ⁿ - 1. Jie žymimi C_n ir yra atskiras Proto skaičių atvejis. Juos pirmąkart 1905-ais išnagrinėjo airių matematikas Dž. Kulenas (J. Cullen, 1867-1933).

Vudalo skaičiai – natūriniai skaičiai, turintys pavidalą n x 2ⁿ - 1. Jie žymimi W_n. Juos pirmąkart 1917 m. nagrinėjo britai A.J.C. Cunningham’as and H.J. Woodall’as.

1976 m. Ch. Hooley įrodė, kad pirminių Kuleno skaičių tankis mažėja, t.y., beveik visi Kuleno skaičiai yra sudėtiniai. H. Suyama tą teiginį apibendrino atvejui
n x 2^n+a + b, kur a ir b yra sveikieji skaičiai (taigi, apimant ir Vudalo skaičius; tad jie kartais vadinami kito tipo Kuleno skaičiais).
Yra žinoma vos keliolika pirminių Kuleno skaičių: kai n=1, 141, 4713, 5795, 6611, …, 6679881 (paskutinį 2009 m. rugpjūtį atrado paskirstytų skaičiavimų PrimeGrid projekte).
Taip pat ir pirminių Vudalo skaičių: kai n= 2, 3, 6, 30, 75, 81, 115, 123, 249, 362, ..., 3752948 (paskutinį 2007 m. atrado paskirstytų skaičiavimų PrimeGrid projekte).
Didžiausias apibendrintas Kuleno skaičius (n x Bⁿ + 1) ten pat surastas 2021 m. rugpjūtį bazei B=73 ir n=2525532: 2525532*7^32525532+1 (4 705 888 skaitmenų).

Nėra įrodyta, tačiau manoma, kad yra be galo daug pirminių Kuleno ir Vudalo skaičių.

Savybės:

Kuleno skaičius C_n yra dalus iš p = 2n – 1, jei p yra pirminis skaičius formatu 8k – 3, - tai seka iš mažosios Ferma teoremos.

Ferma skaičiai: 2^2ⁿ+1
Kiekvienas Ferma skaičiaus daliklis F_n, kai n>2, gali būti išreikštas k × 2ⁿ⁺²+1, tačiau nebūtinai galios nelygybė 2ⁿ⁺²>k (Oileris, Liuka; 1878).

Ferma skaičiai

1640 m. laiške kolegoms (Paskaliui, Hiugensui, Brouckner‘iui, Wallis‘ui ir kt.) P. Ferma pasiūlė įrodyti, kad visi skaičiai, dabar vadinami Ferma skaičiais, yra pirminiai. Bet jis neteigė, kad pats yra tai įrodęs (pvz., 1640 m. rugpjūtį rašė: „Je n'en ai pas la demonstration exacte...“).

Ferma skaičiai gali būti ir pirminiai, ir sudėtiniai, nors pats P. Ferma 1640 m. spėjo, kad jie visi yra pirminiai. Jei skaičius yra pirminis, jis vadinamas Ferma pirminiu skaičiumi. Iš tikrųjų, Ferma skaičiai, kai k = 0, 1, 2, 3, 4, yra pirminiai (3, 5, 17, 257 ir 65537), o skaičius F₅= 4294967297 yra sudėtinis. 1732 m. Oileris parodė, kad 641 dalo F₅ (641 x 6700417). Įdomu, kad iki šiol (2015 m.) daugiau nerasta nė vieno pirminio Ferma skaičiaus (F₅-F₃₂ yra sudėtiniai), nors 1844 m. Eizenšteinas ir teigė įrodęs, kad yra begalinis skaičius pirminių Ferma skaičių. Pvz., 1987 m. Cray-2 superkompiuteris per 10 parų parodė, kad F₂₀ irgi nėra pirminis.

Ferma laikais manyta, kad galioja kinų hipotezė, kad jei 2ⁿ º 2 (mod n), tai n yra pirminis skaičius, tačiau ji iš tikro nėra teisinga (pvz., kai n=341), tačiau būtent ji galėjo paskatinti P. Ferma manyti, kad 2^F_n º 2 (mod F_n) visiems n.

Nėra žinoma, ar Ferma pirminių skaičių (kaip ir Merseno) yra be galo daug, ar tik baigtinis skaičius. Ferma skaičiai taip pat yra susiję su kitais matematikos uždaviniais. Pvz.,, taisyklingą n-kampį galima nubrėžti su skriestuvu ir liniuote tik tada, kai n yra Ferma pirminis skaičius arba skiriasi nuo tokio skaičiaus daugikliu 2^m (Gauso-Vancelio teorema - skaitykite apie Vancelio atradimus).

Kitos Ferma skaičių savybės:

Tarp skaičių 2ⁿ+1 pirminiais gali būti tik Ferma skaičiai;

Ferma skaičiai, kai n > 1, baigiasi 7;

Ferma skaičiai negali būti tobulaisiais skaičiais;

Ferma skaičiai negali būti Vifericho pirminiais skaičiai

Apibendrintieji Ferma skaičiai (pagal Ribenboimą) turi pavidalą a^2ⁿ + b^2ⁿ

Tai pirminiai skaičiai, turintys formą M_n=2ⁿ-1. Pirmieji 9-ji yra: 3, 7, 31, 127, 8191, 13071, 524287, 2147483647, 2305843009213693951...
Jie pavadinti juos tyrinėjusio 17 a. prancūzų vienuolio Marin Mersenne^*) (1588-1648) garbei. Dar nėra įrodyta, ar Mersenne pirminių skaičių kiekis begalinis. Jų privalumas tas, kad egzistuoja greiti algoritmai jų paieškai, tad ir šiuo metu didžiausi žinomi pirminiai skaičiai yra Mersenne pirminiai skaičiai.
Istoriškai Marseno skaičiai naudojami kompiuterių aparatinei daliai tikrinti. Taip 2016 m. buvo aptiktas defektas „Intel“ Skylake procesoriuje...

Didžiausias (tuo metu) 47-asis pagal dydį Merseno skaičius buvo atrastas 2008 m. rugpjūčio 23 d. ir jis yra sudarytas iš 12.978.189 skaitmenų (46-ąjį pagal dydį atrado 2009 m. balandžio 12 d.). Tačiau nėra žinoma, kad tarp 40-ojo ir 47-ojo nėra daugiau dar neatrastų Merseno skaičių. Nuo 1997 m. visi nauji Merseno skaičiai (nuo 35-o iki 47-o) atrasti paskirstyto skaičiavimo projekto internete (GIMPS) dėka.
2016 m. sausio 29 d. C. Cooper’is GIMPS tinkle rado 22 338 618 skaitmenų ilgio Marseno skaičių 2^74 207 281-1. O 2017 m. gruodžio 26 d. GIMPS'e dar didesnį skaičių 2^77,232,917 iš 23 249 425 skaitmenų (M77232917) surado JAV inžinierius J. Pace. 2021 m. liepą didžiausiu buvo 2^82,589,933 (M82589933; 24 862 048 skaitmenys) atrastas 2018 m. gruodžio 7 d. IT specialisto iš JAV Patrick Laroche. Daugiau apie paskirstytus skaičiavimus >>>>>

Oficialus skaičiaus žymuo priskiriamas pagal atradimo laiką. Tačiau kuriozas įvyko su M4253, nes 1961 m. amerikiečių matematikas A. Hurwitz’ius peržiūrinėjo listingą iš galo į pradžią ir M4423 pamatė keliomis sekundėmis anksčiau už M4253. Su ankstesniu Marseno skaičiumi taip pat įvyko nesusipratimas: kompiuteris jį paskaičiavo 2015 m.rugsėjo 17 d., tačiau dėl klaidos el. laiškas nebuvo išsiųstas – ir jisai išbuvo nepastebėtas iki 2016 m. sausio 7 d.

Pirminiai skaičiai naudojami kriptografijoje, tačiau šie yra tokie dideli, kad praktikoje nepritaikomi (gal kvantinė kriptografija įstengs?!).
Ir vis tik kodėl reikia milijono skaitmenų pirminių skaičių?
Godfrey Harold Hardy išsireiškė: „Grynoji matematika bendrai imant yra gerokai naudingesnė nei pritaikoma. Labiausiai naudinga yra technika, o matematinė technika labiausiai išreiškiama per grynąją matematiką“. Tad visai nesvarbu, ar tokie dideli pirminiai skaičiai bus pritaikomi kriptografijoje ar kur kitur.

^*) Marenas Mersenas (Marin Mersenne, 1588-1648) – prancūzų pranciškonas, matematikas, fizikas, filosofas, teologas, muzikos teoretikas. Labiausiai pasižymėjo kaip mokslo koordinatorius, vesdamas aktyvų susirašinėjimą su beveik visais iškiliais to meto mokslininkais (korespondencija sudarė 17 tomų). Apie P. Ferma atradimus praktiškai težinome iš jų susirašinėjimo. Bet buvo ir aktyvus eksperimentatorius, bandymais patikrinęs ir padėjęs atrasti naujus gamtos dėsnius.

^**) Praimorialas (angl. primorial) – į faktorialą panaši funkcija, žymima #, tik vietoje natūrinių skaičių dauginami pirminiai skaičiai, pvz., 13# = 2*3*5*7*11*13 =30030. Terminą 1987 m. įvedė amerikiečių inžinierius H. Dubneris (1928-2019).

Priedas

Artimos pirminiams skaičių atmainos

Linksmieji skaičiai

Jie gaunami panašiai kaip pirminiai skaičiai „išsijojami’ naudojant Eratosteno rėtį, tik su „maža“ pataisa.

1. Išrašome visus teigiamus skaičius;
2. Išbraukiame 1;
3. Paliekame pirmą likusį mažiausią skaičių p (p=2);
4. Išbraukiam kiekvieną p-ąjį skaičių tolesnėje sekoje (4, 6, 8, …);
5. Vėl paliekame kitą likusį mažiausią skaičių p (p=3);
6. Vėl išbraukiam kiekvieną p-ąjį skaičių tolesnėje sekoje sudarytą iš anksčiau „išgyvenusių“ skaičių (9, 15, 21, ...);
7. Vėl kartojame procesą (p=5: 19, 35, 49...; p=7: 31, 59, 85... ir t.t.) ....

Gauname „linksmųjų“ skaičių seką (A003309):
2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, ....

Tarp „linksmųjų skaičių“ yra ne tik pirminių, bet ir sudėtinių skaičių, pvz., sudėtiniais jų tarpe yra (seka A192504; kai linksmųjų pirminių seka yra A192503):
25, 77, 91, 115, 119, 121, 143, 161, 175, 209,…

Laimingieji skaičiai

Jie gaunami sijojant dar viena rėčio modifikacija:

1. Išvardinkite visus nelyginius skaičius;
2. Imame sekantį p iš išlikusių skaičių (p=3);
3. Šaliname kitą iš išlikusių (pradedant 5) ir toliau kas p-tą (5, 11, 17, 23…)
4. Kartojame procesą (p=7: 19, 31…;

Gauname laimingųjų skaičių seką (seka A000959; vien pirminių laimingųjų seka yra A031157):
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73...

Šie skaičiai įvesti 1956 m. straipsnyje

V. Gardiner, R. Lazarus, N. Metropolis, S. Ulam. On certain sequences of integers defined by sieves// Mathematics Magazine 1956, 29 (3): p.117–122

Šis rėtis vadinamas „Jozefo Flavijaus rėčiu“, nes jis panašus į išskaičiuotės žaidimą Jozefo uždavinyje [Juozapas Flavijus – mūsų eros pradžios žydų istorikas].

Laimingieji skaičiai turi kai kurias savybes, panašias į pirminių skaičių (pvz., panašų asimptotinį elgesį; panašų „laimingųjų dvynių“ pasiskirstymą ir kt.)