Teorema.

Postoji beskonačno mnogo prostih brojeva.

Dokaz.

Pretpostavimo da nije. To jest, pretpostavimo da postoji samo n prostih brojeva, a ti prosti brojevi su p 1 , p 2 , …, p n . Pokažimo da uvijek možemo pronaći prost broj drugačiji od navedenih.

Razmotrimo broj p jednak p 1 ·p 2 ·…·p n +1 . Jasno je da se ovaj broj razlikuje od svakog od prostih brojeva p 1 , p 2 , …, p n . Ako je broj p prost, tada je teorema dokazana. Ako je ovaj broj kompozitan, onda, na osnovu prethodne teoreme, postoji prost djelitelj ovog broja (označimo ga p n+1 ). Pokažimo da se ovaj djelitelj ne poklapa ni sa jednim od brojeva p 1 , p 2 , …, p n .

Da to nije tako, onda bi po svojstvima djeljivosti proizvod p 1 ·p 2 ·…·p n bio djeljiv sa p n+1 . Ali broj p je također djeljiv sa p n+1, jednak zbiru p 1 ·p 2 ·…·p n +1. To implicira da drugi član ovog zbira, koji je jednak jedinici, mora biti djeljiv sa p n+1, a to je nemoguće.

Dakle, dokazano je da se uvijek može pronaći novi prost broj, koji nije sadržan ni u jednom broju unaprijed datih prostih brojeva. Dakle, postoji beskonačno mnogo prostih brojeva.

Dakle, zbog činjenice da prostih brojeva ima beskonačno mnogo, pri sastavljanju tabela prostih brojeva oni se uvijek odozgo ograničavaju na neki broj, obično 100, 1.000, 10.000 itd.

Eratostenovo sito

Sada ćemo razgovarati o načinima sastavljanja tabela prostih brojeva. Pretpostavimo da treba da napravimo tabelu prostih brojeva do 100.

Najočiglednija metoda za rješavanje ovog problema je sekvencijalna provjera pozitivnih cijelih brojeva, počevši od 2 i završavajući sa 100 , na prisustvo pozitivnog djelitelja koji je veći od 1 i manji od broja koji se provjerava (iz svojstava djeljivosti, mi znati da apsolutna vrijednost djelitelja ne prelazi apsolutnu vrijednost dividende, različitu od nule). Ako takav djelitelj nije pronađen, tada je broj koji se provjerava prost i upisuje se u tablicu prostih brojeva. Ako se takav djelitelj pronađe, onda je broj koji se provjerava složen, NE unosi se u tabelu prostih brojeva. Nakon toga slijedi prijelaz na sljedeći broj, koji se na sličan način provjerava da li postoji djelitelj.

Hajde da opišemo prvih nekoliko koraka.

Počinjemo sa brojem 2. Broj 2 nema pozitivnih djelitelja osim 1 i 2. Dakle, on je prost, pa ga unosimo u tabelu prostih brojeva. Ovdje treba reći da je 2 najmanji prost broj. Pređimo na broj 3. Njegov mogući pozitivni djelitelj osim 1 i 3 je 2. Ali 3 nije deljivo sa 2, dakle, 3 je prost broj, a takođe ga treba uneti u tabelu prostih brojeva. Pređimo na broj 4. Njegovi pozitivni djelitelji osim 1 i 4 mogu biti 2 i 3, provjerimo ih. Broj 4 je djeljiv sa 2, dakle, 4 je složeni broj i ne treba ga unositi u tablicu prostih brojeva. Imajte na umu da je 4 najmanji složeni broj. Pređimo na broj 5. Provjeravamo da li je barem jedan od brojeva 2, 3, 4 njegov djelitelj. Pošto 5 nije deljivo ni sa 2, ni sa 3, ni sa 4, on je prost i mora biti zapisan u tabeli prostih brojeva. Zatim slijedi prijelaz na brojeve 6, 7 i tako dalje do 100.

Ovaj pristup sastavljanju tabele prostih brojeva je daleko od idealnog. Na ovaj ili onaj način, on ima pravo na postojanje. Imajte na umu da ovom metodom konstruisanja tablice cijelih brojeva možete koristiti kriterije djeljivosti, što će malo ubrzati proces pronalaženja djelitelja.

Postoji pogodniji način za sastavljanje tabele prostih brojeva koji se zove . Riječ "sito" prisutna u nazivu nije slučajna, jer radnje ove metode pomažu, takoreći, da se kroz sito Eratostenovih cijelih brojeva "prosijevaju", velike jedinice, kako bi se odvojile jednostavne od složenih.

Pokažimo Eratostenovo sito u akciji prilikom sastavljanja tabele prostih brojeva do 50.

Prvo zapisujemo redom brojeve 2, 3, 4, ..., 50.

Prvi broj napisan 2 je prost. Sada se od broja 2 uzastopno pomičemo udesno za dva broja i precrtavamo te brojeve dok ne dođemo do kraja sastavljene tablice brojeva. Dakle, svi brojevi koji su višestruki od dva će biti precrtani.

Prvi neprecrtani broj nakon 2 je 3. Ovaj broj je prost. Sada se od broja 3 uzastopno pomičemo udesno za tri broja (uzimajući u obzir već precrtane brojeve) i precrtavamo ih. Dakle, svi brojevi koji su višestruki od tri će biti precrtani.

