Çfarë janë numrat e thjeshtë? A është ky numër i thjeshtë apo i përbërë? Vetitë e numrave të thjeshtë

Teorema.

Ka një numër të pafund numrash të thjeshtë.

Dëshmi.

Le të supozojmë se nuk është kështu. Kjo do të thotë, supozoni se ka vetëm n numra të thjeshtë, dhe këta numra të thjeshtë janë p 1, p 2, ..., p n. Le të tregojmë se gjithmonë mund të gjejmë një numër të thjeshtë të ndryshëm nga ata të treguar.

Konsideroni numrin p të barabartë me p 1 ·p 2 ·…·p n +1. Është e qartë se ky numër është i ndryshëm nga secili prej numrave të thjeshtë p 1, p 2, ..., p n. Nëse numri p është i thjeshtë, atëherë teorema vërtetohet. Nëse ky numër është i përbërë, atëherë në bazë të teoremës së mëparshme ekziston një pjesëtues kryesor i këtij numri (e shënojmë p n+1). Le të tregojmë se ky pjesëtues nuk përkon me asnjë nga numrat p 1, p 2, ..., p n.

Nëse nuk do të ishte kështu, atëherë, sipas vetive të pjesëtueshmërisë, prodhimi p 1 ·p 2 ·…·p n do të pjesëtohet me p n+1. Por numri p është gjithashtu i pjesëtueshëm me p n+1, i barabartë me shumën p 1 ·p 2 ·…·p n +1. Nga kjo rrjedh se p n+1 duhet të ndajë termin e dytë të kësaj shume, e cila është e barabartë me një, por kjo është e pamundur.

Kështu, është vërtetuar se gjithmonë mund të gjendet një numër i ri i thjeshtë që nuk përfshihet në asnjë numër numrash të thjeshtë të paracaktuar. Prandaj, ka pafundësisht shumë numra të thjeshtë.

Pra, për faktin se ka një numër të pafund numrash të thjeshtë, kur përpiloni tabela të numrave të thjeshtë, gjithmonë kufizoheni nga lart në një numër, zakonisht 100, 1.000, 10.000, etj.

Sita e Eratosthenes

Tani do të diskutojmë mënyrat për të krijuar tabela të numrave të thjeshtë. Supozoni se duhet të bëjmë një tabelë me numra të thjeshtë deri në 100.

Metoda më e dukshme për zgjidhjen e këtij problemi është të kontrolloni në mënyrë sekuenciale numrat e plotë pozitivë, duke filluar nga 2 dhe duke përfunduar me 100, për praninë e një pjesëtuesi pozitiv që është më i madh se 1 dhe më i vogël se numri që testohet (nga vetitë e pjesëtueshmërisë që dimë se vlera absolute e pjesëtuesit nuk e kalon vlerën absolute të dividentit, jo zero). Nëse një pjesëtues i tillë nuk gjendet, atëherë numri që testohet është i thjeshtë dhe ai futet në tabelën e numrave të thjeshtë. Nëse gjendet një pjesëtues i tillë, atëherë numri që testohet është i përbërë, NUK futet në tabelën e numrave të thjeshtë. Pas kësaj, ka një kalim në numrin tjetër, i cili kontrollohet në mënyrë të ngjashme për praninë e një pjesëtuesi.

Le të përshkruajmë hapat e parë.

Fillojmë me numrin 2. Numri 2 nuk ka pjesëtues pozitivë përveç 1 dhe 2. Prandaj, është e thjeshtë, prandaj e fusim në tabelën e numrave të thjeshtë. Këtu duhet thënë se 2 është numri më i vogël i thjeshtë. Le të kalojmë në numrin 3. Pjesëtuesi i tij pozitiv i mundshëm përveç 1 dhe 3 është numri 2. Por 3 nuk është i pjesëtueshëm me 2, prandaj, 3 është një numër i thjeshtë, dhe gjithashtu duhet të përfshihet në tabelën e numrave të thjeshtë. Le të kalojmë në numrin 4. Pjesëtuesit e tij pozitivë përveç 1 dhe 4 mund të jenë numrat 2 dhe 3, le t'i kontrollojmë ato. Numri 4 është i pjesëtueshëm me 2, prandaj, 4 është një numër i përbërë dhe nuk ka nevojë të përfshihet në tabelën e numrave të thjeshtë. Ju lutemi vini re se 4 është numri më i vogël i përbërë. Le të kalojmë në numrin 5. Kontrollojmë nëse të paktën njëri nga numrat 2, 3, 4 është pjesëtuesi i tij. Meqenëse 5 nuk pjesëtohet me 2, 3 ose 4, atëherë ai është i thjeshtë dhe duhet të shkruhet në tabelën e numrave të thjeshtë. Pastaj ka një kalim në numrat 6, 7 dhe kështu me radhë deri në 100.

