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. predstavlja skup.
Skup svih prostih brojeva je označen simbolom. Dakle, zbog definicije skupa prostih brojeva, možemo napisati: .
Niz prostih brojeva izgleda ovako:
Osnovna teorema aritmetike
Osnovna teorema aritmetike kaže 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 "građevinski blokovi" skupa prirodni brojevi.
Proširenje prirodnog broja title="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: .
Predstavljanje prirodnog broja kao proizvoda prostih brojeva se također naziva faktorizacija broja.
Svojstva prostih brojeva
Eratostenovo sito
Jedan od najpoznatijih algoritama za traženje i prepoznavanje prostih brojeva je Eratostenovo sito. Tako je ovaj algoritam 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, slijedite ove korake:
Korak 1. Zapišite sve prirodne brojeve od dva do , tj. .
Korak 2. Dodijelite varijabli vrijednost , odnosno vrijednost jednaku najmanjem prostom broju.
Korak 3. Precrtajte na listi sve brojeve od do koji su višekratnici , odnosno brojevi: .
Korak 4. Pronađite prvi neprekriženi broj na listi veći od , i dodijelite vrijednost ovog broja varijabli.
Korak 5. Ponavljajte korake 3 i 4 dok se ne postigne broj.
Proces primjene algoritma će izgledati ovako:
Svi preostali neprekršteni brojevi na listi na kraju procesa primene algoritma biće skup prostih brojeva od do .
Goldbachova pretpostavka
Korica knjige “Ujka Petros i Goldbahova hipoteza”
Uprkos činjenici da su proste brojeve matematičari proučavali dosta dugo, mnogi povezani problemi i danas ostaju neriješeni. Jedan od najpoznatijih neriješenih problema je Goldbachova hipoteza, 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 dva prosta broja (Goldbachova binarna hipoteza)?
- Da li je tačno da se svaki neparni broj veći od 5 može predstaviti kao zbir? tri jednostavna brojevi (ternarna Goldbachova hipoteza)?
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 je postala široko poznata izvan matematičke zajednice 2000. godine zahvaljujući promotivnom marketinškom potezu 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”, obećale su da će isplatiti nagradu od milion američkih dolara svakome ko dokaže Goldbachovu hipotezu u roku od 2 godine od datuma objavljivanja knjige. Ponekad se spomenuta nagrada od izdavača miješa s nagradama za rješavanje problema Milenijumske nagrade. Ne budite zabune, Goldbachovu hipotezu Institut Clay ne klasifikuje kao "milenijumski izazov", iako je usko povezana sa Riemannova hipoteza- jedan od „milenijumskih izazova“.
Knjiga “Prosti brojevi. Dug put u beskonačnost"
Naslovnica knjige „Svijet matematike. primarni brojevi. Dug put u beskonačnost"
Osim toga, preporučujem čitanje fascinantne naučno-popularne knjige u kojoj piše: „Potraga za prostim brojevima jedan je od najparadoksalnih problema u matematici. Naučnici to pokušavaju riješiti nekoliko milenijuma, ali, rastući s novim verzijama i hipotezama, ova misterija i dalje ostaje neriješena. Pojava prostih brojeva nije podložna nikakvom sistemu: oni se pojavljuju 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 koncepata od antičkih vremena do danas i uvede najzanimljivije teorije traženja prostih brojeva.”
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 u prvi plan 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 su danas opšteprihvaćene. 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 – pravilo koje je postajalo sve neuhvatljivije kako je potraga napredovala. Također ćemo se detaljno osvrnuti na historijski kontekst: pod kojim su uvjetima radili matematičari i u kojoj mjeri je njihov rad uključivao mistične i polureligijske prakse, koje nimalo nisu slične naučne metode, koristi se i danas. Ipak, polako i s mukom, pripremalo se tlo za nove poglede koji su inspirisali Fermata i Ojlera u 17. i 18. veku.”
Brojevi su različiti: prirodni, racionalni, racionalni, cjelobrojni i razlomak, pozitivni i negativni, složeni i prosti, neparni i parni, realni itd. Iz ovog članka možete saznati šta su prosti brojevi.
Koji se brojevi na engleskom zovu "jednostavni"?
Vrlo često školarci ne znaju kako da odgovore na jedno od najjednostavnijih pitanja u matematici na prvi pogled, o tome šta je prost broj. Često brkaju proste brojeve s prirodnim brojevima (odnosno brojevima koje ljudi koriste prilikom brojanja objekata, dok u nekim izvorima počinju s nulom, a u drugima s jedinicom). Ali ovo su potpuno dva različita koncepta. Prosti brojevi su prirodni brojevi, odnosno cijeli brojevi i pozitivni brojevi koji su veći od jedan i koji imaju samo 2 prirodna djelila. Štaviše, jedan od ovih djelitelja je dati broj, a drugi je jedan. Na primjer, tri je prost broj jer se ne može podijeliti bez ostatka ni sa jednim brojem osim sa samim sobom i jednim.
Kompozitni brojevi
Suprotnost prostim brojevima su složeni brojevi. Oni su također prirodni, također veći od jedan, ali nemaju dva, već veći broj djelitelja. Tako, na primjer, brojevi 4, 6, 8, 9 itd. su prirodni, složeni, ali nisu prosti brojevi. Kao što vidite, to su uglavnom parni brojevi, ali ne svi. Ali "dva" je paran broj i "prvi broj" u nizu prostih brojeva.
Subsequence
Da biste konstruirali niz prostih brojeva, potrebno je odabrati između svih prirodnih brojeva, uzimajući u obzir njihovu definiciju, odnosno morate djelovati kontradiktorno. Potrebno je ispitati svaki od pozitivnih prirodnih brojeva da vidimo da li ima više od dva djelitelja. Pokušajmo da napravimo niz (sekvencu) koji se sastoji od prostih brojeva. Lista počinje sa dva, a zatim slede tri, jer je deljiva samo sa sobom i jednim. Uzmite u obzir broj četiri. Da li ima djelitelje osim četiri i jedan? Da, taj broj je 2. Dakle, četiri nije prost broj. Pet je također prosto (nije djeljivo ni sa jednim drugim brojem, osim 1 i 5), ali šest je djeljivo. I općenito, ako pratite sve parne brojeve, primijetit ćete da osim "dva", nijedan od njih nije prost. Iz ovoga zaključujemo da parni brojevi, osim dva, nisu prosti. Još jedno otkriće: svi brojevi djeljivi sa tri, osim samih tri, bilo da su parni ili neparni, također nisu prosti (6, 9, 12, 15, 18, 21, 24, 27, itd.). Isto važi i za brojeve koji su djeljivi sa pet i sedam. Svo njihovo mnoštvo takođe nije jednostavno. Hajde da sumiramo. Dakle, jednostavni jednocifreni brojevi uključuju sve neparne brojeve osim jedan i devet, a čak i "dva" su parni brojevi. Same desetice (10, 20,... 40, itd.) nisu jednostavne. Dvocifreni, trocifreni itd. prosti brojevi se mogu odrediti na osnovu gornjih principa: ako nemaju djelitelje osim sebe i jedan.
Teorije o svojstvima prostih brojeva
Postoji nauka koja proučava svojstva cijelih brojeva, uključujući proste brojeve. Ovo je grana matematike koja se zove viša. Osim svojstava cijelih brojeva, bavi se i algebarskim i transcendentalnim brojevima, kao i funkcijama različitog porijekla vezanim za aritmetiku ovih brojeva. U ovim studijama, pored elementarnih i algebarskih metoda, koriste se i analitičke i geometrijske. Konkretno, “Teorija brojeva” se bavi proučavanjem prostih brojeva.
Prosti brojevi su "građevinski blokovi" prirodnih brojeva
U aritmetici postoji teorema koja se zove fundamentalna teorema. Prema njemu, svaki prirodan broj, osim jednog, može se predstaviti kao proizvod čiji su faktori prosti brojevi, a redoslijed faktora je jedinstven, što znači da je način predstavljanja jedinstven. To se zove faktoring prirodnog broja u proste faktore. Postoji još jedan naziv za ovaj proces - faktorizacija brojeva. Na osnovu toga, prosti brojevi se mogu nazvati “ građevinski materijal“, “blokovi” za konstruisanje prirodnih brojeva.
Traži proste brojeve. Testovi jednostavnosti
Mnogi naučnici iz različitih vremena pokušavali su da pronađu neke principe (sisteme) za pronalaženje liste prostih brojeva. Nauka poznaje sisteme koji se zovu Atkin sito, Sundartamovo sito i Eratostenovo sito. Međutim, oni ne daju nikakve značajne rezultate, a za pronalaženje prostih brojeva koristi se jednostavan test. Matematičari su takođe kreirali algoritme. Obično se nazivaju testovima primarnosti. Na primjer, postoji test koji su razvili Rabin i Miller. Koriste ga kriptografi. Tu je i Kayal-Agrawal-Sasquena test. Međutim, uprkos dovoljnoj preciznosti, veoma je teško izračunati, što umanjuje njen praktični značaj.
Ima li skup prostih brojeva ograničenje?
Drevni grčki naučnik Euklid napisao je u svojoj knjizi "Elementi" da je skup prostih brojeva beskonačan. Rekao je ovo: „Zamislimo na trenutak da prosti brojevi imaju ograničenje. Zatim ih pomnožimo jedno s drugim i dodamo jedan proizvodu. Broj dobijen kao rezultat ovih jednostavnih radnji ne može se podijeliti ni sa jednim od nizova prostih brojeva, jer će ostatak uvijek biti jedan. To znači da postoji još neki broj koji još nije uključen u listu prostih brojeva. Dakle, naša pretpostavka nije tačna i ovaj skup ne može imati granicu. Pored Euklidovog dokaza, postoji modernija formula koju je dao švajcarski matematičar Leonhard Euler iz osamnaestog veka. Prema njemu, zbir recipročan zbroju prvih n brojeva raste neograničeno kako se broj n povećava. A evo formule teoreme o raspodjeli prostih brojeva: (n) raste kao n/ln (n).
Koji je najveći prost broj?
Isti Leonard Ojler je uspeo da pronađe najveći prosti broj svog vremena. Ovo je 2 31 - 1 = 2147483647. Međutim, do 2013. godine izračunat je još jedan najprecizniji najveći na listi prostih brojeva - 2 57885161 - 1. Zove se Mersenov broj. Sadrži oko 17 miliona decimalnih cifara. Kao što vidite, broj koji je pronašao naučnik iz osamnaestog veka je nekoliko puta manji od ovog. Trebalo je da bude tako, jer je Ojler ovaj proračun izvršio ručno, dok je našem savremeniku verovatno pomogao kompjuter. Štaviše, ovaj broj je dobijen na Matematičkom fakultetu na jednom od američkih odsjeka. Brojevi nazvani po ovom naučniku prolaze Luc-Lemaireov test primarnosti. Međutim, nauka ne želi stati na tome. Electronic Frontier Foundation, koja je osnovana 1990. godine u Sjedinjenim Američkim Državama (EFF), ponudila je novčanu nagradu za pronalaženje velikih prostih brojeva. A ako bi se do 2013. nagrada dodjeljivala onim naučnicima koji bi ih pronašli između 1 i 10 miliona decimalni brojevi, tada je danas ova cifra dostigla sa 100 miliona na 1 milijardu. Nagrade se kreću od 150 do 250 hiljada američkih dolara.
Nazivi specijalnih prostih brojeva
Oni brojevi koji su pronađeni zahvaljujući algoritmima koje su kreirali određeni naučnici i koji su prošli test jednostavnosti nazivaju se posebnim. Evo nekih od njih:
1. Merssen.
4. Cullen.
6. Mills et al.
Jednostavnost ovih brojeva, nazvanih po gore navedenim naučnicima, utvrđena je pomoću sljedećih testova:
1. Luc-Lemaire.
2. Pepina.
3. Riesel.
4. Billhart - Lemaire - Selfridge i drugi.
Moderna nauka tu ne staje, a vjerovatno će u bliskoj budućnosti svijet saznati imena onih koji su uspjeli da osvoje nagradu od 250.000 dolara pronalazeći najveći prosti broj.
- 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 zbir vlastitih djelitelja jednak 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.
U vrijeme Euklidovih elemenata 300. godine p.n.e. nekoliko je već dokazano važne činjenice u vezi prostih brojeva. U IX knjizi Elementi, Euklid je dokazao da postoji beskonačan broj prostih brojeva. Ovo je, inače, jedan od prvih primjera korištenja dokaza kontradikcijom. On također dokazuje osnovnu teoremu aritmetike - svaki cijeli broj može se jedinstveno predstaviti kao proizvod prostih brojeva.
Takođe je pokazao da ako je broj 2n-1 prost, onda će broj 2n-1 * (2n-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 je nepoznato da li postoje neparni savršeni brojevi.
Godine 200. pne. 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. On je dokazao pretpostavku 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 napisati kao zbir četiri kvadrata.
Razvio se 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 biti tačno da je a p = a modulo p.
Ova izjava dokazuje polovinu onoga što je bilo poznato kao "kineska pretpostavka" i datira prije 2000 godina: cijeli broj n je prost ako i samo ako je 2 n -2 djeljivo sa n. Drugi dio hipoteze pokazao se netačnim - na primjer, 2.341 - 2 je djeljivo sa 341, iako je broj 341 složen: 341 = 31 × 11.
Fermatova mala teorema poslužila je kao osnova za mnoge druge rezultate u teoriji brojeva i metode za testiranje da li su brojevi prosti brojevi – od kojih se mnogi i danas koriste.
Fermat se mnogo dopisivao sa svojim savremenicima, posebno sa redovnikom po imenu Maren 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 je uvjeren da u slučaju kada n nije stepen dva, broj nije nužno prost. Ovi brojevi se nazivaju Fermaovi brojevi, a samo 100 godina kasnije Euler je pokazao da je sljedeći broj, 2 32 + 1 = 4294967297, djeljiv sa 641, te 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 opširno 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 M 19 dokazao Cataldi 1588. godine i 200 godina je bio najveći poznati prost broj, sve dok Ojler nije dokazao da je i M 31 prost. Ovaj rekord je postojao još stotinu godina, a onda je Lucas pokazao da je M 127 prost (a to je već broj od 39 cifara), a nakon toga se istraživanje nastavilo 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 mogao 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 +…
Rezultat dobiven zbirom recipročnih vrijednosti prostih brojeva također se razlikuje. Zbir n članova harmonijskog niza raste približno kao log(n), a 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, čini se da su prosti brojevi prilično nasumično raspoređeni među cijelim brojevima. 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 pitanjima njihove distribucije. Gauss je jednom prijatelju rekao da u bilo kojih slobodnih 15 minuta uvijek broji broj prostih brojeva 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 osnovna gustina 1/log(n). Legendre je procijenio broj prostih brojeva u rasponu od 1 do n kao
π(n) = n/(log(n) - 1,08366)
A Gaus je kao logaritamski integral
π(n) = ∫ 1/log(t) dt
Sa intervalom integracije od 2 do n.
Tvrdnja o gustoći prostih brojeva 1/log(n) poznata je kao teorema distribucije prostih brojeva. Pokušavali su to dokazati tokom cijelog 19. vijeka, a napredak su postigli Čebišev i Riman. Povezali su je s Riemannom hipotezom, još nedokazanom hipotezom o raspodjeli nula Riemannove zeta funkcije. Gustinu prostih brojeva istovremeno su dokazali Adamard i Vallée-Poussin 1896. godine.
Još uvijek postoje mnoga neriješena pitanja u teoriji prostih brojeva, od kojih su neka stara stotinama godina:
- Hipoteza prostih blizanaca je 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)
- Da li je broj Fermatovih prostih brojeva beskonačan? 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? - 1?
- ako je p prost, da li 2 p -1 uvijek ne sadrži proste kvadrate među svojim faktorima?
- 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 otkriveni su 2007. godine.
Najveći faktorijalni prost broj (tipa 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.
Oznake: Dodajte oznake
U članku se razmatraju koncepti prostih i složenih brojeva. Definicije takvih brojeva su date uz primjere. Dajemo dokaz da je broj prostih brojeva neograničen i to ćemo zapisati u tablicu prostih brojeva po Eratostenovom metodu. Dat će se dokazi da se utvrdi je li 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 biste razumjeli koncept složenih brojeva, prvo morate proučiti koncepte 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 prirodni brojevi, odnosno koriste se u brojanju.
Definicija 3
primarni brojevi su prirodni brojevi koji imaju samo dva pozitivna djelitelja.
Definicija 4
Kompozitni broj je prirodan broj koji ima više od dva pozitivna djelila.
Svaki broj koji je 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. Hajde da damo definiciju celih 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 1. Složeni brojevi: 6, 63, 121, 6697. Odnosno, 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 se rastavlja na 37 i 181. Imajte na umu da su koncepti prostih brojeva i međusobno 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 dostignu veličinu od 10000 ili 1000000000, onda biste trebali razmisliti o korištenju Eratostenovog sita.
Razmotrimo teoremu koja objašnjava posljednju izjavu.
Teorema 1
Najmanji pozitivni djelitelj različit od 1 prirodnog broja većeg od jedan je prost broj.
Dokazi 1
Pretpostavimo da je a prirodan broj veći od 1, b je najmanji ne-jedan djelitelj a. Da je b prost broj potrebno je dokazati metodom kontradikcije.
Pretpostavimo 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 je jasno da je a podeljeno sa b, b podeljeno sa b 1, što znači da se koncept deljivosti izražava na sledeći 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 za broj a. Nejednakost 1< b 1 < b Ne odgovara, jer nalazimo da je b najmanji pozitivni i ne-1 djelitelj a.
Teorema 2
Postoji beskonačan broj prostih brojeva.
Dokazi 2
Vjerovatno ćemo uzeti konačan broj prirodnih brojeva n i označiti ih kao p 1, p 2, …, p n. Razmotrimo opciju pronalaženja prostog broja različitog od navedenih.
Uzmimo u obzir 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 morate uzeti zapis p n + 1 i pokazati da se djelitelj ne poklapa ni sa jednim od p 1, p 2, ..., p n.
Ako to nije tako, onda, na osnovu svojstva djeljivosti proizvoda p 1, p 2, ..., p n , nalazimo da bi bilo djeljivo sa pn + 1. Imajte na umu da je izraz p n + 1 deljenjem broja p dobija se zbir 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 itd.
Prilikom sastavljanja tablice prostih brojeva treba uzeti u obzir da takav zadatak zahtijeva uzastopnu 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.
Pogledajmo to 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. Isto je i sa brojem 3. Broj 4 je složen; mora se rastaviti na 2 i 2. Broj 5 je prost, što znači da se može upisati u tabelu. Radite to do broja 100.
Ova metoda nezgodno i dugo. Možete kreirati sto, ali ćete morati 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 kao primjer. Za početak, zapisuju se brojevi 2, 3, 4, ..., 50.
Sada morate precrtati sve brojeve koji su višekratni od 2. Izvršite uzastopno precrtavanje. Dobijamo sto kao:
Prelazimo na precrtavanje brojeva koji su višestruki od 5. Dobijamo:
Precrtajte brojeve koji su višestruki od 7, 11. Na kraju tabela izgleda tako
Pređ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.
Dokazi 3
Potrebno je označiti b najmanji djelitelj složenog broja a. Postoji cijeli broj q, gdje je a = b · q, i imamo da je b ≤ q. Nejednakosti oblika su neprihvatljive b > q, jer je uslov prekršen. Obje strane nejednakosti b ≤ q treba pomnožiti sa 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 jasno je 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 sa 4, a višekratnik od 3 sa 9, i tako dalje do 100.
Sastavljanje takve tabele koristeći Eratostenovu teoremu sugeriše da kada se precrtaju svi složeni brojevi, ostaju prosti brojevi 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 čija vrednost nije veća od vrednosti korena iz 50. Pretraga brojeva se vrši precrtavanjem.
Prije rješavanja morate saznati da li je broj prost ili složen. Često se koriste kriteriji djeljivosti. Pogledajmo ovo u primjeru ispod.
Primjer 1
Dokažite da je broj 898989898989898989 složen.
Rješenje
Zbir cifara datog broja je 9 8 + 9 9 = 9 17. To znači da je broj 9 · 17 djeljiv sa 9, na osnovu testa djeljivosti sa 9. Iz toga slijedi da je kompozitna.
Takvi znakovi ne mogu dokazati jednostavnost broja. Ako je potrebna provjera, treba poduzeti druge radnje. Većina pogodan način- To je gomila brojeva. Tokom procesa, prosti i složeni brojevi se mogu pronaći. Odnosno, brojevi ne bi trebali prelaziti vrijednost a. Odnosno, broj a se mora razložiti u proste faktore. ako je ovo zadovoljeno, 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 , To 108 2 < 11 723 < 109 2 . Iz toga slijedi da je 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Prilikom proširenja nalazimo da su 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 su svi prosti brojevi. Cijeli ovaj proces može se opisati kao podjela kolonom. Odnosno, podijelite 11723 sa 19. Broj 19 je jedan od njegovih faktora, jer dobijamo deljenje bez ostatka. Predstavimo podjelu kao kolonu:
Iz toga slijedi da je 11723 složeni 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
- Prevod
Svojstva prostih brojeva prvi su proučavali matematičari stare Grčke. 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 zbir vlastitih djelitelja jednak 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.
U vrijeme Euklidovih elemenata 300. godine p.n.e. Nekoliko važnih činjenica o prostim brojevima je već dokazano. U IX knjizi Elementi, Euklid je dokazao da postoji beskonačan broj prostih brojeva. Ovo je, inače, jedan od prvih primjera korištenja dokaza kontradikcijom. On također dokazuje osnovnu teoremu aritmetike - svaki cijeli broj može se jedinstveno predstaviti kao proizvod prostih brojeva.
Takođe je pokazao da ako je broj 2n-1 prost, onda će broj 2n-1 * (2n-1) biti savršen. Drugi matematičar, Euler, uspio je 1747. pokazati da se svi čak i savršeni brojevi mogu napisati u ovom obliku. Do danas je nepoznato da li postoje neparni savršeni brojevi.
Godine 200. pne. 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. On je dokazao pretpostavku 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 napisati kao zbir četiri kvadrata.
Razvio je novu metodu za faktoriranje velikih brojeva i demonstrirao je na broju 2027651281 = 44021 × 46061. Također je dokazao Fermatovu malu teoremu: ako je p prost broj, tada će za bilo koji cijeli broj a biti tačno da je p = a modulo str.
Ova izjava dokazuje polovinu onoga što je bilo poznato kao "kineska pretpostavka" i datira prije 2000 godina: cijeli broj n je prost ako i samo ako je 2 n -2 djeljivo sa n. Drugi dio hipoteze pokazao se netačnim - na primjer, 2.341 - 2 je djeljivo sa 341, iako je broj 341 složen: 341 = 31 × 11.
Fermatova mala teorema poslužila je kao osnova za mnoge druge rezultate u teoriji brojeva i metode za testiranje da li su brojevi prosti brojevi – od kojih se mnogi i danas koriste.
Fermat se mnogo dopisivao sa svojim savremenicima, posebno sa redovnikom po imenu Maren 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 je uvjeren da u slučaju kada n nije stepen dva, broj nije nužno prost. Ovi brojevi se nazivaju Fermaovi brojevi, a samo 100 godina kasnije Euler je pokazao da je sljedeći broj, 2 32 + 1 = 4294967297, djeljiv sa 641, te 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 opširno 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 M 19 dokazao Cataldi 1588. godine i 200 godina je bio najveći poznati prost broj, sve dok Ojler nije dokazao da je i M 31 prost. Ovaj rekord je postojao još stotinu godina, a onda je Lucas pokazao da je M 127 prost (a to je već broj od 39 cifara), a nakon toga se istraživanje nastavilo 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 mogao dokazati) kvadratni zakon reciprociteta.
Bio je prvi koji je uveo metode matematičke analize 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 +…
Rezultat dobiven zbirom recipročnih vrijednosti prostih brojeva također se razlikuje. Zbir n članova harmonijskog niza raste približno kao log(n), a 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, čini se da su prosti brojevi prilično nasumično raspoređeni među cijelim brojevima. 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 pitanjima njihove distribucije. Gauss je jednom prijatelju rekao da u bilo kojih slobodnih 15 minuta uvijek broji broj prostih brojeva 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 osnovna gustina 1/log(n). Legendre je procijenio broj prostih brojeva u rasponu od 1 do n kao
π(n) = n/(log(n) - 1,08366)
A Gaus je kao logaritamski integral
π(n) = ∫ 1/log(t) dt
Sa intervalom integracije od 2 do n.
Tvrdnja o gustoći prostih brojeva 1/log(n) poznata je kao teorema distribucije prostih brojeva. Pokušavali su to dokazati tokom cijelog 19. vijeka, a napredak su postigli Čebišev i Riman. Povezali su je s Riemannom hipotezom, još nedokazanom hipotezom o raspodjeli nula Riemannove zeta funkcije. Gustinu prostih brojeva istovremeno su dokazali Adamard i Vallée-Poussin 1896. godine.
Još uvijek postoje mnoga neriješena pitanja u teoriji prostih brojeva, od kojih su neka stara stotinama godina:
- Hipoteza prostih blizanaca je 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)
- Da li je broj Fermatovih prostih brojeva beskonačan? Ima li Fermatovih prostih brojeva nakon 4?
- postoji li 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? - 1?
- ako je p prost, da li 2 p -1 uvijek ne sadrži proste kvadrate među svojim faktorima?
- 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 otkriveni su 2007. godine.
Najveći faktorijalni prost broj (tipa 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.