Pirminiai skaičiai: istorija ir faktai. Kaip rasti pirminius skaičius

Teorema.

Pirminių skaičių yra begalinis skaičius.

Įrodymas.

Tarkime, kad taip nėra. Tai yra, tarkime, kad yra tik n pirminių skaičių ir šie pirminiai skaičiai yra p 1, p 2, ..., p n. Parodykime, kad visada galime rasti pirminį skaičių, kuris skiriasi nuo nurodytųjų.

Apsvarstykite skaičių p lygų p 1 · p 2 ·… · p n +1. Akivaizdu, kad šis skaičius skiriasi nuo kiekvieno pirminio skaičiaus p 1, p 2, ..., p n. Jei skaičius p yra pirminis, tai teorema įrodyta. Jei šis skaičius yra sudėtinis, tai pagal ankstesnę teoremą yra šio skaičiaus pirminis daliklis (žymime jį p n+1). Parodykime, kad šis daliklis nesutampa nė su vienu iš skaičių p 1, p 2, ..., p n.

Jei taip nebūtų, tada sandauga p 1 ·p 2 ·…·p n pagal dalomumo savybes būtų padalinta iš p n+1. Tačiau skaičius p taip pat dalijasi iš p n+1, lygus sumai p 1 ·p 2 ·…·p n +1. Iš to seka, kad p n+1 turi padalyti antrąjį šios sumos narį, kuris yra lygus vienetui, bet tai neįmanoma.

Taigi buvo įrodyta, kad visada galima rasti naują pirminį skaičių, kuris nėra įtrauktas į jokį iš anksto nustatytų pirminių skaičių skaičių. Todėl pirminių skaičių yra be galo daug.

Taigi dėl to, kad pirminių skaičių yra be galo daug, sudarydami pirminių skaičių lenteles visada apsiribojate iš viršaus į kokį nors skaičių, dažniausiai 100, 1000, 10000 ir t.t.

Eratosteno sietelis

Dabar aptarsime pirminių skaičių lentelių kūrimo būdus. Tarkime, kad turime sudaryti pirminių skaičių lentelę iki 100.

Akivaizdžiausias šios problemos sprendimo būdas yra nuosekliai tikrinti teigiamus sveikuosius skaičius, pradedant nuo 2 ir baigiant 100, ar nėra teigiamo daliklio, kuris yra didesnis nei 1 ir mažesnis už tikrinamą skaičių (iš mums žinomų dalijamumo savybių kad daliklio absoliuti reikšmė neviršytų absoliučios dividendo vertės, ne nulis). Jei tokio daliklio nerandama, tada tikrinamas skaičius yra pirminis, ir jis įrašomas į pirminių skaičių lentelę. Jei toks daliklis randamas, tai tikrinamas skaičius yra sudėtinis, jis NĖRA įrašytas į pirminių skaičių lentelę. Po to pereinama prie kito skaičiaus, kuris panašiai tikrinamas, ar nėra daliklio.

Apibūdinkime kelis pirmuosius žingsnius.

Pradedame nuo 2 skaičiaus. Skaičius 2 neturi teigiamų daliklių, išskyrus 1 ir 2. Todėl tai paprasta, todėl įvedame jį į pirminių skaičių lentelę. Čia reikėtų pasakyti, kad 2 yra mažiausias pirminis skaičius. Pereikime prie numerio 3. Galimas teigiamas jo daliklis, išskyrus 1 ir 3, yra skaičius 2. Bet 3 nesidalija iš 2, todėl 3 yra pirminis skaičius, jį taip pat reikia įtraukti į pirminių skaičių lentelę. Pereikime prie 4 numerio. Jo teigiami dalikliai, išskyrus 1 ir 4, gali būti skaičiai 2 ir 3, patikrinkime juos. Skaičius 4 dalijasi iš 2, todėl 4 yra sudėtinis skaičius ir jo nereikia įtraukti į pirminių skaičių lentelę. Atminkite, kad 4 yra mažiausias sudėtinis skaičius. Pereikime prie numerio 5. Tikriname, ar bent vienas iš skaičių 2, 3, 4 yra jo daliklis. Kadangi 5 nesidalija iš 2, 3 ar 4, tai jis yra pirminis ir turi būti užrašytas pirminių skaičių lentelėje. Tada pereinama prie skaičių 6, 7 ir tt iki 100.

