§2 Prosti brojevi.

str.1 Prosti i složeni brojevi.

Koliko djelitelja može imati prirodan broj? Broj 1 ima samo jedan djelitelj. Svaki prirodan broj ima dva djelitelja: 1 i sam broj A. Postoje brojevi koji nemaju drugih djelitelja.

Definicija . Prirodni broj R naziva se prostim ako ima tačno dva djelitelja: 1 i p.

Definicija . Prirodni broj, a, naziva se kompozitnim ako, pored 1 i a, ima i najmanje jedan djelitelj.

Komentar. Broj 1 nije ni složen ni prost.

Gomila N može se podijeliti u tri podskupa.

1 je broj koji ima jedan djelitelj.

Prosti brojevi koji imaju tačno dva djelitelja.

Složeni brojevi koji imaju najmanje tri djelitelja.

Zapišimo prvih nekoliko prostih brojeva:

2, 3, 5, 7, 11, 13, 17 …

Da li je ovaj niz beskonačan ili možemo navesti sve proste brojeve? Odgovor je već bio poznat Euklidu.

Teorema. (Euklid)

Skup prostih brojeva je beskonačan.

Dokaz. “
„Neka
- skup svih prostih brojeva, gdje - posljednji (najveći) prost broj.

Hajde da napravimo broj
. Očigledno,
, znači, N-kompozit.
je podijeljen na jedan od jednostavnih, na primjer, na . Ali tada, prema svojstvima djeljivosti, 1 se dijeli sa , što je nemoguće.

Razmotrimo neka elementarna svojstva prostih brojeva.

1. Neka
- najmanji djelitelj prirodnog broja a.

Onda str-Prost broj.

Dokaz. Neka d- neki djelitelj broja str.

Ali str-najmanji djelitelj
ili
str-jednostavno.

2. Neka
- najmanji djelitelj složenog broja A.

Onda

Dokaz. a-kompozit, znači

Po stanju

3. Neka je a prirodan broj, str- Prost broj.

Tada je a podijeljeno sa str, ili A I str obostrano jednostavno.

Dokaz. Neka
. D- prosti djelitelj
ili

Ako d=1, zatim a i str obostrano jednostavno.

Ako d=str, tada je a podijeljeno sa r.

4. Neka str- prost broj, proizvod a b podijeljena str, tada je a podijeljeno sa str ili b podijeljeno sa r.

Dokaz. Ako a nije djeljivo sa str, zatim svojstvom 3 GCD(A, str)=1.

Ali onda, po svojstvu 2 koprosta broja, b podijeljena R.

Napomena 1. Svojstvo 4 može se lako generalizirati indukcijom: ako je proizvod
djeljiv prostim str, onda postoji faktor , koji je podijeljen na r.

Napomena 2. Ako je posao
djeljiv prostim str, i svi faktori su prosti brojevi, onda je barem jedan od faktora jednak p.

Za sastavljanje liste prostih brojeva koji ne prelaze dati broj N, koristite algoritam nazvan “Eratostenovo sito”.

Zapišimo prirodne brojeve od 2 do N.

Broj 2 je prost. Precrtajmo sve brojeve koji su višekratnici 2 (osim 2) sa liste. Prvi od preostalih, broj 3, bit će prost. Precrtajmo sve brojeve koji su višekratnici broja 3 (osim 3) sa liste. Prvi od preostalih brojeva, 5, će biti prost. Zatim precrtavamo sve brojeve koji su višestruki od 5 (osim broja 5) i tako dalje.

Algoritam će se zaustaviti kada broj koji nije precrtan postane veći od
. Zaista, prema svojstvu 2, svi složeni brojevi u našoj listi imaju djelitelj
. To znači da su već precrtani.

Svi ostali brojevi su prosti.

Primjer. Pronađite sve proste brojeve u intervalu od 2 do 100.

Rješenje. Precrtajmo (označimo) brojeve koji su višestruki od 2 (slika 1).

Sledeći prost broj
svi ostali brojevi su prosti (slika 5).

Komentar. Ako str- prvi broj nije precrtan, onda su svi brojevi manji već precrtano.
Precrtajte višekratnike broja str možete početi sa .

