7 prvočíslo alebo 9 prvočíslo. Ako nájsť prvočísla

Zoznam deliteľov. Podľa definície číslo n je prvočíslo iba vtedy, ak nie je rovnomerne deliteľné 2 a akýmikoľvek inými celými číslami ako 1 a sebou samým. Vyššie uvedený vzorec odstraňuje zbytočné kroky a šetrí čas: napríklad po kontrole, či je číslo deliteľné 3, nie je potrebné kontrolovať, či je deliteľné 9.

• Funkcia floor(x) zaokrúhli x na najbližšie celé číslo menšie alebo rovné x.

Získajte informácie o modulárnej aritmetike. Operácia "x mod y" (mod je skratka pre latinské slovo "modulo", čo znamená "modul") znamená "rozdeliť x y a nájsť zvyšok". Inými slovami, v modulárnej aritmetike, pri dosiahnutí určitej hodnoty, ktorá je tzv modul, čísla sa "otočia" späť na nulu. Napríklad hodiny merajú čas v module 12: ukazujú 10, 11 a 12 hodín a potom sa vrátia na 1.

• Mnoho kalkulačiek má mod kľúč. Koniec tejto časti ukazuje, ako manuálne vypočítať túto funkciu pre veľké čísla.

Čísla sú rôzne: prirodzené, prirodzené, racionálne, celé a zlomkové, kladné a záporné, komplexné a prvočíslo, nepárne a párne, skutočné atď. V tomto článku sa dozviete, čo základné čísla.

Aké čísla sa nazývajú anglické slovo „simple“?

Školáci veľmi často nevedia odpovedať na jednu zo zdanlivo najjednoduchších otázok v matematike, čo je prvočíslo. Často si zamieňajú prvočísla s prirodzenými číslami (to znamená číslami, ktoré ľudia používajú pri počítaní predmetov, zatiaľ čo v niektorých zdrojoch začínajú od nuly av iných - od jednotky). Ale sú úplne dva rôzne koncepty. Prvočísla sú prirodzené čísla, teda celé a kladné čísla, ktoré sú väčšie ako jedna a majú iba 2 prirodzených deliteľov. V tomto prípade je jedným z týchto deliteľov dané číslo a druhým je jednotka. Napríklad trojka je prvočíslo, pretože nie je rovnomerne deliteľné žiadnym iným číslom, než je samo sebou a jedna.

Zložené čísla

Opakom prvočísel sú zložené čísla. Sú tiež prirodzené, tiež väčšie ako jedna, ale nemajú dvoch, ale viac deliteľov. Takže napríklad čísla 4, 6, 8, 9 atď. sú prirodzené, zložené, ale nie prvočísla. Ako vidíte, ide väčšinou o párne čísla, ale nie o všetky. Ale „dvojka“ je párne číslo a „prvé číslo“ v rade prvočísel.

Následná sekvencia

Na zostavenie série prvočísel je potrebné urobiť výber zo všetkých prirodzených čísel, berúc do úvahy ich definíciu, to znamená, že musíte konať protirečivo. Je potrebné zvážiť každé z prirodzených kladných čísel na tému, či má viac ako dvoch deliteľov. Skúsme zostaviť rad (sekvenciu), ktorý pozostáva z prvočísel. Zoznam začína dvomi, potom príde tromi, keďže je deliteľný iba sám sebou a jedným. Zvážte číslo štyri. Má iné delitele ako štyri a jedna? Áno, to číslo je 2. Štyri teda nie je prvočíslo. Päťka je tiež prvočíslo (okrem 1 a 5 nie je deliteľné žiadnym iným číslom), ale šesť je deliteľné. A vo všeobecnosti, ak budete sledovať všetky párne čísla, všimnete si, že okrem „dvojky“ žiadne z nich nie je prvočíslo. Z toho usudzujeme, že párne čísla, okrem dvoch, nie sú prvočísla. Ďalší objav: všetky čísla, ktoré sú deliteľné tromi, okrem samotnej trojky, či už párnej alebo nepárnej, tiež nie sú prvočísla (6, 9, 12, 15, 18, 21, 24, 27 atď.). To isté platí pre čísla, ktoré sú deliteľné piatimi a siedmimi. Celá ich zostava tiež nie je jednoduchá. Poďme si to zhrnúť. Takže jednoducho jednociferné sú zahrnuté všetky nepárne čísla okrem jednotky a deviatky a z párnych iba „dvojka“. Samotné desiatky (10, 20,... 40 atď.) nie sú prvočíslo. Dvojciferné, trojciferné atď. prvočísla možno definovať na základe vyššie uvedených zásad: ak nemajú iných deliteľov okrem seba a jedného.