Šis pirminių skaičių lentelės sudarymo metodas toli gražu nėra idealus. Vienaip ar kitaip, jis turi teisę egzistuoti. Atkreipkite dėmesį, kad naudojant šį sveikųjų skaičių lentelės sudarymo būdą galite naudoti dalijamumo kriterijus, kurie šiek tiek pagreitins daliklių paieškos procesą.

Yra patogesnis būdas sukurti pirminių skaičių lentelę, vadinamą. Pavadinime esantis žodis „sietas“ nėra atsitiktinis, nes šio metodo veiksmai padeda tarsi „persijoti“ sveikus skaičius ir didelius vienetus per Eratosteno sietą, kad būtų atskirti paprasti nuo sudėtinių.

Parodykime veikiantį Eratosteno sietą, kai sudarome pirminių skaičių lentelę iki 50.

Pirmiausia užrašykite skaičius 2, 3, 4, ..., 50.

Pirmasis parašytas skaičius 2 yra pirminis. Dabar nuo 2 skaičiaus paeiliui judame į dešinę dviem skaičiais ir išbraukiame šiuos skaičius, kol pasieksime sudaromos skaičių lentelės pabaigą. Taip bus išbraukti visi skaičiai, kurie yra dviejų kartotiniai.

Pirmasis skaičius po 2, kuris nėra perbrauktas, yra 3. Šis skaičius yra pirminis. Dabar nuo 3 skaičiaus paeiliui pereiname į dešinę trimis skaičiais (atsižvelgiant į jau perbrauktus skaičius) ir juos perbraukiame. Taip bus išbraukti visi skaičiai, kurie yra trijų kartotiniai.

Pirmasis skaičius po 3, kuris nėra perbrauktas, yra 5. Šis skaičius yra pirminis. Dabar nuo skaičiaus 5 nuosekliai pereiname į dešinę 5 skaičiais (taip pat atsižvelgiame į anksčiau perbrauktus skaičius) ir juos perbraukiame. Taip bus išbraukti visi skaičiai, kurie yra penkių kartotiniai.

Toliau išbraukiame skaičius, kurie yra 7 kartotiniai, tada 11 kartotiniai ir pan. Procesas baigiasi, kai nebėra skaičių, kuriuos reikia perbraukti. Žemiau yra užpildyta pirminių skaičių iki 50 lentelė, gauta naudojant Eratosteno sietą. Visi neperbraukti skaičiai yra pirminiai, o visi perbraukti skaičiai yra sudėtiniai.

Taip pat suformuluokime ir įrodykime teoremą, kuri pagreitins pirminių skaičių lentelės sudarymo procesą naudojant Eratosteno sietą.

Teorema.

Mažiausias teigiamas sudėtinio skaičiaus a daliklis, kuris skiriasi nuo vieneto, neviršija , kur yra iš a .

Įrodymas.

Raide b pažymėkime mažiausią sudėtinio skaičiaus a daliklį, kuris skiriasi nuo vieno (skaičius b yra pirminis, kaip matyti iš teoremos, įrodytos pačioje ankstesnės pastraipos pradžioje). Tada yra sveikasis skaičius q, kad a=b·q (čia q yra teigiamas sveikasis skaičius, kuris išplaukia iš sveikųjų skaičių daugybos taisyklių), ir (b>q sąlyga, kad b yra mažiausias a daliklis, pažeidžiama , nes q taip pat yra skaičiaus a daliklis dėl lygybės a=q·b ). Padauginus abi nelygybės puses teigiamu ir sveikuoju skaičiumi, didesniu už vieną (mums leidžiama tai padaryti), gauname , Iš kurių ir .

Ką mums duoda įrodyta teorema apie Eratosteno sietą?