klauzula 2 Faktorizacija.

Složeni broj 495 ima djelitelj 5, što znači
. Drugi faktor je takođe složeni broj
. Nastavljajući proces, možete u početku faktorizirati broj

Definicija . Faktoring kompozitnog broja N nazvana dekompozicija N u osnovne faktore.

Najočigledniji način da se faktori broje N svodi se na nabrajanje svih mogućih prostih djelitelja,
.

Primjer. Faktori broj 323.

primeti, to
. To znači da se djelitelj mora tražiti među prostim brojevima
. Prolazeći kroz njih jednu po jednu otkrivamo to

Primjer. Dokažite da je 919 prost broj.

Jer
, tada najmanji prosti djelitelj ne prelazi 29. Provjerom ćemo se uvjeriti da 919 nije djeljivo prostim brojevima.
- Prost broj.

Za velike prirodne brojeve, razmatrana metoda je neefikasna. Mnogi matematičari su tražili jednostavnije metode faktorizacije koje su zahtijevale manje računanja.

I. Fermatova metoda.

Neka N- dati broj,
. Formiranje brojeva

Ako se ispostavi da je jedan od njih tačan kvadrat, onda dobijamo jednakost
, ili
.

Pretraživanje treba izvršiti do vrijednosti
. (U ovom slučaju
I
). Ako je tačan kvadrat tada se nisu sreli N- Prost broj.

Primjer. Faktoriziraj N=9271.

Imamo
, što znači m=97. Izračunajmo sekvencijalno: .

II. Ojlerova metoda.

Euler je predložio zapisivanje broja N kao suma
, Gdje d- posebno odabran množitelj takav da GCD (x, y d)=1. magnitude d zavisi od vrste broja N. Sta ako N=4k+1 onda d=1 ako N=6k+1 onda d=3, itd. Ojler je ukupno naveo 65 faktora d za različite tipove N.

Ako N predstavljen kao
dva načina (sa istim d), To N može biti faktorizovana.

Na primjer, neka

Onda gde GCD(u,v)=1.

Dobijamo sistem:
I

rješavajući koje, nalazimo: .

Primjer. Faktoriziraj N = 2197.

Dakle, u=2, v=3, t=10, s=24.

.

III. Brojne tehnike su zasnovane na jednostavnim algebarskim identitetima. Na primjer, teorema Sophije Germain to kaže
- složeni broj.

Ovo proizilazi iz činjenice da kada N>1 oba faktora su veća od 1.

Poslednjih decenija, potraga za novim efikasnim algoritmima faktorizacije bio je jedan od najhitnijih problema u teoriji brojeva. Razlog za to bio je razvoj kriptografskih algoritama javnog ključa, čije dešifriranje zahtijeva faktorizaciju velikih kompozitnih brojeva.

klauzula 3. O formulama koje generiraju proste brojeve.

Dugo vremena matematičari su pokušavali pronaći formulu koja bi im omogućila da izračunaju bilo koji veliki prost broj. Najpoznatija je Mersenneova formula.
i Fermatovi brojevi .

Definicija .
- Mersenovi brojevi.

Za složene vrijednosti
broj
podijeljena a to znači da neće biti jednostavno.

Neka N- Prost broj. Zatim su prosti brojevi.

Ali već
, dakle prost broja str ne garantuje prostatu
.

Ispostavilo se da su Mersenneovi brojevi jednostavni na .

Jednostavnost brojeva
(napisano u 139 cifara) dokazao je 1876. godine francuski matematičar E. Luc.

Dalja potraga za Mesenne prostim brojevima nastavljena je uz pomoć kompjuterske tehnologije.

Najpoznatiji (od 2011.) prost broj je 46. Mersenov broj. Ovo
. Za pisanje je potrebno oko 13 miliona cifara.

Osnova za računske algoritme je kriterijum jednostavnosti brojeva
, koju je naveo Luc 1878. i poboljšao Lemaire 1930. godine.

Lucas–Lemaireov kriterij.

Broj
prost ako i samo ako je u rekurentnom nizu
član
podijeljena
.

Danas je nepoznato da li je skup Mersenovih brojeva konačan ili beskonačan.