Teórie o vlastnostiach prvočísel

Existuje veda, ktorá študuje vlastnosti celých čísel, vrátane prvočísel. Toto je odvetvie matematiky, ktoré sa nazýva vyššie. Okrem vlastností celých čísel sa zaoberá aj algebraickými, transcendentálnymi číslami, ako aj funkciami rôzneho pôvodu súvisiacimi s aritmetikou týchto čísel. V týchto štúdiách sa okrem elementárnych a algebraické metódy, sa používajú aj analytické a geometrické. Konkrétne sa štúdium prvočísel zaoberá „Teóriou čísel“.

Prvočísla sú „stavebnými kameňmi“ prirodzených čísel

V aritmetike existuje veta nazývaná hlavná veta. Podľa nej akékoľvek prirodzené číslo, okrem jednoty, môže byť reprezentovaný ako súčin, ktorého faktory sú prvočísla a poradie faktorov je jedinečné, to znamená, že spôsob zobrazenia je jedinečný. Hovorí sa tomu rozklad prirodzeného čísla na prvočiniteľa. Tento proces má aj iný názov – rozklad čísel. Na základe toho možno prvočísla nazývať „ stavebný materiál“, „bloky“ na zostavovanie prirodzených čísel.

Hľadajte prvočísla. Testy jednoduchosti

Mnoho vedcov rôznych čias sa snažilo nájsť nejaké princípy (systémy) na nájdenie zoznamu prvočísel. Veda pozná systémy nazývané Atkinovo sito, Sundartamovo sito, Eratosthenovo sito. Nedávajú však žiadne významné výsledky a na nájdenie prvočísel sa používa jednoduchý test. Algoritmy vytvorili aj matematici. Nazývajú sa testy primality. Existuje napríklad test, ktorý vyvinuli Rabin a Miller. Používajú ho kryptografi. Existuje aj test Kayala-Agrawala-Saskena. Napriek dostatočnej presnosti je však veľmi náročný na výpočet, čo znižuje jeho praktickú hodnotu.

Má množina prvočísel limit?

To, že množina prvočísel je nekonečno, napísal v knihe „Začiatky“ staroveký grécky vedec Euklides. Povedal toto: „Predstavme si na chvíľu, že prvočísla majú limit. Potom ich medzi sebou vynásobme a jednu pridajme k produktu. Číslo získané ako výsledok týchto jednoduchých operácií nemôže byť deliteľné žiadnym z radu prvočísel, pretože zvyšok bude vždy jedna. A to znamená, že existuje nejaké ďalšie číslo, ktoré ešte nie je zahrnuté v zozname prvočísel. Náš predpoklad preto nie je pravdivý a táto množina nemôže mať limit. Okrem Euklidovho dôkazu je ich viac moderný vzorec podal švajčiarsky matematik z osemnásteho storočia Leonhard Euler. Podľa neho súčet, prevrátená hodnota súčtu prvých n čísel, rastie donekonečna s rastom čísla n. A tu je vzorec vety o rozdelení prvočísel: (n) rastie ako n / ln (n).

Aké je najväčšie prvočíslo?