Kjo qasje për të përpiluar një tabelë të numrave të thjeshtë është larg nga idealja. Në një mënyrë apo tjetër, ai ka të drejtë të ekzistojë. Vini re se me këtë metodë të ndërtimit të një tabele me numra të plotë, mund të përdorni kriteret e pjesëtueshmërisë, të cilat do të shpejtojnë paksa procesin e gjetjes së pjesëtuesve.

Ekziston një mënyrë më e përshtatshme për të krijuar një tabelë me numra të thjeshtë, të quajtur. Fjala "sitë" e pranishme në emër nuk është e rastësishme, pasi veprimet e kësaj metode ndihmojnë, si të thuash, për të "shoshitur" numrat e plotë dhe njësitë e mëdha përmes sitës së Eratosthenes për të ndarë ato të thjeshta nga ato të përbëra.

Le të tregojmë sitën e Eratosthenes në veprim kur përpilojmë një tabelë me numrat e thjeshtë deri në 50.

Fillimisht, shënoni me radhë numrat 2, 3, 4, ..., 50.

Numri i parë i shkruar, 2, është i thjeshtë. Tani, nga numri 2, lëvizim në mënyrë sekuenciale në të djathtë me dy numra dhe i kalojmë këta numra derisa të arrijmë në fund të tabelës së numrave që përpilohet. Kjo do të kalojë të gjithë numrat që janë shumëfish të dy.

Numri i parë pas 2 që nuk është gërmuar është 3. Ky numër është i thjeshtë. Tani, nga numri 3, ne lëvizim vazhdimisht në të djathtë me tre numra (duke marrë parasysh numrat tashmë të kryqëzuar) dhe i kalojmë ato. Kjo do të kalojë të gjithë numrat që janë shumëfish të tre.

Numri i parë pas 3 që nuk është gërmuar është 5. Ky numër është i thjeshtë. Tani nga numri 5 ne lëvizim vazhdimisht në të djathtë me 5 numra (ne marrim parasysh edhe numrat e kryqëzuar më parë) dhe i kalojmë ato. Kjo do të kalojë të gjithë numrat që janë shumëfish të pesë.

Më pas, kryqëzojmë numrat që janë shumëfish të 7-ës, pastaj shumëfisha të 11-ës, e kështu me radhë. Procesi përfundon kur nuk ka më numra për të kryqëzuar. Më poshtë është tabela e plotësuar e numrave të thjeshtë deri në 50, të marra duke përdorur sitën e Eratosthenes. Të gjithë numrat e pakryqëzuar janë të thjeshtë dhe të gjithë numrat e kryqëzuar janë të përbërë.

Le të formulojmë dhe vërtetojmë gjithashtu një teoremë që do të përshpejtojë procesin e përpilimit të një tabele të numrave të thjeshtë duke përdorur sitën e Eratosthenes.

Teorema.

Pjesëtuesi më i vogël pozitiv i një numri të përbërë a që është i ndryshëm nga një nuk e kalon , ku është nga a .

Dëshmi.

Le të shënojmë me shkronjën b pjesëtuesin më të vogël të një numri të përbërë a që është i ndryshëm nga një (numri b është i thjeshtë, siç vijon nga teorema e provuar në fillim të paragrafit të mëparshëm). Pastaj ka një numër të plotë q i tillë që a=b·q (këtu q është një numër i plotë pozitiv, i cili rrjedh nga rregullat e shumëzimit të numrave të plotë), dhe (për b>q kushti që b është pjesëtuesi më i vogël i a është shkelur , meqë q është edhe pjesëtues i numrit a për shkak të barazisë a=q·b ). Duke shumëzuar të dyja anët e pabarazisë me një pozitiv dhe një numër të plotë më të madh se një (ne lejohet ta bëjmë këtë), marrim , Nga e cila dhe .

Çfarë na jep teorema e provuar në lidhje me sitën e Eratosthenes?