Pirma, sudėtinių skaičių, kurie yra pirminio skaičiaus b kartotiniai, perbraukimas turėtų prasidėti skaičiumi, lygiu (tai išplaukia iš nelygybės). Pavyzdžiui, skaičių, kurie yra dviejų kartotiniai, perbraukimas turėtų prasidėti skaičiumi 4, trijų kartotiniai - skaičiumi 9, penkių kartotiniai - skaičiumi 25 ir pan.

Antra, pirminių skaičių lentelės sudarymas iki skaičiaus n naudojant Eratosteno sietą gali būti laikomas baigtu, kai visi sudėtiniai skaičiai, kurie yra pirminių skaičių kartotiniai, neviršija . Mūsų pavyzdyje n=50 (kadangi mes sudarome pirminių skaičių lentelę iki 50), todėl Eratosteno sietas turėtų pašalinti visus sudėtinius skaičius, kurie yra pirminių skaičių 2, 3, 5 ir 7 kartotiniai. neviršija aritmetinės kvadratinės šaknies iš 50. Tai reiškia, kad mums nebereikia ieškoti ir išbraukti skaičių, kurie yra pirminių skaičių 11, 13, 17, 19, 23 kartotiniai ir tt iki 47, nes jie jau bus nubraukti kaip mažesnių pirminių skaičių 2 kartotiniai. , 3, 5 ir 7 .

Ar šis skaičius pirminis ar sudėtinis?

Kai kurioms užduotims reikia išsiaiškinti, ar nurodytas skaičius yra pirminis, ar sudėtinis. Apskritai ši užduotis toli gražu nėra paprasta, ypač skaičiams, kurių rašymą sudaro daug simbolių. Daugeliu atvejų turite ieškoti konkretaus būdo, kaip tai išspręsti. Tačiau mes stengsimės duoti kryptį minčių traukiniui paprastiems atvejams.

Žinoma, galite pabandyti naudoti dalijamumo testus, kad įrodytumėte, jog nurodytas skaičius yra sudėtinis. Jei, pavyzdžiui, koks nors dalijimosi testas rodo, kad tam tikras skaičius dalijasi iš kokio nors teigiamo sveikojo skaičiaus, didesnio už vienetą, tada pradinis skaičius yra sudėtinis.

Pavyzdys.

Įrodykite, kad 898 989 898 989 898 989 yra sudėtinis skaičius.

Sprendimas.

Šio skaičiaus skaitmenų suma lygi 9·8+9·9=9·17. Kadangi skaičius, lygus 9·17, dalijasi iš 9, tai pagal dalumą iš 9 galime teigti, kad pradinis skaičius taip pat dalijasi iš 9. Todėl jis yra sudėtinis.

Reikšmingas šio metodo trūkumas yra tas, kad dalijamumo kriterijai neleidžia įrodyti skaičiaus pirmumo. Todėl bandydami skaičių, kad pamatytumėte, ar jis pirminis, ar sudėtinis, turite elgtis kitaip.

Logiškiausias būdas yra išbandyti visus galimus tam tikro skaičiaus daliklius. Jei nė vienas iš galimų daliklių nėra tikrasis tam tikro skaičiaus daliklis, tada šis skaičius bus pirminis, priešingu atveju jis bus sudėtinis. Iš teoremų, įrodytų ankstesnėje pastraipoje, išplaukia, kad tam tikro skaičiaus a daliklių reikia ieškoti tarp pirminių skaičių, neviršijančių . Taigi duotą skaičių a galima nuosekliai padalyti iš pirminių skaičių (kurie patogiai paimti iš pirminių skaičių lentelės), bandant rasti skaičiaus a daliklį. Jei rastas daliklis, tada skaičius a yra sudėtinis. Jei tarp pirminių skaičių, neviršijančių , nėra skaičiaus a daliklio, tada skaičius a yra pirminis.

Pavyzdys.

Skaičius 11 723 paprastas ar sudėtinis?

Sprendimas.

Sužinokime, iki kokio pirminio skaičiaus gali būti skaičiaus 11 723 dalikliai. Norėdami tai padaryti, įvertinkime.