Prvi neprecrtani broj nakon 3 je 5. Ovaj broj je prost. Sada, od broja 5, uzastopno se pomičemo udesno za 5 brojeva (uzimamo u obzir i ranije precrtane brojeve) i precrtavamo ih. Dakle, svi brojevi koji su višestruki od pet će biti precrtani.

Zatim precrtavamo brojeve koji su višestruki od 7, zatim višestruki od 11, i tako dalje. Proces se završava kada više nema brojeva za precrtavanje. Ispod je popunjena tabela prostih brojeva do 50 dobijenih pomoću Eratostenovog sita. Svi neprecrtani brojevi su prosti, a svi precrtani brojevi su složeni.

Hajde da formulišemo i dokažemo teoremu koja će ubrzati proces sastavljanja tabele prostih brojeva koristeći Eratostenovo sito.

Teorema.

Najmanji pozitivni ne-jedan djelitelj kompozitnog broja a ne prelazi , gdje je iz a .

Dokaz.

Slovom b označavamo najmanji djelitelj složenog broja a koji se razlikuje od jedinice (broj b je prost, što proizlazi iz teoreme dokazane na samom početku prethodnog pasusa). Tada postoji cijeli broj q takav da je a=b q (ovdje je q pozitivan cijeli broj, što slijedi iz pravila za množenje cijelih brojeva), i (kada je b>q, narušen je uvjet da je b najmanji djelitelj a, jer q je također djelitelj a zbog jednakosti a=q b ). Množenjem obje strane nejednakosti pozitivnim i većim od jednog cijelog broja b (to nam je dopušteno), dobivamo , odakle i .

Šta nam dokazana teorema daje u vezi sa Eratostenovim sitom?

Prvo, brisanje složenih brojeva koji su višekratnici prostog broja b treba započeti brojem jednakim (ovo slijedi iz nejednakosti ). Na primjer, precrtavanje brojeva koji su višestruki od dva treba započeti brojem 4, višekratnika tri - brojem 9, višekratnika pet - brojem 25, itd.

Drugo, sastavljanje tabele prostih brojeva do broja n pomoću Eratostenovog sita može se smatrati završenim kada se precrtaju svi složeni brojevi koji su višekratnici prostih brojeva koji ne prelaze. U našem primjeru, n=50 (jer tabelariziramo proste brojeve do 50 ) i , tako da Eratostenovo sito mora izbaciti sve složene višekratnike prostih brojeva 2 , 3 , 5 i 7 koji ne prelaze aritmetički kvadratni korijen od 50 . Odnosno, više ne trebamo tražiti i precrtavati brojeve koji su višekratnici prostih brojeva 11 , 13 , 17 , 19 , 23 i tako dalje do 47 , jer će oni već biti precrtani kao višekratnici manjih prostih brojeva 2 , 3, 5 i 7.

Je li ovaj broj prost ili složen?

Neki zadaci zahtijevaju utvrđivanje da li je dati broj prost ili složen. U opštem slučaju, ovaj zadatak je daleko od jednostavnog, posebno za brojeve čiji se zapis sastoji od značajnog broja znakova. U većini slučajeva morate tražiti neki specifičan način da to riješite. Međutim, pokušaćemo da usmjerimo tok misli za jednostavne slučajeve.

Bez sumnje, može se pokušati koristiti kriterije djeljivosti da se dokaže da je dati broj kompozitan. Ako, na primjer, neki kriterij djeljivosti pokazuje da je dati broj djeljiv s nekim pozitivnim cijelim brojem većim od jedan, tada je originalni broj složen.

Primjer.

Dokaži da je broj 898 989 898 989 898 989 složen.

Rješenje.

Zbir cifara ovog broja je 9 8+9 9=9 17 . Pošto je broj jednak 9 17 djeljiv sa 9, onda se prema kriteriju djeljivosti sa 9 može tvrditi da je i originalni broj djeljiv sa 9. Stoga je kompozit.

Značajan nedostatak ovog pristupa je što nam kriteriji djeljivosti ne dozvoljavaju da dokažemo jednostavnost broja. Stoga, kada provjeravate broj da li je prost ili složen, morate postupiti drugačije.

Najlogičniji pristup je da se nabroje svi mogući djelitelji datog broja. Ako nijedan od mogućih djelitelja nije pravi djelitelj datog broja, tada je taj broj prost; u suprotnom je složen. Iz teorema dokazanih u prethodnom paragrafu, slijedi da se djelitelji datog broja a moraju tražiti među prostim brojevima koji ne prelaze . Dakle, dati broj a može se sukcesivno podijeliti prostim brojevima (koje je zgodno uzeti iz tabele prostih brojeva), pokušavajući pronaći djelitelj broja a. Ako je djelitelj pronađen, tada je broj a složen. Ako među prostim brojevima koji ne prelaze , nema djelitelja broja a, tada je broj a prost.

Primjer.

Broj 11 723 jednostavno ili složeno?

Rješenje.

Hajde da saznamo na koji prosti broj mogu biti djelitelji broja 11 723. Za ovo procjenjujemo.