Napriek tomu Leonard Euler dokázal nájsť najväčšie prvočíslo svojej doby. To je 2 31 - 1 = 2147483647. Do roku 2013 však bolo vypočítané ďalšie najpresnejšie najväčšie v zozname prvočísel - 2 57885161 - 1. Nazýva sa Mersennovo číslo. Obsahuje asi 17 miliónov desatinných číslic. Ako vidíte, číslo nájdené vedcom z osemnásteho storočia je niekoľkonásobne menšie ako toto. Malo to tak byť, pretože Euler tento výpočet robil ručne, no nášmu súčasníkovi zrejme pomohol počítač. Navyše, toto číslo bolo získané na Katedre matematiky na jednom z amerických oddelení. Čísla pomenované po tomto vedcovi prechádzajú Luc-Lehmerovým testom primálnosti. Veda sa však pri tom nechce zastaviť. Nadácia Electronic Frontier Foundation, ktorá bola založená v roku 1990 v Spojených štátoch amerických (EFF), ponúkla peňažnú odmenu za nájdenie veľkých prvočísel. A ak do roku 2013 bola cena udelená tým vedcom, ktorí ich nájdu medzi 1 a 10 miliónmi desatinné čísla, potom dnes toto číslo dosiahlo od 100 miliónov do 1 miliardy. Ceny sa pohybujú od 150 do 250 tisíc amerických dolárov.

Názvy špeciálnych prvočísel

Čísla, ktoré boli nájdené vďaka algoritmom vytvoreným určitými vedcami a prešli testom jednoduchosti, sa nazývajú špeciálne. Tu sú niektoré z nich:

1. Mersin.

4. Cullen.

6. Mills a kol.

Jednoduchosť týchto čísel, pomenovaných podľa vyššie uvedených vedcov, je stanovená pomocou nasledujúcich testov:

1. Lucas-Lemer.

2. Pepina.

3. Riesel.

4. Billhart - Lehmer - Selfridge a ďalší.

Moderná veda sa tam nekončí a svet pravdepodobne v blízkej budúcnosti spozná mená tých, ktorí dokázali získať cenu 250 000 dolárov nájdením najväčšieho prvočísla.

Článok sa zaoberá pojmami prvočíselných a zložených čísel. Uvádzame definície takýchto čísel s príkladmi. Preukážeme, že počet prvočísel je neobmedzený a urobíme zápis do tabuľky prvočísel pomocou Eratosthenovy metódy. Budú poskytnuté dôkazy o tom, či je číslo prvočíslo alebo zložené.

Yandex.RTB R-A-339285-1

Prvočísla a zložené čísla – definície a príklady

Prvočísla a zložené čísla sú klasifikované ako kladné celé čísla. Musia byť väčšie ako jedna. Deliče sa tiež delia na jednoduché a zložené. Aby sme pochopili pojem zložených čísel, je potrebné najprv preštudovať pojmy deliteľov a násobkov.

Definícia 1

Prvočísla sú celé čísla, ktoré sú väčšie ako jedna a majú dvoch kladných deliteľov, teda samy seba a 1.

Definícia 2

Zložené čísla sú celé čísla, ktoré sú väčšie ako jedna a majú aspoň troch kladných deliteľov.

Jedna nie je ani prvočíslo, ani zložené číslo. Má iba jedného kladného deliteľa, takže sa líši od všetkých ostatných kladných čísel. Všetky kladné celé čísla sa nazývajú prirodzené, to znamená, že sa používajú pri počítaní.

Definícia 3

základné čísla sú prirodzené čísla, ktoré majú iba dvoch kladných deliteľov.

Definícia 4

Zložené číslo je prirodzené číslo, ktoré má viac ako dvoch kladných deliteľov.

Akékoľvek číslo väčšie ako 1 je buď prvočíslo alebo zložené. Z vlastnosti deliteľnosti máme, že 1 a číslo a bude vždy deliteľom pre ľubovoľné číslo a, čiže bude deliteľné samo sebou a 1. Uvádzame definíciu celých čísel.

Definícia 5

