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.

Sophie Germain pirminiai skaičiai.
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, ...
Didžiausias žinomas yra 18543637900515 × 2666667 - 1 (iš 200701 skaitmenų, atrastas PrimeGrid projekte 2012 m.).

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).
Jie buvo paminėti filme „Įrodymas“ (2005), pagal David Auburn’o pjesę (1998).

Proth pirminiai skaičiai
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.).

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).
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).

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 VancelioA 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ⁿ

Mersenne pirminiai skaičiai
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, egzistuoja greiti algoritmai jų paieškai, tad ir šiuo metu didžiausi žinomi pirminiai skaičiai yra Mersenne pirminiai skaičiai.

Didžiausias 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 žinomą, 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 (GIMS) dėka.
Beje, 2016 m. sausio 29 d. C. Cooper’is paskelbė GIMPS kompiuterių tinklo dėka radęs Marseno skaičių 2^74 207 281-1, kuris yra 22 338 618 skaitmenų ilgio.

^*) Marenas Mersenas (Marin Mersenne, 1588-1648) – prancūzų pranciškonas, matematikas, fizikas, filofofas, 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.

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.

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