To je sasvim očigledno , od 200 2 \u003d 40 000 i 11 723<40 000 (при необходимости смотрите статью poređenje brojeva). Dakle, mogući prosti djelitelji od 11.723 su manji od 200. Ovo već uvelike pojednostavljuje naš zadatak. Da to ne znamo, onda bismo morali sortirati sve proste brojeve ne do 200, već do broja 11 723.

Po želji možete preciznije procijeniti. Od 108 2 = 11 664 i 109 2 = 11 881, onda 108 2<11 723<109 2 , следовательно, . Dakle, bilo koji od prostih brojeva manji od 109 potencijalno je prost djelitelj datog broja 11,723.

Sada ćemo redom podijeliti broj 11 723 na proste brojeve 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 5 , 5 6 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Ako se broj 11 723 u potpunosti podijeli jednim od napisanih prostih brojeva, tada će biti složen. Ako nije djeljiv ni sa jednim od zapisanih prostih brojeva, tada je originalni broj prost.

Nećemo opisivati ​​cijeli ovaj monoton i monoton proces podjele. Recimo samo da 11 723

Trenutno su nepoznati polinomski algoritmi za faktoring brojeva, iako nije dokazano da takvi algoritmi ne postoje. RSA kriptosistem i neki drugi su zasnovani na navodnoj visokoj računskoj složenosti problema faktorizacije. Faktorizacija sa polinomskom složenošću je teoretski moguća na kvantnom računaru koristeći Shorov algoritam.

Algoritmi za traženje i prepoznavanje prostih brojeva

Jednostavni načini pronalaženja početne liste prostih brojeva do neke vrijednosti daju Eratostenovo sito, Sundaramovo sito i Atkinovo sito.

Međutim, u praksi, umjesto dobijanja liste prostih brojeva, često je potrebno provjeriti da li je dati broj prost. Algoritmi koji rješavaju ovaj problem nazivaju se testovi primarnosti. Postoji mnogo polinomskih testova primarnosti, ali većina njih je probabilistički (na primjer, Miller-Rabin test) i koristi se za potrebe kriptografije. Godine 2002. dokazano je da je problem provjere primarnosti općenito polinomski rješiv, ali predloženi deterministički Agrawal-Kayal-Saksena test ima prilično veliku računsku složenost, što otežava njegovu primjenu u praksi.

Za neke klase brojeva postoje specijalizovani efikasni testovi primarnosti (vidi dole).

Beskonačnost prostih brojeva

Postoji beskonačno mnogo prostih brojeva. Najstariji poznati dokaz ove činjenice dao je Euklid u Elementima (knjiga IX, izjava 20). Njegov dokaz se može ukratko reproducirati na sljedeći način:

Matematičari su ponudili druge dokaze. Jedan od njih (koji je dao Euler) pokazuje da je zbir recipročnih vrijednosti prvog n prosti brojevi, raste neograničeno s rastom n.

Mersenovi brojevi su povoljni u poređenju sa ostalima tako što imaju efikasan test primarnosti: Luc-Lehmerov test. Zahvaljujući njemu, Mersenneovi prosti brojevi dugo drže rekord kao najveći poznati prosti brojevi.

Za pronalaženje prostih brojeva od preko 100.000.000 i 1.000.000.000 decimalnih cifara, EFF je dodijelio novčane nagrade od 150.000 dolara i 250.000 dolara, respektivno. EFF je ranije dodijelio nagrade za pronalaženje prostih brojeva od 1.000.000 i 10.000.000 decimalnih cifara.

Prosti brojevi posebne vrste

Postoji veliki broj brojeva čija se primarnost može efikasno utvrditi korišćenjem specijalizovanih algoritama.

Za traženje prostih brojeva određenih tipova trenutno se koriste projekti distribuiranog računarstva GIMPS, PrimeGrid. [email protected], Sedamnaest ili poprsje , Riesel sito , [email protected].

Neke nekretnine

