1 je prvočíslo. Prvočísla: obyčajnosť nevyriešenej hádanky

Všetky prirodzené čísla, okrem jedného, sa delia na prvočísla a zložené. Prvočíslo je prirodzené číslo, ktoré má iba dvoch deliteľov: jedného a samého seba.. Všetky ostatné sa nazývajú kompozitné. Štúdiom vlastností prvočísel sa zaoberá špeciálny oddiel matematiky – teória čísel. V teórii prstencov prvočísla súvisia s neredukovateľnými prvkami.

Tu je postupnosť prvočísel od 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, ... atď.

Podľa základnej vety aritmetiky môže byť každé prirodzené číslo väčšie ako jedna reprezentované ako súčin prvočísel. Avšak, toto je jediná cesta zastupovanie prirodzené čísla až po poradie faktorov. Na základe toho môžeme povedať, že prvočísla sú elementárne časti prirodzených čísel.

Takéto zobrazenie prirodzeného čísla sa nazýva rozklad prirodzeného čísla na prvočísla alebo rozklad čísla na rozklad.

Jedným z najstarších a najefektívnejších spôsobov výpočtu prvočísel je „Erastothenovo sito“.

Prax ukázala, že po výpočte prvočísel pomocou sita Erastofen je potrebné skontrolovať, či je dané číslo prvočíslo. Za týmto účelom vyvinuté špeciálne testy, takzvané testy primality. Algoritmus týchto testov je pravdepodobnostný. Najčastejšie sa používajú v kryptografii.

Mimochodom, pre niektoré triedy čísel existujú špecializované účinné testy prvočíselnosti. Napríklad na testovanie jednoduchosti Mersennových čísel sa používa Lucas-Lehmerov test a na testovanie jednoduchosti Fermatových čísel sa používa Pepinov test.

Všetci vieme, že čísel je nekonečne veľa. Oprávnene vyvstáva otázka: koľko je teda prvočísel? Existuje tiež nekonečné množstvo prvočísel. Najstarším dôkazom tohto rozsudku je dôkaz Euklida, ktorý je uvedený v Živloch. Euklidov dôkaz je nasledujúci:

Predstavte si, že počet prvočísel je konečný. Vynásobme ich a jednu pripočítame. Výsledné číslo nemožno deliť žiadnym z konečnej množiny prvočísel, pretože zvyšok po delení ktorýmkoľvek z nich dáva jednotku. Číslo teda musí byť deliteľné nejakým prvočíslom, ktoré nie je zahrnuté v tejto množine.

Veta o rozdelení prvočísel uvádza, že počet prvočísel menších ako n, označovaných π(n), rastie ako n / ln(n).

Počas tisícok rokov štúdia prvočísel sa zistilo, že najväčšie známe prvočíslo je 243112609 − 1. Toto číslo má 12 978 189 desatinných číslic a je to Mersennovo prvočíslo (M43112609). Tento objav bol urobený 23. augusta 2008 na matematickom oddelení univerzity uCLA ako súčasť distribuovaného hľadania Mersennových prvočísel pomocou GIMPS.

Domov charakteristický znak Mersennove čísla sú prítomnosťou vysoko účinného Luc-Lehmerovho testu primality. Mersennove prvočísla sú tak po dlhú dobu najväčšími známymi prvočíslami.

Na mnohé otázky o prvočíslach však dodnes nedostali presné odpovede. Edmund Landau na 5. medzinárodnom matematickom kongrese sformuloval hlavné problémy v oblasti prvočísel:

Goldbachov problém alebo Landauov prvý problém spočíva v tom, že je potrebné dokázať alebo vyvrátiť, že každé párne číslo väčšie ako dva môže byť vyjadrené ako súčet dvoch prvočísel a každé nepárne číslo väčšie ako 5 môže byť vyjadrené ako súčet. tri jednoduchéčísla.
Druhý Landauov problém si vyžaduje nájsť odpoveď na otázku: existuje nekonečná množina „jednoduchých dvojčiat“ – prvočísel, medzi ktorými je rozdiel rovný 2?
Legendreho dohad alebo Landauov tretí problém znie: je pravda, že medzi n2 a (n + 1)2 je vždy prvočíslo?
Štvrtý Landauov problém: Je množina prvočísel v tvare n2 + 1 nekonečná?
Okrem vyššie uvedených problémov existuje problém určenia nekonečného počtu prvočísel v mnohých celočíselných postupnostiach, ako je Fibonacciho číslo, Fermatovo číslo atď.