Gana akivaizdu, kad , nuo 200 2 = 40 000 ir 11 723<40 000 (при необходимости смотрите статью skaičių palyginimas). Taigi galimi pirminiai koeficientai 11 723 yra mažesni nei 200. Tai jau labai palengvina mūsų užduotį. Jei to nežinotume, turėtume pereiti visus pirminius skaičius ne iki 200, o iki skaičiaus 11 723.

Jei pageidaujate, galite įvertinti tiksliau. Kadangi 108 2 = 11 664 ir 109 2 = 11 881, tada 108 2<11 723<109 2 , следовательно, . Taigi bet kuris pirminis skaičius, mažesnis nei 109, potencialiai yra pirminis duoto skaičiaus 11 723 koeficientas.

Dabar skaičių 11 723 iš eilės padalinsime į pirminius skaičius 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 , 103 , 107 . Jei skaičius 11 723 yra padalintas iš vieno iš užrašytų pirminių skaičių, jis bus sudėtinis. Jei jis nesidalija iš nė vieno užrašyto pirminio skaičiaus, tada pirminis skaičius yra pirminis.

Viso šio monotoniško ir monotoniško dalijimosi proceso neaprašysime. Iš karto pasakykime, kad 11 723

pirminis skaičius

natūralusis skaičius, didesnis už vienetą ir neturintis kitų daliklių, išskyrus save ir vienetą: 2, 3, 5, 7, 11, 13... Pirminių skaičių skaičius yra begalinis.

pirminis skaičius

teigiamas sveikasis skaičius, didesnis už vienetą, kuris neturi daliklių, išskyrus save ir vieną: 2, 3, 5, 7, 11, 13,... Skaičiaus sąvoka yra esminė tiriant natūraliųjų (teigiamų sveikųjų skaičių) dalijamumą ) skaičiai; Būtent, pagrindinė dalijimosi teorijos teorema nustato, kad kiekvienas teigiamas sveikas skaičius, išskyrus 1, yra vienareikšmiškai išskaidomas daugelio skaičių sandaugoje (į veiksnių eilę neatsižvelgiama). Pirminių skaičių yra be galo daug (šis pasiūlymas buvo žinomas senovės graikų matematikams; jo įrodymas yra 9-ojoje Euklido elementų knygoje). Natūraliųjų skaičių dalijimosi klausimai, taigi ir su pirminiais skaičiais susiję klausimai, svarbūs tiriant grupes; visų pirma, grupės su baigtiniu elementų skaičiumi struktūra yra glaudžiai susijusi su būdu, kuriuo šis elementų skaičius (grupės tvarka) išskaidomas į pirminius veiksnius. Algebrinių skaičių teorija nagrinėja algebrinių sveikųjų skaičių dalijimosi klausimus; Dalinio skaičiaus samprata pasirodė esanti nepakankama dalijimosi teorijai sukurti, todėl buvo sukurta idealo samprata. P. G. L. Dirichlet 1837 metais nustatė, kad aritmetinėje progresijoje a + bx, kai x = 1, 2,... su pirminiais sveikaisiais skaičiais a ir b yra be galo daug pirminių skaičių. Nustatyti pirminių skaičių pasiskirstymą natūralioje skaičių serijoje yra labai sunku. problema skaičių teorijoje. Jis suformuluotas kaip funkcijos p(x), kuri žymi dalinių skaičių, neviršijančių teigiamo skaičiaus x, asimptotinės elgsenos tyrimas. Pirmieji rezultatai šia kryptimi priklauso P. L. Čebyševui, kuris 1850 m. įrodė, kad yra dvi konstantos a ir A, kad ═< p(x) < ═при любых x ³ 2 [т. е., что p(х) растет, как функция ]. Хронологически следующим значительным результатом, уточняющим теорему Чебышева, является т. н. асимптотический закон распределения П. ч. (Ж. Адамар, 1896, Ш. Ла Валле Пуссен, 1896), заключающийся в том, что предел отношения p(х) к ═равен

