Veta.

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

Dôkaz.

Predpokladajme, že nie. To znamená, že predpokladajme, že existuje len n prvočísel a tieto prvočísla sú p 1, p 2, ..., p n. Ukážme, že vždy môžeme nájsť iné prvočíslo, ako sú uvedené.

Uvažujme číslo p rovné p 1 · p 2 ·... · p n +1. Je jasné, že toto číslo sa líši od každého z prvočísel p 1, p 2,…, p n. Ak je p prvočíslo, potom je veta dokázaná. Ak je toto číslo zložené, potom na základe predchádzajúcej vety existuje prvočíselník tohto čísla (označíme ho p n + 1). Ukážme, že tento deliteľ sa nezhoduje so žiadnym z čísel p 1, p 2,…, p n.

Ak by to tak nebolo, potom by podľa vlastností deliteľnosti bol súčin p 1 · p 2 ·… · p n deliteľný p n + 1. Ale číslo p je tiež deliteľné p n + 1, čo sa rovná súčtu p 1 · p 2 ·... · p n +1. Z toho vyplýva, že druhý člen tohto súčtu, ktorý sa rovná jednej, musí byť vydelený p n + 1, ale to nie je možné.

Bolo dokázané, že vždy sa dá nájsť nové prvočíslo, ktoré nie je medzi ľubovoľným počtom vopred priradených prvočísel. Preto prvočísel je nekonečne veľa.

Čiže vzhľadom na to, že prvočísel je nekonečne veľa, pri zostavovaní tabuliek prvočísiel sa vždy zhora obmedzia nejakým číslom, zvyčajne 100, 1000, 10000 atď.

Eratosthenove sito

Teraz si rozoberieme spôsoby zostavovania tabuliek prvočísel. Povedzme, že potrebujeme vytvoriť tabuľku prvočísel do 100.

Najzrejmejšou metódou riešenia tohto problému je postupná kontrola kladných celých čísel, počnúc 2 a končiac 100, na prítomnosť kladného deliteľa, ktorý je väčší ako 1 a menší ako testované číslo (z vlastností deliteľnosti vieme že absolútna hodnota deliteľa nepresahuje absolútnu hodnotu dividendy, nenulovú). Ak sa takýto deliteľ nenájde, kontrolované číslo je prvočíslo a zapíše sa do tabuľky prvočísel. Ak sa takýto deliteľ nájde, potom je kontrolované číslo zložené, NEZApisuje sa do tabuľky prvočísel. Potom sa uskutoční prechod na ďalšie číslo, ktoré sa podobne skontroluje na prítomnosť deliteľa.

Poďme si popísať prvých pár krokov.

Začíname číslom 2. Číslo 2 nemá kladných deliteľov, okrem 1 a 2. Preto je to jednoduché, preto to zapíšeme do tabuľky prvočísel. Tu treba povedať, že 2 je najmenšie prvočíslo. Prechod na číslo 3. Jeho možný kladný deliteľ, iný ako 1 a 3, je 2. Ale 3 nie je deliteľné 2, preto je 3 prvočíslo a treba ho zadať aj do tabuľky prvočísel. Prejdeme k číslu 4. Jeho pozitívnymi faktormi, okrem 1 a 4, môžu byť čísla 2 a 3, poďme si ich overiť. Číslo 4 je deliteľné 2, takže 4 je zložené číslo a nie je potrebné ho zadávať do prvočísla. Všimnite si, že 4 je najmenšie zložené číslo. Prejdeme k číslu 5. Skontrolujte, či aspoň jedno z čísel 2, 3, 4 je jeho deliteľ. Keďže 5 nie je deliteľné 2, 3 alebo 4, je jednoduché a treba ho zapísať do tabuľky prvočísel. Potom nasleduje prechod na čísla 6, 7 a tak ďalej až do 100.

Tento prístup k zostaveniu tabuľky prvočísel má ďaleko od ideálu. Tak či onak, má právo na existenciu. Všimnite si, že pri tejto metóde konštrukcie tabuľky celých čísel môžete použiť kritériá deliteľnosti, ktoré mierne urýchlia proces hľadania deliteľov.