Definicija .
- Fermaovi brojevi.

Prvi članovi niza su prosti brojevi:

Fermat je predložio (1650) da bi svi brojevi ovog tipa bili prosti. Međutim, Euler je pokazao (1739) da .

Trenutno je nepoznato da li postoje drugi Fermatovi prosti brojevi na
.

Koristeći Fermatove brojeve možemo dobiti još jedan dokaz Euklidove teoreme.

Teorema(Poya).

Bilo koja dva Fermatova broja su relativno prosti.

Dokaz. Neka I
- proizvoljni Fermaovi brojevi.

Pokažimo to
podijeljena . U stvari, deljiv je sa x+1, tj. on .

Neka je m zajednički djelitelj I
. Tada i od tada
, znači,
. Ali Fermaovi brojevi su neparni

Posljedica. Postoji beskonačan broj prostih brojeva.

Dokaz. svaki od
ima neparni djelitelj koji ne dijeli ostale Fermatove brojeve; dakle, postoji najmanje N jednostavni neparni brojevi,
Postoji beskonačno mnogo prostih brojeva.

Komentar. Fermatovi prosti brojevi se neočekivano pojavljuju u problemu konstruisanja regularnog N– kvadrat pomoću šestara i ravnala. Gauss je dokazao da je konstrukcija moguća ako i samo ako
, Gdje - Fermaovi prosti brojevi.

Neosnovane pretpostavke o jednostavnosti brojeva
I podstakao je naučnike da potraže druge formule čije bi vrijednosti bile samo prosti brojevi ili bi barem sadržavali beskonačan broj prostih vrijednosti.

Ojler je obratio pažnju na polinome:
, specificirajući proste brojeve na
i , uzimajući jednostavne vrijednosti na
.

Kasnije je dokazana sljedeća teorema.

Teorema(Goldbach).

Nema polinoma
sa cjelobrojnim koeficijentima ne mogu uzeti proste vrijednosti
pred svima
.

Dokaz. Pusti, pusti
- Prost broj.

Zatim prema Taylorovoj formuli: .

Sve šanse
- cijeli brojevi
podijeljeno sa r.

Ako pokušate dobiti vrijednosti
tada su bile jednostavne
za sav cijeli broj t, ali to je u suprotnosti sa činjenicom da
.

Definicija 1. prost broj− je prirodni broj veći od jednog koji je djeljiv samo sam sa sobom i 1.

Drugim riječima, broj je prost ako ima samo dva različita prirodna djelitelja.

Definicija 2. Poziva se svaki prirodni broj koji osim sebe i jedinice ima druge djelitelje složeni broj.

Drugim riječima, prirodni brojevi koji nisu prosti brojevi nazivaju se složenim brojevima. Iz definicije 1 slijedi da složeni broj ima više od dva prirodna faktora. Broj 1 nije ni prost ni složen jer ima samo jedan djelitelj 1 i, pored toga, mnoge teoreme o prostim brojevima ne vrijede za jedinicu.

Iz definicija 1 i 2 slijedi da je svaki pozitivni cijeli broj veći od 1 ili prost broj ili složeni broj.

Ispod je program za prikaz prostih brojeva do 5000. Popunite ćelije, kliknite na dugme "Kreiraj" i sačekajte nekoliko sekundi.

Tabela prostih brojeva

Izjava 1. Ako str- prost broj i a bilo koji cijeli broj, tada bilo koji a podijeljena str, ili str I a koprosti brojevi.

Zaista. Ako str Prost broj je djeljiv samo sam sa sobom i 1 ako a nije djeljivo sa str, tada najveći zajednički djelitelj a I str je jednako 1. Tada str I a koprosti brojevi.

Izjava 2. Ako je proizvod više brojeva brojeva a 1 , a 2 , a 3, ... je djeljiv prostim brojem str, zatim barem jedan od brojeva a 1 , a 2 , a 3, ...djeljivo sa str.

Zaista. Ako nijedan od brojeva nije djeljiv sa str, zatim brojevi a 1 , a 2 , a 3, ... bili bi koprosti brojevi u odnosu na str. Ali iz korolara 3 () proizlazi da je njihov proizvod a 1 , a 2 , a 3, ... je također relativno prost u odnosu na str, što je u suprotnosti sa uslovom izjave. Stoga je barem jedan od brojeva djeljiv sa str.

