Prvočísla sú jedným z najzaujímavejších matematických javov, ktorý už viac ako dve tisícročia púta pozornosť vedcov aj bežných občanov. 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. Iné párne číslo sa sem jednoducho nedostane, keďž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. Navyše, samotné rozloženie týchto čísel pozdĺž prirodzeného radu možno predpovedať, ak je celý tento rad prezentovaný 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.

Definícia 1. prvočíslo je prirodzené číslo väčšie ako 1, ktoré je deliteľné iba samo sebou a 1.

Inými slovami, číslo je prvočíslo, ak má iba dvoch odlišných prirodzených deliteľov.

Definícia 2. Volá sa akékoľvek prirodzené číslo, ktoré má okrem seba a jedného aj iných deliteľov zložené číslo.

Inými slovami, prirodzené čísla, ktoré nie sú prvočísla, sa nazývajú zložené čísla. Definícia 1 znamená, že zložené číslo má viac ako dvoch prirodzených deliteľov. Číslo 1 nie je ani prvočíslo, ani zložené. má iba jedného deliteľa 1 a okrem toho mnohé vety o prvočíslach neplatia pre jednotu.

Definície 1 a 2 znamenajú, že každé kladné celé číslo väčšie ako 1 je buď prvočíslo alebo zložené číslo.

Nižšie je uvedený program na zobrazenie prvočísel do 5000. Vyplňte bunky, kliknite na tlačidlo „Vytvoriť“ a počkajte niekoľko sekúnd.

Tabuľka prvočísel

Vyhlásenie 1. Ak p je prvočíslo a a akékoľvek celé číslo, potom buď a deleno p, alebo p a a relatívne prvočísla.

naozaj. Ak p prvočíslo, potom je deliteľné len samo sebou a 1, ak a nedeliteľné p, potom najväčší spoločný deliteľ a a p rovná sa 1. Potom p a a relatívne prvočísla.

Vyhlásenie 2. Ak je súčin niekoľkých čísel a 1 , a 2 , a 3 , ... je deliteľné prvočíslom p, potom aspoň jedno z čísel a 1 , a 2 , a 3 , ... je deliteľné p.

naozaj. Ak žiadne z čísel nie je deliteľné p, potom čísla a 1 , a 2 , a 3 , ... by boli relatívne prvočísla vzhľadom na p. Ale z Dôsledku 3 () vyplýva, že ich produkt a 1 , a 2 , a 3, ... je tiež coprime vzhľadom na p, čo odporuje podmienke tvrdenia. Preto je aspoň jedno z čísel deliteľné p.

Veta 1. Akékoľvek zložené číslo môže byť vždy reprezentované, a navyše jedinečným spôsobom, ako súčin konečného počtu prvočísel.

Dôkaz. Nechať byť k zložené číslo, a nech a 1 je jeden z jeho deliteľov odlišný od 1 a samého seba. Ak a 1 je zložený, potom má okrem 1 a a 1 a ďalší rozdeľovač a 2. Ak a 2 je zložené číslo, potom má okrem 1 aj a 2 a ďalší rozdeľovač a 3. Argumentovať týmto spôsobom a brať do úvahy, že čísla a 1 , a 2 , a 3 , ... pokles a tento rad obsahuje konečný počet členov, dostaneme sa k nejakému prvočíslu p jeden . Potom k môže byť reprezentovaný ako

Predpokladajme, že existujú dve rozšírenia čísla k:

Ako k=p 1 p 2 p 3 ... je deliteľné prvočíslom q 1, potom aspoň jeden z faktorov, napr p 1 je deliteľné q jeden . ale p 1 je prvočíslo a je deliteľné iba 1 a sebou samým. Preto p 1 =q 1 (pretože q 1 ≠1)

Potom z (2) môžeme vylúčiť p 1 a q 1:

Zabezpečíme teda, že každé prvočíslo, ktoré vstúpi do prvého rozšírenia ako faktor jeden alebo viackrát, vstúpi do druhého rozšírenia aspoň toľkokrát a naopak, každé prvočíslo, ktoré vstúpi do druhého rozšírenia ako faktor jeden alebo niekoľko časy tiež vstupujú do prvej expanzie minimálne toľkokrát. Preto každé prvočíslo vstupuje ako činiteľ do oboch expanzií rovnako veľakrát, a teda tieto dve expanzie sú rovnaké.■

