Č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 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ý, 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é 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 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. Poďme sa pozrieť na tabuľky nižšie. 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ý odmocnina daného čísla.

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ť tvaru 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 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 Eratosthenove sito preosieva všetky zložené čísla, ktorých hodnota nie je väčšia ako hodnota odmocniny 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 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.

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 меньше числа 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 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á aj deliteľa 19 .

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

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

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á "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.

Prečítajte si o úskaliach Fermatovej Malej vety. Všetky čísla, pre ktoré nie sú splnené podmienky testu, sú zložené, ale zostávajúce čísla sú len pravdepodobne sa považujú za jednoduché. Ak sa chcete vyhnúť nesprávnym výsledkom, hľadajte n v zozname „Carmichaelových čísel“ (zložené čísla, ktoré vyhovujú tomuto testu) a „pseudoprvočísla Fermat“ (tieto čísla spĺňajú podmienky testu len pre niektoré hodnoty a).

Ak je to vhodné, použite Miller-Rabinov test. Hoci je táto metóda dosť ťažkopádna na manuálne výpočty, často sa používa v počítačových programoch. Poskytuje prijateľnú rýchlosť a poskytuje menej chýb ako Fermatova metóda. Zložené číslo sa nebude považovať za prvočíslo, ak sa výpočty robia pre viac ako ¼ hodnôt a. Ak náhodne vyberiete rôzne hodnoty a a u všetkých z nich test poskytne pozitívny výsledok, môžeme s pomerne vysokou mierou istoty predpokladať, že n je prvočíslo.

Pre veľké čísla použite modulárnu aritmetiku. Ak nemáte po ruke modovú kalkulačku alebo ak vaša kalkulačka nie je navrhnutá tak, aby zvládla také veľké čísla, použite vlastnosti napájania a modulárnu aritmetiku na uľahčenie výpočtov. Nižšie je uvedený príklad pre 3 50 (\displaystyle 3^(50)) mod 50:

• Prepíšte výraz do vhodnejšej podoby: mod 50. Pri manuálnom výpočte môžu byť potrebné ďalšie zjednodušenia.
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Tu sme brali do úvahy vlastnosť modulárneho násobenia.
• 3 25 (\displaystyle 3^(25)) mod 50 = 43.
• (3 25 (\displaystyle (3^(25)) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
• = 1849 (\displaystyle =1849) mod 50.
• = 49 (\displaystyle=49).

• 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 je p prvočíslo, potom a p = modulo p bude platiť pre akékoľvek celé číslo a.

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 používajú dodnes.

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 dvojky, čí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 aj M 31 je prvočíslo. 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é celkom 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é stovky 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.

• 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 je p prvočíslo, potom a p = modulo p bude platiť pre akékoľvek celé číslo a.

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 používajú dodnes.

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 dvojky, čí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 aj M 31 je prvočíslo. 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é celkom 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é stovky 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.

Štítky: Pridajte štítky

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. Toto je však jediný spôsob, ako reprezentovať prirodzené čísla až do poradia 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. Na tento účel boli vyvinuté špeciálne testy, takzvané testy jednoduchosti. 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.

Hlavným rozlišovacím znakom Mersennových čísel je prítomnosť 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, je 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 troch prvočísel.
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ď.