Teorema 1. Bilo koji složeni broj se uvijek može predstaviti, i to na jedinstven način, kao proizvod konačnog broja prostih brojeva.

Dokaz. Neka k kompozitni broj, i neka a 1 je jedan od njegovih djelitelja različitih od 1 i samog sebe. Ako a 1 je složen, a zatim ima pored 1 i a 1 i još jedan djelitelj a 2. Ako a 2 je složeni broj, tada ima, pored 1 i a 2 i još jedan djelitelj a 3. Rezonirajući na ovaj način i uzimajući u obzir da su brojke a 1 , a 2 , a 3 , ... smanjimo i ovaj niz sadrži konačan broj članova, doći ćemo do nekog prostog broja str 1 . Onda k može se predstaviti u obliku

Pretpostavimo da postoje dvije dekompozicije broja k:

Jer k=p 1 str 2 str 3...djeljivo prostim brojem q 1, zatim barem jedan od faktora, na primjer str 1 je djeljiv sa q 1 . Ali str 1 je prost broj i djeljiv je samo sa 1 i samim sobom. Dakle str 1 =q 1 (jer q 1 ≠1)

Tada iz (2) možemo isključiti str 1 i q 1:

Dakle, uvjereni smo da se svaki prost broj koji se pojavljuje kao faktor u prvom proširenju jedan ili više puta također pojavljuje u drugom proširenju najmanje toliko puta, i obrnuto, svaki prost broj koji se pojavljuje kao faktor u drugom proširenju jedan ili više puta se također pojavljuje u prvom proširenju barem isti broj puta. Stoga se bilo koji prosti broj pojavljuje kao faktor u oba proširenja isti broj puta i stoga su ova dva proširenja ista.■

Proširivanje složenog broja k može se napisati u sljedećem obliku

(3)

Gdje str 1 , str 2, ... razni prosti brojevi, α, β, γ ... pozitivni cijeli brojevi.

Poziva se ekspanzija (3). kanonska ekspanzija brojevi.

Prosti brojevi se javljaju neravnomjerno u nizu prirodnih brojeva. U nekim dijelovima reda ih je više, u drugim - manje. Što se dalje krećemo duž niza brojeva, prosti brojevi su rjeđi. Postavlja se pitanje da li postoji najveći prost broj? Drevni grčki matematičar Euklid je dokazao da postoji beskonačno mnogo prostih brojeva. U nastavku donosimo ovaj dokaz.

Teorema 2. Broj prostih brojeva je beskonačan.

Dokaz. Pretpostavimo da postoji konačan broj prostih brojeva i neka bude najveći prost broj str. Uzmimo sve brojeve većim str. Prema pretpostavci tvrdnje, ovi brojevi moraju biti složeni i moraju biti djeljivi sa najmanje jednim od prostih brojeva. Odaberimo broj koji je proizvod svih ovih prostih brojeva plus 1:

Broj z više str jer 2p već više str. str nije djeljiv ni sa jednim od ovih prostih brojeva, jer kada se podijeli sa svakim od njih daje ostatak od 1. Tako dolazimo do kontradikcije. Stoga postoji beskonačan broj prostih brojeva.

Ova teorema je poseban slučaj općenitije teoreme:

Teorema 3. Neka je data aritmetička progresija

Zatim bilo koji prost broj uključen n, treba uključiti u m, dakle u n ostali primarni faktori koji nisu uključeni u m i, štaviše, ovi primarni faktori u n nisu uključeni više puta nego u m.

Vrijedi i suprotno. Ako je svaki prosti faktor broja n uključeno najmanje isto toliko puta u broj m, To m podijeljena n.

Izjava 3. Neka a 1 ,a 2 ,a 3,... razni prosti brojevi uključeni u m Dakle

Gdje i=0,1,...α , j=0,1,...,β , k=0,1,..., γ . primeti, to αi prihvata α +1 vrijednosti, β j prihvata β +1 vrijednosti, γ k prihvata γ +1 vrijednosti, ... .