Vėliau didelės matematikų pastangos buvo nukreiptos į dažnio koeficiento pasiskirstymo asimptozės dėsnio išaiškinimą, dažnio koeficiento pasiskirstymo klausimai nagrinėjami tiek elementariais, tiek matematinės analizės metodais. Ypač vaisingas yra tapatybės naudojimu pagrįstas metodas

(produktas apima visus P. h. p = 2, 3,...), pirmą kartą nurodė L. Euleris; ši tapatybė galioja visiems kompleksiniams s, kurių realioji dalis yra didesnė už vienybę. Remiantis šia tapatybe, P. skaičių pasiskirstymo klausimai vedami į specialios funkcijos ≈ zeta x(s), nustatytos Res > 1 pagal eilutę, tyrimą.

Šią funkciją Čebyševas naudojo pirminių skaičių paskirstymo realiems s klausimams; B. Riemann atkreipė dėmesį į x(s) tyrimo svarbą kompleksinėms s reikšmėms. Riemannas iškėlė hipotezę, kad visos lygties x(s) = 0 šaknys, esančios dešinėje pusplokštumoje, turi realiąją dalį, lygią 1/

Ši hipotezė iki šiol neįrodyta (1975 m.); jo įrodymas labai daug nuveiktų sprendžiant pirminių skaičių skirstinio problemą.Pirminių skaičių skirstymo klausimai glaudžiai susiję su Goldbacho problema, vis dar neišspręsta „dvynių“ problema ir kitomis analitinės skaičių teorijos problemomis. „Dvynių“ uždavinys yra išsiaiškinti, ar P. skaičių, besiskiriančių 2 (pvz., 11 ir 13), skaičius yra baigtinis ar begalinis. P. skaičių lentelės, esančios pirmuose 11 milijonų natūraliųjų skaičių, rodo labai didelių „dvynių“ buvimą (pavyzdžiui, 10006427 ir 10006429), tačiau tai nėra jų skaičiaus begalybės įrodymas. Už sudarytų lentelių ribų yra žinomi atskiri daliniai skaičiai, turintys paprastą aritmetinę išraišką [pvz., nustatyta (1965), kad 211213 ≈1 yra reguliarus skaičius; jis turi 3376 skaitmenis].

Lit.: Vinogradov I.M., Skaičių teorijos pagrindai, 8 leid., M., 1972; Hasse G., Paskaitos apie skaičių teoriją, vert. iš vokiečių kalbos, M., 1953 m. Ingham A.E., Pirminių skaičių pasiskirstymas, vert. iš anglų k., M. ≈ L., 1936 m. Prahar K., Pirminių skaičių pasiskirstymas, vert. iš vokiečių kalbos, M., 1967 m. Trost E., Pirminiai skaičiai, vertimas, iš vokiečių kalbos, M., 1959 m.

Vikipedija

pirminis skaičius

pirminis skaičius– natūralusis skaičius, turintis lygiai du skirtingus natūraliuosius daliklius – ir save patį. Kitaip tariant, skaičius x yra pirminis, jei jis didesnis nei 1 ir dalijasi be liekanos tik iš 1 ir x. Pavyzdžiui, 5 yra pirminis skaičius, o 6 yra sudėtinis skaičius, nes, be 1 ir 6, jis taip pat dalijasi iš 2 ir 3.

Natūralūs skaičiai, kurie yra didesni už vieną ir nėra pirminiai skaičiai, vadinami sudėtiniais skaičiais. Taigi visi natūralieji skaičiai skirstomi į tris klases: vieną. Skaičių teorija tiria pirminių skaičių savybes. Žiedo teorijoje pirminiai skaičiai atitinka neredukuojamus elementus.

Pirminių skaičių seka prasideda taip:

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 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 …

• Vertimas

Pirminių skaičių savybes pirmiausia ištyrė Senovės Graikijos matematikai. Pitagoro mokyklos (500 – 300 m. pr. Kr.) matematikai pirmiausia domėjosi mistinėmis ir numerologinėmis pirminių skaičių savybėmis. Jie buvo pirmieji, kurie sugalvojo tobulus ir draugiškus skaičius.