Prirodzené čísla, ktoré nie sú prvočísla, sa nazývajú zložené čísla.

Prvočísla: 2, 3, 11, 17, 131, 523. Sú deliteľné iba sebou samými a 1. Zložené čísla: 6, 63, 121, 6697. To znamená, že číslo 6 možno rozložiť na 2 a 3 a 63 na 1, 3, 7, 9, 21, 63 a 121 na 11, 11, to znamená, že jeho deliteľmi budú 1, 11, 121. Číslo 6697 sa rozloží na 37 a 181. Všimnite si, že pojmy prvočísla a relatívne prvočísla sú odlišné pojmy.

Aby bolo používanie prvočísel jednoduchšie, musíte použiť tabuľku:

Tabuľka pre všetky existujúce prirodzené čísla je nereálna, keďže ich je nekonečne veľa. Keď čísla dosiahnu veľkosť 10 000 alebo 1 000 000 000, mali by ste premýšľať o použití Eratosthenovho sita.

Zvážte vetu, ktorá vysvetľuje posledné tvrdenie.

Veta 1

Najmenší kladný deliteľ prirodzeného čísla väčšieho ako 1 okrem 1 je prvočíslo.

Dôkaz 1

Predpokladajme, že a je prirodzené číslo väčšie ako 1, b je najmenším nejednotným deliteľom a. Musíme dokázať, že b je prvočíslo pomocou metódy kontradikcie.

Povedzme, že b je zložené číslo. Odtiaľto máme, že existuje deliteľ pre b , ktorý je odlišný od 1 aj od b . Takýto deliteľ je označený ako b 1 . Je potrebné splniť podmienku 1< b 1 < b bolo dokončené.

Z podmienky je zrejmé, že a je deliteľné b, b je deliteľné b 1, čo znamená, že pojem deliteľnosti je vyjadrený takto: a = b q a b = b 1 q 1 , odkiaľ a = b 1 (q 1 q), kde q a q 1 sú celé čísla. Podľa pravidla násobenia celých čísel máme, že súčin celých čísel je celé číslo s rovnosťou tvaru a = b 1 · (q 1 · q) . Je vidieť, že b 1 je deliteľom a. Nerovnosť 1< b 1 < b nie zhoduje sa, pretože dostaneme, že b je najmenší kladný ne-1 deliteľ a.

Veta 2

Prvočísel je nekonečne veľa.

Dôkaz 2

Predpokladajme, že vezmeme konečný počet prirodzených čísel n a označíme ako p 1 , p 2 , … , p n . Uvažujme o variante nájdenia prvočísla odlišného od uvedených.

Uvažujme číslo p, ktoré sa rovná p 1 , p 2 , … , p n + 1 . Nerovná sa každému z čísel zodpovedajúcich prvočíslam v tvare p 1 , p 2 , … , p n . Číslo p je prvočíslo. Potom sa veta považuje za dokázanú. Ak je zložený, potom musíme vziať zápis p n + 1 a ukázať nesúlad deliteľa s ktorýmkoľvek z p 1 , p 2 , ... , p n .

Ak by to tak nebolo, potom na základe vlastnosti deliteľnosti súčinu p 1 , p 2 , … , p n , dostaneme, že by to bolo deliteľné p n + 1 . Všimnite si, že výraz p n + 1 delené číslo p sa rovná súčtu p 1 , p 2 , … , p n + 1 . Dostaneme, že výraz p n + 1 druhý člen tohto súčtu, ktorý sa rovná 1, treba rozdeliť, ale to nie je možné.

Je vidieť, že medzi ľubovoľným počtom daných prvočísel možno nájsť akékoľvek prvočíslo. Z toho vyplýva, že prvočísel je nekonečne veľa.

Keďže prvočísel je veľa, tabuľky sú obmedzené na čísla 100, 1000, 10000 atď.

