Visi natūralieji skaičiai, išskyrus vieną, skirstomi į pirminius ir sudėtinius. Pirminis skaičius yra natūralusis skaičius, kuris turi tik du daliklius: vieną ir save. Visi kiti vadinami sudėtiniais. Savybių tyrimas pirminiai skaičiai nagrinėja specialią matematikos šaką – skaičių teoriją. Žiedo teorijoje pirminiai skaičiai yra susiję su neredukuojamais elementais.
Čia yra pirminių skaičių seka, prasidedanti nuo 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 ir kt.
Pagal pagrindinę aritmetikos teoremą kiekvienas natūralusis skaičius, didesnis už vienetą, gali būti pavaizduotas kaip pirminių skaičių sandauga. Tuo pačiu metu tai yra vienintelis būdas pavaizduoti natūraliuosius skaičius iki veiksnių eilės. Remdamiesi tuo, galime teigti, kad pirminiai skaičiai yra elementariosios natūraliųjų skaičių dalys.
Šis natūraliojo skaičiaus vaizdavimas vadinamas natūraliojo skaičiaus išskaidymu į pirminius skaičius arba skaičiaus faktoriavimu.
Vienas iš seniausių ir veiksmingi būdai Pirminių skaičių apskaičiavimas yra „Erasstofeno sietelis“.
Praktika parodė, kad suskaičiavus pirminius skaičius naudojant Erastofeno sietą, reikia patikrinti, ar duotas skaičius yra pirminis. Tam buvo sukurti specialūs testai, vadinamieji paprastumo testai. Šių testų algoritmas yra tikimybinis. Dažniausiai jie naudojami kriptografijoje.
Beje, kai kurioms skaičių klasėms yra specializuoti veiksmingi pirmumo testai. Pavyzdžiui, norint patikrinti Mersenne skaičių pirmumą, naudojamas Luc-Lehmer testas, o Fermat skaičių pirmumui patikrinti naudojamas Pepin testas.
Visi žinome, kad skaičių yra be galo daug. Teisingai kyla klausimas: kiek tada yra pirminių skaičių? Taip pat yra begalinis pirminių skaičių skaičius. Seniausias šio teiginio įrodymas yra Euklido įrodymas, išdėstytas elementuose. Euklido įrodymas atrodo taip:
Įsivaizduokime, kad pirminių skaičių skaičius yra baigtinis. Padauginkime juos ir pridėkime vieną. Gautas skaičius negali būti padalintas iš bet kurios baigtinės pirminių skaičių aibės, nes dalijimo iš bet kurio iš jų liekana duoda vieną. Taigi skaičius turi dalytis iš kokio nors pirminio skaičiaus, neįeinančio į šią aibę.
Pirminių skaičių pasiskirstymo teorema teigia, kad pirminių skaičių, mažesnių už n, skaičius, žymimas π(n), auga kaip n / ln(n).
Po tūkstančius metų tyrinėjant pirminius skaičius, didžiausias žinomas pirminis skaičius yra 243112609 − 1. Šis skaičius turi 12 978 189 dešimtainius skaitmenis ir yra Mersenne pirminis skaičius (M43112609). Šis atradimas buvo atliktas 2008 m. rugpjūčio 23 d. uCLA universiteto Matematikos fakultete vykdant paskirstytos Mersenne pirminių skaičių paieškos projektą GIMPS.
Namai išskirtinis bruožas Mersenne skaičiai yra labai efektyvus Luc-Lemaire pirmumo testas. Su jo pagalba Merseno pirminiai skaičiai ilgą laiką yra didžiausi žinomi pirminiai skaičiai.
Tačiau iki šiol daugelis klausimų, susijusių su pirminiais skaičiais, negavo tikslių atsakymų. 5-ajame tarptautiniame matematikos kongrese Edmundas Landau suformulavo pagrindines pirminių skaičių srities problemas:
Goldbacho arba pirmoji Landau problema yra ta, kad būtina įrodyti arba paneigti, kad kiekvienas lyginis skaičius, didesnis nei 2, gali būti pavaizduotas kaip dviejų pirminių skaičių suma, o kiekvienas nelyginis skaičius, didesnis nei 5, gali būti pavaizduotas kaip suma trys paprasti numeriai.
Antroji Landau problema reikalauja rasti atsakymą į klausimą: ar „pirminių dvynių“ - pirminių skaičių, kurių skirtumas yra 2, aibė yra begalinė?
Legendre'o spėjimas arba trečioji Landau problema yra tokia: ar tiesa, kad tarp n2 ir (n + 1)2 visada yra pirminis skaičius?
Ketvirtoji Landau problema: ar pirminių skaičių aibė formos n2 + 1 yra begalinė?
Be minėtų problemų, yra begalinio pirminių skaičių nustatymo daugelyje sveikųjų skaičių sekų, tokių kaip Fibonačio skaičius, Ferma skaičius ir kt., problema.
Žmonės senovėje žinojo, kad yra skaičių, kurie nesidalina iš jokio kito skaičiaus. Pirminių skaičių seka atrodo maždaug taip:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …
Įrodymą, kad šių skaičių yra be galo daug, taip pat pateikė Euklidas, gyvenęs 300 m.pr.Kr. Maždaug tais pačiais metais kitas graikų matematikas, Eratostenas, sugalvojo gana paprastą pirminių skaičių gavimo algoritmą, kurio esmė buvo nuosekliai išbraukti skaičius iš lentelės. Tie likę skaičiai, kurie iš nieko nesidalijo, buvo pirminiai. Algoritmas vadinamas „Eratosteno sietu“ ir dėl savo paprastumo (nėra daugybos ar dalybos operacijų, tik sudėjimas) vis dar naudojamas kompiuterinėse technologijose.
Matyt, jau Eratosteno laikais paaiškėjo, kad nėra aiškaus kriterijaus, ar skaičius yra pirminis – tai galima patikrinti tik eksperimentiškai. Egzistuoti įvairių būdų supaprastinti procesą (pavyzdžiui, akivaizdu, kad skaičius neturėtų būti lyginis), tačiau paprastas patikrinimo algoritmas dar nerastas ir greičiausiai nebus rastas: išsiaiškinti, ar skaičius yra pirminis, ar ne, turite pabandyti suskirstyti jį į vis mažesnius skaičius.
Ar pirminiai skaičiai paklūsta kokiems nors dėsniams? Taip, ir jie yra gana smalsūs.
Pavyzdžiui, prancūzų matematikas Mersenne dar XVI amžiuje jis atrado, kad daugelis pirminių skaičių turi formą 2^N - 1, šie skaičiai vadinami Merseno skaičiais. Netrukus prieš tai, 1588 m., italų matematikas Cataldi atrado pirminį skaičių 2 19 - 1 = 524287 (pagal Merseno klasifikaciją jis vadinamas M19). Šiandien šis skaičius atrodo gana trumpas, tačiau ir dabar su skaičiuotuvu jo paprastumui patikrinti prireiktų ne vienos dienos, tačiau XVI amžiuje tai buvo tikrai didžiulis darbas.
Po 200 metų matematikas Euleris surado kitą pirminį skaičių 2 31 - 1 = 2147483647. Vėlgi, kiekvienas gali pats įsivaizduoti reikiamą skaičiavimų kiekį. Jis taip pat iškėlė hipotezę (vėliau pavadintą „Eulerio problema“ arba „dvejetaine Goldbacho problema“), kurios esmė paprasta: kiekvienas lyginis skaičius, didesnis už du, gali būti pavaizduotas kaip dviejų pirminių skaičių suma.
Pavyzdžiui, galite paimti bet kokius 2 lyginius skaičius: 123456 ir 888777888.
Naudodami kompiuterį galite rasti jų sumą dviejų pirminių skaičių pavidalu: 123456 = 61813 + 61643 ir 888777888 = 444388979 + 444388909. Įdomu tai, kad tikslus šios teoremos įrodymas dar nerastas. kompiuterių pagalba buvo patikrinta iki skaičių su 18 nulių.
Yra dar viena matematiko teorema Pierre'as Fermatas, atrasta 1640 m., kuri sako, kad jei pirminio skaičiaus forma yra 4*k+1, tai jį galima pavaizduoti kaip kitų skaičių kvadratų sumą. Taigi, pavyzdžiui, mūsų pavyzdyje pirminis skaičius 444388909 = 4*111097227 + 1. Ir iš tiesų, naudodamiesi kompiuteriu galite rasti, kad 444388909 = 19197*19197 + 8710*8710.
Teoremą Euleris įrodė tik po 100 metų.
Ir, galiausiai Bernhardas Riemanas 1859 m. buvo iškelta vadinamoji „Riemano hipotezė“ apie pirminių skaičių skirstinių skaičių, neviršijantį tam tikro skaičiaus. Ši hipotezė dar neįrodyta, ji įtraukta į septynių „tūkstantmečio problemų“ sąrašą, už kurių kiekvienos išsprendimą Kembridžo Clay matematikos institutas yra pasirengęs sumokėti po milijoną JAV dolerių.
Taigi su pirminiais skaičiais nėra taip paprasta. Taip pat yra nuostabių faktų. Pavyzdžiui, rusų matematikas 1883 m JUOS. Pervušinas iš Permės rajono įrodė skaičiaus 2 61 pirmenybę - 1 = 2305843009213693951 . Net ir dabar buitiniai skaičiuotuvai negali dirbti su tokiais ilgais skaičiais, tačiau tuo metu tai buvo tikrai milžiniškas darbas, o kaip tai buvo padaryta, iki šiol nelabai aišku. Nors tikrai yra žmonių, turinčių unikalius smegenų gebėjimus – pavyzdžiui, autistai, kaip žinoma, mintyse gali rasti (!) 8 skaitmenų pirminius skaičius. Kaip jie tai daro, neaišku.
Modernumas
Ar pirminiai skaičiai vis dar aktualūs ir šiandien? Ir kaip! Pirminiai skaičiai yra šiuolaikinės kriptografijos pagrindas, todėl dauguma žmonių jais naudojasi kasdien net nesusimąstydami. Bet koks autentifikavimo procesas, pavyzdžiui, telefono registravimas tinkle, banko mokėjimai ir pan., reikalauja kriptografinių algoritmų.
Idėjos esmė čia yra labai paprasta ir yra algoritmo esmė RSA, pasiūlytas dar 1975 m. Siuntėjas ir gavėjas kartu pasirenka vadinamąjį „privatų raktą“, kuris saugomas saugioje vietoje. Šis raktas, kaip skaitytojai tikriausiai jau atspėjo, yra pirminis skaičius. Antroji dalis yra „viešasis raktas“, taip pat pirminis skaičius, sugeneruotas siuntėjo ir perduodamas kaip produktas kartu su pranešimu. aiškiu tekstu, tai netgi gali būti paskelbta laikraštyje. Algoritmo esmė ta, kad nežinant „uždarosios dalies“ neįmanoma gauti šaltinio teksto.
Pavyzdžiui, jei imsime du pirminius skaičius 444388979 ir 444388909, tada „privatus raktas“ bus 444388979, o produktas 197481533549433911 (444388979*444388909 bus perduotas viešai). Tik žinodamas savo antrąją pusę gali apskaičiuoti trūkstamą skaičių ir juo iššifruoti tekstą.
Kas čia per triukas? Esmė ta, kad dviejų pirminių skaičių sandaugą apskaičiuoti nesunku, tačiau atvirkštinė operacija neegzistuoja – jei nežinai pirmosios dalies, tai tokią procedūrą galima atlikti tik grubia jėga. O jei imsite tikrai didelius pirminius skaičius (pavyzdžiui, 2000 simbolių ilgio), tai jų produkto dekodavimas net šiuolaikiniame kompiuteryje užtruks kelerius metus (iki to laiko žinutė jau seniai bus nereikšminga).
Šios schemos genialumas yra tas, kad pačiame algoritme nėra nieko slapto – jis atviras ir visi duomenys yra paviršiuje (žinomas ir algoritmas, ir didelių pirminių skaičių lentelės). Pats šifras kartu su viešuoju raktu gali būti perduodamas pagal pageidavimą bet kokia atvira forma. Tačiau nežinodami slaptosios rakto dalies, kurią pasirinko siuntėjas, šifruoto teksto negausime. Pavyzdžiui, galime sakyti, kad 1977 metais žurnale buvo išspausdintas RSA algoritmo aprašymas, ten taip pat buvo pateiktas šifro pavyzdys. Tik 1993 m., pasitelkus paskirstytą skaičiavimą 600 savanorių kompiuteriuose, buvo gautas teisingas atsakymas.
Taigi pirminiai skaičiai pasirodė visai ne tokie paprasti, ir jų istorija akivaizdžiai tuo nesibaigia.
Skaičiai yra skirtingi: natūralūs, racionalūs, racionalūs, sveikieji ir trupmeniniai, teigiami ir neigiami, kompleksiniai ir pirminiai, nelyginiai ir lyginiai, tikrieji ir tt Iš šio straipsnio galite sužinoti, kas yra pirminiai skaičiai.
Kokie skaičiai angliškai vadinami „paprastais“?
Labai dažnai moksleiviai iš pirmo žvilgsnio nežino, kaip atsakyti į vieną paprasčiausių matematikos klausimų, kas yra pirminis skaičius. Jie dažnai painioja pirminius skaičius su natūraliaisiais skaičiais (ty skaičiais, kuriuos žmonės naudoja skaičiuodami objektus, o kai kuriuose šaltiniuose jie prasideda nuliu, o kituose - vienetu). Tačiau tai yra visiškai dvi skirtingos sąvokos. Pirminiai skaičiai yra natūralūs skaičiai, tai yra sveikieji ir teigiami skaičiai, kurie yra didesni už vieną ir turi tik 2 natūraliuosius daliklius. Be to, vienas iš šių daliklių yra nurodytas skaičius, o antrasis yra vienas. Pavyzdžiui, trys yra pirminis skaičius, nes jo negalima padalyti be likučio iš jokio kito skaičiaus, išskyrus jį patį ir vieną.
Sudėtiniai skaičiai
Pirminių skaičių priešingybė yra sudėtiniai skaičiai. Jie taip pat yra natūralūs, taip pat didesni už vieną, bet turi ne du, o didesnį daliklių skaičių. Taigi, pavyzdžiui, skaičiai 4, 6, 8, 9 ir kt. yra natūralūs, sudėtiniai, bet ne pirminiai skaičiai. Kaip matote, tai iš esmės lyginiai skaičiai, Bet ne visi. Tačiau „du“ yra lyginis skaičius ir „pirmasis skaičius“ pirminių skaičių serijoje.
Pasekmė
Norint sudaryti pirminių skaičių seką, reikia pasirinkti iš visų natūraliųjų skaičių, atsižvelgiant į jų apibrėžimą, tai yra, reikia veikti prieštaringai. Būtina išnagrinėti kiekvieną iš teigiamų natūraliųjų skaičių, ar jis turi daugiau nei du daliklius. Pabandykime sukurti seriją (seką), kurią sudaro pirminiai skaičiai. Sąrašas prasideda dviem, o paskui trimis, nes jis dalijasi tik iš savęs ir vieno. Apsvarstykite skaičių keturi. Ar jis turi kitus daliklius nei keturi ir vienas? Taip, tas skaičius yra 2. Taigi keturi nėra pirminis skaičius. Penki taip pat yra pirminiai (jis nesidalija iš jokio kito skaičiaus, išskyrus 1 ir 5), bet šeši dalijasi. Ir apskritai, jei vadovausitės visais lyginiais skaičiais, pastebėsite, kad, išskyrus „du“, nė vienas iš jų nėra pirminis. Iš to darome išvadą, kad lyginiai skaičiai, išskyrus du, nėra pirminiai. Kitas atradimas: visi skaičiai, dalijami iš trijų, išskyrus pačius tris, nesvarbu, ar jie lyginiai, ar nelyginiai, taip pat nėra pirminiai (6, 9, 12, 15, 18, 21, 24, 27 ir kt.). Tas pats pasakytina apie skaičius, kurie dalijasi iš penkių ir septynių. Visa jų gausybė taip pat nėra paprasta. Apibendrinkime. Taigi, paprasti vienaženkliai skaičiai apima visus nelyginius skaičius, išskyrus vieną ir devynis, o net „du“ yra lyginiai skaičiai. Patys dešimtukai (10, 20,... 40 ir kt.) nėra paprasti. Pirminius dviženklius, triženklius ir kt.
Teorijos apie pirminių skaičių savybes
Yra mokslas, tiriantis sveikųjų skaičių, įskaitant pirminius skaičius, savybes. Tai matematikos šaka, vadinama aukštąja. Be sveikųjų skaičių savybių, ji taip pat nagrinėja algebrinius ir transcendentinius skaičius, taip pat įvairios kilmės funkcijas, susijusias su šių skaičių aritmetika. Šiuose tyrimuose, be elementariųjų ir algebrinių metodų, naudojami ir analitiniai bei geometriniai. Konkrečiai, „Skaičių teorija“ yra susijusi su pirminių skaičių tyrimu.
Pirminiai skaičiai yra natūraliųjų skaičių „statybiniai blokai“.
Aritmetikoje yra teorema, vadinama pagrindine teorema. Pagal ją bet koks natūralusis skaičius, išskyrus vieną, gali būti pavaizduotas kaip sandauga, kurios veiksniai yra pirminiai skaičiai, o veiksnių eilė yra unikali, vadinasi, vaizdavimo būdas yra unikalus. Tai vadinama natūraliojo skaičiaus faktorinavimu į pirminius veiksnius. Yra ir kitas šio proceso pavadinimas – skaičių faktorizacija. Remiantis tuo, pirminiai skaičiai gali būti vadinami Statybinė medžiaga“, „blokai“, skirti natūraliems skaičiams sudaryti.
Ieškokite pirminių skaičių. Paprastumo testai
Daugelis skirtingų laikų mokslininkų bandė rasti tam tikrus principus (sistemas), kaip rasti pirminių skaičių sąrašą. Mokslas žino sistemas, vadinamas Atkin sietu, Sundartham sietu ir Eratosthenes sietu. Tačiau jie neduoda jokių reikšmingų rezultatų, o pirminiams skaičiams rasti naudojamas paprastas testas. Matematikai taip pat sukūrė algoritmus. Paprastai jie vadinami pirmumo testais. Pavyzdžiui, yra Rabino ir Millerio sukurtas testas. Jį naudoja kriptografai. Taip pat yra Kayal-Agrawal-Sasquena testas. Tačiau, nepaisant pakankamo tikslumo, jį labai sunku apskaičiuoti, o tai sumažina jo praktinę reikšmę.
Ar pirminių skaičių aibė turi ribą?
Senovės graikų mokslininkas Euklidas savo knygoje „Elementai“ rašė, kad pirminių skaičių rinkinys yra begalybė. Jis pasakė taip: „Akimirkai įsivaizduokime, kad pirminiai skaičiai turi ribą. Tada padauginkime juos tarpusavyje ir pridėkite vieną prie produkto. Iš jų gautas skaičius paprasti veiksmai, negalima padalyti iš pirminių skaičių, nes likusioji dalis visada bus viena. Tai reiškia, kad yra koks nors kitas skaičius, kuris dar neįtrauktas į pirminių skaičių sąrašą. Todėl mūsų prielaida nėra teisinga, ir ši aibė negali turėti ribos. Be Euklido įrodymo, yra ir modernesnė formulė, kurią pateikė XVIII amžiaus šveicarų matematikas Leonhardas Euleris. Pagal ją pirmųjų n skaičių sumos atvirkštinė suma didėja neribotai didėjant skaičiui n. O štai teoremos formulė dėl pirminių skaičių skirstinio: (n) auga kaip n/ln (n).
Koks yra didžiausias pirminis skaičius?
Tas pats Leonardas Euleris sugebėjo rasti didžiausią savo laiko pirminį skaičių. Tai yra 2 31 – 1 = 2147483647. Tačiau iki 2013 metų pirminių skaičių sąraše buvo paskaičiuotas dar vienas tiksliausias didžiausias – 2 57885161 – 1. Jis vadinamas Merseno skaičiumi. Jame yra apie 17 milijonų dešimtainių skaitmenų. Kaip matote, aštuonioliktojo amžiaus mokslininko rastas skaičius yra kelis kartus mažesnis už šį. Taip turėjo būti, nes Euleris šį skaičiavimą atliko rankiniu būdu, bet mūsų amžininkui tikriausiai padėjo Skaičiavimo mašina. Be to, šis skaičius buvo gautas Matematikos fakultete vienoje iš Amerikos katedrų. Šio mokslininko vardu pavadinti skaičiai išlaiko Luc-Lemaire pirmumo testą. Tačiau mokslas tuo sustoti nenori. „Electronic Frontier Foundation“, kuris buvo įkurtas 1990 m. Jungtinėse Amerikos Valstijose (EFF), pasiūlė piniginį atlygį už didelių pirminių skaičių suradimą. Ir jei iki 2013 metų premija būtų skirta tiems mokslininkams, kurie juos suras iš 1 ir 10 mln. dešimtainiai skaičiai, tada šiandien šis skaičius pasiekė nuo 100 mln. iki 1 mlrd. Prizai siekia nuo 150 iki 250 tūkstančių JAV dolerių.
Specialiųjų pirminių skaičių pavadinimai
Tie skaičiai, kurie buvo rasti tam tikrų mokslininkų sukurtų algoritmų dėka ir išlaikė paprastumo testą, vadinami ypatingais. Štai keletas iš jų:
1. Merssenas.
4. Kalenas.
6. Mills ir kt.
Šių skaičių, pavadintų aukščiau minėtų mokslininkų vardu, paprastumas nustatomas naudojant šiuos testus:
1. Luc-Lemaire.
2. Pepina.
3. Ryzelis.
4. Billhart – Lemaire – Selfridge ir kt.
Šiuolaikinis mokslas tuo nesibaigia ir tikriausiai netolimoje ateityje pasaulis sužinos vardus tų, kurie sugebėjo gauti 250 000 USD prizą, radę didžiausią pirminį skaičių.
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 yra „x mod y“ (mod trumpinys Lotyniškas žodis„modulo“ 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.
Sužinokite apie Ferma mažosios teoremos spąstus. Visi skaičiai, kuriems netenkinamos bandymo sąlygos, yra sudėtiniai, tačiau likę skaičiai yra tik tikriausiai yra klasifikuojami kaip paprasti. Jei norite išvengti neteisingų rezultatų, ieškokite n sąraše „Carmichael skaičiai“ (sudėtiniai skaičiai, atitinkantys šį testą) ir „pseudo pirminiai Fermat skaičiai“ (šie skaičiai atitinka bandymo sąlygas tik kai kurioms reikšmėms a).
Jei patogu, naudokite Miller-Rabin testą. Nors šis metodas gana sudėtingas skaičiuojant rankiniu būdu, jis dažnai naudojamas kompiuterines programas. Jis užtikrina priimtiną greitį ir sukelia mažiau klaidų nei Fermat metodas. Sudėtinis skaičius nebus priimtas kaip pirminis skaičius, jei skaičiuojama daugiau nei ¼ reikšmių a. Jei pasirinksite atsitiktinai skirtingos reikšmės a ir jiems visiems testas duos teigiamas rezultatas, galime su gana dideliu pasitikėjimu manyti, kad n yra pirminis skaičius.
Dideliam skaičiui naudokite modulinę aritmetiką. Jei po ranka neturite skaičiuotuvo su modifikavimo funkcija arba skaičiuotuvas nėra skirtas operacijoms su tokiais dideli skaičiai, naudokite galių savybes ir modulinę aritmetiką, kad būtų lengviau atlikti skaičiavimus. Žemiau yra pavyzdys, skirtas 3 50 (\displaystyle 3^ (50)) 50 mod.:
- Perrašykite išraišką patogesne forma: mod 50. Atliekant skaičiavimus rankiniu būdu, gali prireikti papildomų supaprastinimų.
- (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Čia atsižvelgėme į modulinės daugybos savybę.
- 3 25 (\displaystyle 3^(25)) mod 50 = 43.
- (3 25 (\displaystyle (3^(25)) 50 mod ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 * 43) (\displaystyle (43*43)) 50 mod.
- = 1849 (\displaystyle =1849) 50 mod.
- = 49 (\displaystyle =49).
Šiame straipsnyje mes išnagrinėsime pirminiai ir sudėtiniai skaičiai. Pirmiausia pateiksime pirminių ir sudėtinių skaičių apibrėžimus, taip pat pateiksime pavyzdžių. Po to įrodysime, kad pirminių skaičių yra be galo daug. Toliau užrašysime pirminių skaičių lentelę ir apsvarstysime pirminių skaičių lentelės sudarymo būdus, ypatingą dėmesį skirdami metodui, vadinamam Eratosteno sietu. Baigdami pabrėšime pagrindinius dalykus, į kuriuos reikia atsižvelgti įrodant, kad tam tikras skaičius yra pirminis arba sudėtinis.
Puslapio naršymas.
Pirminiai ir sudėtiniai skaičiai – apibrėžimai ir pavyzdžiai
Pirminių skaičių ir sudėtinių skaičių sąvokos reiškia skaičius, didesnius už vienetą. Tokie sveikieji skaičiai, priklausomai nuo jų teigiamų daliklių, skirstomi į pirminius ir sudėtinius skaičius. Taigi suprasti pirminių ir sudėtinių skaičių apibrėžimai, turite gerai suprasti, kas yra dalikliai ir kartotiniai.
Apibrėžimas.
pirminiai skaičiai yra sveikieji skaičiai, dideli vienetai, turintys tik du teigiamus daliklius, būtent save ir 1.
Apibrėžimas.
Sudėtiniai skaičiai- tai sveikieji skaičiai, dideli vienetai, kurie pagal bent jau, trys teigiami dalikliai.
Atskirai pažymime, kad skaičius 1 netaikomas nei pirminiams, nei sudėtiniams skaičiams. Vienetas turi tik vieną teigiamą daliklį, kuris yra pats skaičius 1. Tai išskiria skaičių 1 nuo visų kitų teigiamų sveikųjų skaičių, turinčių bent du teigiamus daliklius.
Atsižvelgiant į tai, kad teigiami sveikieji skaičiai yra , o vienas turi tik vieną teigiamą daliklį, galime pateikti kitas pirminių ir sudėtinių skaičių apibrėžimų formuluotes.
Apibrėžimas.
pirminiai skaičiai yra natūralūs skaičiai, turintys tik du teigiamus daliklius.
Apibrėžimas.
Sudėtiniai skaičiai yra natūralūs skaičiai, turintys daugiau nei du teigiamus daliklius.
Atkreipkite dėmesį, kad kiekvienas teigiamas sveikasis skaičius, didesnis už vienetą, yra pirminis arba pirminis sudėtinis skaičius. Kitaip tariant, nėra nė vieno sveikojo skaičiaus, kuris nebūtų nei pirminis, nei sudėtinis. Tai išplaukia iš dalijamumo savybės, kuri teigia, kad skaičiai 1 ir a visada yra bet kurio sveikojo skaičiaus a dalikliai.
Remdamiesi ankstesnėje pastraipoje pateikta informacija, galime pateikti tokį sudėtinių skaičių apibrėžimą.
Apibrėžimas.
Vadinami natūralieji skaičiai, kurie nėra pirminiai sudėtinis.
Duokim pirminių ir sudėtinių skaičių pavyzdžiai.
Sudėtinių skaičių pavyzdžiai yra 6, 63, 121 ir 6 697. Šį teiginį taip pat reikia paaiškinti. Skaičius 6, be teigiamų daliklių 1 ir 6, taip pat turi daliklius 2 ir 3, nes 6 = 2 3, todėl 6 tikrai yra sudėtinis skaičius. Teigiami koeficientai 63 yra skaičiai 1, 3, 7, 9, 21 ir 63. Skaičius 121 yra lygus sandaugai 11·11, todėl jo teigiami dalikliai yra 1, 11 ir 121. Ir skaičius 6 697 yra sudėtinis, nes jo teigiami dalikliai, be 1 ir 6 697, taip pat yra skaičiai 37 ir 181.
Baigdamas šį klausimą taip pat norėčiau atkreipti dėmesį į tai, kad pirminiai skaičiai ir pirminiai skaičiai toli gražu nėra tas pats dalykas.
Pirminių skaičių lentelė
Pirminiai skaičiai, tolimesnio jų naudojimo patogumui, įrašomi į lentelę, vadinamą pirminių skaičių lentele. Žemiau yra pirminių skaičių lentelė iki 1000.
Kyla logiškas klausimas: „Kodėl pirminių skaičių lentelę užpildėme tik iki 1000, ar negalima sukurti visų esamų pirminių skaičių lentelės“?
Pirmiausia atsakykime į pirmąją šio klausimo dalį. Daugeliui problemų, kurioms reikia naudoti pirminius skaičius, pakaks pirminių skaičių tūkstančio ribose. Kitais atvejais greičiausiai teks griebtis specialių sprendimų. Nors tikrai galime sukurti pirminių skaičių lentelę iki savavališkai didelio baigtinio teigiamo sveikojo skaičiaus, nesvarbu, ar tai būtų 10 000 ar 1 000 000 000, kitoje pastraipoje kalbėsime apie pirminių skaičių lentelių kūrimo metodus, ypač pažvelgsime į metodą. paskambino.
Dabar pažvelkime į galimybę (tiksliau, neįmanomumą) sudaryti visų esamų pirminių skaičių lentelę. Negalime sudaryti visų pirminių skaičių lentelės, nes pirminių skaičių yra be galo daug. Paskutinis teiginys yra teorema, kurią įrodysime po šios pagalbinės teoremos.
Teorema.
Mažiausias teigiamas natūraliojo skaičiaus, didesnio už vienetą, daliklis, išskyrus 1, yra pirminis skaičius.
Įrodymas.
Leisti a yra natūralusis skaičius, didesnis už vieną, o b yra mažiausias teigiamas kito nei vienas daliklis. Įrodykime, kad b yra pirminis skaičius prieštaravimu.
Tarkime, kad b yra sudėtinis skaičius. Tada yra skaičiaus b daliklis (pažymime jį b 1), kuris skiriasi ir nuo 1, ir nuo b. Jeigu dar atsižvelgsime į tai, kad daliklio absoliuti vertė neviršija absoliučios dividendo vertės (tai žinome iš dalijamumo savybių), tai 1 sąlyga turi būti įvykdyta
Kadangi skaičius a dalijasi iš b pagal sąlygą, o mes sakėme, kad b dalijasi iš b 1, dalijimosi sąvoka leidžia kalbėti apie sveikųjų skaičių q ir q 1 egzistavimą, kad a=b q ir b=b 1 q 1 , iš kur a= b 1 · (q 1 · q) . Iš to seka, kad dviejų sveikųjų skaičių sandauga yra sveikasis skaičius, tai lygybė a=b 1 ·(q 1 ·q) rodo, kad b 1 yra skaičiaus a daliklis. Atsižvelgiant į pirmiau minėtus nelygumus 1
Dabar galime įrodyti, kad pirminių skaičių yra be galo daug.
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ėje. 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.
Toks 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 sudaroma pirminių skaičių iki 50 lentelę.
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, išbraukimas 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.
Tai gana akivaizdu 
, 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 iš pirminių skaičių, mažesnių nei 109, potencialiai yra duoto skaičiaus 11 723 pirminis 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