• Ako je p prost i p dijeli ab, tada p dijeli a ili b. Dokaz ove činjenice dao je Euklid i poznat je kao Euklidova lema. Koristi se u dokazu osnovne aritmetičke teoreme.
• prsten odbitaka $\backslash mathbb(Z)\_n$ je polje ako i samo ako $n$- jednostavno.
• Karakteristika svakog polja je nula ili prost broj.
• Ako a $str$- jednostavno i $a$- onda prirodno $a^p-a$ podijeljena $str$(Fermatova mala teorema).
• Ako a $G$ je konačna grupa čiji je red $|G|$ podijeljena $str$, onda $G$ sadrži element reda $str$(Cauchyjev teorem).
• Ako a $G$ je konačna grupa, i $p^n$- maksimalni stepen $str$, koji deli $|G|$, onda $G$ ima podgrupu reda $p^n$, nazvana silovska podgrupa , štaviše, broj silovskih podgrupa je jednak $pk+1$ za neki cijeli broj $k$(Sylowove teoreme).
• Prirodno $p\; >\; 1$ je jednostavno ako i samo ako $(p-1)!\; +1$ podijeljena $str$(Wilsonova teorema).
• Ako a $n\; >\; 1$ je prirodno, onda postoji jednostavan $str$, takav da (Bertrandov postulat).
• Niz brojeva inverznih prostim brojevima divergira. Štaviše, kod $x\backslash to\backslash infty$
• Bilo koja aritmetička progresija oblika $a,\; a\; +\; q,\; a\; +\; 2\; q,\; a\; +\; 3\; q,\; ...$, gdje $a,\; q\; >\; 1$- koprosti cijeli brojevi, sadrži beskonačno mnogo prostih brojeva (Dirichletov teorem o prostim brojevima u aritmetičkoj progresiji).
• Svaki prost broj veći od 3 može se predstaviti kao $6k+1$ ili $6k-1$, gdje $k$ je neki prirodan broj. Dakle, ako je razlika između nekoliko uzastopnih prostih brojeva (za k>1) ista, onda je ona nužno višekratnik od 6 - na primjer: 251-257-263-269; 199-211-223; 20183-20201-20219.
• Ako a $p\; >\; 3$- Onda jednostavno $p^2-1$ djeljivo sa 24 (važi i za sve neparne brojeve koji nisu djeljivi sa 3) .
• Green-Tao teorema. Postoje proizvoljno dugačke konačne aritmetičke progresije koje se sastoje od prostih brojeva.
• $n^k-1$, gdje n>2, k>1. Drugim riječima, broj koji slijedi nakon prostog broja ne može biti kvadrat ili veći stepen sa osnovom većom od 2. Iz ovoga također slijedi da ako prost broj ima oblik $2^k-1$, onda k- prosti (vidi Mersenne brojeve).
• Nijedan prost broj ne može biti u obliku $n^(2k+1)+1$, gdje n>1, k>0. Drugim riječima, broj koji prethodi prostom ne može biti kocka ili veći neparni stepen sa osnovom većom od 1.

Formule za pronalaženje prostih brojeva

U različitim vremenima, pokušaji su da se specificira izraz čije vrijednosti, kada različita značenja njegove sastavne varijable bi bili prosti brojevi. L. Euler je ukazao na polinom $\backslash textstyle\; n^2-n+41,$ uzimajući proste vrijednosti na n = 0, 1, 2, …, 40. Međutim, kada n=41 vrijednost polinoma je složeni broj. Može se dokazati da u jednoj varijabli n ne postoji polinom koji uzima proste vrijednosti za sve cijele brojeve n. P. Fermat je predložio da svi brojevi oblika 2 2 k + 1 jednostavno; međutim, Euler je opovrgao ovu pretpostavku dokazavši da je broj 2 2 5 + 1 = 4 294 967 297 - kompozitni.

Ipak, postoje polinomi čiji se skup pozitivnih vrijednosti, za nenegativne vrijednosti varijabli, poklapa sa skupom prostih brojeva. Jedan primjer je polinom

• $\backslash begin\; (poravnati)$

&(k+2) (1 - ^2 - [(gk + 2g + k + 1)(h + j) + h - z]^2 - ^2 - \\ &^2 - ^2 - [(a ^2 - 1)y^2 + 1 - x^2]^2 - \\ &^2 - [((a + u^2(u^2 - a))^2 - 1)(n + 4dy) ^2 + 1 - (x + cu)^2]^2 - ^2 - \\ &[(a^2 - 1)l^2 + 1 - m^2]^2 - ^2 - ^2 - \ \ &^2 - ^2) \end(poravnati) koji sadrži 26 varijabli i ima stepen 25. Najmanji stepen za poznate polinome ovog tipa je 5 sa 42 varijable; najmanji broj varijabli je 10 sa stepenom od oko 1,6·10 45 . Ovaj rezultat je poseban slučaj Diofantovog svojstva bilo kojeg nabrojivog skupa koji je dokazao Jurij Matijasevič.

Otvorena pitanja

Još uvijek ima mnogo otvorenih pitanja u vezi s prostim brojevima, od kojih je najpoznatija naveo Edmund Landau na Petom međunarodnom matematičkom kongresu:

Otvoren problem je i postojanje beskonačnog broja prostih brojeva u mnogim cjelobrojnim nizovima, uključujući Mersenne brojeve, Fibonačijeve brojeve, Fermatove brojeve i druge.

Prijave

Veliki prosti brojevi (reda od 10.300) se koriste u kriptografiji s javnim ključem. Prosti brojevi se također koriste u hash tablicama i za generiranje pseudoslučajnih brojeva (posebno u Mersenne Whirlwind PRNG).

Varijacije i generalizacije

• U teoriji prstenova, grani opće algebre, definirani su koncepti praelementa i prostog ideala.
• U teoriji čvorova, koncept jednostavnog čvora je definiran kao netrivijalan čvor koji se ne može predstaviti kao povezani zbir netrivijalnih čvorova.

vidi takođe

Napišite recenziju na članak "Prom broj"

Bilješke

Izvod koji karakteriše prost broj