Pri zostavovaní tabuľky prvočísel je potrebné vziať do úvahy skutočnosť, že takáto úloha vyžaduje postupnú kontrolu čísel od 2 do 100. Ak nie je deliteľ, zapíše sa do tabuľky, ak je zložený, do tabuľky sa nezapíše.

Uvažujme krok za krokom.

Ak začínate číslom 2, potom má len 2 deliteľov: 2 a 1, čo znamená, že ho možno zapísať do tabuľky. Aj s číslom 3 . Číslo 4 je zložené, treba ho rozložiť na 2 a 2. Číslo 5 je prvočíslo, čo znamená, že ho možno v tabuľke opraviť. Urobte to až do čísla 100.

Táto metóda nepríjemné a dlhé. Môžete si vyrobiť stôl, ale musíte minúť veľké množstvočas. Je potrebné použiť kritériá deliteľnosti, ktoré urýchlia proces hľadania deliteľov.

Metóda využívajúca Eratosthenovo sito sa považuje za najvhodnejšiu. Pozrime sa na nižšie uvedené tabuľky. Na začiatok sa píšu čísla 2, 3, 4, ..., 50.

Teraz musíte prečiarknuť všetky čísla, ktoré sú násobkami 2. Vykonajte postupné prečiarknutie. Dostaneme tabuľku vo forme:

Prejdime k vyčiarknutiu čísel, ktoré sú násobkami 5. Dostaneme:

Prečiarkneme čísla, ktoré sú násobkami 7, 11. Nakoniec tabuľka vyzerá

Prejdime k formulácii vety.

Veta 3

Najmenší kladný a ne-1 deliteľ základného čísla a nepresahuje a , kde a je aritmetický koreň dané číslo.

Dôkaz 3

B je potrebné označiť ako najmenšieho deliteľa zloženého čísla a. Existuje celé číslo q , kde a = b · q , a máme, že b ≤ q . Nerovnosť formy b > q pretože je porušená podmienka. Obe strany nerovnosti b ≤ q by sa mali vynásobiť ľubovoľným kladným číslom b, ktoré sa nerovná 1 . Dostaneme, že b b ≤ b q , kde b 2 ≤ a a b ≤ a .

Z dokázanej vety je vidieť, že vymazanie čísel v tabuľke vedie k tomu, že je potrebné začať s číslom, ktoré sa rovná b 2 a spĺňa nerovnosť b 2 ≤ a . To znamená, že ak prečiarknete čísla, ktoré sú násobkami 2, proces začne od 4 a tie, ktoré sú násobkami 3, začnú od 9 a tak ďalej až do 100.

Zostavenie takejto tabuľky pomocou Eratosthenovho teorému hovorí, že keď sa prečiarknu všetky zložené čísla, zostanú prvočísla, ktoré nepresiahnu n. V príklade, kde n = 50, máme, že n = 50. Odtiaľto dostávame, že Eratosthenovo sito preosieva všetky zložené čísla, ktorých hodnota nie je väčšia ako hodnota odmocniny 50. Vyhľadávanie čísel prebieha prečiarknutím.

Pred riešením je potrebné zistiť, či je číslo prvočíslo alebo zložené. Často sa používajú kritériá deliteľnosti. Pozrime sa na to v príklade nižšie.

Príklad 1

Dokážte, že 898989898989898989 je zložené číslo.

Riešenie

Súčet číslic daného čísla je 9 8 + 9 9 = 9 17 . Takže číslo 9 17 je deliteľné 9 na základe znamienka deliteľnosti 9. Z toho vyplýva, že je zložený.

Takéto znaky nie sú schopné dokázať prvoradosť čísla. Ak je potrebné overenie, mali by sa podniknúť ďalšie kroky. Najvhodnejším spôsobom je vyčísliť čísla. Počas procesu možno nájsť prvočísla a zložené čísla. To znamená, že hodnota čísel by nemala presiahnuť . To znamená, že číslo a treba rozložiť na prvočiniteľa. ak je to pravda, potom číslo a možno považovať za prvočíslo.

Príklad 2

