- Prevod
Svojstva prostih brojeva prvi su proučavali matematičari Ancient Greece. Matematičari Pitagorejske škole (500 - 300 pne) su prvenstveno bili zainteresovani za mistična i numerološka svojstva prostih brojeva. Oni su prvi došli na ideju o savršenim i prijateljskim brojevima.
Savršen broj ima svoje djelitelje jednake samom sebi. Na primjer, pravi djelitelji broja 6 su: 1, 2 i 3. 1 + 2 + 3 = 6. Djelitelji broja 28 su 1, 2, 4, 7 i 14. Štaviše, 1 + 2 + 4 + 7 + 14 = 28.
Brojevi se nazivaju prijateljskim ako je zbir pravih djelitelja jednog broja jednak drugom, i obrnuto - na primjer, 220 i 284. Možemo reći da je savršeni broj prijateljski prema sebi.
Do pojave djela Euklidovih "Početaka" 300. godine prije Krista. nekoliko je već dokazano važne činjenice o prostim brojevima. U IX knjizi Elementi, Euklid je dokazao da postoji beskonačan broj prostih brojeva. Inače, ovo je jedan od prvih primjera upotrebe dokaza kontradikcijom. On također dokazuje osnovnu teoremu aritmetike - svaki cijeli broj može biti predstavljen na jedinstven način kao proizvod prostih brojeva.
Takođe je pokazao da ako je broj 2 n -1 prost, onda će broj 2 n-1 * (2 n -1) biti savršen. Drugi matematičar, Ojler, uspeo je 1747. da pokaže da je sve ravno savršeni brojevi može se napisati u ovom obliku. Do danas nije poznato da li postoje neparni savršeni brojevi.
Godine 200. p.n.e. Grčki Eratosten osmislio je algoritam za pronalaženje prostih brojeva nazvan Eratostenovo sito.
A onda je došlo do velikog preloma u istoriji proučavanja prostih brojeva povezanih sa srednjim vekom.
Sljedeća otkrića je već početkom 17. stoljeća napravio matematičar Fermat. Dokazao je hipotezu Alberta Girarda da se bilo koji prost broj oblika 4n+1 može jedinstveno napisati kao zbir dva kvadrata, a također je formulirao teoremu da se bilo koji broj može predstaviti kao zbir četiri kvadrata.
On se razvio nova metoda faktorizaciju velikih brojeva, i to demonstrirao na broju 2027651281 = 44021 × 46061. On je također dokazao Fermatovu malu teoremu: ako je p prost broj, tada će za bilo koji cijeli broj a, a p = a modulo p biti istinito.
Ova izjava dokazuje polovinu onoga što je bilo poznato kao "kineska hipoteza" i datira 2000 godina ranije: cijeli broj n je prost ako i samo ako je 2n-2 djeljivo sa n. Drugi dio hipoteze pokazao se netačnim - na primjer, 2341 - 2 je djeljivo sa 341, iako je broj 341 složen: 341 = 31 × 11.
Fermatova mala teorema bila je osnova za mnoge druge rezultate u teoriji brojeva i metode za testiranje da li su brojevi prosti, od kojih su mnogi i danas u upotrebi.
Fermat se intenzivno dopisivao sa svojim savremenicima, posebno sa redovnikom po imenu Marin Mersenne. U jednom od svojih pisama, on je pretpostavio da će brojevi oblika 2 n + 1 uvijek biti prosti ako je n stepen dva. Testirao je ovo za n = 1, 2, 4, 8 i 16 i bio siguran da kada n nije stepen dva, broj nije nužno prost. Ovi brojevi se zovu Fermaovi brojevi, i tek 100 godina kasnije Ojler je pokazao da je sledeći broj, 232 + 1 = 4294967297, djeljiv sa 641 i stoga nije prost.
Brojevi oblika 2 n - 1 su takođe bili predmet istraživanja, jer je lako pokazati da ako je n složen, onda je i sam broj kompozitan. Ovi brojevi se nazivaju Mersennovi brojevi jer ih je on aktivno proučavao.
Ali nisu svi brojevi oblika 2 n - 1, gdje je n prost, prosti. Na primjer, 2 11 - 1 = 2047 = 23 * 89. Ovo je prvi put otkriveno 1536. godine.
Dugi niz godina, brojevi ove vrste davali su matematičarima najveće poznate proste brojeve. Da je broj M 19 dokazao Cataldi 1588. godine i da je 200 godina bio najveći poznati prost broj, sve dok Ojler nije dokazao da je i M 31 prost. Ovaj rekord se održao još stotinu godina, a onda je Lucas pokazao da je M 127 prost (a to je već broj od 39 cifara), a nakon toga su istraživanja nastavljena pojavom kompjutera.
Godine 1952. dokazana je jednostavnost brojeva M 521 , M 607 , M 1279 , M 2203 i M 2281.
Do 2005. godine pronađena su 42 Mersenneova prosta broja. Najveći od njih, M 25964951, sastoji se od 7816230 znamenki.
Ojlerov rad imao je ogroman uticaj na teoriju brojeva, uključujući proste brojeve. On je proširio Fermatovu malu teoremu i uveo φ-funkciju. Faktorizirao 5. Fermaov broj 2 32 +1, pronašao 60 parova prijateljskih brojeva i formulisao (ali nije uspio dokazati) kvadratni zakon reciprociteta.
On je prvi uveo metode matematička analiza i razvio analitičku teoriju brojeva. On je dokazao da ne samo harmonijski niz ∑ (1/n), već i niz oblika
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
Dobijeno zbirom količina inverznih prostim brojevima, također divergira. Zbir n članova harmonijskog niza raste otprilike kao log(n), dok drugi niz divergira sporije, kao log[ log(n)]. To znači da će, na primjer, zbir recipročnih vrijednosti svih do sada pronađenih prostih brojeva dati samo 4, iako se niz i dalje razlikuje.
Na prvi pogled izgleda da su prosti brojevi raspoređeni među cijelim brojevima prilično nasumično. Na primjer, među 100 brojeva neposredno prije 10000000, ima 9 prostih brojeva, a među 100 brojeva odmah nakon ove vrijednosti, ima samo 2. Ali na velikim segmentima, prosti brojevi su raspoređeni prilično ravnomjerno. Legendre i Gauss su se bavili njihovom distribucijom. Gauss je jednom prijatelju rekao da u bilo kojih slobodnih 15 minuta uvijek broji prosti broj u sljedećih 1000 brojeva. Do kraja života izbrojao je sve proste brojeve do 3 miliona. Legendre i Gauss su jednako izračunali da je za veliko n gustina prostih brojeva 1/log(n). Legendre je procijenio broj prostih brojeva između 1 i n kao
π(n) = n/(log(n) - 1,08366)
I Gaus - kao logaritamski integral
π(n) = / 1/log(t) dt
Sa intervalom integracije od 2 do n.
Izjava o gustoći prostih brojeva 1/log(n) poznata je kao Teorema o prostim brojevima. Pokušavali su to dokazati tokom cijelog 19. vijeka, a Čebišev i Riman su napredovali. Povezali su je s Riemannom hipotezom, dosad nedokazanom pretpostavkom o raspodjeli nula Riemannove zeta funkcije. Gustinu prostih brojeva istovremeno su dokazali Adamard i de la Vallée-Poussin 1896. godine.
U teoriji prostih brojeva još uvijek postoji mnogo neriješenih pitanja, od kojih su neka stara stotinama godina:
- Hipoteza prostih blizanaca - o beskonačnom broju parova prostih brojeva koji se međusobno razlikuju za 2
- Goldbachova pretpostavka: bilo koji paran broj, počevši od 4, može se predstaviti kao zbir dva prosta broja
- Postoji li beskonačan broj prostih brojeva oblika n 2 + 1?
- da li je uvijek moguće pronaći prost broj između n 2 i (n + 1) 2 ? (Čebišev je dokazao činjenicu da uvijek postoji prost broj između n i 2n)
- Postoji li beskonačan broj Fermatovih prostih brojeva? ima li Fermatovih prostih brojeva nakon 4.?
- da li postoji aritmetička progresija uzastopnih prostih brojeva za bilo koju datu dužinu? na primjer, za dužinu 4: 251, 257, 263, 269. Maksimalna pronađena dužina je 26 .
- Postoji li beskonačan broj skupova od tri uzastopna prosta broja u aritmetičkoj progresiji?
- n 2 - n + 41 je prost broj za 0 ≤ n ≤ 40. Postoji li beskonačan broj takvih prostih brojeva? Isto pitanje za formulu n 2 - 79 n + 1601. Ovi brojevi su prosti za 0 ≤ n ≤ 79.
- Postoji li beskonačan broj prostih brojeva oblika n# + 1? (n# je rezultat množenja svih prostih brojeva manjih od n)
- Postoji li beskonačan broj prostih brojeva oblika n# -1?
- Postoji li beskonačan broj prostih brojeva oblika n! +1?
- Postoji li beskonačan broj prostih brojeva oblika n! - jedan?
- ako je p prost, da li 2 p -1 uvijek ne uključuje među faktore prostih brojeva na kvadrat
- Da li Fibonačijev niz sadrži beskonačan broj prostih brojeva?
Najveći prosti brojevi blizanci su 2003663613 × 2 195000 ± 1. Sastoje se od 58711 cifara i pronađeni su 2007. godine.
Najveći faktorijalni prost broj (u obliku n! ± 1) je 147855! - 1. Sastoji se od 142891 cifre i pronađen je 2002. godine.
Najveći primarni prost broj (broj oblika n# ± 1) je 1098133# + 1.
Članak se bavi pojmovima prostih i složenih brojeva. Date su definicije takvih brojeva sa primjerima. Dajemo dokaz da je broj prostih brojeva neograničen i unosimo u tabelu prostih brojeva koristeći Eratostenovu metodu. Dat će se dokazi da li je broj prost ili složen.
Yandex.RTB R-A-339285-1
Prosti i složeni brojevi - definicije i primjeri
Prosti i složeni brojevi se klasificiraju kao pozitivni cijeli brojevi. Moraju biti veći od jedan. Delitelji se također dijele na proste i složene. Da bismo razumjeli pojam složenih brojeva, potrebno je prvo proučiti pojmove djelitelja i višekratnika.
Definicija 1
Prosti brojevi su cijeli brojevi koji su veći od jedan i imaju dva pozitivna djelitelja, odnosno sebe i 1.
Definicija 2
Složeni brojevi su cijeli brojevi koji su veći od jedan i imaju najmanje tri pozitivna djelitelja.
Jedan nije ni prost ni kompozitni broj. Ima samo jedan pozitivan djelitelj, pa se razlikuje od svih ostalih pozitivnih brojeva. Svi pozitivni cijeli brojevi nazivaju se prirodnim, odnosno koriste se u brojanju.
Definicija 3
primarni brojevi - ovo cijeli brojevi ima samo dva pozitivna djelitelja.
Definicija 4
Kompozitni broj je prirodan broj koji ima više od dva pozitivna djelila.
Svaki broj veći od 1 je prost ili složen. Iz svojstva djeljivosti imamo da je 1 i da će broj a uvijek biti djelitelj za bilo koji broj a, odnosno da će biti djeljiv sam sa sobom i sa 1. Dajemo definiciju cijelih brojeva.
Definicija 5
Prirodni brojevi koji nisu prosti nazivaju se složeni brojevi.
Prosti brojevi: 2, 3, 11, 17, 131, 523. Oni su djeljivi samo sa sobom i sa 1. Kompozitni brojevi: 6, 63, 121, 6697. To jest, broj 6 se može razložiti na 2 i 3, a 63 na 1, 3, 7, 9, 21, 63 i 121 na 11, 11, odnosno, njegovi djelitelji će biti 1, 11, 121. Broj 6697 će se razložiti na 37 i 181. Imajte na umu da su koncepti prostih brojeva i relativno prostih brojeva različiti koncepti.
Da biste olakšali korištenje prostih brojeva, trebate koristiti tabelu:
Tabela za sve postojeće prirodne brojeve je nerealna, jer ih ima beskonačan broj. Kada brojevi dosegnu veličinu od 10000 ili 1000000000, tada biste trebali razmisliti o korištenju Eratostenovog sita.
Razmotrimo teoremu koja objašnjava posljednju izjavu.
Teorema 1
Najmanji pozitivni djelitelj prirodnog broja većeg od 1 osim 1 je prost broj.
Dokaz 1
Pretpostavimo da je a prirodan broj veći od 1, b je najmanji ne-jedan djelitelj a. Moramo dokazati da je b prost broj koristeći metodu kontradikcije.
Recimo da je b složeni broj. Odavde imamo da postoji djelitelj za b, koji je različit od 1 kao i od b. Takav djelitelj se označava kao b 1 . Neophodno je da uslov 1< b 1 < b je završeno.
Iz uslova se vidi da je a deljivo sa b, b deljivo sa b 1, što znači da se koncept deljivosti izražava na ovaj način: a = b q i b = b 1 q 1 , odakle je a = b 1 (q 1 q) , gdje je q i q 1 su cijeli brojevi. Prema pravilu množenja cijelih brojeva, imamo da je proizvod cijelih brojeva cijeli broj sa jednakošću oblika a = b 1 · (q 1 · q) . Može se vidjeti da je b 1 je djelitelj a. Nejednakost 1< b 1 < b ne poklapa se, jer dobijamo da je b najmanji pozitivni ne-1 djelitelj a.
Teorema 2
Postoji beskonačno mnogo prostih brojeva.
Dokaz 2
Pretpostavimo da uzmemo konačan broj prirodnih brojeva n i označimo ih kao p 1 , p 2 , … , p n . Razmotrimo varijantu pronalaženja prostog broja različitog od navedenih.
Razmotrimo broj p, koji je jednak p 1 , p 2 , … , p n + 1 . Nije jednak svakom od brojeva koji odgovaraju prostim brojevima oblika p 1 , p 2 , … , p n . Broj p je prost. Tada se smatra da je teorema dokazana. Ako je kompozitno, onda moramo uzeti oznaku p n + 1 i pokaži neslaganje djelitelja sa bilo kojim od p 1 , p 2 , … , p n .
Ako to nije tako, onda, na osnovu svojstva djeljivosti proizvoda p 1 , p 2 , … , p n , dobijamo da bi bilo deljivo sa p n + 1 . Imajte na umu da je izraz p n + 1 broj p podijeljen je jednak zbiru p 1 , p 2 , … , p n + 1 . Dobijamo da je izraz p n + 1 drugi član ovog zbira, koji je jednak 1, mora se podijeliti, ali to je nemoguće.
Može se vidjeti da se bilo koji prost broj može naći među bilo kojim brojem datih prostih brojeva. Iz toga slijedi da postoji beskonačno mnogo prostih brojeva.
Pošto postoji mnogo prostih brojeva, tabele su ograničene na brojeve 100, 1000, 10000 i tako dalje.
Prilikom sastavljanja tablice prostih brojeva, treba imati na umu da takav zadatak zahtijeva sekvencijalnu provjeru brojeva, počevši od 2 do 100. Ako nema djelitelja, upisuje se u tabelu, ako je složen, onda se ne unosi u tabelu.
Razmotrimo korak po korak.
Ako počnete sa brojem 2, onda ima samo 2 djelitelja: 2 i 1, što znači da se može unijeti u tabelu. Takođe sa brojem 3. Broj 4 je složen, treba ga rastaviti na 2 i 2. Broj 5 je prost, što znači da se može fiksirati u tabeli. Uradite to do broja 100.
Ova metoda neprijatno i dugo. Možete napraviti sto, ali morate potrošiti veliki broj vrijeme. Potrebno je koristiti kriterije djeljivosti, što će ubrzati proces pronalaženja djelitelja.
Metoda pomoću Eratostenovog sita smatra se najprikladnijom. Pogledajmo donje tabele. Za početak, napisani su brojevi 2, 3, 4, ..., 50.
Sada morate precrtati sve brojeve koji su višestruki od 2. Napravite sekvencijalno precrtavanje. Dobijamo tabelu oblika:
Pređimo na precrtavanje brojeva koji su višestruki od 5. Dobijamo:
Precrtavamo brojeve koji su višekratni od 7, 11. Konačno tabela izgleda
Prijeđimo na formulaciju teoreme.
Teorema 3
Najmanji pozitivni i ne-1 djelitelj osnovnog broja a ne prelazi a , gdje je a aritmetički korijen datog broja.
Dokaz 3
Potrebno je označiti b kao najmanji djelitelj složenog broja a. Postoji cijeli broj q, gdje je a = b · q, i imamo da je b ≤ q. Nejednakost oblika b > q jer je uslov prekršen. Obje strane nejednakosti b ≤ q treba pomnožiti bilo kojim pozitivan broj b , nije jednako 1 . Dobijamo da je b b ≤ b q, gdje je b 2 ≤ a i b ≤ a.
Iz dokazane teoreme se vidi da precrtavanje brojeva u tabeli dovodi do toga da je potrebno početi od broja koji je jednak b 2 i koji zadovoljava nejednakost b 2 ≤ a . Odnosno, ako precrtate brojeve koji su višestruki od 2, tada proces počinje od 4, a oni koji su višestruki od 3 počinju od 9, i tako dalje do 100.
Sastavljanje takve tabele koristeći Eratostenovu teoremu kaže da kada se precrtaju svi složeni brojevi, ostaće prosti koji ne prelaze n. U primjeru gdje je n = 50, imamo da je n = 50. Odavde dobijamo da Eratostenovo sito izbacuje sve složene brojeve koji po vrednosti nisu veći od vrednosti korena iz 50. Pretraga brojeva se vrši precrtavanjem.
Prije rješavanja potrebno je utvrditi da li je broj prost ili složen. Često se koriste kriteriji djeljivosti. Pogledajmo ovo u primjeru ispod.
Primjer 1
Dokažite da je 898989898989898989 složeni broj.
Rješenje
Zbir cifara datog broja je 9 8 + 9 9 = 9 17 . Dakle, broj 9 17 je djeljiv sa 9, na osnovu znaka djeljivosti sa 9. Iz toga slijedi da je kompozitna.
Takvi znakovi ne mogu dokazati jednostavnost broja. Ako je potrebna provjera, treba poduzeti druge korake. Većina pogodan način- To je niz brojeva. Tokom procesa, prosti i složeni brojevi se mogu pronaći. To jest, brojevi u vrijednosti ne bi trebali biti veći od . To jest, broj a se mora razložiti na proste faktore. ako je to tačno, onda se broj a može smatrati prostim.
Primjer 2
Odredi složeni ili prosti broj 11723.
Rješenje
Sada morate pronaći sve djelitelje za broj 11723. Treba procijeniti 11723 .
Odavde vidimo da 11723< 200 , то 200 2 = 40 000 i 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Za precizniju procjenu broja 11723 potrebno je napisati izraz 108 2 = 11 664, a 109 2 = 11 881 , onda 108 2 < 11 723 < 109 2 . Iz ovoga slijedi da je 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Prilikom dekompozicije dobijamo 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 7 , 7 , 7 , 7 83 , 89 , 97 , 101 , 103 , 107 su svi prosti brojevi. Cijeli ovaj proces može se prikazati kao podjela kolonom. Odnosno, podijelite 11723 sa 19. Broj 19 je jedan od njegovih faktora, jer dobijamo deljenje bez ostatka. Opišimo podjelu kolonom:
Iz toga slijedi da je 11723 složen broj, jer pored sebe i 1 ima djelitelj 19 .
odgovor: 11723 je složeni broj.
Ako primijetite grešku u tekstu, označite je i pritisnite Ctrl+Enter
Prosti brojevi su jedan od najzanimljivijih matematičkih fenomena koji više od dva milenijuma privlači pažnju naučnika i običnih građana. Uprkos činjenici da danas živimo u eri kompjutera i najsavremenijih informacionih programa, mnoge misterije prostih brojeva još uvek nisu rešene, ima čak i onih kojima naučnici ne znaju kako da pristupe.
Prosti brojevi su, kao što je poznato iz kursa elementarne aritmetike, oni koji su bez ostatka djeljivi samo jednim i samim sobom. Usput, ako je prirodni broj djeljiv, pored gore navedenih, još jednim brojem, onda se naziva složenim. Jedna od najpoznatijih teorema kaže da se bilo koji složeni broj može predstaviti kao jedini mogući proizvod prostih brojeva.
Nekoliko zanimljivih činjenica. Prvo, jedinica je jedinstvena u smislu da, u stvari, ne pripada ni prostim ni kompozitnim brojevima. Istovremeno, u naučnoj zajednici još uvijek je uobičajeno da se pripisuje prvoj grupi, jer formalno u potpunosti zadovoljava svoje zahtjeve.
Drugo, jedini paran broj koji se uvukao u grupu "prostih brojeva" je, naravno, dva. Bilo koji drugi paran broj jednostavno ne može doći ovdje, jer je po definiciji, osim sebe i jedan, također djeljiv sa dva.
Prosti brojevi, čija lista, kao što je gore pomenuto, može početi sa jedan, su beskonačan niz, beskonačan kao i niz prirodnih brojeva. Na osnovu osnovne aritmetičke teoreme može se doći do zaključka da se prosti brojevi nikada ne prekidaju i nikada ne završavaju, jer bi inače niz prirodnih brojeva neizbježno bio prekinut.
Prosti brojevi se ne pojavljuju nasumično u prirodnom nizu, kao što se može činiti na prvi pogled. Nakon što ih pažljivo analizirate, odmah možete uočiti nekoliko karakteristika, od kojih su najzanimljivije povezane s takozvanim brojevima "blizanaca". Zovu se tako jer su na neki neshvatljiv način završili jedno do drugog, razdvojeni samo parnim graničnikom (pet i sedam, sedamnaest i devetnaest).
Ako ih pažljivo pogledate, primijetit ćete da je zbir ovih brojeva uvijek višestruki od tri. Štaviše, kada se dijeli sa trojkom lijevog druga, ostatak uvijek ostaje dvojka, a desni - jedan. Osim toga, sama raspodjela ovih brojeva duž prirodnog niza može se predvidjeti ako se cijeli ovaj niz predstavi u obliku oscilatornih sinusoida, čije glavne točke nastaju kada se brojevi podijele sa tri i dva.
Prosti brojevi nisu samo predmet pomnog proučavanja matematičara širom svijeta, već se dugo uspješno koriste u sastavljanju različitih serija brojeva, što je osnova, uključujući i šifriranje. Istovremeno, treba priznati da ogroman broj misterija povezanih s ovim divnim elementima još uvijek čeka na rješavanje, mnoga pitanja imaju ne samo filozofski, već i praktični značaj.
prost broj je prirodan (pozitivan cijeli) broj koji je bez ostatka djeljiv sa samo dva prirodna broja: sam po sebi. Drugim riječima, prost broj ima tačno dva prirodna djelitelja: i sam broj.
Po definiciji, skup svih djelitelja prostog broja je dvoelementan, tj. je set.
Skup svih prostih brojeva je označen simbolom . Dakle, na osnovu definicije skupa prostih brojeva, možemo napisati: .
Niz prostih brojeva izgleda ovako:
Osnovna teorema aritmetike
Osnovna teorema aritmetike tvrdi da se svaki prirodni broj veći od jedan može predstaviti kao proizvod prostih brojeva, i to na jedinstven način, do reda faktora. Dakle, prosti brojevi su elementarni" blokovi» skupovi prirodnih brojeva.
Dekompozicija prirodnog broja title="(!LANG:Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} kanonski:
gdje je prost broj, i . Na primjer, kanonsko proširenje prirodnog broja izgleda ovako: .
Reprezentacija prirodnog broja kao proizvoda prostih brojeva se također naziva faktorizacija brojeva.
Svojstva prostih brojeva
Eratostenovo sito
Jedan od najpoznatijih algoritama za traženje i prepoznavanje prostih brojeva je Eratostenovo sito. Dakle, ovaj algoritam je dobio ime po grčkom matematičaru Eratostenu iz Kirene, koji se smatra autorom algoritma.
Da biste pronašli sve proste brojeve manje od datog broja, slijedeći Eratostenovu metodu, trebate slijediti ove korake:
Korak 1. Napišite u redu sve prirodne brojeve od dva do , tj. .
Korak 2 Dodijelite vrijednost varijabli, odnosno vrijednost jednaku najmanjem prostom broju.
Korak 3 Izbrišite sa liste sve brojeve od do višekratnike , odnosno brojeve: .
Korak 4 Pronađite prvi neprecrtani broj na listi veći od , i dodijelite vrijednost tog broja varijabli.
Korak 5 Ponavljajte korake 3 i 4 dok se ne postigne broj.
Proces primjene algoritma će izgledati ovako:
Svi preostali neprecrtani brojevi na listi na kraju procesa primjene algoritma bit će skup prostih brojeva od do .
Goldbachova hipoteza
Naslovnica knjige "Ujka Petros i Goldbachova pretpostavka"
Uprkos činjenici da su proste brojeve matematičari proučavali dugo vremena, danas mnogi povezani problemi ostaju neriješeni. Jedan od najpoznatijih neriješenih problema je Goldbachova pretpostavka, koji je formuliran na sljedeći način:
- Da li je tačno da se svaki paran broj veći od dva može predstaviti kao zbir dvaju prostih brojeva (Goldbachova binarna pretpostavka)?
- Da li je tačno da se svaki neparni broj veći od 5 može predstaviti kao zbir tri jednostavna brojevi (ternarna Goldbachova pretpostavka)?
Treba reći da je ternarna Goldbachova hipoteza poseban slučaj binarne Goldbachove hipoteze, ili, kako matematičari kažu, ternarna Goldbachova hipoteza je slabija od binarne Goldbachove hipoteze.
Goldbachova pretpostavka postala je nadaleko poznata izvan matematičke zajednice 2000. godine zahvaljujući marketinškoj reklamnoj akciji izdavačkih kompanija Bloomsbury USA (SAD) i Faber and Faber (UK). Ove izdavačke kuće, nakon što su objavile knjigu “Ujka Petros i Goldbachova pretpostavka” (“Uncle Petros and Goldbach's Conjecture”), obećale su da će isplatiti nagradu od 1 milion američkih dolara u roku od 2 godine od datuma objavljivanja knjige onome ko dokazuje Goldbachovu pretpostavku. Ponekad se pomenuta nagrada izdavača meša sa nagradama za rešavanje problema Milenijumske nagrade. Ne budite zabune, Goldbachova hipoteza nije navedena kao milenijumski izazov od strane Instituta Clay, iako je usko povezana sa Riemannova hipoteza jedan od milenijumskih izazova.
Knjiga „Jednostavni brojevi. Dug put u beskonačnost
Naslovnica knjige „Svijet matematike. Jednostavni brojevi. Dug put u beskonačnost
Osim toga, preporučujem čitanje fascinantne naučno-popularne knjige, uz napomenu: „Potraga za prostim brojevima jedan je od najparadoksalnih problema u matematici. Naučnici to pokušavaju riješiti nekoliko milenijuma, ali, stječući nove verzije i hipoteze, ova misterija i dalje ostaje neriješena. Pojava prostih brojeva nije podložna nikakvom sistemu: oni nastaju spontano u nizu prirodnih brojeva, zanemarujući sve pokušaje matematičara da identifikuju obrasce u njihovom nizu. Ova knjiga će omogućiti čitaocu da prati evoluciju naučnih ideja od antičkih vremena do danas i uvede najzanimljivije teorije o potrazi za prostim brojevima.
Osim toga, citiraću početak drugog poglavlja ove knjige: „Prosti brojevi su jedan od važne teme, koji nas vraćaju na same početke matematike, a zatim nas, putem sve složenije, vode do vrhunca moderna nauka. Stoga bi bilo vrlo korisno pratiti fascinantnu i složenu istoriju teorije prostih brojeva: kako se tačno razvijala, kako su tačno prikupljene činjenice i istine koje se danas smatraju opšteprihvaćenim. U ovom poglavlju ćemo vidjeti kako su generacije matematičara pažljivo proučavale prirodne brojeve u potrazi za pravilom koje predviđa pojavu prostih brojeva, pravilom koje je tokom traženja postajalo sve neuhvatljivije. Pobliže ćemo se osvrnuti i na historijski kontekst: u kakvim su uvjetima radili matematičari i u kojoj mjeri su u njihovom radu primjenjivane mistične i polureligijske prakse koje nimalo nisu slične naučne metode danas se koristi. Ipak, polako i s mukom, pripremalo se tlo za nove poglede koji su inspirisali Fermata i Ojlera u 17. i 18. veku.”
M. Gardner slikovito govori kako je ovo zapažanje napravljeno u Matematičkom slobodnom vremenu (M., Mir, 1972). Evo ovog dela (str. 413-417):
Ovisno o rasporedu cijelih brojeva, prosti brojevi mogu formirati jedan ili drugi obrazac. Jednom je matematičar Stanislav M. Ulam morao da prisustvuje jednom veoma dugom i veoma dosadnom, po njegovim rečima, izveštaju. Kako bi se nekako zabavio, nacrtao je okomite i horizontalne linije na komadu papira i htio da počne sastavljati šahovske studije, ali se onda predomislio i počeo numerisati raskrsnice, stavljajući 1 u centar i krećući se u smjeru suprotnom od kazaljke na satu u spirali . Bez ikakvog skrivenog motiva, zaokružio je sve proste brojeve. Ubrzo, na njegovo iznenađenje, krugovi su počeli da se nižu duž pravih linija sa neverovatnom upornošću. Na sl. 203 prikazuje kako je spirala izgledala sa sto prvih brojeva (od 1 do 100). [ Ovo je skraćena verzija gornje slike 1 za dva okreta, tako da je ne uključujem ovdje. — E.G.A.] Radi praktičnosti, brojevi su upisani u ćelije i ne stoje na sjecištu linija.
Blizu centra, poravnanje prostih brojeva duž pravih linija se i dalje može očekivati, jer je gustina prostih brojeva u početku velika i svi su, osim broja 2, neparni. Ako ćelije chessboard prenumerirajte u spiralu, tada će svi neparni brojevi pasti na ćelije iste boje. Uzimajući 17 pješaka (što odgovara 17 prostih brojeva koji ne prelaze 64) i nasumično ih stavite na polja iste boje, vidjet ćete da su pijuni poredani duž dijagonalnih linija. Međutim, nije bilo razloga očekivati da će se u području velikih brojeva, gdje je gustina prostih brojeva mnogo manja, i oni poredati duž pravih linija. Ulama je zanimalo kako bi izgledala njegova spirala da se proširi na nekoliko hiljada prostih brojeva.
U računarskom odeljenju laboratorije u Los Alamosu, gde je Ulam radio, nalazila se magnetna traka na kojoj je zabeleženo 90 miliona prostih brojeva. Ulam je zajedno sa Myronom L. Steinom i Markom B. Wellsom napisao program za kompjuter MANIAC koji je omogućio ispis uzastopnih cijelih brojeva od 1 do 65 000 na spirali. Prikazan je rezultujući uzorak (ponekad nazvan "Ulam stolnjak"). na sl. 204. [ A ovo je proširena verzija gornje slike 2, pa je donosim. — E.G.A.] Obratite pažnju na činjenicu da čak i na ivici slike prosti brojevi nastavljaju poslušno da stoje na pravim linijama.
Prije svega, klasteri prostih brojeva na dijagonalama su upečatljivi, ali još jedna tendencija prostih brojeva da se poredaju duž vertikale i horizontalne linije, na kojoj su sve ćelije bez prostih brojeva zauzete neparnim brojevima. Prosti brojevi koji padaju na linije koje se protežu izvan segmenta koji sadrži uzastopne brojeve koji leže na nekom okretu spirale mogu se smatrati vrijednostima nekih kvadratnih izraza počevši od pojma 4 x². Na primjer, niz prostih brojeva 5, 19, 41, 71, koji stoji na jednoj od dijagonala na sl. 204, su vrijednosti koje uzima kvadratni trinom 4 x² + 10 x+ 5 at x jednako 0, 1, 2 i 3. Sa sl. 204 može se vidjeti da su kvadratni izrazi koji uzimaju proste vrijednosti "siromašni" (daju nekoliko prostih brojeva) i "bogati" i da se na "bogatim" linijama promatraju cijeli "placers" prostih brojeva.
Pokretanjem spirale ne od 1, već od nekog drugog broja, dobijamo druge kvadratne izraze za proste brojeve koji se poredaju duž pravih linija. Zamislite spiralu koja počinje brojem 17 (slika 205, lijevo). Brojevi duž glavne dijagonale koji idu od "sjeveroistoka" prema "jugozapadu" generirani su kvadratnim trinomom 4 x² + 2 x+ 17. Zamjena pozitivne vrijednosti x, dobijamo donju polovinu dijagonale zamjenom negativnih vrijednosti - gornju. Ako razmotrimo cijelu dijagonalu i preuredimo proste brojeve u rastućem redoslijedu, ispada (a ovo je ugodno iznenađenje) da su svi brojevi opisani jednostavnijom formulom x² + x+ 17. Ovo je jedna od mnogih formula za "generisanje" prostih brojeva koje je u 18. veku otkrio veliki matematičar Leonhard Euler. At x, koji uzima vrijednosti od 0 do 15, daje samo proste brojeve. Stoga, produžavajući dijagonalu dok ne ispuni kvadrat 16x16, vidimo da je cijela dijagonala popunjena prostim brojevima.
Ojlerov najpoznatiji kvadratni trinom, koji daje proste brojeve, x² + x+ 41, ispostaviće se ako spiralu započnete brojem 41 (Sl. 205, desno). Ovaj trinom vam omogućava da dobijete 40 uzastopnih prostih brojeva koji ispunjavaju cijelu dijagonalu kvadrata 40 × 4! Odavno je poznato da je od 2398 prvih vrijednosti koje je uzeo ovaj trinom, tačno polovina jednostavna. Prošavši sve vrijednosti poznatog trinoma, koje ne prelaze 10.000.000, Ulam, Stein i Wells su otkrili da je udio prostih brojeva među njima 0,475 ... . Matematičari bi veoma voleli da otkriju formulu koja vam omogućava da dođete do nje svima Uglavnom x raznih prostih brojeva, ali do sada nije otkrivena takva formula. Možda ne postoji.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
| Rice. 205. Dijagonale ispunjene prostim brojevima generiranim kvadratnim trinomima x² + x+ 17 (lijevo) i x² + x+ 41 (desno). | ||||||||||||||||||||||||||||||||||||||||||||||||||||
Ulamska spirala je pokrenula mnoga nova pitanja o obrascima i nasumičnosti u distribuciji prostih brojeva. Postoje li linije koje sadrže beskonačno mnogo prostih brojeva? Kolika je maksimalna gustina raspodjele prostih brojeva duž linija? Da li se distribucije gustoće prostih brojeva u kvadrantima Ulamovog stolnjaka značajno razlikuju, ako pretpostavimo da se to nastavlja u nedogled? Ulamska spirala je zabavna, ali je treba shvatiti ozbiljno.