Ilijin odgovor je tačan, ali ne baš detaljan. Inače, u 18. veku jedan se još uvek smatrao prostim brojem. Na primjer, tako veliki matematičari kao što su Euler i Goldbach. Goldbach je autor jednog od sedam problema milenijuma - Goldbach hipoteze. Originalna formulacija kaže da se svaki 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 oblik: "svaki paran broj, počevši od 4, može se predstaviti kao zbir dva prosta broja."

Prisjetimo se definicije. Prosti broj 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.

Sada pretpostavimo 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 razlikuje od njega (sa 1). Ali dva različita prosta broja ne mogu se međusobno podijeliti, jer inače to nisu prosti brojevi, 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 algebarskog polja. Štaviše, s obzirom na operaciju sabiranja, 1 je također generirajući element za prsten cijelih brojeva.

Uz ovo razmatranje, nije teško otkriti analoge prostih brojeva u drugim algebarskim strukturama. Pretpostavimo da imamo multiplikativnu grupu formiranu 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 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 rečima, broj str onda će biti jednostavno kada je veće od jedan i može se podijeliti samo s jednim i samim sobom - str.

Zovu se prirodni brojevi, velike jedinice i brojevi koji nisu prosti kompozitni brojevi. Dakle, svi prirodni brojevi su podijeljeni u 3 klase: jedinica (ima 1 djelitelj), primarni brojevi(imaju 2 djelitelja) 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 zamislimo prirodne brojeve kao proizvod prostih brojeva, onda ćemo to nazvati dekompozicijom prostih brojeva ili faktorizacija broja.

Najveći poznati prost broj.

Najveći poznati prost broj je 257885161 - 1. Ovaj broj ima 17.425.170 decimalnih cifara i naziva se prost Mersennov broj(M 57885161).

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, ali a- prirodno, znači a p -a mogu se podijeliti na str (Fermatova mala teorema).

Kada G je konačna grupa čiji je red |G| podijeljena str, što znači G postoji element reda str (Cauchyjev teorem).

Kada G je konačna grupa, i p n- najviši stepen str, podjela |G|, što znači G postoji podgrupa reda p n, koji se naziva silovska podgrupa; pored toga, odgovara i broj silovskih podgrupa pk+1 za neku celinu k(Silowov teorem).

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

Kada n > 1- prirodno znači da je jednostavno str: n< p < 2 n (Bertrandov postulat).

Niz brojeva koji su inverzni od prostih brojeva divergira. Osim toga, kada .

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

Svaki prost broj veći od tri može se predstaviti kao 6k+1 ili 6k-1, Gdje k- prirodni broj. Na osnovu toga, kada razlika nekoliko uzastopnih prostih brojeva (sa 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 na neparnim brojevima koji nisu djeljivi sa tri).

Green-Tao teorema. Postoje beskonač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 dva. Može se zaključiti da kada je prost broj predstavljen kao 2 k -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 tipa je pet sa 42 varijable; najmanji broj varijabli je deset sa snagom od približno 1,6 10 45 .

Akcije sa prostim brojevima.

1. Proizvod prostih brojeva.

2. Razlika prostih brojeva.

3. Zbir prostih brojeva.

4. Podjela prostih brojeva.

U ovom članku ćemo istražiti prosti i složeni brojevi. Prvo ćemo dati definicije prostih i složenih brojeva, kao i primjere. Nakon ovoga ćemo dokazati da postoji beskonačno mnogo prostih brojeva. Zatim ćemo zapisati tabelu prostih brojeva i razmotriti metode za sastavljanje tabele prostih brojeva, obraćajući posebnu pažnju na metodu zvanu Eratostenovo sito. U zaključku ćemo istaknuti glavne točke koje treba uzeti u obzir pri dokazivanju da je dati broj prost ili složen.

Navigacija po stranici.

Prosti i složeni brojevi - definicije i primjeri

Koncepti prostih i složenih brojeva odnose se na brojeve koji su veći od jedan. Takvi cijeli brojevi, ovisno o broju njihovih pozitivnih djelitelja, dijele se na proste i složene brojeve. Da razumem definicije prostih i složenih brojeva, morate dobro razumjeti šta su djelitelji i višekratnici.

