Kontrola, či je číslo prvočíslo. Ako skontrolovať, či je číslo prvočíslo

To, že existujú čísla, ktoré nie sú deliteľné žiadnym iným číslom, vedeli ľudia už v staroveku. Postupnosť prvočísel vyzerá asi takto:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Dôkaz, že týchto čísel je nekonečne veľa, podal Euklides, ktorý žil v roku 300 pred Kr Približne v rovnakom čase ďalší grécky matematik, Eratosthenes, prišiel s pomerne jednoduchým algoritmom na získavanie prvočísel, ktorého podstatou bolo postupné vymazávanie čísel z tabuľky. Tie zostávajúce čísla, ktoré neboli ničím deliteľné, boli prvočísla. Algoritmus sa nazýva „Eratosthenovo sito“ a pre svoju jednoduchosť (nie sú v ňom operácie násobenia ani delenia, iba sčítanie) sa stále používa vo výpočtovej technike.

Zrejme už za čias Eratosthena sa ukázalo, že neexistuje jasné kritérium pre to, či je číslo prvočíslo - to sa dá overiť iba experimentálne. Existovať rôznymi spôsobmi zjednodušiť proces (napríklad je zrejmé, že číslo by nemalo byť párne), ale jednoduchý overovací algoritmus sa doteraz nenašiel a pravdepodobne ani nenájde: zistiť, či je číslo prvočíslo alebo nie , treba to skúsiť rozdeliť na všetky menšie čísla.

Či poslúchajú základné čísla nejaké zákony? Áno, a sú dosť zvedaví.

Napríklad francúzsky matematik Mersenne ešte v 16. storočí zistil, že mnohé prvočísla majú tvar 2 ^ N - 1, tieto čísla sa nazývajú Mersennove čísla. Krátko predtým, v roku 1588, taliansky matematik Cataldi objavil prvočíslo 2 19 - 1 = 524287 (podľa Mersenovej klasifikácie sa nazýva M19). Dnes sa toto číslo zdá byť veľmi krátke, ale aj teraz s kalkulačkou by kontrola jeho jednoduchosti zabrala viac ako jeden deň a na 16. storočie to bola naozaj obrovská práca.

O 200 rokov neskôr matematik Euler našiel ďalšie prvočíslo 2 31 - 1 = 2147483647. Potrebné množstvo výpočtov si opäť každý vie predstaviť sám. Predložil tiež hypotézu (neskôr nazvanú „Eulerov problém“ alebo „binárny Goldbachov problém“), ktorej podstata je jednoduchá: každé párne číslo väčšie ako dva môže byť vyjadrené ako súčet dvoch prvočísel.

Môžete si napríklad vziať ľubovoľné 2 párne čísla: 123456 a 888777888.

Pomocou počítača zistíte ich súčet v tvare dvoch prvočísel: 123456 = 61813 + 61643 a 888777888 = 444388979 + 444388909. Tu je zaujímavé, že presný dôkaz tejto vety sa doteraz nepodarilo nájsť, pomocou počítačov bolo overené na čísla s 18 nulami.

Existuje ďalšia matematická veta Pierre Fermat, objavený v roku 1640, ktorý hovorí, že ak má prvočíslo tvar 4 * k + 1, potom ho možno reprezentovať ako súčet druhých mocnín iných čísel. Takže napríklad v našom príklade je prvočíslo 444388909 = 4*111097227 + 1. V skutočnosti pomocou počítača zistíte, že 444388909 = 19197*19197 + 8710*8710.

Euler túto vetu dokázal až o 100 rokov neskôr.

A nakoniec Bernhard Riemann v roku 1859 bola predložená takzvaná „Riemannova hypotéza“ o počte rozdelení prvočísel, ktoré nepresahujú určitý počet. Táto hypotéza sa doteraz nepotvrdila, je zaradená do zoznamu siedmich „problémov tisícročia“, za riešenie každého z nich je Clayov matematický inštitút v Cambridge pripravený vyplatiť odmenu milión amerických dolárov.