Už od čias starých Grékov boli prvočísla pre matematikov veľmi príťažlivé. Neustále hľadajú rôzne cesty ich umiestnenie, ale väčšina efektívnym spôsobom„Zachytenie“ prvočísel sa považuje za metódu, ktorú našiel alexandrijský astronóm a matematik Eratosthenes. Táto metóda je stará už asi 2000 rokov.

Aké čísla sú prvočísla

Ako definovať prvočíslo? Mnohé čísla sú rovnomerne deliteľné inými číslami. Číslo, ktorým je celé číslo deliteľné, sa nazýva deliteľ.

V tomto prípade hovoríme o delení bezo zvyšku. Napríklad číslo 36 možno deliť 1, 2, 3, 4, 6, 9, 12, 18 a samo sebou, teda 36. Čiže 36 má 9 deliteľov. Číslo 23 je deliteľné len samo sebou a 1, to znamená, že toto číslo má 2 deliteľov - toto číslo je prvočíslo.

Čísla, ktoré majú iba dvoch deliteľov, sa nazývajú prvočísla. Čiže číslo, ktoré je deliteľné bezo zvyšku len samo sebou a jednotkou, sa nazýva prvočíslo.

Pre matematikov je objavovanie vzorov v rade čísel, z ktorých sa potom dajú vytvárať hypotézy, veľmi príjemnou udalosťou. Ale prvočísla sa odmietajú podriadiť akémukoľvek vzoru. Existuje však spôsob, ako definovať prvočísla. Túto metódu našiel Eratosthenes, nazýva sa „Eratosthenovo sito“. Pozrime sa na variant takého "sita", prezentovaného vo forme tabuľky čísel do 48, a pochopíme, ako sa zostavuje.

V tejto tabuľke sú označené všetky prvočísla menšie ako 48 oranžová . Nachádzajú sa takto:

1 - má jediného deliteľa, a preto nie je prvočíslo;
2 je najmenšie prvočíslo a jediné párne, keďže všetky ostatné párne čísla sú deliteľné 2, to znamená, že majú aspoň 3 deliteľov, tieto čísla sa redukujú na fialový stĺpec;
3 je prvočíslo, má dvoch deliteľov, všetky ostatné čísla, ktoré sú deliteľné 3 sú vylúčené - tieto čísla sú zhrnuté v žltom stĺpci. Stĺpec označený fialovou aj žltou farbou obsahuje čísla deliteľné 2 a 3;
5 je prvočíslo, všetky čísla, ktoré sú deliteľné 5 sú vylúčené - tieto čísla sú obklopené zeleným oválom;
7 je prvočíslo, všetky čísla, ktoré sú deliteľné 7, sú zakrúžkované červenou farbou - nie sú prvočísla;

Všetky iné ako prvočísla sú označené modrou farbou. Ďalej môže byť táto tabuľka zostavená na obrázku a podobe.

základné čísla predstavujú jeden z najzaujímavejších matematických fenoménov, ktorý priťahuje pozornosť vedcov i bežných občanov už viac ako dve tisícročia. Napriek tomu, že dnes žijeme v dobe počítačov a najmodernejších informačných programov, mnohé záhady prvočísel ešte nie sú vyriešené, dokonca sú aj také, ku ktorým vedci nevedia, ako sa priblížiť.

Prvočísla sú, ako je známe z kurzu elementárnej aritmetiky, tie, ktoré sú bezo zvyšku deliteľné iba jedným a sebou samým. Mimochodom, ak je prirodzené číslo deliteľné okrem vyššie uvedených aj iným číslom, potom sa nazýva zložené. Jedna z najznámejších teorém hovorí, že akékoľvek zložené číslo môže byť reprezentované ako jediný možný súčin prvočísel.

Pár zaujímavých faktov. Po prvé, jednotka je jedinečná v tom zmysle, že v skutočnosti nepatrí ani do prvočísel, ani do zložených čísel. Zároveň je vo vedeckej komunite stále zvykom priraďovať ho k prvej skupine, pretože formálne plne spĺňa jej požiadavky.

