Veta.

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

Dôkaz.

Predpokladajme, že nie. To znamená, že predpokladajme, že existuje iba n prvočísel a tieto prvočísla sú p 1 , p 2 , …, p n . Ukážme, že vždy môžeme nájsť prvočíslo odlišné od uvedených.

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 číslo 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, ktoré sa rovná súčtu p 1 ·p 2 ·...·p n +1. To znamená, že druhý člen tohto súčtu, ktorý sa rovná jednej, musí byť deliteľný p n+1, čo je nemožné.

Je teda dokázané, že vždy sa dá nájsť nové prvočíslo, ktoré nie je obsiahnuté v žiadnom z vopred zadaných prvočísel. Preto je prvočísel nekonečne veľa.

Takže vzhľadom na to, že prvočísel je nekonečne veľa, pri zostavovaní tabuliek prvočísel sa vždy zhora obmedzia na nejaké číslo, zvyčajne 100, 1 000, 10 000 atď.

Eratosthenove sito

Teraz si rozoberieme spôsoby zostavovania tabuliek prvočísel. Predpokladajme, ž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 kontrolované číslo (z vlastností deliteľnosti vedieť, že absolútna hodnota deliteľa nepresahuje absolútnu hodnotu dividendy odlišnú od nuly). Ak sa takýto deliteľ nenájde, potom je kontrolované číslo 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 nasleduje prechod na ďalšie číslo, ktoré sa podobne kontroluje na prítomnosť deliteľa.

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

Začíname číslom 2. Číslo 2 nemá žiadneho kladného deliteľa okrem 1 a 2 . Preto je prvočíslo, preto ho zapíšeme do tabuľky prvočísel. Tu treba povedať, že 2 je najmenšie prvočíslo. Prejdime k číslu 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. Prejdime k číslu 4. Jeho kladné deliče iné ako 1 a 4 môžu byť 2 a 3 , skontrolujme ich. Číslo 4 je deliteľné 2, preto je 4 zložené číslo a netreba ho zadávať do tabuľky prvočísel. Všimnite si, že 4 je najmenšie zložené číslo. Prejdime k číslu 5. Skontrolujeme, či aspoň jedno z čísel 2 , 3 , 4 je jeho deliteľ. Keďže 5 nie je deliteľné ani 2, ani 3, ani 4, je prvočíslo 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 s názvom . Slovo „sito“ prítomné v názve nie je náhodné, pretože akcie tejto metódy pomáhajú takpovediac „preosiať“ cez sito Eratosthenove celé čísla, veľké jednotky, aby sa oddelili jednoduché od zložených.

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é zapísané číslo 2 je prvočíslo. Teraz sa od čísla 2 posúvame postupne o dve čísla doprava a tieto čísla škrtáme, kým sa nedostaneme na koniec zostavenej tabuľky čísel. Takže všetky čísla, ktoré sú násobkom dvoch, budú prečiarknuté.

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

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 aj predtým prečiarknuté čísla) a prečiarkneme ich. Takže všetky čísla, ktoré sú násobkom piatich, budú prečiarknuté.

Ďalej prečiarkneme čísla, ktoré sú násobkami 7, potom násobkami 11 atď. Proces končí, keď nezostanú žiadne čísla na prečiarknutie. Nižšie je vyplnená 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ý nejednotný deliteľ zloženého čísla a nepresahuje , kde je z a .

Dôkaz.

Písmenom b označujeme najmenšieho deliteľa zloženého čísla a, ktoré sa líši od jednotky (číslo b je prvočíslo, čo vyplýva z vety dokázanej na samom začiatku predchádzajúceho odseku). 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 (keď b>q je porušená podmienka, že b je najmenším deliteľom a), pretože q je tiež deliteľom a kvôli rovnosti a=q b ). Vynásobením oboch strán nerovnosti kladným a väčším ako jedno celé číslo b (môžeme to urobiť), dostaneme , odkiaľ a .

Čo nám dáva dokázaná veta ohľadom Eratosthenovho sita?

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

Po druhé, zostavenie tabuľky prvočísel až po číslo n pomocou Eratosthenovho sita možno považovať za úplné, keď sa prečiarknu všetky zložené čísla, ktoré sú násobkami prvočísel, ktoré nepresahujú. V našom príklade n=50 (pretože tabulkujeme prvočísla do 50) a , takže Eratosthenovo sito musí odstrániť všetky zložené násobky prvočísel 2, 3, 5 a 7, ktoré nepresahujú aritmetickú druhú odmocninu 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. Obr.

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ä pri číslach, 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ť. My sa však pokúsime nasmerovať myšlienkový pochod pre jednoduché prípady.