Së pari, kryqëzimi i numrave të përbërë që janë shumëfish të një numri të thjeshtë b duhet të fillojë me një numër të barabartë me (kjo rrjedh nga pabarazia). Për shembull, kryqëzimi i numrave që janë shumëfish të dy duhet të fillojë me numrin 4, shumëfishat e tre me numrin 9, shumëfishat e pesë me numrin 25, e kështu me radhë.

Së dyti, përpilimi i një tabele me numra të thjeshtë deri në numrin n duke përdorur sitën e Eratosthenes mund të konsiderohet i plotë kur të gjithë numrat e përbërë që janë shumëfisha të numrave të thjeshtë që nuk e kalojnë . Në shembullin tonë, n=50 (pasi po bëjmë një tabelë me numrat e thjeshtë deri në 50) dhe, për rrjedhojë, sita e Eratosthenes duhet të eliminojë të gjithë numrat e përbërë që janë shumëfish të numrave të thjeshtë 2, 3, 5 dhe 7 që bëjnë të mos kalojë rrënjën katrore aritmetike prej 50. Kjo do të thotë, ne nuk kemi më nevojë të kërkojmë dhe të kryqëzojmë numra që janë shumëfish të numrave të thjeshtë 11, 13, 17, 19, 23 e kështu me radhë deri në 47, pasi ata tashmë do të kryqëzohen si shumëfisha të numrave të thjeshtë 2. , 3, 5 dhe 7.

A është ky numër i thjeshtë apo i përbërë?

Disa detyra kërkojnë të zbulohet nëse një numër i caktuar është i thjeshtë apo i përbërë. Në rastin e përgjithshëm, kjo detyrë nuk është aspak e thjeshtë, veçanërisht për numrat, shkrimi i të cilëve përbëhet nga një numër i konsiderueshëm karakteresh. Në shumicën e rasteve, duhet të kërkoni një mënyrë specifike për ta zgjidhur atë. Megjithatë, ne do të përpiqemi t'i japim drejtim trenit të mendimit për raste të thjeshta.

Sigurisht, mund të provoni të përdorni teste pjesëtueshmërie për të vërtetuar se një numër i caktuar është i përbërë. Nëse, për shembull, një test i pjesëtueshmërisë tregon se një numër i caktuar është i pjesëtueshëm me një numër të plotë pozitiv më të madh se një, atëherë numri origjinal është i përbërë.

Shembull.

Vërtetoni se 898,989,898,989,898,989 është një numër i përbërë.

Zgjidhje.

Shuma e shifrave të këtij numri është 9·8+9·9=9·17. Meqenëse numri i barabartë me 9·17 është i pjesëtueshëm me 9, atëherë me kriterin e pjesëtueshmërisë me 9 mund të argumentohet se numri origjinal është gjithashtu i pjesëtueshëm me 9. Prandaj, është i përbërë.

Një pengesë e rëndësishme e kësaj qasjeje është se kriteret e pjesëtueshmërisë nuk lejojnë që dikush të vërtetojë parësinë e një numri. Prandaj, kur kontrolloni një numër për të parë nëse është i thjeshtë apo i përbërë, duhet të vazhdoni ndryshe.

Qasja më logjike është të provoni të gjithë pjesëtuesit e mundshëm të një numri të caktuar. Nëse asnjë nga pjesëtuesit e mundshëm nuk është pjesëtues i vërtetë i një numri të caktuar, atëherë ky numër do të jetë i thjeshtë, përndryshe do të jetë i përbërë. Nga teoremat e vërtetuara në paragrafin e mëparshëm, rezulton se pjesëtuesit e një numri të caktuar a duhet të kërkohen midis numrave të thjeshtë që nuk e kalojnë . Kështu, një numër i dhënë a mund të ndahet në mënyrë sekuenciale me numrat e thjeshtë (të cilët merren me lehtësi nga tabela e numrave të thjeshtë), duke u përpjekur të gjejë pjesëtuesin e numrit a. Nëse gjendet një pjesëtues, atëherë numri a është i përbërë. Nëse midis numrave të thjeshtë që nuk e kalojnë , nuk ka pjesëtues të numrit a, atëherë numri a është i thjeshtë.

Shembull.

Numri 11 723 e thjeshtë apo e përbërë?

Zgjidhje.