Definicija.

primarni brojevi su cijeli brojevi, velike jedinice, koje imaju samo dva pozitivna djelitelja, odnosno sebe i 1.

Definicija.

Kompozitni brojevi su cijeli brojevi, veliki, koji imaju najmanje tri pozitivna djelila.

Odvojeno, napominjemo da se broj 1 ne odnosi ni na proste ni na složene brojeve. Jedinica ima samo jedan pozitivan djelitelj, a to je sam broj 1. Ovo razlikuje broj 1 od svih ostalih pozitivnih cijelih brojeva koji imaju najmanje dva pozitivna djelitelja.

S obzirom da su pozitivni cijeli brojevi , i da jedan ima samo jedan pozitivan djelitelj, možemo dati i druge formulacije navedenih definicija prostih i složenih brojeva.

Definicija.

primarni brojevi su prirodni brojevi koji imaju samo dva pozitivna djelitelja.

Definicija.

Kompozitni brojevi su prirodni brojevi koji imaju više od dva pozitivna djelila.

Imajte na umu da je svaki pozitivni cijeli broj veći od jedan ili prost ili složeni broj. Drugim riječima, ne postoji niti jedan cijeli broj koji nije ni prost ni složen. Ovo slijedi iz svojstva djeljivosti, koje kaže da su brojevi 1 i a uvijek djelitelji bilo kojeg cijelog broja a.

Na osnovu informacija iz prethodnog paragrafa možemo dati sljedeću definiciju kompozitnih brojeva.

Definicija.

Prirodni brojevi koji nisu prosti se nazivaju kompozitni.

Hajde da damo primjeri prostih i složenih brojeva.

Primjeri složenih brojeva uključuju 6, 63, 121 i 6,697. Ova izjava takođe zahteva pojašnjenje. Broj 6, pored pozitivnih djelitelja 1 i 6, ima i djelitelje 2 i 3, budući da je 6 = 2 3, dakle 6 je zaista složeni broj. Pozitivni faktori od 63 su brojevi 1, 3, 7, 9, 21 i 63. Broj 121 jednak je proizvodu 11·11, pa su njegovi pozitivni djelitelji 1, 11 i 121. A broj 6.697 je složen, jer su njegovi pozitivni djelitelji, pored 1 i 6.697, i brojevi 37 i 181.

U zaključku ove tačke, takođe bih želeo da skrenem pažnju na činjenicu da prosti brojevi i međusobno prosti brojevi nisu daleko od iste stvari.

Tabela prostih brojeva

Prosti brojevi, radi pogodnosti njihove dalje upotrebe, zapisuju se u tablicu koja se zove tabela prostih brojeva. Ispod je tabela prostih brojeva do 1.000.

Postavlja se logično pitanje: „Zašto smo popunili tabelu prostih brojeva samo do 1.000, zar nije moguće napraviti tabelu svih postojećih prostih brojeva“?

Odgovorimo prvo na prvi dio ovog pitanja. Za većinu problema koji zahtijevaju upotrebu prostih brojeva, prosti brojevi unutar hiljadu bit će dovoljni. U drugim slučajevima, najvjerovatnije, morat ćete pribjeći nekim posebnim rješenjima. Iako sigurno možemo kreirati tablicu prostih brojeva do proizvoljno velikog konačnog pozitivnog cijelog broja, bilo da je 10.000 ili 1.000.000.000, u sljedećem paragrafu ćemo govoriti o metodama za kreiranje tablica prostih brojeva, posebno ćemo pogledati metodu pozvao.

Pogledajmo sada mogućnost (ili bolje rečeno, nemogućnost) sastavljanja tabele svih postojećih prostih brojeva. Ne možemo napraviti tabelu svih prostih brojeva jer postoji beskonačno mnogo prostih brojeva. Posljednja izjava je teorema koju ćemo dokazati nakon sljedeće pomoćne teoreme.

Teorema.

Najmanji pozitivni djelitelj različit od 1 prirodnog broja većeg od jedan je prost broj.

Dokaz.

Neka a je prirodni broj veći od jedan, a b je najmanji pozitivni djelitelj drugog od jedan. Dokažimo da je b prost broj kontradiktorno.