Rozklad zloženého čísla k možno napísať v nasledujúcej forme

kde p 1 , p 2 , ... odlišné prvočísla, α, β, γ ... celé kladné čísla.

Rozklad (3) sa nazýva kanonický rozkladčísla.

Prvočísla v rade prirodzených čísel sa vyskytujú nerovnomerne. V niektorých častiach série je ich viac, v iných menej. Čím ďalej sa pohybujeme po číselnom rade, tým sú prvočísla zriedkavejšie. Otázkou je, či existuje najväčšie prvočíslo? Staroveký grécky matematik Euclid dokázal, že prvočísel je nekonečne veľa. Tento dôkaz uvádzame nižšie.

Veta 2. Počet prvočísel je nekonečný.

Dôkaz. Predpokladajme, že existuje konečný počet prvočísel a nech je najväčšie prvočíslo p. Zoberme si všetky čísla p. Podľa predpokladu tvrdenia musia byť tieto čísla zložené a musia byť deliteľné aspoň jedným z prvočísel. Vyberme číslo, ktoré je súčinom všetkých týchto prvočísel plus 1:

číslo z viac p ako 2p už viac p. p nie je deliteľné žiadnym z týchto prvočísel, keďže pri delení každým z nich dáva zvyšok 1. Dostávame sa teda k rozporu. Preto existuje nekonečný počet prvočísel.

Táto veta je špeciálnym prípadom všeobecnejšej vety:

Veta 3. Nech je uvedený aritmetický postup

Potom zadajte ľubovoľné prvočíslo n, by mali byť zahrnuté aj v m, teda v n nemôže zahŕňať iné hlavné faktory, ktoré nie sú zahrnuté m a navyše tieto hlavné faktory v n sa neobjaví viackrát ako v m.

Platí to aj naopak. Ak je každý prvočíslo číslo n vyskytuje aspoň rovnaký počet krát m, potom m deleno n.

Vyhlásenie 3. Nechať byť a 1 ,a 2 ,a 3 ,... rôzne prvočísla objavujúce sa v m tak

kde i=0,1,...α , j=0,1,...,β , k=0,1,..., γ . Všimni si a i prijíma α +1 hodnoty, β j prijíma β +1 hodnoty, γ k berie γ +1 hodnoty, ... .

• Preklad

Vlastnosti prvočísel ako prví skúmali matematici starovekého Grécka. Matematici pytagorejskej školy (500 - 300 pred Kristom) sa zaujímali predovšetkým o mystické a numerologické vlastnosti prvočísel. Ako prví prišli s nápadmi o dokonalých a priateľských číslach.

Dokonalé číslo má svojich vlastných deliteľov, ktorí sú sebe rovní. Napríklad správnymi deliteľmi čísla 6 sú: 1, 2 a 3. 1 + 2 + 3 = 6. Deliteľmi čísla 28 sú 1, 2, 4, 7 a 14. Navyše 1 + 2 + 4 + 7 + 14 = 28.

Čísla sa nazývajú priateľské, ak sa súčet vlastných deliteľov jedného čísla rovná druhému a naopak - napríklad 220 a 284. Môžeme povedať, že dokonalé číslo je priateľské samo k sebe.

V čase objavenia sa diela Euklidove „Začiatky“ v roku 300 pred Kr. Niekoľko dôležitých faktov o prvočíslach už bolo dokázaných. V knihe IX prvkov Euklides dokázal, že existuje nekonečný počet prvočísel. Mimochodom, toto je jeden z prvých príkladov použitia dôkazu protirečením. Dokazuje tiež základnú vetu aritmetiky - každé celé číslo môže byť reprezentované jedinečným spôsobom ako súčin prvočísel.

Ukázal tiež, že ak je číslo 2 n -1 prvočíslo, potom číslo 2 n-1 * (2 n -1) bude dokonalé. Iný matematik Euler v roku 1747 dokázal, že v tejto forme možno zapísať všetky párne dokonalé čísla. Dodnes nie je známe, či existujú nepárne dokonalé čísla.

V roku 200 p.n.l. Grék Eratosthenes prišiel s algoritmom na hľadanie prvočísel, ktorý sa nazýva Eratosthenovo sito.

A potom nastal veľký zlom v dejinách skúmania prvočísel spojených so stredovekom.