Le të zbulojmë deri në cilin numër të thjeshtë mund të jenë pjesëtuesit e numrit 11723. Për ta bërë këtë, le të vlerësojmë.

Është shumë e qartë se , që nga viti 200 2 =40,000, dhe 11,723<40 000 (при необходимости смотрите статью krahasimi i numrave). Kështu, faktorët kryesorë të mundshëm prej 11,723 janë më pak se 200. Kjo tashmë e bën detyrën tonë shumë më të lehtë. Nëse nuk do ta dinim këtë, atëherë do të duhej të kalonim nëpër të gjithë numrat e thjeshtë jo deri në 200, por deri në numrin 11,723.

Nëse dëshironi, mund të vlerësoni më saktë. Meqenëse 108 2 = 11,664, dhe 109 2 = 11,881, atëherë 108 2<11 723<109 2 , следовательно, . Kështu, çdo nga numrat e thjeshtë më pak se 109 është potencialisht një faktor kryesor i numrit të dhënë 11,723.

Tani do ta ndajmë në mënyrë sekuenciale numrin 11,723 në numrat e thjeshtë 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Nëse numri 11.723 pjesëtohet me një nga numrat e thjeshtë të shkruar, atëherë ai do të jetë i përbërë. Nëse nuk është i pjesëtueshëm me asnjë nga numrat e thjeshtë të shkruar, atëherë numri origjinal është i thjeshtë.

Ne nuk do ta përshkruajmë gjithë këtë proces monoton dhe monoton të ndarjes. Le të themi menjëherë se 11,723

• Përkthimi

Vetitë e numrave të thjeshtë u studiuan fillimisht nga matematikanët e Greqisë antike. Matematikanët e shkollës së Pitagorës (500 - 300 pes) ishin të interesuar kryesisht për vetitë mistike dhe numerologjike të numrave të thjeshtë. Ata ishin të parët që dolën me ide për numra të përsosur dhe miqësorë.

Një numër i përsosur ka një shumë të pjesëtuesve të tij të barabartë me vetveten. Për shembull, pjesëtuesit e duhur të numrit 6 janë 1, 2 dhe 3. 1 + 2 + 3 = 6. Pjesëtuesit e numrit 28 janë 1, 2, 4, 7 dhe 14. Për më tepër, 1 + 2 + 4 + 7 + 14 = 28.

Numrat quhen miqësorë nëse shuma e pjesëtuesve të duhur të një numri është e barabartë me një tjetër, dhe anasjelltas - për shembull, 220 dhe 284. Mund të themi se një numër i përsosur është miqësor me vetveten.

Në kohën e Elementeve të Euklidit në vitin 300 p.e.s. Tashmë janë vërtetuar disa fakte të rëndësishme për numrat e thjeshtë. Në Librin IX të Elementeve, Euklidi vërtetoi se ka një numër të pafund numrash të thjeshtë. Ky, meqë ra fjala, është një nga shembujt e parë të përdorimit të provës me kontradiktë. Ai vërteton gjithashtu Teoremën Themelore të Aritmetikës - çdo numër i plotë mund të përfaqësohet në mënyrë unike si produkt i numrave të thjeshtë.

Ai gjithashtu tregoi se nëse numri 2n-1 është i thjeshtë, atëherë numri 2n-1 * (2n-1) do të jetë i përsosur. Një tjetër matematikan, Euler, ishte në gjendje të tregonte në 1747 se të gjithë numrat madje të përsosur mund të shkruhen në këtë formë. Deri më sot nuk dihet nëse ekzistojnë numra të përsosur tek.

Në vitin 200 p.e.s. Eratosthenes grek doli me një algoritëm për gjetjen e numrave të thjeshtë të quajtur Sita e Eratosthenes.

Dhe pastaj pati një ndërprerje të madhe në historinë e studimit të numrave të thjeshtë, të lidhur me Mesjetën.

Zbulimet e mëposhtme u bënë tashmë në fillim të shekullit të 17-të nga matematikani Fermat. Ai vërtetoi hamendjen e Albert Girard se çdo numër i thjeshtë i formës 4n+1 mund të shkruhet në mënyrë unike si shuma e dy katrorëve, dhe gjithashtu formuloi teoremën se çdo numër mund të shkruhet si shuma e katër katrorëve.