Nepochybne sa môžeme pokúsiť použiť kritériá deliteľnosti, aby sme dokázali, že dané číslo je zložené. Ak napríklad nejaké kritérium 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 rovnajúce sa 9 17 je deliteľné 9, potom podľa kritéria 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 kritériá deliteľnosti nám neumožňujú dokázať jednoduchosť čísla. Preto pri kontrole čísla, či je prvočíslo alebo zložené, musíte postupovať inak.

Najlogickejším prístupom je vymenovať všetkých možných deliteľov daného čísla. Ak žiadny z možných deliteľov nie je skutočným deliteľom daného čísla, potom je toto číslo prvočíslo, inak je zložené. Z teorém dokázaných v predchádzajúcom odseku vyplýva, že deliče daného čísla a treba hľadať medzi prvočíslami nepresahujúcimi . Dané číslo a teda môžeme 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 číslo a je zložené. Ak medzi prvočíslami nepresahujúcimi , 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. Na tento účel odhadujeme.

Je celkom zrejmé, že , od 200 2 \u003d 40 000 a 11 723<40 000 (при необходимости смотрите статью porovnanie čísel). Možných hlavných deliteľov 11 723 je teda menej ako 200. To už značne zjednodušuje našu úlohu. Ak by sme to nevedeli, museli by sme zoradiť všetky prvočísla nie do 200, ale do čísla 11 723 .

Ak chcete, môžete odhadnúť presnejšie. Od 108 2 \u003d 11 664 a 109 2 \u003d 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 na prvočísla 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 5 1 , 53 , 6 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, že 11 723

Definícia 1. prvočíslo je prirodzené číslo väčšie ako 1, ktoré je deliteľné iba sebou samým 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.

Z definícií 1 a 2 vyplýva, ž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é iba 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. Nechaj 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 1. Potom k môže byť reprezentovaný ako

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

Pretože 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 1. 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 preto sú tieto dve expanzie 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 pretože 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. Tak sa dostávame 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činiteľ čísla n vyskytuje aspoň rovnaký počet krát m, To m deleno n.

Vyhlásenie 3. Nechaj a 1 ,a 2 ,a 3 ,... rôzne prvočísla objavujúce sa v m Takže

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

prvočíslo je prirodzené (kladné celé číslo) číslo, ktoré je bezo zvyšku deliteľné iba dvoma prirodzenými číslami: sebou samým a samo sebou. Inými slovami, prvočíslo má práve dvoch prirodzených deliteľov: a samotné číslo.

Podľa definície je množina všetkých deliteľov prvočísla dvojprvková, t.j. je súprava.

Množina všetkých prvočísel je označená symbolom . Na základe definície množiny prvočísel teda môžeme písať: .

Postupnosť prvočísel vyzerá takto:

Základná veta aritmetiky

Základná veta aritmetiky tvrdí, že každé prirodzené číslo väčšie ako jedna môže byť reprezentované ako súčin prvočísel, a to jedinečným spôsobom, až do poradia faktorov. Prvočísla sú teda základnými „stavebnými kameňmi“ množiny prirodzených čísel.

Rozklad prirodzeného čísla title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} kanonický:

kde je prvočíslo a . Napríklad kanonický rozvoj prirodzeného čísla vyzerá takto: .

Reprezentácia prirodzeného čísla ako súčinu prvočísel sa tiež nazýva rozklad čísel.

Vlastnosti prvočísel

Eratosthenove sito

Jedným z najznámejších algoritmov na vyhľadávanie a rozpoznávanie prvočísel je sito Eratosthenes. Tento algoritmus bol teda pomenovaný po gréckom matematikovi Eratosthenesovi z Kyrény, ktorý je považovaný za autora algoritmu.

Ak chcete nájsť všetky prvočísla menšie ako dané číslo, podľa metódy Eratosthenes musíte postupovať podľa týchto krokov:

Krok 1. Vypíšte za sebou všetky prirodzené čísla od dvoch do , t.j. .
Krok 2 Priraďte premennej hodnotu, teda hodnotu rovnajúcu sa najmenšiemu prvočíslu.
Krok 3 Vymažte zo zoznamu všetky čísla od do násobkov , teda čísla: .
Krok 4 Nájdite prvé nezačiarknuté číslo v zozname väčšie ako a priraďte hodnotu tohto čísla do premennej.
Krok 5 Opakujte kroky 3 a 4, kým nedosiahnete požadované číslo.

Proces aplikácie algoritmu bude vyzerať takto:

Všetky zostávajúce nezačiarknuté čísla v zozname na konci procesu aplikácie algoritmu budú množinou prvočísel od do .