Tobulas skaičius turi savo daliklių sumą, lygią jam pačiam. Pavyzdžiui, tinkami skaičiaus 6 dalikliai yra 1, 2 ir 3. 1 + 2 + 3 = 6. Skaičiaus 28 dalikliai yra 1, 2, 4, 7 ir 14. Be to, 1 + 2 + 4 + 7 + 14 = 28.

Skaičiai vadinami draugiškaisiais, jei vieno skaičiaus tinkamųjų daliklių suma yra lygi kitam, ir atvirkščiai – pavyzdžiui, 220 ir 284. Galima sakyti, kad tobulas skaičius yra draugiškas sau.

Iki Euklido elementų 300 m. pr. Kr. Jau buvo įrodyta keletas svarbių faktų apie pirminius skaičius. IX elementų knygoje Euklidas įrodė, kad pirminių skaičių yra be galo daug. Tai, beje, vienas iš pirmųjų įrodymų panaudojimo prieštaravimu pavyzdžių. Jis taip pat įrodo pagrindinę aritmetikos teoremą – kiekvienas sveikas skaičius gali būti pavaizduotas unikaliai kaip pirminių skaičių sandauga.

Jis taip pat parodė, kad jei skaičius 2n-1 yra pirminis, tada skaičius 2n-1 * (2n-1) bus tobulas. Kitas matematikas Euleris 1747 m. sugebėjo parodyti, kad visi net tobuli skaičiai gali būti užrašyti šia forma. Iki šiol nežinoma, ar egzistuoja nelyginiai tobuli skaičiai.

200 metais prieš Kristų. Graikas Eratostenas sugalvojo pirminių skaičių paieškos algoritmą, vadinamą Eratosteno sietu.

Ir tada įvyko didelis lūžis pirminių skaičių, siejamų su viduramžiais, tyrimo istorijoje.

Šiuos atradimus jau XVII amžiaus pradžioje padarė matematikas Fermatas. Jis įrodė Alberto Girardo spėjimą, kad bet kurį pirminį 4n+1 formos skaičių galima parašyti vienareikšmiškai kaip dviejų kvadratų sumą, taip pat suformulavo teoremą, kad bet kurį skaičių galima užrašyti kaip keturių kvadratų sumą.

Jis sukūrė naują didelių skaičių faktoringo metodą ir pademonstravo jį skaičiumi 2027651281 = 44021 × 46061. Jis taip pat įrodė mažąją Ferma teoremą: jei p yra pirminis skaičius, tai bet kuriam sveikajam skaičiui a bus tiesa, kad a p = modulis p.

Šis teiginys įrodo pusę to, kas buvo žinoma kaip „kinų spėjimas“ ir yra 2000 metų senumo: sveikasis skaičius n yra pirminis tada ir tik tada, kai 2 n -2 dalijasi iš n. Antroji hipotezės dalis pasirodė klaidinga - pavyzdžiui, 2 341 - 2 dalijasi iš 341, nors skaičius 341 yra sudėtinis: 341 = 31 × 11.

Mažoji Ferma teorema buvo daugelio kitų skaičių teorijos rezultatų ir metodų, skirtų patikrinti, ar skaičiai yra pirminiai skaičiai, pagrindas – daugelis jų vis dar naudojami ir šiandien.

Fermatas daug susirašinėjo su savo amžininkais, ypač su vienuoliu, vardu Maren Mersenne. Viename iš savo laiškų jis iškėlė hipotezę, kad 2 n +1 formos skaičiai visada bus pirminiai, jei n yra dviejų laipsnis. Jis išbandė tai, kai n = 1, 2, 4, 8 ir 16, ir buvo įsitikinęs, kad tuo atveju, kai n nėra dviejų laipsnis, skaičius nebūtinai yra pirminis. Šie skaičiai vadinami Ferma skaičiais ir tik po 100 metų Euleris parodė, kad kitas skaičius 2 32 + 1 = 4294967297 dalijasi iš 641, todėl nėra pirminis.