Ai zhvilloi një metodë të re për faktorizimin e numrave të mëdhenj dhe e demonstroi atë në numrin 2027651281 = 44021 × 46061. Ai gjithashtu vërtetoi Teoremën e vogël të Fermatit: nëse p është një numër i thjeshtë, atëherë për çdo numër të plotë a do të jetë e vërtetë se a p = një modul fq.

Ky pohim vërteton gjysmën e asaj që njihej si "hamendja kineze" dhe daton 2000 vjet më parë: një numër i plotë n është i thjeshtë nëse dhe vetëm nëse 2 n -2 pjesëtohet me n. Pjesa e dytë e hipotezës doli të jetë e rreme - për shembull, 2,341 - 2 është i ndashëm me 341, megjithëse numri 341 është i përbërë: 341 = 31 × 11.

Teorema e vogël e Fermatit shërbeu si bazë për shumë rezultate të tjera në teorinë e numrave dhe metodat për të testuar nëse numrat janë të thjeshtë - shumë prej të cilave përdoren ende sot.

Fermat korrespondonte shumë me bashkëkohësit e tij, veçanërisht me një murg të quajtur Maren Mersenne. Në një nga letrat e tij, ai hipotezoi se numrat e formës 2 n +1 do të jenë gjithmonë të thjeshtë nëse n është një fuqi e dy. Ai e testoi këtë për n = 1, 2, 4, 8 dhe 16 dhe ishte i bindur se në rastin kur n nuk ishte një fuqi e dy, numri nuk ishte domosdoshmërisht i thjeshtë. Këta numra quhen numrat e Fermatit, dhe vetëm 100 vjet më vonë Euler tregoi se numri tjetër, 2 32 + 1 = 4294967297, është i pjesëtueshëm me 641, dhe për këtë arsye nuk është i thjeshtë.

Numrat e formës 2 n - 1 kanë qenë gjithashtu objekt studimi, pasi është e lehtë të tregohet se nëse n është i përbërë, atëherë edhe vetë numri është i përbërë. Këta numra quhen numra Mersenne sepse ai i studioi ato gjerësisht.

Por jo të gjithë numrat e formës 2 n - 1, ku n është i thjeshtë, janë të thjeshtë. Për shembull, 2 11 - 1 = 2047 = 23 * 89. Kjo u zbulua për herë të parë në 1536.

Për shumë vite, numrat e këtij lloji u dhanë matematikanëve numrat kryesorë më të mëdhenj të njohur. Se M 19 u vërtetua nga Cataldi në 1588, dhe për 200 vjet ishte numri më i madh i njohur, derisa Euler vërtetoi se M 31 ishte gjithashtu i thjeshtë. Ky rekord qëndroi për njëqind vjet të tjera, dhe më pas Lucas tregoi se M 127 është kryeministër (dhe ky është tashmë një numër prej 39 shifrash), dhe pas kësaj kërkimi vazhdoi me ardhjen e kompjuterëve.

Në vitin 1952, u vërtetua parësia e numrave M 521, M 607, M 1279, M 2203 dhe M 2281.

Deri në vitin 2005, ishin gjetur 42 primare Mersenne. Më i madhi prej tyre, M 25964951, përbëhet nga 7816230 shifra.

Puna e Euler-it pati një ndikim të madh në teorinë e numrave, duke përfshirë numrat e thjeshtë. Ai zgjeroi Teoremën e Vogël të Fermatit dhe prezantoi funksionin φ. Faktorizoi numrin e 5-të të Fermatit 2 32 +1, gjeti 60 çifte numrash miqësorë dhe formuloi (por nuk mundi të provonte) ligjin e reciprocitetit kuadratik.

Ai ishte i pari që prezantoi metodat e analizës matematikore dhe zhvilloi teorinë analitike të numrave. Ai vërtetoi se jo vetëm seria harmonike ∑ (1/n), por edhe një seri e formës

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Rezultati i përftuar nga shuma e reciprocaleve të numrave të thjeshtë gjithashtu ndryshon. Shuma e n termave të serisë harmonike rritet përafërsisht si log(n), dhe seria e dytë divergon më ngadalë si log[ log(n) ]. Kjo do të thotë që, për shembull, shuma e reciprokeve të të gjithë numrave të thjeshtë të gjetur deri më sot do të japë vetëm 4, megjithëse seria ende ndryshon.