Existuje pohodlnejší spôsob zostavenia tabuľky prvočísel, tzv. Slovo „sito“ prítomné v názve nie je náhodné, pretože pôsobenie tejto metódy pomáha takpovediac „preosiať“ cez Eratosthenovo sito celé čísla, veľké jednotky, aby sa oddelilo prvočíslo od zloženého.

Ukážme si Eratosthenovo sito v akcii pri zostavovaní tabuľky prvočísel do 50.

Najprv si zapíšeme čísla 2, 3, 4,…, 50 v poradí.

Prvé zaznamenané číslo 2 je prvočíslo. Teraz sa od čísla 2 postupne posúvame o dve čísla doprava a tieto čísla škrtáme, kým sa nedostaneme na koniec zostavenej tabuľky čísel. Tým sa prečiarknu všetky násobky dvoch.

Prvé neprečiarknuté číslo po 2 je 3. Toto číslo je prvočíslo. Teraz sa od čísla 3 postupne posunieme o tri čísla doprava (berúc do úvahy už prečiarknuté čísla) a prečiarkneme ich. Tým sa prečiarknu všetky čísla, ktoré sú násobkami troch.

Prvé neprečiarknuté číslo po 3 je 5. Toto číslo je prvočíslo. Teraz sa od čísla 5 postupne posunieme doprava o 5 čísel (berieme do úvahy predtým prečiarknuté čísla) a prečiarkneme ich. Tým sa prečiarknu všetky násobky piatich.

Potom prečiarknite čísla, ktoré sú násobkom 7, potom násobkom 11 atď. Proces končí, keď nezostanú žiadne čísla na prečiarknutie. Nižšie je uvedená kompletná tabuľka prvočísel do 50 získaných pomocou Eratosthenovho sita. Všetky neprečiarknuté čísla sú prvočísla a všetky prečiarknuté čísla sú zložené.

Sformulujme a dokážme vetu, ktorá urýchli proces zostavovania tabuľky prvočísel pomocou Eratosthenovho sita.

Veta.

Najmenší kladný a nie jeden deliteľ zloženého čísla a nepresahuje, kde je od a.

Dôkaz.

Nech b označuje najmenšieho a nejednotného deliteľa zloženého čísla a (číslo b je prvočíslo, čo vyplýva z vety dokázanej na samom začiatku predchádzajúceho pododdielu). Potom existuje celé číslo q také, že a = b q (tu q je kladné celé číslo, čo vyplýva z pravidiel pre násobenie celých čísel) a (pre b> q je porušená podmienka, že b je najmenším deliteľom a), pretože q je tiež deliteľom čísla a na základe rovnosti a = q · b). Vynásobením oboch strán nerovnosti kladným celým číslom b väčším ako jedna (môžeme to urobiť), dostaneme, odkiaľ a.

Čo nám dáva dokázaná veta o Eratosthenovom site?

Po prvé, vymazanie zložených čísel, ktoré sú násobkami prvočísla b, by malo začínať číslom rovným (to vyplýva z nerovnosti). Napríklad prečiarknutie čísel, ktoré sú násobkom dvoch, by malo začínať 4, násobky troch 9, násobky piatich 25 atď.

Po druhé, zostavenie tabuľky prvočísel až po číslo n pomocou Eratosthenovho sita možno považovať za úplné, keď sa vymažú všetky zložené čísla, ktoré sú násobkami prvočísel, ktoré nepresahujú. V našom príklade je n = 50 (keďže zostavujeme tabuľku prvočísel do 50), a preto musí Eratosthenove sito odstrániť všetky zložené čísla, ktoré sú násobkami prvočísel 2, 3, 5 a 7, ktoré nepresahujú aritmetická druhá odmocnina z 50. To znamená, že už nemusíme hľadať a preškrtávať čísla, ktoré sú násobkami prvočísel 11, 13, 17, 19, 23 a tak ďalej až do 47, keďže už budú prečiarknuté ako násobky menších prvočísel 2, 3, 5 a 7...

Je toto číslo prvočíslo alebo zložené?

Niektoré úlohy vyžadujú zistenie, či je dané číslo prvočíslo alebo zložené. Vo všeobecnom prípade nie je táto úloha ani zďaleka jednoduchá, najmä pokiaľ ide o čísla, ktorých záznam pozostáva z veľkého počtu znakov. Vo väčšine prípadov musíte hľadať nejaký konkrétny spôsob, ako to vyriešiť. Pokúsime sa však nasmerovať tok myšlienok pre jednoduché prípady.