2 formos n - 1 skaičiai taip pat buvo tiriami, nes nesunku parodyti, kad jei n yra sudėtinis, tai ir pats skaičius yra sudėtinis. Šie skaičiai vadinami Merseno skaičiais, nes jis juos daug tyrinėjo.

Tačiau ne visi 2 formos n - 1 skaičiai, kur n yra pirminis, yra pirminiai. Pavyzdžiui, 2 11 - 1 = 2047 = 23 * 89. Pirmą kartą tai buvo atrasta 1536 m.

Daugelį metų tokio pobūdžio skaičiai matematikams suteikdavo didžiausius žinomus pirminius skaičius. Kad M 19 įrodė Cataldi 1588 m., ir 200 metų buvo didžiausias žinomas pirminis skaičius, kol Euleris įrodė, kad M 31 taip pat yra pirminis. Šis rekordas išliko dar šimtą metų, o tada Lucas parodė, kad M 127 yra pirminis (ir tai jau yra 39 skaitmenų skaičius), o po to tyrimai tęsėsi atsiradus kompiuteriams.

1952 m. buvo įrodytas skaičių M 521, M 607, M 1279, M 2203 ir M 2281 pirmumas.

Iki 2005 m. buvo rasti 42 Mersenne pirminiai laipsniai. Didžiausias iš jų, M 25964951, susideda iš 7816230 skaitmenų.

Eulerio darbas turėjo didžiulę įtaką skaičių teorijai, įskaitant pirminius skaičius. Jis išplėtė Ferma mažąją teoremą ir įvedė φ funkciją. Faktorizuotas 5-asis Fermato skaičius 2 32 +1, surasta 60 porų draugiškų skaičių ir suformuluotas (bet negalėjo įrodyti) kvadratinio abipusiškumo dėsnis.

Jis pirmasis pristatė matematinės analizės metodus ir sukūrė analitinę skaičių teoriją. Jis įrodė, kad ne tik harmonikų serija ∑ (1/n), bet ir formos eilutė

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Pirminių skaičių atvirkštinių dydžių suma gautas rezultatas taip pat skiriasi. Harmonikos eilutės n narių suma auga maždaug kaip log(n), o antroji eilutė skiriasi lėčiau kaip log[ log(n) ]. Tai reiškia, kad, pavyzdžiui, visų iki šiol rastų pirminių skaičių atvirkštinių dydžių suma duos tik 4, nors eilutės vis tiek skiriasi.

Iš pirmo žvilgsnio atrodo, kad pirminiai skaičiai tarp sveikųjų skaičių pasiskirsto gana atsitiktinai. Pavyzdžiui, tarp 100 skaičių prieš pat 10000000 yra 9 pirminiai skaičiai, o tarp 100 skaičių iškart po šios reikšmės yra tik 2. Tačiau dideliuose segmentuose pirminiai skaičiai pasiskirsto gana tolygiai. Legendre ir Gaussas sprendė jų platinimo klausimus. Gaussas kartą pasakė draugui, kad per bet kurias laisvas 15 minučių jis visada skaičiuoja pirminių skaičių kituose 1000 skaičių. Iki savo gyvenimo pabaigos jis buvo suskaičiavęs visus pirminius skaičius iki 3 mln. Legendre ir Gaussas vienodai apskaičiavo, kad dideliems n pirminis tankis yra 1/log(n). Legendre apskaičiavo pirminių skaičių diapazone nuo 1 iki n as

π(n) = n/(log(n) – 1,08366)

O Gausas yra tarsi logaritminis integralas

π(n) = ∫ 1/log(t) dt

Su integravimo intervalu nuo 2 iki n.

Teiginys apie pirminių skaičių 1/log(n) tankį yra žinomas kaip pirminio skirstinio teorema. Jie bandė tai įrodyti visą XIX amžių, o pažangą pasiekė Čebyševas ir Riemannas. Jie susiejo tai su Riemann hipoteze, vis dar neįrodyta hipoteze apie Riemann zeta funkcijos nulių pasiskirstymą. Pirminių skaičių tankį vienu metu įrodė Hadamardas ir Vallée-Poussin 1896 m.