Nataša je bila mirnija, ali ne i vedrija. Ona ne samo da je izbegavala sve spoljašnje uslove radosti: balove, klizanje, koncerte, pozorište; ali se nikada nije smijala tako da se njene suze nisu čule zbog njenog smijeha. Nije znala da peva. Čim je počela da se smeje ili pokušala da peva sama sa sobom, suze su je gušile: suze kajanja, suze sećanja na to neopozivo, čisto vreme; suze ozlojeđenosti što je tako, uzalud, uništila svoj mladi život, koji je mogao biti tako srećan. Smijeh i pjevanje posebno su joj se činili kao bogohuljenje na njenu tugu. Nikada nije razmišljala o koketiji; nije se ni morala suzdržati. Govorila je i osjećala da su u to vrijeme za nju svi muškarci bili potpuno isti kao luda Nastasja Ivanovna. Unutrašnji čuvar joj je odlučno zabranio bilo kakvu radost. I nije imala sve nekadašnje životne interese iz tog djevojačkog, bezbrižnog načina života puna nade. Češće i najbolnije prisjećala se jesenjih mjeseci, lova, strica i Božića provedenog s Nicolasom u Otradnom. Šta bi dala da vrati makar jedan dan iz tog vremena! Ali bilo je gotovo zauvijek. Tada je nije zavarala slutnja da se to stanje slobode i otvorenosti za sve radosti više nikada neće vratiti. Ali morao sam živjeti.
Bilo joj je utješno misliti da nije bolja, kao što je prije mislila, već gora i mnogo gora od svih, svih, koji samo postoje na svijetu. Ali ovo nije bilo dovoljno. Ona je to znala i pitala se: „Šta dalje? I onda nije bilo ništa. U životu nije bilo radosti, a život je prošao. Nataša se, očigledno, trudila samo da nikome ne bude na teretu i da se nikome ne meša, ali za sebe ništa nije trebalo. Odselila se od svih kod kuće, a samo sa bratom Petjom joj je bilo lako. Više je voljela biti s njim nego s ostalima; a ponekad, kada je bila s njim oči u oči, smijala se. Jedva je izlazila iz kuće, a od onih koji su dolazili da ih vide, bilo joj je drago samo zbog Pjera. Nije bilo moguće prema njoj postupati nježnije, pažljivije i u isto vrijeme ozbiljnije nego što se prema njoj odnosio grof Bezuhov. Natasha Osss je svjesno osjetila tu nježnost tretmana i stoga je nalazila veliko zadovoljstvo u njegovom društvu. Ali nije mu bila ni zahvalna na njegovoj nježnosti; ništa dobro od Pjera nije joj se činilo naporom. Činilo se tako prirodnim da Pjer bude ljubazan prema svima da u njegovoj dobroti nije bilo nikakve zasluge. Ponekad je Nataša primećivala Pjerovu neprijatnost i nespretnost u njenom prisustvu, posebno kada je želeo da učini nešto prijatno za nju ili kada se plašio da će nešto u razgovoru dovesti Natašu u bolna sećanja. Ona je to primetila i pripisala njegovoj opštoj ljubaznosti i stidljivosti, koja je, prema njenim rečima, kao i kod nje, trebalo da bude sa svima. Posle onih nehotičnih reči da bi, da je slobodan, tražio od nje ruke i ljubav na kolenima, izgovorenih u trenutku tako silnog uzbuđenja za nju, Pjer nikada nije rekao ništa o svojim osećanjima prema Nataši; i bilo joj je očigledno da su te reči, koje su je tada tako tešile, izgovorene, kao što se izgovaraju svakakve besmislene reči da se uteše dete koje plače. Ne zato što je Pjer bio oženjen muškarac, već zato što je Nataša između sebe i njega u najvišem stepenu osećala tu silu moralnih barijera - čije je odsustvo osećala sa Kyraginom - nije joj palo na pamet da bi mogla da izađe iz veze sa Pjerom. ne samo ljubav s nje, ili još manje s njegove strane, nego čak i ona vrsta nježnog, samoizvjesnog, poetskog prijateljstva između muškarca i žene, za koje je znala nekoliko primjera.
Na kraju Petrovskog posta, Agrafena Ivanovna Belova, susjeda Rostovskih Otradnenskaja, došla je u Moskvu da se pokloni moskovskim svecima. Pozvala je Natašu da ode u krevet, a Nataša je sa radošću prihvatila ovu ideju. Uprkos zabrani lekara da izlazi rano ujutru, Nataša je insistirala na postu, a ne na postu kao obično u kući Rostovovih, odnosno da sluša tri službe kod kuće, već da bi postila kao što je Agrafena Ivanovna nekada postila. je, cijeli tjedan bez propuštanja niti jedne večernje, mise ili jutrenja.
Grofici se dopao Natašina revnost; u duši, posle neuspešnog lečenja, nadala se da će joj molitva pomoći sa još lekova, i iako sa strahom i skrivajući se od lekara, pristala je na Natašinu želju i poverila je Belovoj. Agrafena Ivanovna je došla u tri sata ujutru da probudi Natašu i uglavnom je zatekla kako više ne spava. Nataša se plašila da prespava vreme jutra. Umivši se žurno i ponizno obučevši svoju najgoru haljinu i staru mantiju, dršćući od svježine, Nataša je izašla na puste ulice, providno obasjane jutarnjom zorom. Po savetu Agrafene Ivanovne, Nataša nije išla u crkvu u svojoj parohiji, već u crkvi, u kojoj je, prema pobožnoj Belovoj, bio veoma strog sveštenik i high life. U crkvi je uvijek bilo malo ljudi; Nataša i Belova zauzele su svoje uobičajeno mesto ispred ikone Majke Božije, ugrađene u zadnji deo leve pevnice, a Natašin novi osećaj poniznosti pred velikim, neshvatljivim, obuzeo ju je kada je, u ovaj neobičan čas ujutru, gledajući u crno lice Bogorodice, obasjano svećama koje su gorele ispred njega, i svetlost jutra koja je padala sa prozora, slušala je zvuke službe, koju je pokušavala da prati, razumijevanje njih. Kada ih je razumela, njeno lično osećanje sa svojim nijansama pridružilo se njenoj molitvi; kad nije razumela, ipak joj je bilo slađe misliti da je želja da se sve razume ponos, da je nemoguće sve razumeti, da se samo treba verovati i predati se Bogu, koji je u tom trenutku – osetila je – vladao njenu dušu. Prekrstila se, poklonila, a kad nije razumjela, samo je, užasnuta svojom gadošću, zamolila Boga da joj sve oprosti, za sve i smiluj se. Molitve kojima se najviše posvetila bile su molitve pokajanja. Vraćajući se kući u ranim jutarnjim satima, kada su na posao išli samo zidari, domara meli ulicu, a svi su još spavali po kućama, Nataša je za nju doživjela novi osjećaj mogućnosti da se popravi od svojih poroka i mogućnost novog, čistog života i sreće.
Tokom cijele sedmice u kojoj je vodila ovaj život, ovaj osjećaj je svakim danom rastao. A sreća zajedništva ili opštenja, kako joj je Agrafena Ivanovna rekla radosno se igrajući ovom rečju, učinila joj se tolikom da joj se činilo da neće doživeti ovu blagoslovenu nedelju.
Ali došao je srećan dan i kada se Nataša, te nezaboravne nedelje, u beloj haljini od muslina, vratila sa pričesti, prvi put posle mnogo meseci osetila se smirenom i neopterećenom životom koji je pred njom.
Doktor koji je došao tog dana pregledao je Natašu i naredio da se nastavi sa poslednjim puderima koje je prepisao pre dve nedelje.
„Imperativ je nastaviti – ujutro i uveče“, rekao je, očito i sam savjesno zadovoljan svojim uspjehom. „Samo molim vas budite oprezni. Smirite se, grofice, - reče doktor u šali, spretno podižući zlatnu u šaku, - uskoro će opet zapjevati i postati žustar. Veoma, veoma u prilog njenom poslednjem leku. Mnogo se razvedrila.
Grofica je pogledala svoje nokte i pljunula, vraćajući se u dnevnu sobu vedra lica.