Në pamje të parë, duket se numrat e thjeshtë shpërndahen në mënyrë krejt rastësore midis numrave të plotë. Për shembull, në mesin e 100 numrave menjëherë para 10000000 ka 9 numra të thjeshtë, dhe midis 100 numrave menjëherë pas kësaj vlere ka vetëm 2. Por në segmente të mëdha numrat e thjeshtë shpërndahen mjaft të barabartë. Lezhandri dhe Gausi u morën me çështjet e shpërndarjes së tyre. Gauss i tha një herë një shoku se në çdo 15 minuta të lirë ai numëron gjithmonë numrin e numrave të thjeshtë në 1000 numrat e ardhshëm. Deri në fund të jetës së tij, ai kishte numëruar të gjithë numrat e thjeshtë deri në 3 milionë. Lezhandri dhe Gauss llogaritën në mënyrë të barabartë se për n të mëdha densiteti kryesor është 1/log(n). Lezhandri vlerësoi numrin e numrave të thjeshtë në rangun nga 1 në n si

π(n) = n/(log(n) - 1,08366)

Dhe Gausi është si një integral logaritmik

π(n) = ∫ 1/log(t) dt

Me një interval integrimi nga 2 në n.

Deklarata për densitetin e thjeshtë 1/log(n) njihet si Teorema e Shpërndarjes së Parë. Ata u përpoqën ta provonin gjatë gjithë shekullit të 19-të dhe përparimi u arrit nga Chebyshev dhe Riemann. Ata e lidhën atë me hipotezën e Riemann-it, një hipotezë ende e paprovuar rreth shpërndarjes së zerave të funksionit zeta të Riemann-it. Dendësia e numrave të thjeshtë u vërtetua njëkohësisht nga Hadamard dhe Vallée-Poussin në 1896.

Ka ende shumë pyetje të pazgjidhura në teorinë e numrave të thjeshtë, disa prej të cilave janë qindra vjet të vjetra:

• Hipoteza e thjeshtë binjake ka të bëjë me një numër të pafund të çifteve të numrave të thjeshtë që ndryshojnë nga njëri-tjetri me 2
• Hamendja e Goldbach: çdo numër çift, duke filluar me 4, mund të përfaqësohet si shuma e dy numrave të thjeshtë
• A ka një numër të pafund numrash të thjeshtë të formës n 2 + 1?
• A është gjithmonë e mundur të gjesh një numër të thjeshtë midis n 2 dhe (n + 1) 2? (fakti që ka gjithmonë një numër të thjeshtë midis n dhe 2n u vërtetua nga Chebyshev)
• A është i pafund numri i numrave të thjeshtë të Fermatit? A ka numra të thjeshtë të Fermat pas 4?
• a ka një progresion aritmetik të numrave të thjeshtë të njëpasnjëshëm për çdo gjatësi të caktuar? për shembull, për gjatësinë 4: 251, 257, 263, 269. Gjatësia maksimale e gjetur është 26.
• A ka një numër të pafund grupesh me tre numra të thjeshtë të njëpasnjëshëm në një progresion aritmetik?
• n 2 - n + 41 është një numër i thjeshtë për 0 ≤ n ≤ 40. A ka një numër të pafund të numrave të tillë të thjeshtë? E njëjta pyetje për formulën n 2 - 79 n + 1601. Këta numra janë të thjeshtë për 0 ≤ n ≤ 79.
• A ka një numër të pafund numrash të thjeshtë të formës n# + 1? (n# është rezultat i shumëzimit të të gjithë numrave të thjeshtë më të vegjël se n)
• A ka një numër të pafund numrash të thjeshtë të formës n# -1?
• A ka një numër të pafund numrash të thjeshtë të formës n? + 1?
• A ka një numër të pafund numrash të thjeshtë të formës n? – 1?
• nëse p është i thjeshtë, a nuk përmban gjithmonë 2 p -1 katrorë të thjeshtë midis faktorëve të tij?
• a përmban sekuenca Fibonacci një numër të pafund numrash të thjeshtë?

Numrat kryesorë binjakë më të mëdhenj janë 2003663613 × 2 195000 ± 1. Ata përbëhen nga 58711 shifra dhe u zbuluan në vitin 2007.

Numri më i madh faktorial (i tipit n! ± 1) është 147855! - 1. Përbëhet nga 142891 shifra dhe është gjetur në vitin 2002.