S prvočíslami to teda nie je také jednoduché. Existujú tiež úžasné fakty. Napríklad v roku 1883 ruský matematik ONI. Pervushin z Permského okresu dokázal jednoduchosť čísla 2 61 - 1 = 2305843009213693951 . S takými dlhými číslami nedokážu domáce kalkulačky pracovať ani teraz, no na tú dobu to bola naozaj gigantická práca a ako sa to robilo, dodnes nie je veľmi jasné. Aj keď skutočne existujú ľudia, ktorí jedinečné schopnosti mozog – napríklad autisti sú známi tým, že vedia nájsť v mysli (!) 8-miestne prvočísla. Ako to robia, nie je jasné.

modernosť

Sú dnes prvočísla relevantné? A ako! Prvočísla sú základom modernej kryptografie, takže väčšina ľudí ich používa každý deň bez toho, aby o tom premýšľali. Akýkoľvek proces overovania, ako je registrácia telefónu v sieti, bankové platby atď., vyžaduje kryptografické algoritmy.

Podstata myšlienky je tu mimoriadne jednoduchá a je základom algoritmu RSA navrhnuté už v roku 1975. Odosielateľ a príjemca si spoločne vyberú takzvaný „súkromný kľúč“, ktorý je uložený na bezpečnom mieste. Tento kľúč je, ako čitatelia uhádli, prvočíslo. Druhá časť – „verejný kľúč“, tiež prvočíslo, je tvorená odosielateľom a prenášaná ako produkt spolu so správou v obyčajnom texte, môže byť dokonca uverejnená v novinách. Podstatou algoritmu je, že bez znalosti „uzavretej časti“ nie je možné získať zdrojový text.

Napríklad, ak vezmeme dve prvočísla 444388979 a 444388909, potom „súkromný kľúč“ bude 444388979 a produkt 197481533549433911 (444388979 * 444388909 bude verejne prenesený). Len keď poznáte spriaznenú dušu, môžete vypočítať chýbajúce číslo a rozlúštiť s ním text.

Aký je tu trik? A to, že súčin dvoch prvočísel sa dá ľahko vypočítať, ale inverzná operácia neexistuje – ak nepoznáte prvú časť, tak takýto postup je možné vykonať iba enumeráciou. A ak zoberiete naozaj veľké prvočísla (napríklad 2000 znakov), dekódovanie ich produktu bude trvať niekoľko rokov aj na modernom počítači (vtedy už bude správa dlho irelevantná).

Genialita tejto schémy je v tom, že v samotnom algoritme nie je nič tajné - je otvorený a všetky údaje ležia na povrchu (známe sú algoritmus aj tabuľky veľkých prvočísel). Samotná šifra spolu s verejný kľúč môžu byť prenášané akýmkoľvek spôsobom, v akejkoľvek otvorenej forme. Bez toho, aby sme poznali tajnú časť kľúča, ktorú si odosielateľ vybral, šifrový text nedostaneme. Môžeme napríklad povedať, že popis algoritmu RSA bol publikovaný v časopise v roku 1977 a bol tam uvedený aj príklad šifry. Správna odpoveď bola získaná až v roku 1993 s pomocou distribuovaných počítačov na počítačoch 600 dobrovoľníkov.

Ukázalo sa teda, že prvočísla vôbec nie sú také jednoduché a ich príbeh sa tým zjavne nekončí.

Ilyova 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.

Čí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ď. Z tohto článku sa dozviete, čo sú prvočí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é čísla berúc do úvahy ich definíciu, to znamená, že musíte konať v rozpore. 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 je možné akékoľvek prirodzené číslo, okrem jednoty, znázorniť ako súčin, ktorého činiteľmi sú prvočísla a poradie činiteľov je jedinečné, čo 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ť. 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 nezastaví 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, pretože ich je nekonečné množstvo. 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čína od 4 a čísla, ktoré sú násobkami 3, začínajú 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