Početkom jula u Moskvi su se širile sve uznemirujuće glasine o toku rata: govorilo se o suverenovoj privlačnosti narodu, o dolasku samog suverena iz vojske u Moskvu. A kako manifest i apel nisu primljeni prije 11. jula, o njima i o situaciji u Rusiji kružile su pretjerane glasine. Govorili su da suveren odlazi jer je vojska u opasnosti, govorili su da je Smolensk predat, da Napoleon ima milion vojnika i da samo čudo može spasiti Rusiju.
11. jul, subota, manifest je primljen, ali još nije štampan; a Pjer, koji je bio kod Rostovovih, obećao je sutradan, u nedelju, da će doći na večeru i doneti manifest i apel, koje će dobiti od grofa Rostopčina.
Ove nedjelje, Rostovovi su, kao i obično, otišli na misu u kućnu crkvu Razumovskih. Bio je vruć julski dan. Već u deset sati, kada su Rostovovi izašli iz kočije ispred crkve, na vrelom vazduhu, u povicima trgovaca, u blistavim i laganim letnjim haljinama gomile, u prašnjavom lišću drveća bulevara, u zvucima muzike i belim pantalonama bataljona koji je prošao na razvod, u grmljavini pločnika i U jarkom odsjaju vrelog sunca bila je ona letnja malaksalost, zadovoljstvo i nezadovoljstvo sadašnjošću, koja posebno se oštro osjeća po vedrom vrućem danu u gradu. U crkvi Razumovskih bilo je svo moskovsko plemstvo, svi poznanici Rostovovih (ove godine, kao da su nešto očekivali, u gradu je ostalo mnogo imućnih porodica, koje su se obično kretale po selima). Prolazeći iza lakeja u livreji, koji je razdvajao gomilu pored svoje majke, Nataša je čula glas mladi čovjek, koji je o njoj govorio preglasnim šapatom:
- Ovo je Rostov, isti...
- Kako tanak, ali ipak dobar!
Čula je, ili joj se činilo, da se spominju imena Kuragina i Bolkonskog. Međutim, njoj se to uvijek činilo. Uvek joj se činilo da svi, gledajući u nju, razmišljaju samo o tome šta joj se dogodilo. Pateći i umirući u duši, kao i uvek u gomili, Nataša je hodala u svojoj ljubičastoj svilenoj haljini sa crnom čipkom onako kako žene znaju da hodaju - što mirnije i veličanstvenije, to je osećala bolnije i stidnije u duši. Znala je i nije se varala da je dobra, ali to joj sada nije prijalo, kao ranije. Naprotiv, to ju je najviše mučilo u posljednje vrijeme, a posebno ovog vedrog, vrelog ljetnog dana u gradu. „Još jedna nedjelja, još jedna sedmica“, rekla je sebi, prisjećajući se kako je bila ovdje te nedjelje, „i dalje isti život bez života, i svi isti uslovi u kojima se prije bilo tako lako živjeti. Ona je dobra, mlada, a ja znam da sam sad ja dobra, prije sam bila loša, ali sad sam dobra, znam, pomislila je, ali najbolje godine prolaze uzalud, ni za koga. Stajala je pored majke i razmenjivala odnose sa bliskim poznanicima. Nataša je, iz navike, gledala ženski toalet, osuđivala držanje i nepristojan način da se prekrsti rukom u malom prostoru onog koji je stajao u blizini, opet je s ljutnjom pomislila da je osuđuju, da osuđivala je, i odjednom, čuvši zvukove službe, bila je užasnuta svojom podlosti, užasnuta činjenicom da je opet izgubila svoju nekadašnju čistotu.
Zgodni, tihi starac služio je s tom krotkom svečanošću koja ima tako veličanstven, smirujući učinak na duše onih koji se mole. Kraljevska vrata su se zatvorila, veo se polako povukao; misteriozni tihi glas je rekao nešto odatle. Njoj neshvatljive suze su stajale u Natašinim grudima i uznemirivalo ju je jedno radosno i bolno osećanje.
„Nauči me šta da radim, kako da se unapredim zauvek, zauvek, kako da se nosim sa svojim životom...“ pomislila je.
Đakon je izašao na propovjedaonicu, ispravio je širom thumb, dugu kosu ispod porcije i, stavivši krst na prsa, glasno i svečano počeo čitati riječi molitve:
“Pomolimo se Gospodu za mir.”
„U miru, svi zajedno, bez klasne razlike, bez neprijateljstva, ujedinjeni bratskom ljubavlju, molićemo se“, mislila je Nataša.
- O miru odozgo i o spasenju naših duša!
„O svetu anđela i duša svih bestelesnih bića koja žive iznad nas“, molila se Nataša.
Kada su se molili za vojsku, sjetila se brata i Denisova. Kada su se molili za mornare i putnike, sjetila se kneza Andreja i molila se za njega, i molila se da joj Bog oprosti zlo koje mu je učinila. Kada su se molili za one koji nas vole, molila se za svoju porodicu, za svog oca, majku, Sonju, po prvi put shvativši svu svoju krivicu pred njima i osetivši svu snagu svoje ljubavi prema njima. Kada smo se molili za one koji nas mrze, ona je sebi izmislila neprijatelje i mrzitelje da bi se molila za njih. U neprijatelje je ubrojala kreditore i sve one koji su se obračunali sa njenim ocem, a svaki put kad bi pomislila na neprijatelje i mrzitelje, sjetila se Anatola, koji joj je nanio toliko zla, i iako nije bio mrzitelj, radosno se molila za njega kao neprijatelja. Samo tokom molitve osjećala se sposobnom da se jasno i smireno prisjeti i princa Andreja i Anatola, kao ljudi prema kojima su njena osjećanja uništena u poređenju sa njenim osjećajem straha i strahopoštovanja prema Bogu. Kada su se molili za kraljevsku porodicu i za Sinod, posebno se nisko poklonila i prekrstila, govoreći sebi da, ako ne razumije, ne može sumnjati i još uvijek voli vladajući Sinod i moli se za njega.
Završivši litaniju, đakon prekrsti orarion oko prsa i reče:
“Predajmo sebe i svoje živote Kristu Bogu našem.”
„Izdaćemo se Bogu“, ponavljala je Nataša u duši. Bože moj, posvećujem se tvojoj volji, pomislila je. - Neću ništa, neću; nauči me šta da radim, gde da upotrebim svoju volju! Da, uzmi me, uzmi me! - rekla je Nataša sa dirljivim nestrpljenjem u duši, ne prekrstivši se, spuštajući mršave ruke i kao da očekuje da će je neka nevidljiva sila uzeti i spasiti od nje same, od njenog kajanja, želja, prekora, nada i poroka.
Grofica je nekoliko puta tokom službe osvrnula se na nježno, blistavih očiju, lice svoje kćeri i molila se Bogu da joj pomogne.