Numri më i madh primorial (një numër i formës n# ± 1) është 1098133# + 1.

Etiketa: Shtoni etiketa

Numërimi i pjesëtuesve. Sipas përkufizimit, numri nështë i thjeshtë vetëm nëse nuk pjesëtohet në mënyrë të barabartë me 2 dhe me numra të tjerë të plotë përveç 1 dhe vetvetes. Formula e mësipërme heq hapat e panevojshëm dhe kursen kohë: për shembull, pasi të keni kontrolluar nëse një numër pjesëtohet me 3, nuk ka nevojë të kontrolloni nëse është i pjesëtueshëm me 9.

• Funksioni dysheme(x) rrumbullakos x në numrin e plotë më të afërt që është më i vogël ose i barabartë me x.

Mësoni rreth aritmetikës modulare. Operacioni "x mod y" (mod është një shkurtim i fjalës latine "modulo", domethënë "modul") do të thotë "ndani x me y dhe gjeni pjesën e mbetur". Me fjalë të tjera, në aritmetikën modulare, me arritjen e një vlere të caktuar, e cila quhet modul, numrat “kthehen” sërish në zero. Për shembull, një orë e mban kohën me një modul 12: tregon orën 10, 11 dhe 12 dhe më pas kthehet në 1.

• Shumë kalkulatorë kanë një çelës mod. Fundi i këtij seksioni tregon se si të vlerësoni manualisht këtë funksion për numra të mëdhenj.

Përkufizimi 1. Numri kryesor− është një numër natyror më i madh se ai që pjesëtohet vetëm me vetveten dhe 1.

Me fjalë të tjera, një numër është i thjeshtë nëse ka vetëm dy pjesëtues natyrorë të dallueshëm.

Përkufizimi 2. Çdo numër natyror që ka pjesëtues të tjerë përveç tij dhe një quhet një numër i përbërë.

Me fjalë të tjera, numrat natyrorë që nuk janë numra të thjeshtë quhen numra të përbërë. Nga përkufizimi 1 rezulton se një numër i përbërë ka më shumë se dy faktorë natyrorë. Numri 1 nuk është as i thjeshtë as i përbërë sepse ka vetëm një pjesëtues 1 dhe, përveç kësaj, shumë teorema në lidhje me numrat e thjeshtë nuk vlejnë për unitet.

Nga përkufizimet 1 dhe 2 rrjedh se çdo numër i plotë pozitiv më i madh se 1 është ose një numër i thjeshtë ose një numër i përbërë.

Më poshtë është një program për të shfaqur numrat kryesorë deri në 5000. Plotësoni qelizat, klikoni në butonin "Krijo" dhe prisni disa sekonda.

Tabela e numrave të thjeshtë

deklaratë 1. Nëse fq- numri i thjeshtë dhe açdo numër i plotë, atëherë ose a ndarë nga fq, ose fq Dhe a numrat koprim.

Vërtet. Nëse fq Një numër i thjeshtë ndahet vetëm me vetveten dhe 1 nëse a nuk ndahet me fq, atëherë pjesëtuesi më i madh i përbashkët a Dhe fqështë e barabartë me 1. Atëherë fq Dhe a numrat koprim.

deklaratë 2. Nëse prodhimi i disa numrave të numrave a 1 , a 2 , a 3, ... pjesëtohet me një numër të thjeshtë fq, pastaj të paktën një nga numrat a 1 , a 2 , a 3, ...pjestueshëm me fq.

Vërtet. Nëse asnjë nga numrat nuk ishte i pjesëtueshëm me fq, pastaj numrat a 1 , a 2 , a 3, ... do të ishin numra të dyfishtë në lidhje me fq. Por nga përfundimi 3 () rrjedh se produkti i tyre a 1 , a 2 , a 3, ... është gjithashtu relativisht kryesor në lidhje me fq, që bie ndesh me kushtin e deklaratës. Prandaj të paktën një nga numrat është i pjesëtueshëm me fq.

Teorema 1. Çdo numër i përbërë gjithmonë mund të përfaqësohet, dhe në një mënyrë unike, si prodhim i një numri të fundëm numrash të thjeshtë.

Dëshmi. Le k numër i përbërë, dhe le a 1 është një nga pjesëtuesit e tij i ndryshëm nga 1 dhe vetvetja. Nëse a 1 është i përbërë, pastaj ka përveç 1 dhe a 1 dhe një pjesëtues tjetër a 2. Nëse a 2 është një numër i përbërë, atëherë ai ka, përveç 1 dhe a 2 dhe një pjesëtues tjetër a 3. Duke arsyetuar në këtë mënyrë dhe duke marrë parasysh se numrat a 1 , a 2 , a 3 , ... zvogëlohet dhe kjo seri përmban një numër të kufizuar termash, do të arrijmë një numër të thjeshtë fq 1. Pastaj k mund të paraqitet në formë

Supozoni se ka dy zbërthime të një numri k:

Sepse k=p 1 fq 2 fq 3 ...pjestueshëm me një numër të thjeshtë q 1, pastaj të paktën një nga faktorët, për shembull fq 1 pjesëtohet me q 1. Por fq 1 është një numër i thjeshtë dhe pjesëtohet vetëm me 1 dhe me vetveten. Prandaj fq 1 =q 1 (sepse q 1 ≠1)

Atëherë nga (2) mund të përjashtojmë fq 1 dhe q 1:

Kështu, ne jemi të bindur se çdo numër i thjeshtë që shfaqet si faktor në zgjerimin e parë një ose më shumë herë shfaqet edhe në zgjerimin e dytë të paktën po aq herë, dhe anasjelltas, çdo numër i thjeshtë që shfaqet si faktor në zgjerimin e dytë. një ose më shumë herë shfaqet edhe në zgjerimin e parë të paktën të njëjtin numër herë. Prandaj, çdo numër i thjeshtë shfaqet si faktor në të dy zgjerimet një numër herë të njëjtë dhe, kështu, këto dy zgjerime janë të njëjta.■

Zgjerimi i një numri të përbërë k mund të shkruhet në formën e mëposhtme

Ku fq 1 , fq 2, ... numra të thjeshtë të ndryshëm, α, β, γ ... numrat e plotë pozitiv.

Zgjerimi (3) quhet zgjerim kanonik numrat.

Numrat e thjeshtë ndodhin në mënyrë të pabarabartë në serinë e numrave natyrorë. Në disa pjesë të rreshtit ka më shumë prej tyre, në të tjera - më pak. Sa më tej lëvizim përgjatë serisë së numrave, aq më pak të zakonshëm janë numrat e thjeshtë. Shtrohet pyetja, a ka një numër të thjeshtë më të madh? Matematikani i lashtë grek Euklidi vërtetoi se ka pafundësisht shumë numra të thjeshtë. Këtë provë e paraqesim më poshtë.

Teorema 2. Numri i numrave të thjeshtë është i pafund.

Dëshmi. Supozoni se ka një numër të kufizuar numrash të thjeshtë dhe le të jetë numri më i madh i thjeshtë fq. Le t'i konsiderojmë të gjithë numrat më të mëdhenj fq. Sipas supozimit të pohimit, këta numra duhet të jenë të përbërë dhe duhet të jenë të pjesëtueshëm me të paktën një nga numrat e thjeshtë. Le të zgjedhim një numër që është prodhimi i të gjithë këtyre numrave të thjeshtë plus 1:

Numri z më shumë fq sepse 2p tashmë më shumë fq. fq nuk është i pjesëtueshëm me asnjë nga këta numra të thjeshtë, sepse kur pjesëtohet me secilën prej tyre jep një mbetje prej 1. Kështu vijmë në një kontradiktë. Prandaj ka një numër të pafund numrash të thjeshtë.

Kjo teoremë është një rast i veçantë i një teoreme më të përgjithshme:

Teorema 3. Le të jepet një progresion aritmetik

Pastaj çdo numër kryesor i përfshirë në n, duhet të përfshihet në m, pra në n faktorë të tjerë kryesorë që nuk përfshihen në m dhe, për më tepër, këta faktorë kryesorë në n përfshihen jo më shumë herë se në m.

E kundërta është gjithashtu e vërtetë. Nëse çdo faktor kryesor i një numri n përfshirë të paktën po aq herë në numër m, Kjo m ndarë nga n.

deklaratë 3. Le a 1 ,a 2 ,a 3,... numra të thjeshtë të ndryshëm të përfshirë në m Pra

Ku i=0,1,...α , j=0,1,...,β , k=0,1,..., γ . Vini re se αi pranon α vlerat +1, β j pranon β vlerat +1, γ k pranon γ vlerat +1, ... .