Nepochybne sa môžete pokúsiť použiť kritériá deliteľnosti, aby ste dokázali, že dané číslo je zložené. Ak napríklad nejaký znak deliteľnosti ukazuje, že dané číslo je deliteľné nejakým kladným celým číslom väčším ako jedna, potom je pôvodné číslo zložené.

Príklad.

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

Riešenie.

Súčet číslic tohto čísla je 9 8 + 9 9 = 9 17. Keďže číslo rovné 9 · 17 je deliteľné 9, potom na základe deliteľnosti 9 možno tvrdiť, že pôvodné číslo je deliteľné aj 9. Preto je zložený.

Významnou nevýhodou tohto prístupu je, že testy deliteľnosti neumožňujú dokázať, že číslo je prvočíslo. Preto pri kontrole čísla, či je jednoduché alebo zložené, musíte konať inak.

Najlogickejší prístup je iterovať cez všetky možné delitele daného čísla. Ak žiadny z možných deliteľov nie je skutočným deliteľom daného čísla, potom toto číslo bude prvočíslo, inak bude zložené. Z teorém dokázaných v predchádzajúcej časti vyplýva, že deliteľov daného čísla a treba hľadať medzi prvočíslami, ktoré nepresahujú. Dané číslo a možno teda postupne deliť prvočíslami (ktoré je vhodné vziať z tabuľky prvočísel), pričom sa snažíme nájsť deliteľa čísla a. Ak sa nájde deliteľ, potom je číslo a zložené. Ak medzi prvočíslami, ktoré nepresahujú, nie je deliteľ čísla a, potom číslo a je prvočíslo.

Príklad.

číslo 11 723 jednoduché alebo zložené?

Riešenie.

Poďme zistiť, do akého prvočísla môžu byť deliče čísla 11 723. Za to budeme odhadovať.

To je pomerne zrejmé , od roku 200 2 = 40 000 a 11 723<40 000 (при необходимости смотрите статью porovnanie čísel). Možné hlavné faktory pre 11 723 sú teda menšie ako 200. Už to značne uľahčuje našu úlohu. Ak by sme to nevedeli, museli by sme opakovať všetky prvočísla nie až po 200, ale až po číslo 11 723.

Ak chcete, môžete odhadnúť presnejšie. Pretože 108 2 = 11 664 a 109 2 = 11 881, potom 108 2<11 723<109 2 , следовательно, ... Každé z prvočísel menších ako 109 je teda potenciálne prvočíselným deliteľom daného čísla 11 723.

Teraz postupne rozdelíme číslo 11 723 prvočíslami 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. Ak je číslo 11 723 celé vydelené jedným zo zapísaných prvočísel, bude zložené. Ak nie je deliteľné žiadnym zo zapísaných prvočísel, tak pôvodné číslo je prvočíslo.

Nebudeme popisovať celý tento monotónny a monotónny proces delenia. Povedzme hneď, že 11 723

Článok rozoberá koncepty prvočísel a zložených čísel. Definície takýchto čísel sú uvedené s príkladmi. Podávame dôkaz, že počet prvočísel je neobmedzený a do tabuľky prvočísel zapíšeme Eratosthenovu metódu. Bude poskytnutý dôkaz 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. Musí ich byť viac. Deliče sa tiež delia na jednoduché a zložené. Aby ste pochopili pojem zložených čísel, musíte si 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.

Jednotka 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ú na počítanie.

Definícia 3

základné čísla Sú prirodzené čísla s iba dvoma kladnými deliteľmi.

Definícia 4

Zložené číslo Je prirodzené číslo s viac ako dvoma kladnými deliteľmi.

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, to znamená, že bude deliteľné samo sebou a číslom 1. Uveďme 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. Delia sa len sami sebou 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 rozšíri na 37 a 181. Všimnite si, že koncepty prvočísel a druhých čísel sú odlišné koncepty.

Aby ste si uľahčili používanie prvočísel, 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 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ý a ne-1 deliteľ prirodzeného čísla väčšieho ako jedna je prvočíslo.