Goldbachova hypotéza

Obal knihy „Strýko Petros a Goldbachova domnienka“

Napriek tomu, že prvočísla matematici skúmali už dlho, dnes mnohé súvisiace problémy zostávajú nevyriešené. Jedným z najznámejších nevyriešených problémov je Goldbachova domnienka, ktorý je formulovaný takto:

• Je pravda, že každé párne číslo väčšie ako dva možno znázorniť ako súčet dvoch prvočísel (Goldbachova binárna domnienka)?
• Je pravda, že každé nepárne číslo väčšie ako 5 môže byť vyjadrené ako súčet troch prvočísel (Goldbachova ternárna domnienka)?

Treba povedať, že ternárna Goldbachova domnienka je špeciálnym prípadom binárnej Goldbachovej domnienky, alebo, ako hovoria matematici, ternárna Goldbachova domnienka je slabšia ako binárna Goldbachova domnienka.

Goldbachova domnienka sa stala široko známou mimo matematickej komunity v roku 2000 vďaka reklamnému marketingovému kúsku vydavateľstiev Bloomsbury USA (USA) a Faber and Faber (UK). Tieto vydavateľstvá, ktoré vydali knihu „Uncle Petros and Goldbach’s Conjecture“, sľúbili zaplatiť cenu 1 milión amerických dolárov do 2 rokov od dátumu vydania knihy tomu, kto dokáže Goldbachovu domnienku. Niekedy sa spomínaná cena od vydavateľov zamieňa s cenami za riešenie problémov s cenou tisícročia. Nenechajte sa pomýliť, Goldbachova hypotéza nie je Clayovým inštitútom uvedená ako výzva tisícročia, hoci úzko súvisí s Riemannova hypotéza jedna z výziev tisícročia.

Kniha „Jednoduché čísla. Dlhá cesta do nekonečna

Obal knihy „Svet matematiky. Jednoduché čísla. Dlhá cesta do nekonečna

Okrem toho odporúčam prečítať si fascinujúcu populárno-náučnú knihu, ktorej anotácia hovorí: „Hľadanie prvočísel je jedným z najparadoxnejších problémov v matematike. Vedci sa to pokúšajú vyriešiť už niekoľko tisícročí, no po získaní nových verzií a hypotéz zostáva táto záhada stále nevyriešená. Vzhľad prvočísel nepodlieha žiadnemu systému: vznikajú spontánne v sérii prirodzených čísel, ignorujúc všetky pokusy matematikov identifikovať vzory v ich postupnosti. Táto kniha umožní čitateľovi sledovať vývoj vedeckých myšlienok od staroveku až po súčasnosť a predstaví najkurióznejšie teórie hľadania prvočísel.

Okrem toho odcitujem začiatok druhej kapitoly tejto knihy: „Prvočísla sú jednou z dôležitých tém, ktoré nás vracajú k úplným počiatkom matematiky, a potom nás na ceste zvyšujúcej sa zložitosti vedú k škrtaniu okraj modernej vedy. Preto by bolo veľmi užitočné sledovať fascinujúcu a zložitú históriu teórie prvočísel: ako presne sa vyvinula, ako presne boli zhromaždené fakty a pravdy, ktoré sa dnes považujú za všeobecne akceptované. V tejto kapitole uvidíme, ako generácie matematikov starostlivo študovali prirodzené čísla pri hľadaní pravidla, ktoré predpovedá výskyt prvočísel, pravidla, ktoré sa v priebehu hľadania stávalo stále viac nepolapiteľné. Pozorne sa pozrieme aj na historický kontext: v akých podmienkach matematici pracovali a do akej miery sa ich práca týkala mystických a polonáboženských praktík, ktoré sa vôbec nepodobajú vedeckým metódam používaným v našej dobe. Napriek tomu sa pomaly a ťažko pripravovala pôda pre nové názory, ktoré inšpirovali Fermata a Eulera v 17. a 18. storočí.“

• 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 správnych 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 aj 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 histórii 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 zapísať 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 na testovanie, č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 nasledujúce čí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 líši.

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é stovky rokov:

• hypotéza dvojčiat - o nekonečnom počte dvojíc prvočísel, ktoré sa od seba líšia o 2
• Goldbachova domnienka: každé párne číslo, začínajúce od 4, môže byť reprezentované 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 akúkoľvek 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 nasledujú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 tvaru n! +1?
• Existuje nekonečný počet prvočísel tvaru n! - 1?
• 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 prvotné prvočíslo (číslo v tvare n# ± 1) je 1098133# + 1.

Štítky: Pridajte štítky