Určte zložené alebo prvočíslo 11723.

Riešenie

Teraz musíte nájsť všetkých deliteľov pre číslo 11723. Treba vyhodnotiť 11723 .

Odtiaľ vidíme, že 11723< 200 , то 200 2 = 40 000 a 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Pre presnejší odhad čísla 11723 je potrebné napísať výraz 108 2 = 11 664, resp. 109 2 = 11 881 , potom 108 2 < 11 723 < 109 2 . Z toho vyplýva, že 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

Pri rozklade dostaneme, že 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 7 7 7 , 6 , 7 7 , 6 83 , 89 , 97 , 101 , 103 , 107 sú všetky prvočísla. Celý tento proces možno znázorniť ako rozdelenie podľa stĺpca. To znamená, vydeľte 11723 číslom 19. Číslo 19 je jedným z jeho faktorov, keďže dostávame delenie bezo zvyšku. Znázornime rozdelenie podľa stĺpca:

Z toho vyplýva, že 11723 je zložené číslo, pretože okrem seba a 1 má deliteľa 19 .

odpoveď: 11723 je zložené číslo.

Ak si všimnete chybu v texte, zvýraznite ju a stlačte Ctrl+Enter

Iľjova odpoveď je správna, ale nie veľmi podrobná. V 18. storočí sa mimochodom ešte jedna považovala za prvočíslo. Napríklad takí významní matematici ako Euler a Goldbach. Goldbach je autorom jednej zo siedmich úloh tisícročia – Goldbachovej hypotézy. Pôvodná formulácia hovorí, že akékoľvek párne číslo môže byť reprezentované ako súčet dvoch prvočísel. Navyše, pôvodne sa 1 brala do úvahy ako prvočíslo a vidíme toto: 2 = 1 + 1. to najmenší príklad, čo zodpovedá pôvodnej formulácii hypotézy. Neskôr to bolo opravené a získalo sa znenie moderný vzhľad: "každé párne číslo od 4 môže byť vyjadrené ako súčet dvoch prvočísel."

Pripomeňme si definíciu. Prvočíslo p je prirodzené číslo p, ktoré má iba 2 rôznych prirodzených deliteľov: samotné p a 1. Dôsledok z definície: prvočíslo p má iba jedného prvočísla - samotné p.

Teraz predpokladajme, že 1 je prvočíslo. Prvočíslo má podľa definície iba jedného prvočísla – samo seba. Potom sa ukáže, že každé prvočíslo väčšie ako 1 je deliteľné prvočíslom, ktoré sa od neho líši (1). Ale dve odlišné prvočísla nemôžu byť navzájom deliteľné, pretože inak to nie sú prvočísla, ale zložené čísla, a to je v rozpore s definíciou. S týmto prístupom sa ukazuje, že existuje len 1 prvočíslo - samotná jednotka. Ale toto je absurdné. Preto 1 nie je prvočíslo.

1, rovnako ako 0, tvoria ďalšiu triedu čísel - triedu neutrálnych prvkov vzhľadom na n-nar operácie v niektorej podmnožine algebraického poľa. Okrem toho, čo sa týka operácie sčítania, 1 je tiež generujúcim prvkom kruhu celých čísel.

Vzhľadom na to nie je ťažké nájsť analógy prvočísel v iných algebraických štruktúrach. Predpokladajme, že máme multiplikatívnu skupinu vytvorenú z mocnín 2 počnúc od 1: 2, 4, 8, 16, ... atď. 2 tu pôsobí ako tvarovací prvok. Prvočíslo v tejto skupine je číslo, ktoré je väčšie ako najmenší prvok a deliteľné iba ním samotným a najmenším prvkom. V našej skupine majú takéto vlastnosti len 4. To je všetko. V našej skupine už nie sú žiadne prvočísla.

Ak by aj 2 bola v našej skupine prvočíslo, tak pozri prvý odstavec – opäť by sa ukázalo, že len 2 je prvočíslo.