Ilijin odgovor je tačan, ali ne baš detaljan. Inače, u 18. veku jedan se još uvek smatrao prostim brojem. Na primjer, veliki matematičari kao što su Euler i Goldbach. Goldbach je autor jednog od sedam zadataka milenijuma - Goldbach hipoteze. Originalna formulacija kaže da se bilo koji paran broj može predstaviti kao zbir dva prosta broja. Štaviše, u početku je 1 uzeto u obzir kao prost broj, a vidimo ovo: 2 = 1 + 1. Ovo je najmanji primjer koji zadovoljava originalnu formulaciju hipoteze. Kasnije je to ispravljeno, a formulacija je dobila moderan izgled: "svaki paran broj, počevši od 4, može se predstaviti kao zbir dva prosta broja."

Prisjetimo se definicije. Prosti broj p je prirodan broj p koji ima samo 2 različita prirodna djelitelja: sam p i 1. Posljedica iz definicije: prost broj p ima samo jedan prost djelitelj - sam p.

Pretpostavimo sada da je 1 prost broj. Po definiciji, prost broj ima samo jedan prost djelitelj - sebe. Tada se ispostavlja da je svaki prost broj veći od 1 djeljiv prostim brojem koji se od njega razlikuje (za 1). Ali dva različita prosta broja ne mogu biti djeljiva jedan s drugim, jer inače to nisu prosti, već složeni brojevi, a to je u suprotnosti sa definicijom. Ovakvim pristupom ispada da postoji samo 1 prost broj - sama jedinica. Ali ovo je apsurdno. Dakle, 1 nije prost broj.