Nasledujúce objavy urobil už začiatkom 17. storočia matematik Fermat. Dokázal domnienku Alberta Girarda, že každé prvočíslo v tvare 4n+1 možno zapísať jednoznačne ako súčet dvoch štvorcov, a tiež sformuloval vetu, že každé číslo možno znázorniť ako súčet štyroch štvorcov.

Vyvinul novú faktorizačnú metódu pre veľké čísla a demonštroval ju na čísle 2027651281 = 44021 × 46061. Dokázal aj Fermatovu Malú vetu: ak p je prvočíslo, potom pre akékoľvek celé číslo a platí a p = modulo p .

Toto tvrdenie dokazuje polovicu toho, čo bolo známe ako „čínska hypotéza“ a pochádza z obdobia pred 2000 rokmi: celé číslo n je prvočíslo práve vtedy, ak je 2n-2 deliteľné číslom n. Druhá časť hypotézy sa ukázala ako nepravdivá – napríklad 2341 – 2 je deliteľné 341, hoci číslo 341 je zložené: 341 = 31 × 11.

Fermatova malá veta bola základom mnohých ďalších výsledkov v teórii čísel a metód testovania, či sú čísla prvočísla, z ktorých mnohé sa dodnes používajú.

Fermat si intenzívne dopisoval so svojimi súčasníkmi, najmä s mníchom menom Marin Mersenne. V jednom zo svojich listov sa domnieval, že čísla v tvare 2 n + 1 budú vždy prvočísla, ak n je mocninou dvoch. Testoval to pre n = 1, 2, 4, 8 a 16 a bol si istý, že keď n nie je mocninou dvoch, číslo nemusí byť nevyhnutne prvočíslo. Tieto čísla sa nazývajú Fermatove čísla a až o 100 rokov neskôr Euler ukázal, že ďalšie číslo, 232 + 1 = 4294967297, je deliteľné 641, a teda nie je prvočíslo.

Čísla v tvare 2 n - 1 boli tiež predmetom výskumu, pretože je ľahké ukázať, že ak je n zložené, potom je zložené aj samotné číslo. Tieto čísla sa nazývajú Mersennove čísla, pretože ich aktívne študoval.

Ale nie všetky čísla v tvare 2 n - 1, kde n je prvočíslo, sú prvočísla. Napríklad 2 11 - 1 = 2047 = 23 * 89. Prvýkrát to bolo objavené v roku 1536.

Po mnoho rokov dávali čísla tohto druhu matematikom najväčšie známe prvočísla. Že číslo M 19 dokázal Cataldi v roku 1588 a 200 rokov bolo najväčším známym prvočíslom, kým Euler nedokázal, že prvočíslo je aj M 31. Tento rekord sa držal ďalších sto rokov a potom Lucas ukázal, že M 127 je prvočíslo (a toto je už číslo 39 číslic), a potom výskum pokračoval s príchodom počítačov.

V roku 1952 bola dokázaná prvočísla čísel M 521 , M 607 , M 1279 , M 2203 a M 2281.

Do roku 2005 sa našlo 42 Mersennových prvočísel. Najväčší z nich, M 25964951 , pozostáva zo 7816230 číslic.

Eulerova práca mala obrovský vplyv na teóriu čísel, vrátane prvočísel. Rozšíril Fermatovu Malú vetu a zaviedol φ-funkciu. Faktorizoval 5. Fermatovo číslo 2 32 +1, našiel 60 párov priateľských čísel a sformuloval (ale nedokázal to) kvadratický zákon reciprocity.

Ako prvý predstavil metódy matematickej analýzy a vyvinul analytickú teóriu čísel. Dokázal, že nielen harmonický rad ∑ (1/n), ale aj rad tvaru

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

Získané súčtom veličín inverzných k prvočíslam, tiež diverguje. Súčet n členov harmonického radu rastie približne ako log(n), zatiaľ čo druhý rad diverguje pomalšie, ako log[ log(n) ]. To znamená, že napríklad súčet prevrátených hodnôt všetkých doteraz nájdených prvočísel dá iba 4, hoci séria sa stále rozchádza.