Po druhé, jediné párne číslo, ktoré sa vkradlo do skupiny „prvočísel“, je, samozrejme, dvojka. Žiadne iné párne číslo sa sem jednoducho nedostane, pretože podľa definície je okrem seba a jednotky deliteľné aj dvomi.

Prvočísla, ktorých zoznam, ako už bolo spomenuté vyššie, môže začínať jednotkou, sú nekonečným radom, rovnako nekonečným ako rad prirodzených čísel. Na základe základnej vety aritmetiky možno dospieť k záveru, že prvočísla nie sú nikdy prerušené a nikdy nekončia, pretože inak by bol rad prirodzených čísel nevyhnutne prerušený.

Prvočísla sa v prirodzenom rade nevyskytujú náhodne, ako by sa na prvý pohľad mohlo zdať. Po ich dôkladnej analýze si môžete okamžite všimnúť niekoľko funkcií, z ktorých najkurióznejšie sú spojené s takzvanými „dvojitými“ číslami. Nazývajú sa tak preto, že nejakým nepochopiteľným spôsobom skončili vedľa seba, oddelené len párnym oddeľovačom (päť a sedem, sedemnásť a devätnásť).

Ak sa na ne pozriete pozorne, všimnete si, že súčet týchto čísel je vždy násobkom troch. Navyše, pri delení trojkou ľavého kolegu zostáva zvyšok vždy dva a ten pravý - jeden. Okrem toho sa dá predpovedať samotná distribúcia týchto čísel pozdĺž prirodzeného radu, ak je celý tento rad reprezentovaný vo forme oscilačných sínusoidov, ktorých hlavné body sa tvoria, keď sú čísla delené tromi a dvoma.

Prvočísla nie sú len predmetom podrobného skúmania matematikov na celom svete, ale už dlho sa úspešne používajú pri zostavovaní rôznych radov čísel, čo je základ, a to aj pre šifrovanie. Zároveň treba uznať, že obrovské množstvo záhad spojených s týmito nádhernými prvkami ešte len čaká na vyriešenie, mnohé otázky majú nielen filozofický, ale aj praktický význam.

Prvočíslo je prirodzené číslo, ktoré je deliteľné iba samo sebou a jednotkou.

Zvyšné čísla sa nazývajú zložené.

Jednoduché prirodzené čísla

Ale nie všetky prirodzené čísla sú prvočísla.

Jednoduché prirodzené čísla sú len tie, ktoré sú deliteľné len sebou samým a jedným.

Príklady prvočísel:

2; 3; 5; 7; 11; 13;...

Jednoduché celé čísla

Z toho vyplýva, že prvočísla sú len prirodzené čísla.

To znamená, že prvočísla sú nevyhnutne prirodzené.

Ale všetky prirodzené čísla sú tiež celé čísla.

Všetky prvočísla sú teda celé čísla.

Príklady prvočísel:

2; 3; 5; 7; 11; 13; 17; 19; 23;...

Dokonca prvočísla

Existuje len jedno párne prvočíslo, a to dve.

Všetky ostatné prvočísla sú nepárne.

Prečo párne číslo väčšie ako dva nemôže byť prvočíslo?

Ale pretože každé párne číslo väčšie ako dva bude deliteľné samo o sebe, nie jedným, ale dvoma, teda také číslo bude mať vždy troch deliteľov a možno aj viac.

Č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 do tabuľky prvočísel zapíšeme Eratosthenovu metódu. 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é čísla, je potrebné najprv š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 číslom 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 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, 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ľ sa označí 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 o násobení 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ý, musíme použiť 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é mať na pamäti, že takáto úloha si 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á iba 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 je nepohodlná a časovo náročná. Môžete si vyrobiť stôl, ale musíte minúť veľký početč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

Je potrebné určiť b najmenší deliteľ zložené číslo 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ľnou kladné číslo b , nerovná sa 1 . Dostaneme, že b b ≤ b q , kde b 2 ≤ a a b ≤ a .

Z dokázanej vety je vidieť, že prečiarknutie čí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ž po 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é nie sú väčšiu hodnotu koreň z 50. Vyhľadávanie čísel prebieha preškrtávaní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.

rozhodnutie

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 hlavné faktory. 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.

rozhodnutie

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 menej ako číslo 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 , 61 , 7 , 6 83 , 89 , 97 , 101 , 103 , 107 sú všetky prvočísla. celý tento proces možno znázorniť ako delenie stĺpcom. 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: