Kai kurios pirminių skaičių formos

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 × 1018, t.y. rado 95 676 260 903 887 607 pirminius skaičius (skaitykite apie teigiamą jo įrodymą).
Dabar didžiausias žinomas skaičius yra 257885161 - 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ų.
p10nskaič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, ...

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*21290000-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.

Proth pirminiai skaičiai
Tai pirminiai skaičiai p, tokie, kad p=k × 2n+1, kur n teigiamas sveikasis skaičius toks, kad 2n>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 × 213018586 1 (iš 3 918 990 skaitmenų, atrastas Seventeen or Bust projekte 2007 m.).

Atskirais Proto skaičių atvejais yra:
Kaleno skaičiai: n × 2n+1;

Kuleno ir Vudalo skaičiai

Kuleno skaičiai – natūriniai skaičiai, turintys pavidalą n x 2n - 1. Jie žymimi Cn 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 2n Ž 1. Jie žymimi Wn. 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 2n+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 Cn 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: 22n+1
Kiekvienas Ferma skaičiaus daliklis Fn, kai n>2, gali būti išreikštas k × 2n+2+1, tačiau nebūtinai galios nelygybė 2n+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 F5= 4294967297 yra sudėtinis. 1732 m. Oileris parodė, kad 641 dalo F5 (641 x 6700417). Įdomu, kad iki šiol (2015 m.) daugiau nerasta nė vieno pirminio Ferma skaičiaus (F5-F32 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 F20 irgi nėra pirminis.

Ferma laikais manyta, kad galioja kinų hipotezė, kad jei 2n º 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 2Fn º 2 (mod Fn) 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 2m (Gauso-Vancelio teorema - skaitykite apie Vancelio atradimus).

Kitos Ferma skaičių savybės:

  • Tarp skaičių 2n+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ą a2n + b2n

    Mersenne pirminiai skaičiai

    Tai pirminiai skaičiai, turintys formą Mn=2n-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 ž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 (GIMPS) dėka.
    2016 m. sausio 29 d. C. Cooper’is GIMPS tinkle rado 22 338 618 skaitmenų ilgio Marseno skaičių 274 207 281-1. O 2017 m. gruodžio 26 d. GIMPS'e dar didesnį skaičių 277,232,917 iš 23 249 425 skaitmenų (M77232917) surado JAV inžinierius J. Pace. 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.


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

    Pirminiai dvyniai
    Pirminiai skaičiai
    Harmoninės eilutės
    Aritmetikos pagrindai
    Ar įrodytas abc teiginys?
    Golbacho teiginio įrodymas?
    Hipatija – pirmoji matematikė
    Gauso skaičių teorijos kursas
    Pagrindinė aritmetikos teorema
    Didžiausias bendras daliklis
    Didžioji Ferma teorema
    Euklidas iš Aleksandrijos
    Alef paslaptis: begalybės paieškos
    Naujas pirminių skaičių dėsningumas
    Kaip išgyventi aukštesnius matavimus?
    Fundamentaliosios matematikos teoremos
    Pagrindinės algebrinės struktūros
    A. Puankarė. Mokslas ir hipotezė
    Proveržis skaičiuojant skaidinius
    Iniciatyva: Matematikos keliu
    Revoliucija mazgų teorijoje
    Parabolės lenktas likimas
    Santykis ir proporcija
    Beal'o hipotezė
    Dalyba iš nulio
    Algebros istorija
    Ferma taškas
    Erdvės formos
    Vartiklis