Na prvý pohľad sa zdá, že prvočísla sú medzi celé čísla rozdelené skôr náhodne. Napríklad medzi 100 číslami bezprostredne pred 10000000 je 9 prvočísiel a medzi 100 číslami bezprostredne za touto hodnotou sú len 2. Ale na veľkých segmentoch sú prvočísla rozdelené pomerne rovnomerne. Legendre a Gauss sa zaoberali ich distribúciou. Gauss raz povedal priateľovi, že za každých voľných 15 minút vždy spočíta počet prvočísel v nasledujúcich 1000 číslach. Do konca života narátal všetky prvočísla do 3 miliónov. Legendre a Gauss rovnako vypočítali, že pre veľké n je hustota prvočísel 1/log(n). Legendre odhadol počet prvočísel medzi 1 a n as

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

A Gauss - ako logaritmický integrál

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

S integračným intervalom od 2 do n.

Výrok o hustote prvočísel 1/log(n) je známy ako teorém o prvočíslach. Snažili sa to dokázať počas celého 19. storočia a Čebyšev a Riemann dosiahli pokrok. Spojili to s Riemannovou hypotézou, doteraz nepreukázanou domnienkou o rozdelení núl Riemannovej zeta funkcie. Hustotu prvočísel súčasne dokázali Hadamard a de la Vallée-Poussin v roku 1896.

V teórii prvočísel je stále veľa nevyriešených otázok, z ktorých niektoré sú staré mnoho stoviek rokov:

• hypotéza dvojčiat - o nekonečnom počte dvojíc prvočísel, ktoré sa navzájom líšia o 2
• Goldbachova domnienka: každé párne číslo, začínajúce od 4, môže byť vyjadrené ako súčet dvoch prvočísel
• Existuje nekonečný počet prvočísel v tvare n 2 + 1 ?
• je vždy možné nájsť prvočíslo medzi n 2 a (n + 1) 2 ? (to, že medzi n a 2n je vždy prvočíslo, dokázal Čebyšev)
• Existuje nekonečný počet Fermatových prvočísiel? existujú nejaké Fermatove prvočísla po 4.?
• existuje aritmetický postup po sebe idúcich prvočísiel pre danú dĺžku? napríklad pre dĺžku 4: 251, 257, 263, 269. Maximálna zistená dĺžka je 26 .
• Existuje nekonečný počet množín troch po sebe idúcich prvočísiel v aritmetickej postupnosti?
• n 2 - n + 41 je prvočíslo pre 0 ≤ n ≤ 40. Existuje nekonečný počet takýchto prvočísel? Rovnaká otázka pre vzorec n 2 - 79 n + 1601. Tieto čísla sú prvočísla pre 0 ≤ n ≤ 79.
• Existuje nekonečný počet prvočísel v tvare n# + 1? (n# je výsledkom vynásobenia všetkých prvočísel menších ako n)
• Existuje nekonečný počet prvočísel v tvare n# -1 ?
• Existuje nekonečný počet prvočísel v tvare n! +1?
• Existuje nekonečný počet prvočísel v tvare n! - jeden?
• ak p je prvočíslo, nezahŕňa 2 p -1 vždy medzi faktory druhých mocnín
• Obsahuje Fibonacciho postupnosť nekonečný počet prvočísiel?

Najväčšie dvojčísla sú 2003663613 × 2 195000 ± 1. Pozostávajú z 58711 číslic a boli nájdené v roku 2007.

Najväčšie faktoriál prvočíslo (v tvare n! ± 1) je 147855! - 1. Skladá sa z 142891 číslic a bol nájdený v roku 2002.

Najväčšie prvočíslo (číslo v tvare n# ± 1) je 1098133# + 1.

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 celými číslami okrem 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 latinského slova „modulo“, teda „modul“) znamená „vydeliť 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ď. 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 to sú dva úplne odlišné pojmy. 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 jeden z týchto deliteľov dané číslo a druhý 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. Čiž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 všetky nepárne čísla, okrem jednotky a deviatky, patria k jednoduchým jednociferným číslam a iba „dvojke“ k párnym. 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ých metód využívajú aj analytické a geometrické metódy. 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 možno 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 nazvať „stavebným materiálom“, „blokmi“ na vytváranie 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, Eratosthenove 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“ starogré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 existuje aj modernejší vzorec, ktorý dal švajčiarsky matematik z 18. 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 primality. 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 udeľovaná tým vedcom, ktorí ich nájdu medzi 1 a 10 miliónmi desatinných čísel, dnes toto číslo dosahuje 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. Rizeľ.

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

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