Dôkaz 1

Vezmime si, že a je prirodzené číslo väčšie ako 1, b je najmenší nejednotný deliteľ čísla a. Dokážte, že b je prvočíslo jeho protirečením.

Povedzme, že b je zložené číslo. Z toho vyplýva, že pre b existuje deliteľ, ktorý je odlišný od 1 aj od b. Takýto deliteľ sa označuje ako b 1. Je potrebné splniť podmienku 1< b 1 < b bola splnená.

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 čísla a. Nerovnosť 1< b 1 < b nie zodpovedá, pretože dostaneme, že b je najmenší kladný a 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 ho ako p 1, p 2,…, p n. Zvážte možnosť nájsť iné prvočíslo, ako je uvedené.

Zoberme si do úvahy číslo p, ktoré sa rovná p 1, p 2, ..., p n + 1. Nerovná sa každé z čísel zodpovedajúcich prvočíslam v tvare p 1, p 2, ..., p n. P je prvočíslo. Potom sa veta považuje za dokázanú. Ak je zložený, musíte použiť zápis p n + 1 a ukážte, že deliteľ sa nezhoduje so žiadnym 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 tejto sumy sa musí deliť, čo sa rovná 1, 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é mať na pamäti, že pre takúto úlohu je potrebná postupná kontrola čísel od 2 do 100. V prípade absencie deliteľa sa zaznamená do tabuľky, ak je zložená, tak sa do tabuľky nezapíše.

Uvažujme krok za krokom.

Ak začnete číslom 2, potom má iba 2 deliteľov: 2 a 1, čo znamená, že ho možno zadať do tabuľky. Aj s číslom 3. Číslo 4 je zložené číslo, treba ho rozložiť na 2 a 2 ďalšie. Číslo 5 je jednoduché, čo znamená, že sa dá opraviť v tabuľke. Urobte to až do čísla 100.

Táto metóda je nepohodlná a časovo náročná. Môžete si vyrobiť stôl, ale budete musieť stráviť veľa času. 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. Zvážte príklad tabuliek nižšie. Na začiatok sa zapíš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:

Pokračujeme k prečiarknutiu čísel, ktoré sú násobkami 5. Dostaneme:

Prečiarknite čísla, ktoré sú násobkami 7, 11. Koniec koncov, stôl vyzerá takto

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ého čísla.

Dôkaz 3

Je potrebné označiť b 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, keďže dôjde k porušeniu podmienky. Obe strany nerovnosti b ≤ q by sa mali vynásobiť akýmkoľvek 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 násobky 3 od 9 a tak ďalej až do 100.

Zostavenie takejto tabuľky pomocou Eratosthenovho teorému naznačuje, že pri vymazaní všetkých zložených čísel budú jednoduché čísla, ktoré nepresahujú n. V príklade, kde n = 50, máme, že n = 50. Zistili sme teda, že Eratosthenovo sito eliminuje všetky zložené čísla, ktorých hodnota nie je väčšia ako hodnota odmocniny 50. Čísla sa hľadajú prečiarknutím.

Pred rozhodnutím si musíte zistiť, či je číslo prvočíslo alebo zložené. Často sa používajú kritériá deliteľnosti. Pozrime sa na príklad nižšie.

Príklad 1

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

Riešenie

Súčet číslic daného čísla je 9 8 + 9 9 = 9 17. To znamená, ž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é preukázať jednoduchosť čísla. Ak je potrebné overenie, mali by sa vykonať iné opatrenia. Najvhodnejším spôsobom je opakovať čísla. Počas celého procesu môžete nájsť prvočísla a zložené čísla. To znamená, že čísla by nemali prekročiť hodnotu a. To znamená, že číslo a treba rozložiť na prvočiniteľa. ak sa tak stane, 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. Musíte ohodnotiť 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é zapí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 считается делителем для заданного числа.

V expanzii dostaneme, že 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 sú všetky prvočísla. Celý tento proces možno opísať ako dlhé delenie. To znamená, vydeľte 11723 číslom 19. Číslo 19 je jedným z jeho faktorov, keďže dostávame delenie bezo zvyšku. Predstavme si rozdelenie podľa stĺpca:

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

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

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