Pretpostavimo da je b složeni broj. Zatim postoji djelitelj broja b (označimo ga b 1), koji se razlikuje i od 1 i od b. Ako također uzmemo u obzir da apsolutna vrijednost djelitelja ne prelazi apsolutnu vrijednost dividende (ovo znamo iz svojstava djeljivosti), tada mora biti zadovoljen uvjet 1

Pošto je broj a djeljiv sa b prema uvjetu, a rekli smo da je b djeljiv sa b 1, koncept djeljivosti nam omogućava da govorimo o postojanju cijelih brojeva q i q 1 takvih da su a=b q i b=b 1 q 1 , odakle je a= b 1 ·(q 1 ·q) . Iz toga slijedi da je proizvod dva cijela broja cijeli broj, tada jednakost a=b 1 ·(q 1 ·q) pokazuje da je b 1 djelitelj broja a. Uzimajući u obzir gore navedene nejednakosti 1

Sada možemo dokazati da postoji beskonačno mnogo prostih brojeva.

Teorema.

Postoji beskonačan broj prostih brojeva.

Dokaz.

Pretpostavimo da to nije slučaj. 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.

Smatramo da je 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 složen, onda na osnovu prethodne teoreme postoji prost djelitelj ovog broja (označavamo 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, prema svojstvima djeljivosti, proizvod p 1 ·p 2 ·…·p n bio podijeljen sa p n+1. Ali broj p je također djeljiv sa p n+1, jednak zbiru p 1 ·p 2 ·…·p n +1. Iz toga slijedi da p n+1 mora podijeliti drugi član ovog zbira, koji je jednak jedan, ali to je nemoguće.

Dakle, dokazano je da se uvijek može pronaći novi prost broj koji nije uključen ni u jedan broj unaprijed određenih prostih brojeva. Dakle, postoji beskonačno mnogo prostih brojeva.

Dakle, zbog činjenice da postoji beskonačan broj prostih brojeva, prilikom sastavljanja tabela prostih brojeva, uvijek se ograničavate odozgo na neki broj, obično 100, 1.000, 10.000 itd.

Eratostenovo sito

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

Najočitija metoda za rješavanje ovog problema je sekvencijalna provjera pozitivnih cijelih brojeva, počevši od 2 i završavajući sa 100, na prisutnost pozitivnog djelitelja koji je veći od 1 i manji od broja koji se testira (iz svojstava djeljivosti koje znamo da apsolutna vrijednost djelitelja ne prelazi apsolutnu vrijednost dividende, različitu od nule). Ako takav djelitelj nije pronađen, tada je broj koji se testira prost i unosi se u tabelu prostih brojeva. Ako se takav djelitelj pronađe, tada je broj koji se testira kompozitan i NE upisuje se u tablicu 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. Stoga je jednostavno, pa ga unosimo u tablicu 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 broj 2. Ali 3 nije deljivo sa 2, dakle, 3 je prost broj, a takođe ga treba uključiti u tabelu prostih brojeva. Pređimo na broj 4. Njegovi pozitivni djelitelji osim 1 i 4 mogu biti brojevi 2 i 3, provjerimo ih. Broj 4 je djeljiv sa 2, dakle, 4 je složeni broj i ne mora biti uključen u tabelu 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 sa 2, 3 ili 4, onda je prost i mora se zapisati u tabeli prostih brojeva. Zatim slijedi prijelaz na brojeve 6, 7 i tako dalje do 100.

Ovaj pristup sastavljanju tabele prostih brojeva daleko je od idealnog. Na ovaj ili onaj način, on ima pravo da postoji. 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 kreiranje tabele prostih brojeva, tzv. Riječ "sito" prisutna u nazivu nije slučajna, jer radnje ove metode pomažu, takoreći, da se cijeli brojevi i velike jedinice "prosijaju" kroz Eratostenovo sito kako bi se odvojili jednostavni od složenih.

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

Prvo zapišite redom brojeve 2, 3, 4, ..., 50.

Prvi napisani broj, 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 tablice brojeva koja se sastavlja. Ovo će precrtati sve brojeve koji su višestruki od dva.

Prvi broj nakon 2 koji nije precrtan 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. Ovo će precrtati sve brojeve koji su višestruki od tri.

Prvi broj nakon 3 koji nije precrtan je 5. Ovaj broj je prost. Sada se od broja 5 dosljedno pomičemo udesno za 5 brojeva (također uzimamo u obzir prethodno precrtane brojeve) i precrtavamo ih. Ovo će precrtati sve brojeve koji su višekratni pet.

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, dobijena pomoću Eratostenovog sita. Svi neprecrtani brojevi su prosti, a svi precrtani brojevi su složeni.

Formulirajmo i dokažemo teoremu koja će ubrzati proces sastavljanja tabele prostih brojeva korištenjem Eratostenovog sita.

Teorema.

Najmanji pozitivni djelitelj kompozitnog broja a koji je različit od jedan ne prelazi , gdje je od a .

Dokaz.

Označimo slovom b najmanji djelitelj složenog broja a koji je različit od jedinice (broj b je prost, kao što slijedi iz teoreme dokazane na samom početku prethodnog paragrafa). Tada postoji cijeli broj q takav da je a=b·q (ovdje je q pozitivan cijeli broj, što slijedi iz pravila množenja cijelih brojeva), i (za b>q uvjet da je b najmanji djelitelj a je prekršen , budući da je q također djelitelj broja a zbog jednakosti a=q·b ). Množenjem obje strane nejednakosti pozitivnim i cijelim brojem većim od jedan (to nam je dopušteno), dobivamo , od čega i .

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

Prvo, precrtavanje složenih brojeva koji su višekratnici prostog broja b treba poč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 svi složeni brojevi koji su višekratnici prostih brojeva ne prelaze . U našem primjeru, n=50 (pošto pravimo tablicu prostih brojeva do 50) i, stoga, Eratostenovo sito treba eliminirati sve složene brojeve koji su višekratnici prostih brojeva 2, 3, 5 i 7 koji rade ne prelazi 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. Općenito, ovaj zadatak je daleko od jednostavnog, posebno za brojeve čije se pisanje 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.

Naravno, možete pokušati koristiti testove djeljivosti da dokažete da je dati broj kompozitan. Ako, na primjer, neki test djeljivosti pokaže da je dati broj djeljiv s nekim pozitivnim cijelim brojem većim od jedan, tada je originalni broj složen.

Primjer.

Dokažite da je 898,989,898,989,898,989 složeni broj.

Rješenje.

Zbir cifara ovog broja je 9·8+9·9=9·17. Pošto je broj jednak 9·17 djeljiv sa 9, onda po djeljivosti sa 9 možemo reći da je i originalni broj djeljiv sa 9. Stoga je kompozit.

Značajan nedostatak ovog pristupa je taj što kriteriji djeljivosti ne dozvoljavaju da se dokaže jednostavnost broja. Stoga, kada testirate broj da biste vidjeli da li je prost ili kompozitni, morate stvari učiniti drugačije.

Najlogičniji pristup je isprobati sve moguće djelitelje datog broja. Ako nijedan od mogućih djelitelja nije pravi djelitelj datog broja, onda će ovaj broj biti prost, inače će biti kompozitni. 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 sekvencijalno podijeliti prostim brojevima (koji se zgodno uzimaju 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 do kojeg prostog broja mogu biti djelitelji broja 11,723. Da bismo to učinili, procijenimo.

To je prilično očigledno , od 200 2 =40,000, i 11,723<40 000 (при необходимости смотрите статью poređenje brojeva). Dakle, mogući primarni faktori od 11.723 manji su od 200. Ovo nam već znatno olakšava zadatak. Da to ne znamo, onda bismo morali proći kroz sve proste brojeve ne do 200, već do broja 11.723.

Ako želite, možete preciznije procijeniti. Kako je 108 2 =11,664, a 109 2 =11,881, onda je 108 2<11 723<109 2 , следовательно, . Dakle, bilo koji od prostih brojeva manji od 109 potencijalno je prost faktor 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, 53, 59, 61, 67, 7 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Ako se broj 11.723 podijeli s jednim od zapisanih 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 odmah da 11.723