Pirminių skaičių teorijoje vis dar yra daug neišspręstų klausimų, kai kuriems iš jų yra šimtai metų:

• Dvynių pirminių skaičių hipotezė yra apie begalinį skaičių porų pirminių skaičių, kurios viena nuo kitos skiriasi 2
• Goldbacho spėjimas: bet koks lyginis skaičius, prasidedantis 4, gali būti pavaizduotas kaip dviejų pirminių skaičių suma
• Ar yra begalinis skaičius pirminių skaičių formos n 2 + 1?
• Ar visada galima rasti pirminį skaičių tarp n 2 ir (n + 1) 2? (faktą, kad visada yra pirminis skaičius tarp n ir 2n, įrodė Čebyševas)
• Ar Ferma pirminių skaičių skaičius yra begalinis? Ar po 4 yra Fermat pirminių skaičių?
• ar yra bet kokio ilgio iš eilės einančių pirminių skaičių aritmetinė progresija? pavyzdžiui, 4 ilgiui: 251, 257, 263, 269. Didžiausias rastas ilgis yra 26.
• Ar aritmetinėje progresijoje yra begalinis trijų iš eilės pirminių skaičių aibių skaičius?
• n 2 – n + 41 yra pirminis skaičius, kai 0 ≤ n ≤ 40. Ar yra begalinis tokių pirminių skaičių skaičius? Tas pats klausimas formulei n 2 - 79 n + 1601. Šie skaičiai yra pirminiai, kai 0 ≤ n ≤ 79.
• Ar yra begalinis skaičius pirminių skaičių formos n# + 1? (n# yra visų pirminių skaičių, mažesnių už n, padauginimo rezultatas)
• Ar yra begalinis skaičius pirminių skaičių formos n# -1 ?
• Ar yra begalinis skaičius n formos pirminių skaičių? + 1?
• Ar yra begalinis skaičius n formos pirminių skaičių? - 1?
• jei p yra pirminis, ar 2 p -1 tarp jo veiksnių visada neturi pirminių kvadratų?
• ar Fibonačio sekoje yra begalinis pirminių skaičių skaičius?

Didžiausi dvyniai pirminiai skaičiai yra 2003663613 × 2 195000 ± 1. Jie susideda iš 58711 skaitmenų ir buvo atrasti 2007 m.

Didžiausias pirminis faktorinis skaičius (n! ± 1 tipo) yra 147855! - 1. Jį sudaro 142891 skaitmuo ir rastas 2002 m.

Didžiausias pirminis skaičius (n# ± 1 formos skaičius) yra 1098133# + 1.

Žymos: pridėti žymų

Daliklių surašymas. Pagal apibrėžimą skaičius n yra pirminis tik tada, kai jis nėra tolygiai dalijamas iš 2 ir kitų sveikųjų skaičių, išskyrus 1 ir save patį. Aukščiau pateikta formulė pašalina nereikalingus veiksmus ir sutaupo laiko: pavyzdžiui, patikrinus, ar skaičius dalijasi iš 3, nereikia tikrinti, ar jis dalijasi iš 9.

• Funkcija grindys (x) suapvalina x iki artimiausio sveikojo skaičiaus, kuris yra mažesnis arba lygus x.

Sužinokite apie modulinę aritmetiką. Operacija „x mod y“ (mod yra lotyniško žodžio „modulo“ santrumpa, tai yra „modulis“) reiškia „x padalyti iš y ir rasti likutį“. Kitaip tariant, modulinėje aritmetikoje, pasiekus tam tikrą reikšmę, kuri vadinama modulis, skaičiai vėl „pasisuka“ į nulį. Pavyzdžiui, laikrodis laiko laiką, kurio modulis yra 12: jis rodo 10, 11 ir 12 valandą, o tada grįžta į 1.

• Daugelis skaičiuotuvų turi mod raktą. Šio skyriaus pabaigoje parodyta, kaip rankiniu būdu įvertinti šią funkciją dideliems skaičiams.