1, kao i 0, čine drugu klasu brojeva - klasu neutralnih elemenata u odnosu na n-arne operacije u nekom podskupu algebarsko polje. Štoviše, s obzirom na operaciju sabiranja, 1 je također generirajući element za prsten cijelih brojeva.

S obzirom na to, nije teško pronaći analoge prostih brojeva u drugim algebarskim strukturama. Pretpostavimo da imamo multiplikativna grupa, formiran od stepena 2 počevši od 1: 2, 4, 8, 16, ... itd. 2 ovdje djeluje kao oblikovni element. Prosti broj u ovoj grupi je broj koji je veći od najmanjeg elementa i djeljiv samo sam sa sobom i najmanjim elementom. U našoj grupi samo 4 imaju takva svojstva.To je to. U našoj grupi više nema prostih brojeva.

Da je 2 takođe prost broj u našoj grupi, onda pogledajte prvi pasus - opet bi se pokazalo da je samo 2 prost broj.

Koji ima samo 2 različita prirodna djelitelja. Drugim riječima, broj str onda će biti jednostavno kada je veće od jedinstva i može se podijeliti samo jedinstvom i samim sobom - str.

Zovu se prirodni brojevi, veliki i brojevi koji nisu prosti kompozitni brojevi. Dakle, svi prirodni brojevi su podijeljeni u 3 klase: jedinica (ima 1 djelitelj), primarni brojevi(imaju 2 razdjelnika) i kompozitni brojevi(imaju više od 2 djelitelja).

Početak str nizovi prostih brojeva izgleda ovako:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

Ako prirodne brojeve predstavimo kao proizvod prostih brojeva, onda će se to zvati dekompozicija na proste brojeve ili faktorizacija broja.

Najveći poznati prost broj.

Najveći poznati prost broj je 2 57885161 - 1. Ovaj broj se sastoji od 17 425 170 decimalnih znamenki i naziva se prostim Mersennov broj(M57885161).

Neka svojstva prostih brojeva.

Recimo str- jednostavno, i str deli ab, onda str deli a ili b.

prsten odbitaka Znće se zvati poljem samo ako n- jednostavno.

Karakteristika svih polja je nula ili prost broj.

Kada str- jednostavno i a- prirodnim sredstvima a p-a mogu se podijeliti na str (mala teorema Farma).

Kada G je konačna grupa čiji je red |G| podijeliti po str, tako na G postoji element reda str (Cauchyjev teorem).

Kada G je konačna grupa, i p n- najviši stepen str podjela |G|, tako na G postoji podgrupa reda p n, koji se naziva silovska podgrupa, osim toga, odgovara i broj silovskih podgrupa pk+1 za neku celinu k(Sylowove teoreme).

Prirodno p > 1 biće jednostavno samo ako (p-1)! +1 možeš duvati str (Wilsonova teorema).

Kada n > 1- prirodno, što znači da postoji jednostavno str: n< p < 2 n (postulat Bertranda).

Niz brojeva koji su inverzni prostim brojevima divergira. Osim toga, u .

Bilo koja aritmetička progresija tipa a, a + q, a + 2 q, a + 3 q, ..., gdje a, q > 1- cela relativno prosti brojevi, sadrži beskonačan broj prostih brojeva ( Dirichletova teorema o prostim brojevima u aritmetičkoj progresiji).

Svaki prost broj veći od 3 može se predstaviti kao 6k+1 ili 6k-1, gdje k- prirodni broj. Na osnovu toga, kada razlika nekoliko uzastopnih prostih brojeva (za k>1) je isto, što znači da je tačno djeljivo sa šest - na primjer: 251-257-263-269; 199-211-223; 20183-20201-20219 .

Kada p > 3 je prost broj, što znači p 2 -1 podijeljena 24 (radi i za neparne brojeve koji nisu djeljivi sa tri).

Green-Tao teorema. Postoje beskonačne aritmetičke progresije koje se sastoje od prostih brojeva.

nk-1, gdje n>2, k>1. Drugim riječima, broj koji slijedi nakon prostog broja ne može biti kvadrat ili veći stepen sa osnovom većom od dva. Može se zaključiti da kada je prost broj predstavljen kao 2k-1, znači k- jednostavno.

Nijedan prost broj se ne može predstaviti kao n 2k+1 +1, gdje n>1, k>0. Drugim riječima, broj koji prethodi prostom ne može biti kocka ili veći neparni stepen sa osnovom većom od jedan.

Postoje polinomi u kojima se skup nenegativnih vrijednosti za pozitivne vrijednosti varijabli poklapa sa skupom prostih brojeva. primjer:

Ovaj polinom sadrži 26 varijabli, ima 25. Najniži stepen za poznate polinome prikazanog oblika je pet sa 42 varijable; najmanji broj varijabli je deset pri snazi ​​od približno 1,6·10 45 .

Operacije sa prostim brojevima.

1. Proizvod prostih brojeva.

2. Razlika prostih brojeva.

3. Zbir prostih brojeva.

4. Podjela prostih brojeva.