Prvočíslo - Prime number

Skupiny dvou až dvanácti teček, které ukazují, že složená čísla teček (4, 6, 8, 9, 10 a 12) lze uspořádat do obdélníků, ale prvočísla nemohou
Složená čísla mohou být uspořádána do obdélníků, ale prvočísla nikoli

Prvočíslo (nebo hlavní ) je přirozené číslo větší než 1, který není produktem ze dvou menších přirozených čísel. Přirozené číslo větší než 1, které není prvočíslo, se nazývá složené číslo . Například 5 je prvočíslo, protože jediný způsob, jak jej zapsat jako součin, 1 × 5 nebo 5 × 1 , zahrnuje samotnou 5. 4 je však složené, protože jde o součin ( 2 × 2 ), ve kterém jsou obě čísla menší než 4. Prvočísla jsou ústřední v teorii čísel kvůli základní větě aritmetiky : každé přirozené číslo větší než 1 je buď prvočíslo samo o sobě, nebo lze faktorizovatjako produkt prvočísel, který je jedinečný až do jejich objednávky.

Vlastnost bytí prvočísla se nazývá primálnost . Jednoduchá, ale pomalá metoda kontroly primality daného čísla , nazývaná zkušební dělení , testuje, zda je násobkem libovolného celého čísla mezi 2 a . Mezi rychlejší algoritmy patří Millerův–Rabinův test primality , který je rychlý, ale má malou šanci na chybu, a test primality AKS , který vždy vytvoří správnou odpověď v polynomiálním čase, ale je příliš pomalý na to, aby byl praktický. Obzvláště rychlé metody jsou dostupné pro čísla speciálních formulářů, jako jsou Mersennova čísla . Od prosince 2018 je největším známým prvočíslem Mersennovo prvočíslo s 24 862 048 desetinnými číslicemi .

Prvočísel je nekonečně mnoho , jak prokázal Euclid kolem roku 300 před Kristem. Žádný známý jednoduchý vzorec neodděluje prvočísla od složených čísel. Rozložení prvočísel v přirozených číslech ve velkém však lze statisticky modelovat. Prvním výsledkem v tomto směru je teorém o prvočísle , dokázaný na konci 19. století, který říká, že pravděpodobnost, že náhodně vybrané velké číslo bude prvočíslo, je nepřímo úměrné jeho počtu číslic, tedy jeho logaritmu .

Několik historických otázek týkajících se prvočísel je stále nevyřešeno. Patří mezi ně Goldbachova domněnka , že každé sudé celé číslo větší než 2 může být vyjádřeno jako součet dvou prvočísel, a dvojčí domněnka prvočísel , že existuje nekonečně mnoho dvojic prvočísel majících mezi sebou právě jedno sudé číslo. Tyto otázky podnítily vývoj různých odvětví teorie čísel se zaměřením na analytické nebo algebraické aspekty čísel. Prvočísla se používají v několika rutinách v informačních technologiích , jako je kryptografie veřejného klíče , která se spoléhá na obtížnost faktoringu velkých čísel do jejich primárních faktorů. V abstraktní algebře zahrnují objekty, které se chovají zobecněným způsobem jako prvočísla, prvočísla a prvočísla .

Definice a příklady

Přirozené číslo (1, 2, 3, 4, 5, 6, atd.), Se nazývá prvočíslo (nebo prvočíslo ), pokud je větší než 1 a nelze zapsat jako součin dvou menších přirozených čísel. Čísla větší než 1, která nejsou prvočísla, se nazývají složená čísla . Jinými slovy, je prvočíslo, pokud položky nelze rozdělit do menších skupin stejné velikosti s více než jednou položkou nebo pokud není možné uspořádat tečky do obdélníkové mřížky, která je široká více než jeden bod a vysoká více než jeden bod. . Například mezi čísly 1 až 6 jsou čísla 2, 3 a 5 prvočísla, protože neexistují žádná jiná čísla, která by je dělila rovnoměrně (beze zbytku). 1 není prvočíslo, protože je v definici výslovně vyloučeno. 4 = 2 × 2 a 6 = 2 × 3 jsou oba složené.

Ukázka s Cuisenairovými pruty, že 7 je prvočíslo, protože žádný z 2, 3, 4, 5 nebo 6 ho nerozděluje rovnoměrně
Ukázka s Cuisenaire tyčemi , že 7 je prvočíslo, protože žádný z 2, 3, 4, 5 nebo 6 ho nerozděluje rovnoměrně

K dělitele přirozeného čísla jsou přirozená čísla, které rozdělují rovnoměrně. Každé přirozené číslo má 1 i sebe jako dělitele. Pokud má jiného dělitele, nemůže být prvočíslo. Tato myšlenka vede k jiné, ale ekvivalentní definici prvočísel: jsou to čísla s přesně dvěma kladnými děliteli , 1 a samotné číslo. Ještě další způsob, jak vyjádřit totéž, je, že číslo je prvočíslo, pokud je větší než jedna a pokud žádné z čísel nedělí rovnoměrně.

Prvních 25 prvočísel (všechna prvočísla menší než 100) jsou:

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 ( sekvence A000040 v OEIS ).

Žádné sudé číslo větší než 2 není prvočíslo, protože každé takové číslo lze vyjádřit jako součin . Proto každé prvočíslo jiné než 2 je liché číslo a nazývá se liché prvočíslo . Podobně, když jsou zapsána v obvyklé desítkové soustavě, všechna prvočísla větší než 5 končí 1, 3, 7 nebo 9. Čísla končící jinými číslicemi jsou všechna složená: desetinná čísla, která končí 0, 2, 4, 6 , nebo 8 jsou sudá a desetinná čísla končící 0 nebo 5 jsou dělitelná 5.

Množina všech prvočísel je někdy označován (s tučným kapitálu P ) nebo (v tabuli tučný velkým P).

Dějiny

Rhind matematický papyrus , z doby kolem roku 1550 před naším letopočtem, má egyptské frakce expanze různých forem pro prime a složených čísel. Nejčasnější dochované záznamy o explicitním studiu prvočísel však pocházejí ze starověké řecké matematiky . Euclid 's Elements (c. 300 př.nl) dokazuje nekonečnost prvočísel a základní větu aritmetiky a ukazuje, jak sestavit dokonalé číslo z Mersennova prvočísla . Další řecký vynález, Eratosthenovo síto , se stále používá ke konstrukci seznamů prvočísel.

Kolem roku 1000 našeho letopočtu našel islámský matematik Ibn al-Haytham (Alhazen) Wilsonovu větu , charakterizující prvočísla jako čísla, která se rovnoměrně dělí . Také se domníval, že všechna sudá dokonalá čísla pocházejí z Euklidovy konstrukce pomocí Mersennova prvočísel, ale nebyl schopen to dokázat. Další islámský matematik, Ibn al-Banna' al-Marrakushi , pozoroval, že Eratosthenovo síto lze urychlit testováním pouze dělitelů až do druhé odmocniny největšího testovaného čísla. Fibonacci přinesl inovace z islámské matematiky zpět do Evropy. Jeho kniha Liber Abaci (1202) byla první, která popsala zkušební dělení pro testování primality, opět s použitím dělitelů pouze do druhé odmocniny.

V roce 1640 Pierre de Fermat vyslovil (bez důkazu) Fermatovu malou větu (později doloženou Leibnizem a Eulerem ). Fermat také vyšetřoval Primality z čísel Fermatových a Marin Mersenne studoval prvočísla Mersenne , prvočísel formuláře se sama připravit. Christian Goldbach formuloval Goldbachovu domněnku , že každé sudé číslo je součtem dvou prvočísel, v dopise Eulerovi z roku 1742. Euler dokázal Alhazenovu domněnku (nyní Euklidova-Eulerova věta ), že všechna sudá dokonalá čísla lze sestavit z Mersennových prvočísel. Do této oblasti zavedl metody z matematické analýzy ve svých důkazech nekonečnosti prvočísel a divergence součtu reciprokých prvočísel . Na začátku 19. století, Legendre a Gauss se domníval, že jako tendenci růst do nekonečna, je počet prvočísel až je asymptotic k , kde je přirozený logaritmus z . Slabším důsledkem této vysoké hustoty prvočísel byl Bertrandův postulát , že pro každé existuje prvočíslo mezi a , prokázal roku 1852 Pafnuty Čebyšev . Nápady Bernharda Riemanna ve svém článku z roku 1859 o funkci zeta načrtly obrys pro prokázání Legendreovy a Gaussovy domněnky. Ačkoli blízce příbuzná Riemannova hypotéza zůstává neprokázaná, Riemannův obrys byl dokončen v roce 1896 Hadamardem a de la Vallée Poussinem a výsledek je nyní známý jako teorém o prvočísle . Dalším důležitým výsledkem 19. století byl Dirichletův teorém o aritmetických posloupnostech , že jisté aritmetické posloupnosti obsahují nekonečně mnoho prvočísel.

Mnoho matematiků pracovalo na testech prvočíselnosti pro čísla větší než ta, kde je prakticky použitelné dělení na zkoušku. Mezi metody, které se omezují na konkrétní číselné formy, patří Pépinův test pro Fermatova čísla (1877), Prothův teorém (kolem roku 1878), Lucas-Lehmerův test primálnosti (vzniklý v roce 1856) a zobecněný Lucasův test primálnosti .

Od roku 1951 byla pomocí těchto testů na počítačích nalezena všechna největší známá prvočísla . Hledání stále větších prvočísel vyvolalo zájem mimo matematické kruhy prostřednictvím Great Internet Mersenne Prime Search a dalších distribuovaných počítačových projektů. Myšlenka, že prvočísla mají jen málo aplikací mimo čistou matematiku, byla zničena v 70. letech, kdy byla vynalezena kryptografie s veřejným klíčem a kryptosystém RSA , využívající prvočísla jako základ.

Zvýšený praktický význam počítačového testování primality a faktorizace vedl k vývoji vylepšených metod schopných zvládnout velké množství neomezené formy. Matematická teorie prvočísel se také posunula vpřed s Green-Tao teorémem (2004), že existují libovolně dlouhé aritmetické posloupnosti prvočísel, a důkazem Yitang Zhanga z roku 2013, že existuje nekonečně mnoho prvočísel o omezené velikosti.

Prvořadost jednoho

Většina raných Řeků ani nepovažovala 1 za číslo, takže nemohli považovat její prvořadost. Několik matematiků z této doby také považovalo prvočísla za poddělení lichých čísel, takže také nepovažovali 2 za prvočíslo. Euklides a většina dalších řeckých matematiků však považovali 2 za prvočíslo. Tyto středověké islámské matematici z velké části následovala Řeky v prohlížení 1, že není mnoho. Ve středověku a renesanci začali matematici považovat 1 za číslo a někteří z nich ji zahrnuli jako první prvočíslo. V polovině 18. století Christian Goldbach uvedl 1 jako prvotřídní ve své korespondenci s Leonhardem Eulerem ; Euler sám však 1 nepovažoval za prvočíslo. V 19. století mnoho matematiků stále považovalo 1 za prvočíslo a seznamy prvočísel, které obsahovaly 1, byly publikovány až v roce 1956.

Pokud by se definice prvočísla změnila na označení 1 prvočíslem, mnoho výroků obsahujících prvočísla by muselo být přeformulováno trapnějším způsobem. Například základní věta aritmetiky by musela být přeformulována z hlediska rozkladů na prvočísla větší než 1, protože každé číslo by mělo více rozkladů s různým počtem kopií 1. Podobně by Eratosthenovo síto nefungovalo správně, pokud by zacházelo s 1 jako s prvočíslem, protože by to odstranilo všechny násobky 1 (tedy všechna ostatní čísla) a vypsalo by pouze jediné číslo 1. Některé další techničtější vlastnosti prvočísel také pro číslo 1 neplatí: např. vzorce pro Eulerovu totientovou funkci nebo pro součet dělitelů jsou pro prvočísla jiné než pro 1. Na počátku 20. století se matematici začali shodovat, že 1 by neměla být uváděna jako prvočíslo, ale spíše ve své vlastní speciální kategorii jako " jednotka ".

Elementární vlastnosti

Unikátní faktorizace

Zápis čísla jako součinu prvočísel se nazývá prvočíselný rozklad čísla. Například:

Termíny v produktu se nazývají primární faktory . Stejný prvočinitel se může vyskytnout více než jednou; Tento příklad má dvě kopie nultý faktoru Dojde-li k hlavní vícekrát, umocňování lze seskupit více kopií stejné prvočíslo: například, ve druhém způsobu psaní produkt výše, označuje čtverec nebo druhého výkonu z

Ústřední důležitost prvočísel pro teorii čísel a matematiku obecně pramení ze základní věty aritmetiky . Tato věta říká, že každé celé číslo větší než 1 lze zapsat jako součin jednoho nebo více prvočísel. Ještě silněji je tento produkt jedinečný v tom smyslu, že jakékoli dvě prvočíselné rozklady stejného čísla budou mít stejný počet kopií stejných prvočísel, i když se jejich uspořádání může lišit. Přestože tedy existuje mnoho různých způsobů, jak najít faktorizaci pomocí celočíselného faktorizačního algoritmu, všechny musí přinést stejný výsledek. Prvočísla tak lze považovat za „základní stavební kameny“ přirozených čísel.

Některé důkazy jedinečnosti prvočíselných rozkladů jsou založeny na Euklidově lematu : If je prvočíslo a dělí součin celých čísel a poté dělí nebo dělí (nebo obojí). Naopak, má-li číslo tu vlastnost, že při dělení součinu vždy dělí alespoň jeden faktor součinu, pak musí být prvočíslo.

Nekonečnost

Prvočísel je nekonečně mnoho. Jiný způsob, jak to říci, je posloupnost

2, 3, 5, 7, 11, 13, ...

prvočísel nikdy nekončí. Toto tvrzení je označováno jako Euklidova věta na počest starověkého řeckého matematika Euklida , protože první známý důkaz tohoto tvrzení je připisován jemu. Je známo mnohem více důkazů nekonečnosti prvočísel, včetně analytického důkazu Eulera , Goldbachova důkazu založeného na Fermatových číslech , Furstenbergova důkazu pomocí obecné topologie a Kummerova elegantního důkazu.

Euklidův důkaz ukazuje, že každý konečný seznam prvočísel je neúplný. Klíčovou myšlenkou je vynásobit dohromady prvočísla v jakémkoli daném seznamu a přidat. Pokud se seznam skládá z prvočísel, dostaneme číslo

Podle základní věty má prvočíselný rozklad

s jedním nebo více primárními faktory. je rovnoměrně dělitelné každým z těchto faktorů, ale má zbytek jedna, když je děleno kterýmkoli z prvočísel v daném seznamu, takže žádný z prvočísel nemůže být v daném seznamu. Protože neexistuje konečný seznam všech prvočísel, prvočísel musí být nekonečně mnoho.

Čísla vzniklá přičtením jedničky k součinům nejmenších prvočísel se nazývají euklidovská čísla . Prvních pět z nich je prvotřídních, ale šestý,

je složené číslo.

Vzorce pro prvočísla

Neexistuje žádný známý účinný vzorec pro prvočísla. Například neexistuje žádný nekonstantní polynom , a to ani v několika proměnných, který nabývá pouze prvočísel. Existuje však mnoho výrazů, které kódují všechna prvočísla nebo pouze prvočísla. Jeden možný vzorec je založen na Wilsonově větě a generuje číslo 2 mnohokrát a všechny ostatní prvočísla přesně jednou. Existuje také sada diofantických rovnic v devíti proměnných a jeden parametr s následující vlastností: parametr je prvočíslo právě tehdy, když výsledná soustava rovnic má řešení nad přirozenými čísly. Toho lze použít k získání jediného vzorce s vlastností, že všechny jeho kladné hodnoty jsou prvočísla.

Další příklady vzorců generujících prvočíslo pocházejí z Millsova teorému a Wrightova teorému . Tito tvrdí, že existují skutečné konstanty a podobně

jsou prvočísla pro libovolné přirozené číslo v prvním vzorci a libovolný počet exponentů ve druhém vzorci. Zde představuje funkci podlahy , největší celé číslo menší nebo rovné příslušnému číslu. Ty však nejsou užitečné pro generování prvočísel, protože prvočísla musí být vygenerována nejprve, aby bylo možné vypočítat hodnoty nebo

Otevřené otázky

Mnoho dohadů točících se o prvočíslech bylo položeno. Mnohé z těchto domněnek, které mají často elementární formulaci, obstály po desetiletí: všechny čtyři Landauovy problémy z roku 1912 jsou stále nevyřešeny. Jedním z nich je Goldbachova domněnka , která tvrdí, že každé sudé celé číslo větší než 2 lze zapsat jako součet dvou prvočísel. Od roku 2014 je tato domněnka ověřena pro všechna čísla až Slabší tvrzení, než byla prokázána, např. Vinogradovova věta říká, že každé dostatečně velké liché celé číslo lze zapsat jako součet tří prvočísel. Chenova věta říká, že každé dostatečně velké sudé číslo lze vyjádřit jako součet prvočísel a poloprvočísel (součin dvou prvočísel). Také jakékoli sudé celé číslo větší než 10 lze zapsat jako součet šesti prvočísel. Odvětví teorie čísel studující takové otázky se nazývá aditivní teorie čísel .

Další typ problému se týká prvočísel , rozdílů mezi po sobě jdoucími prvočísly. Existence libovolně velkých prvočíselných mezer může být viděna tím, že posloupnost sestává ze složených čísel pro jakékoli přirozené číslo . Velké prvočíselné mezery se však vyskytují mnohem dříve, než ukazuje tento argument. Například, první prvočíslo délky 8 je mezi prvočísly 89 a 97, mnohem menší než Předpokládá se, že existuje nekonečně mnoho prvočísel dvojčat , párů prvočísel s rozdílem 2; toto je dvojče prvořadá domněnka . Polignacova domněnka obecněji uvádí, že pro každé kladné celé číslo existuje nekonečně mnoho dvojic po sobě jdoucích prvočísel, které se liší Andricovou domněnkou , Brocardovou domněnkou , Legendrovou domněnkou a Oppermannovou domněnkou naznačují, že největší mezery mezi prvočísly od do by měly být nanejvýš přibližně výsledkem že je známo, vyplývá z Riemann hypotéza, zatímco mnohem silnější Cramer domněnku sady největší velikost mezery v mezerách Prime je možné zobecnit na prime -tuples , vzory v rozdílech mezi více než dvěma prvočísel. Jejich nekonečnost a hustota jsou předmětem prvního Hardyho–Littlewoodova dohadu , který může být motivován heuristiky , že prvočísla se chovají podobně jako náhodná posloupnost čísel s hustotou danou teorémem o prvočíslech.

Analytické vlastnosti

Analytická teorie čísel studuje teorii čísel přes čočku spojitých funkcí , limity , nekonečné řady a příbuznou matematiku nekonečna a infinitezimální .

Tato oblast studia začala Leonhardem Eulerem a jeho prvním hlavním výsledkem, řešením basilejského problému . Problém požádal o hodnotě nekonečné částky , které lze dnes uznávána jako hodnota v Riemann zeta . Tato funkce je úzce spojena s prvočísly a jedním z nejvýznamnějších nevyřešených problémů v matematice, Riemannovou hypotézou . Euler to ukázal . Převrácená hodnota tohoto čísla, , je omezující pravděpodobnost, že dvě náhodná čísla vybraná rovnoměrně z velkého rozsahu jsou relativně prvočísla (nemají žádné společné faktory).

Distribuce prvočísel ve velkých, jako je otázka, kolik prvočísel je menších než daný, velký práh, je popsána větou o prvočíslech , ale není znám žádný účinný vzorec pro -té prvočíslo . Dirichletova věta o aritmetických posloupnostech ve své základní podobě tvrdí, že lineární polynomy

s relativně prvočísly a mají nekonečně mnoho prvočísel. Silnější formy věty říkají, že součet převrácených hodnot těchto prvočísel se liší a že různé lineární polynomy se stejným mají přibližně stejné proporce prvočísel. Ačkoli byly formulovány domněnky o poměrech prvočísel v polynomech vyšších stupňů, zůstávají neprokázané a není známo, zda existuje kvadratický polynom, který (pro celočíselné argumenty) je prvočíslo nekonečně často.

Analytický důkaz Euklidovy věty

Eulerův důkaz, že existuje nekonečně mnoho prvočísel, uvažuje součty reciprokých prvočísel,

Euler ukázal, že pro jakékoli libovolné reálné číslo existuje prvočíslo, pro které je tento součet větší než . To ukazuje, že prvočísel je nekonečně mnoho, protože pokud by prvočísel bylo konečně mnoho, součet by dosáhl své maximální hodnoty při největším prvočíslu, spíše než aby rostl kolem každého . Rychlost růstu tohoto součtu přesněji popisuje druhý Mertensův teorém . Pro srovnání suma

neroste do nekonečna, jak jde do nekonečna (viz Basilejský problém ). V tomto smyslu se prvočísla vyskytují častěji než druhé mocniny přirozených čísel, ačkoli obě množiny jsou nekonečné. Brunova věta říká, že součet reciprokých čísel dvojčísel ,

je konečný. Kvůli Brunově větě není možné použít Eulerovu metodu k vyřešení domněnky o prvočíslech dvojčat , že existuje nekonečně mnoho prvočísel dvojčat.

Počet prvočísel pod danou hranicí

Relativní chyba of a logaritmická integrální jako aproximace do funkce prime-počítání . Obě relativní chyby se s růstem snižují k nule , ale konvergence k nule je pro logaritmický integrál mnohem rychlejší.

Funkce počítání prvočísel je definována jako počet prvočísel ne větší než . Například , protože existuje pět prvočísel menších nebo rovných 11. Metody jako Meissel-Lehmerův algoritmus mohou vypočítat přesné hodnoty rychleji, než by bylo možné uvést každé prvočíslo až do . Tyto teorém prvočísla říká, že je asymptotic k , který je označován jako

a znamená, že poměr k pravému zlomku se blíží 1, jak roste do nekonečna. To znamená, že pravděpodobnost, že náhodně vybrané číslo menší než je prvočíslo, je (přibližně) nepřímo úměrné počtu číslic v . Z toho také vyplývá, že th prvočíslo je úměrné , a proto že průměrná velikost prvočísla je úměrná . Přesnější odhad pro je dán offsetovým logaritmickým integrálem

Aritmetické průběhy

Aritmetické posloupnosti je konečný nebo nekonečný posloupnost čísel tak, že po sobě následující čísla v pořadí všechny mají stejný význam. Tento rozdíl se nazývá modul progrese. Například,

3, 12, 21, 30, 39, ...,

je nekonečná aritmetická posloupnost s modulem 9. V aritmetické posloupnosti mají všechna čísla stejný zbytek, když se dělí modulem; v tomto příkladu je zbytek 3. Protože modul 9 i zbytek 3 jsou násobky 3, tak je každý prvek v posloupnosti. Proto tento postup obsahuje pouze jedno prvočíslo, samotnou 3. Obecně platí, že nekonečný vývoj

může mít více než jedno prvočíslo pouze tehdy, když je jeho zbytek a modul relativně prvočíslo. Pokud jsou relativně prvočísla, Dirichletova věta o aritmetických posloupnostech tvrdí, že posloupnost obsahuje nekonečně mnoho prvočísel.

Prvočísla v aritmetickém postupu mod 9.
Prvočísla v aritmetické posloupnosti modulo 9. Každý řádek tenkého vodorovného pruhu ukazuje jednu z devíti možných posloupností mod 9 s prvočísly označenými červeně. Posloupnosti čísel 0, 3 nebo 6 mod 9 obsahují nejvýše jedno prvočíslo (číslo 3); zbývající posloupnosti čísel 2, 4, 5, 7 a 8 mod 9 mají nekonečně mnoho prvočísel s podobným počtem prvočísel v každé posloupnosti

V Green-Tao věta ukazuje, že jsou libovolně dlouho konečné aritmetické posloupnosti sestávající pouze z prvočísel.

Prvočísla kvadratických polynomů

Ulamská spirála
Ulam spirála . Prvočísla (červená) se shlukují na některých úhlopříčkách a na jiných ne. Primární hodnoty jsou zobrazeny modře.

Euler poznamenal, že funkce

dává prvočísla pro , ačkoli složená čísla se objevují mezi jeho pozdějšími hodnotami. Pátrání po vysvětlení pro tento jev vedl k hluboké algebraické teorie čísel z čísel Heegner a problémem číslo třídy . Hardy-Littlewood domněnka F předpovídá hustotu prvočísel mezi hodnotami kvadratických polynomů s celočíselnými koeficienty , pokud jde o logaritmické integrálu a koeficientů polynomu. Nebylo prokázáno, že by žádný kvadratický polynom nabýval nekonečně mnoha prvočísel.

Ulamova spirála zařizuje přirozených čísel v dvourozměrném rastru spirále v soustředných čtverců obklopovat původ jako prvočísel zvýrazněny. Vizuálně se zdá, že prvočísla se shlukují na určitých úhlopříčkách a na jiných ne, což naznačuje, že některé kvadratické polynomy nabývají prvočíselných hodnot častěji než jiné.

Zeta funkce a Riemannova hypotéza

Graf absolutních hodnot funkce zeta
Graf absolutních hodnot funkce zeta, ukazující některé její rysy

Jeden z nejznámějších nevyřešených otázek v matematice, z roku 1859, a jeden z problémy tisíciletí , je Riemann hypotéza , který se ptá, kde nuly z Riemann zeta funkce se nacházejí. Tato funkce je analytická funkce na komplexních číslech . Pro komplexní čísla s reálnou částí větší než jedna se rovná jak nekonečnému součtu přes všechna celá čísla, tak nekonečnému součinu nad prvočísly,

Tato rovnost mezi součtem a součinem, objevená Eulerem, se nazývá Eulerův součin . Eulerův součin lze odvodit ze základní věty aritmetiky a ukazuje úzké spojení mezi funkcí zeta a prvočísly. Vede to k dalšímu důkazu, že prvočísel je nekonečně mnoho: kdyby jich bylo jen konečně mnoho, pak by rovnost součtu-součinu platila také v , ale součet by se rozcházel (je to harmonická řada ), zatímco součin by byl konečný, rozpor.

Riemannova hypotéza říká, že nuly zeta-funkce jsou buď záporná sudá čísla, nebo komplexní čísla s reálnou částí rovnou 1/2. Původní důkaz věty o prvočísle byl založen na slabé formě této hypotézy, že neexistují žádné nuly s reálnou částí rovnou 1, i když byly nalezeny další, elementárnější důkazy. Funkce prvočísla může být vyjádřena Riemannovou explicitní rovnicí jako součet, ve kterém každý člen pochází z jedné z nul funkce zeta; hlavním členem tohoto součtu je logaritmický integrál a zbývající členy způsobí, že součet kolísá nad a pod hlavním členem. V tomto smyslu nuly řídí, jak pravidelně jsou prvočísla distribuována. Je-li Riemannova hypotéza pravdivá, budou tyto fluktuace malé a asymptotická distribuce prvočísel daná větou o prvočísle bude platit i pro mnohem kratší intervaly (o délce o odmocnině z pro intervaly blízko čísla ).

Abstraktní algebra

Modulární aritmetika a konečná pole

Modulární aritmetika modifikuje obvyklou aritmetiku pouze použitím čísel , pro přirozené číslo nazývané modul. Jakékoli jiné přirozené číslo lze do tohoto systému namapovat jeho nahrazením jeho zbytkem po dělení . Modulární součty, rozdíly a součiny se počítají provedením stejné náhrady zbytkem na výsledku obvyklého součtu, rozdílu nebo součinu celých čísel. Rovnost celých čísel odpovídá kongruenci v modulární aritmetice: a jsou kongruentní (psáno mod ), když mají stejný zbytek po dělení . V tomto systému čísel je však dělení všemi nenulovými čísly možné tehdy a pouze tehdy, když je modul prvočíslo. Například s prvočíslem jako modulem je možné dělení : , protože vymazáním jmenovatelů vynásobením obou stran číslem získáte platný vzorec . S kompozitním modulem je však dělení podle nemožné. Neexistuje žádné platné řešení pro : vymazání jmenovatelů násobením způsobí, že levá strana se stane, zatímco pravá strana se stane buď nebo . V terminologii abstraktní algebry schopnost provádět dělení znamená, že modulární aritmetický modulo prvočíslo tvoří pole nebo, přesněji, konečné pole , zatímco jiné moduly dávají pouze prsten, ale ne pole.

Pomocí modulární aritmetiky lze formulovat několik vět o prvočíslech. Například Fermatova malá věta říká, že když (mod ), pak (mod ). Když to sečteme přes všechny možnosti, dostaneme rovnici

platí vždy, když je prvočíslo. Giuga domněnka říká, že tato rovnice je také postačující podmínkou pro to, aby byla prvočíslo. Wilsonova věta říká, že celé číslo je prvočíslo právě tehdy, když je faktoriál shodný s mod . Pro složené číslo to nemůže platit, protože jeden z jeho faktorů dělí n i , a tak je nemožné.

p -adická čísla

Pořadí -adic celého čísla je počet kopií v prvočíselném rozkladu . Stejný koncept lze rozšířit z celých čísel na racionální čísla definováním -adic řádu zlomku být . -Adic absolutní hodnota každé racionální číslo je pak definována jako . Vynásobením celého čísla jeho absolutní hodnotou -adic se vyruší faktory faktorizace a zůstanou pouze ostatní prvočísla. Stejně jako lze vzdálenost mezi dvěma reálnými čísly měřit absolutní hodnotou jejich vzdálenosti, lze vzdálenost mezi dvěma racionálními čísly měřit jejich vzdáleností -adic, -adic absolutní hodnotou jejich rozdílu. Pro tuto definici vzdálenosti jsou dvě čísla blízko u sebe (mají malou vzdálenost), když je jejich rozdíl dělitelný velkou mocninou . Stejným způsobem, jakým mohou být reálná čísla tvořena z racionálních čísel a jejich vzdáleností, přidáním dalších limitujících hodnot k vytvoření úplného pole , lze racionální čísla se vzdáleností -adic rozšířit na jiné úplné pole, -adic čísla .

Tento obrázek řádu, absolutní hodnoty a z nich odvozeného kompletního pole lze zobecnit na algebraická číselná pole a jejich ohodnocení (určitá zobrazení z multiplikativní grupy pole na zcela uspořádanou aditivní skupinu , nazývanou také řády), absolutní hodnoty ( určitá multiplikativní zobrazení z pole na reálná čísla, nazývaná také normy, a místa (rozšíření na úplná pole, ve kterých je dané pole hustou množinou , nazývané také dokončení). Rozšíření od racionálních čísel k reálným číslům , například, je místo, ve kterém vzdálenost mezi čísly je obvyklá absolutní hodnota jejich rozdílu. Odpovídající mapování na aditivní skupinu by bylo logaritmem absolutní hodnoty, i když to nesplňuje všechny požadavky na ocenění. Podle Ostrowskiho teorému až do přirozeného pojmu ekvivalence jsou reálná čísla a -adic čísla se svými řády a absolutními hodnotami jedinými oceněními, absolutními hodnotami a místy na racionálních číslech. Princip místní globální umožňuje určité problémy v průběhu racionálních čísel, které mají být řešeny Sestavujeme společně řešení od každého ze svých míst, znovu zdůraznil význam prvočísel na teorii čísel.

Základní prvky v kroužcích

Gaussova připraví s normou méně než 500

Komutativní prsten je algebraická struktura , kde jsou definovány sčítání, odečítání a násobení. Celá čísla jsou kruh a prvočísla v celých číslech byla zobecněna na kruhy dvěma různými způsoby, prvočísly a neredukovatelné prvky . Prvek kruhu se nazývá prvočíslo, pokud je nenulový, nemá žádnou multiplikativní inverzní hodnotu (to znamená, že není jednotkou ) a splňuje následující požadavek: kdykoli rozděluje součin dvou prvků prvku , dělí také alespoň jeden z prvků. nebo . Prvek je neredukovatelný, není-li jednotkou ani součinem dvou dalších nejednotkových prvků. V kruhu celých čísel tvoří prvočíslo a neredukovatelné prvky stejnou množinu,

V libovolném kruhu jsou všechny primární prvky neredukovatelné. Opak neplatí obecně, ale platí pro jedinečné faktorizační domény .

Základní teorém aritmetiky nadále platí (podle definice) v jedinečných faktorizačních doménách. Příkladem takové oblasti jsou Gaussova celá čísla , kruh komplexních čísel ve tvaru kde označuje imaginární jednotku a a jsou libovolná celá čísla. Jeho prvočísla jsou známá jako Gaussova prvočísla . Ne každé číslo, které je prvočíslo mezi celými čísly, zůstává prvočíslo v Gaussových celých číslech; například číslo 2 lze zapsat jako součin dvou Gaussových prvočísel a . Racionální prvočísla (prvotní prvky v celých číslech) shodná s 3 mod 4 jsou gaussovská prvočísla, ale racionální prvočísla shodná s 1 mod 4 nikoli. Je to důsledek Fermatovy věty o součtech dvou čtverců , která říká, že liché prvočíslo je vyjádřitelné jako součet dvou čtverců , a tedy faktorizovatelné jako , přesně když je 1 mod 4.

Prvotní ideály

Ne každý prsten je unikátní faktorizační doménou. Například v kruhu čísel (pro celá čísla a ) má číslo dvě faktorizace , kde žádný ze čtyř faktorů nelze dále redukovat, takže nemá jednoznačnou faktorizaci. Abychom rozšířili jedinečnou faktorizaci na větší třídu kruhů, lze pojem čísla nahradit pojmem ideál , podmnožinou prvků kruhu, který obsahuje všechny součty dvojic jeho prvků a všechny jeho součiny. prvky s prstencovými prvky. Primární ideály , které zobecňují prvočísla v tom smyslu, že hlavní ideál generovaný prvočíslem je primárním ideálem, jsou důležitým nástrojem a předmětem studia v komutativní algebře , algebraické teorii čísel a algebraické geometrii . Prvořadé ideály kruhu celých čísel jsou ideály (0), (2), (3), (5), (7), (11), ... Základní věta aritmetiky zobecňuje na Lasker-Noetherovu větu , který vyjadřuje každý ideál v noetherovském komutativním kruhu jako průsečík primárních ideálů , což jsou vhodná zobecnění primárních mocnin .

Spektrum prstenu je geometrický prostor, jehož body jsou hlavními ideály kruhu. Aritmetická geometrie také těží z tohoto pojmu a mnoho konceptů existuje jak v geometrii, tak v teorii čísel. Například, faktorizace nebo větvení primárních ideálů když zvednutý k poli rozšíření , základní problém algebraické teorie čísel, nese nějakou podobnost s větvením v geometrii . Tyto koncepty mohou dokonce pomoci v otázkách teorie čísel, které se týkají výhradně celých čísel. Například primární ideály v kruhu celých čísel z kvadratických číselných polí mohou být použity při prokazování kvadratickou vzájemnost , prohlášení, že se týká existence odmocniny modulo číslo prvočísel. Časné pokusy dokázat Fermatův poslední teorém vedly ke Kummerovu zavedení pravidelných prvočísel , celočíselných prvočísel spojených s neúspěchem jedinečné faktorizace v cyklotomických celých číslech . Otázku, kolik celočíselných prvočísel započítáváme do součinu vícenásobných prvočísel v algebraickém číselném poli, řeší Čebotarevův teorém o hustotě , který (když je aplikován na cyklotomická celá čísla) má jako speciální případ Dirichletovu větu o prvočíslech v aritmetických posloupnostech.

Teorie skupin

V teorii konečných skupin se věty Sylow naznačují, že pokud síla prvočíslo rozdělí pořadí skupiny , pak tato skupina má podskupina objednávky . Podle Lagrangeovy věty je každá skupina prvočísel cyklickou grupou a podle Burnsideovy věty je řešitelná každá skupina, jejíž pořadí je dělitelné pouze dvěma prvočísly .

Výpočetní metody

Malé ozubené kolo v tomto zemědělském zařízení má 13 zubů, prvočíslo, a střední ozubené kolo má 21, relativně prvočíslo ku 13.

Po dlouhou dobu byla teorie čísel obecně a studium prvočísel zvláště považováno za kanonický příklad čisté matematiky bez jiných aplikací mimo matematiku, než je použití zubů ozubených kol s prvočíslem k rovnoměrnému rozložení opotřebení. Zejména teoretici čísel, jako je britský matematik GH Hardy, byli hrdí na to, že vykonávali práci, která neměla absolutně žádný vojenský význam.

Tato vize čistoty teorie čísel byla zničena v 70. letech 20. století, kdy bylo veřejně oznámeno, že prvočísla lze použít jako základ pro vytvoření kryptografických algoritmů s veřejným klíčem . Tyto aplikace vedly k významnému studiu algoritmů pro počítání s prvočísly, a zejména testování prvočísel , metod pro určení, zda je dané číslo prvočíslo. Nejzákladnější rutina testování primality, zkušební dělení, je příliš pomalá na to, aby byla užitečná pro velké počty. Jedna skupina moderních testů primality je použitelná pro libovolná čísla, zatímco účinnější testy jsou k dispozici pro množství speciálních typů. Většina testů primality pouze říká, zda je jejich argument prvořadý nebo ne. Rutiny, které také poskytují primární faktor složených argumentů (nebo všechny jeho primární faktory), se nazývají faktorizační algoritmy. Prvočísla se také používají ve výpočtech pro kontrolní součty , hašovací tabulky a generátory pseudonáhodných čísel .

Zkušební divize

Nejzákladnější metoda kontroly primality daného celého čísla se nazývá zkušební dělení . Tato metoda dělí každým celým číslem od 2 až po druhou odmocninu z . Jakékoli takové celočíselné dělení rovnoměrně se zakládá jako složené; jinak je prvotřídní. Celá čísla větší než druhá odmocnina nemusí být zkontrolovány, protože vždy, když jedna z těchto dvou faktorů a je menší než nebo rovna odmocnině z . Další optimalizací je zkontrolovat pouze prvočísla jako faktory v tomto rozsahu. Například pro kontrolu, zda je 37 prvočíslo, jej tato metoda vydělí prvočísly v rozsahu od 2 do , což jsou 2, 3 a 5. Každé dělení vytváří nenulový zbytek, takže 37 je skutečně prvočíslo.

Ačkoli je tato metoda jednoduchá na popis, je nepraktická pro testování primality velkých celých čísel, protože počet testů, které provádí, roste exponenciálně jako funkce počtu číslic těchto celých čísel. Stále se však používá zkušební dělení s menším limitem, než je druhá odmocnina velikosti dělitele, k rychlému objevení složených čísel s malými faktory před použitím složitějších metod na čísla, která projdou tímto filtrem.

Síta

Animace Eratosthenova síta
Síto Eratosthenovo začíná všechna čísla neoznačených (šedá). Opakovaně najde první neoznačené číslo, označí ho jako prvočíslo (tmavé barvy) a jeho druhou mocninu a všechny pozdější násobky označí jako složené (světlejší barvy). Po označení násobků 2 (červená), 3 (zelená), 5 (modrá) a 7 (žlutá) byla zpracována všechna prvočísla až do druhé odmocniny velikosti tabulky a všechna zbývající neoznačená čísla (11, 13 , atd.) jsou označeny jako prvočísla (purpurová).

Před počítači byly běžně tištěny matematické tabulky se všemi prvočísly nebo rozklady na prvočísla až do daného limitu. Nejstarší metoda pro generování seznamu prvočísel se nazývá Eratosthenovo síto. Animace ukazuje optimalizovanou variantu této metody. Další asymptoticky účinnější metodou prosévání pro stejný problém je Atkinovo síto . V pokročilé matematice aplikuje teorie síta podobné metody na jiné problémy.

Testování primality versus dokazování primality

Některé z nejrychlejších moderních testů, zda je libovolné dané číslo prvočíslo, jsou pravděpodobnostní (nebo Monte Carlo ) algoritmy, což znamená, že mají malou náhodnou šanci na nesprávnou odpověď. Například Solovayův–Strassenův test primality na daném čísle vybírá číslo náhodně od přes a používá modulární umocňování ke kontrole, zda je dělitelné . Pokud ano, odpoví ano a jinak odpoví ne. Pokud je skutečně prvočíslo, vždy odpoví ano, ale pokud je složené, odpoví ano s pravděpodobností nejvýše 1/2 a ne s pravděpodobností nejméně 1/2. Pokud se tento test opakuje na stejném čísle, pravděpodobnost, že by složené číslo mohlo v testu pokaždé projít, je maximálně . Protože toto klesá exponenciálně s počtem testů, poskytuje vysokou jistotu (i když ne jistotu), že číslo, které projde opakovaným testem, je prvočíslo. Na druhou stranu, pokud test někdy selže, pak je číslo určitě složené. Složené číslo, které projde takovým testem, se nazývá pseudoprvočíslo .

Naproti tomu některé jiné algoritmy zaručují, že jejich odpověď bude vždy správná: prvočísla budou vždy určena jako prvočísla a kompozity budou vždy určeny jako složené. To platí například pro zkušební dělení. Algoritmy se zaručeně správným výstupem zahrnují jak deterministické (nenáhodné) algoritmy, jako je test primality AKS , tak randomizované algoritmy Las Vegas, kde náhodné volby provedené algoritmem neovlivňují jeho konečnou odpověď, jako jsou některé varianty eliptického dokazování primality křivky . Když metoda eliptické křivky dospěje k závěru, že číslo je prvočíslo, poskytuje certifikát primality, který lze rychle ověřit. Test primality eliptické křivky je v praxi nejrychlejší ze zaručeně správných testů primality, ale jeho analýza za běhu je založena spíše na heuristických argumentech než na přísných důkazech. Test primality AKS má matematicky prokázanou časovou složitost, ale je pomalejší než dokazování primality eliptické křivky v praxi. Tyto metody lze použít ke generování velkých náhodných prvočísel generováním a testováním náhodných čísel, dokud se nenajde jedno, které je prvočíslo; když to uděláte, rychlejší pravděpodobnostní test může rychle odstranit většinu složených čísel, než se použije zaručeně správný algoritmus k ověření, že zbývající čísla jsou prvočísla.

Následující tabulka uvádí některé z těchto testů. Jejich doba běhu je dána jako , počet testů a v případě pravděpodobnostních algoritmů počet provedených testů. Navíc je libovolně malé kladné číslo a log je logaritmus k blíže neurčenému základu. Tyto velký O notace znamená, že pokaždé, když váže by měly být vynásobeny konstantním faktorem ji převést z nekonečně malých jednotek na jednotkách času; tento faktor závisí na detailech implementace, jako je typ počítače použitého ke spuštění algoritmu, ale ne na vstupních parametrech a .

Test Vyvinutý v Typ Doba běhu Poznámky Reference
Test primality AKS 2002 deterministický
Dokazování primality eliptické křivky 1986 Las Vegas heuristicky
Test primality Baillie–PSW 1980 Monte Carlo
Miller-Rabinův test primálnosti 1980 Monte Carlo pravděpodobnost chyby
Solovay-Strassen test primality 1977 Monte Carlo pravděpodobnost chyby

Speciální algoritmy a největší známé prvočíslo

Kromě výše zmíněných testů, které platí pro libovolné přirozené číslo, lze rychleji otestovat primalitu u některých čísel speciálního tvaru. Například Lucas-Lehmerův test primality může určit, zda je Mersennovo číslo (jedna menší než mocnina dvou ) prvočíslo, deterministicky, ve stejnou dobu jako jediná iterace Miller-Rabinova testu. To je důvod, proč od roku 1992 (od prosince 2018) je největším známým prvočíslem vždy Mersennova prvočíslo. Předpokládá se, že existuje nekonečně mnoho Mersennových prvočísel.

Následující tabulka uvádí největší známá prvočísla různých typů. Některá z těchto prvočísel byla nalezena pomocí distribuované práce na počítači . V roce 2009 byl projekt Great Internet Mersenne Prime Search oceněn cenou 100 000 USD za první objevení prvočísla s alespoň 10 miliony číslic. Electronic Frontier Foundation nabízí $ 150,000 $ 250,000 pro připraví nejméně 100 milionů číslic a 1 miliardu čísel, resp.

Typ primární Počet desetinných číslic datum Nalezen uživatelem
Mersenne prvotřídní 2 82 589 933 − 1 24,862,048 7. prosince 2018 Patrick Laroche, Great Internet Mersenne Prime Search
Proth primární 10 223 × 2 31 172 165 + 1 9,383,761 31. října 2016 Péter Szabolcs, PrimeGrid
faktoriální prvočíslo 208 003! − 1 1,015,843 července 2016 Sou Fukui
prvotní prvočíslo 1 098 133 # − 1 476,311 březen 2012 James P. Burt, PrimeGrid
dvojitá prvočísla 2.996.863.034.895 x 2 1290000 ± 1 388,342 září 2016 Tom Greer, PrimeGrid

Faktorizace celého čísla

Vzhledem k tomu, kompozitní číslo úkol poskytovat jeden (nebo všechny) hlavními faktory, je označován jako faktorizace části . Je výrazně obtížnější než testování primality, a přestože je známo mnoho faktorizačních algoritmů, jsou pomalejší než nejrychlejší metody testování primálností. Zkušební dělení a Pollardův algoritmus rho lze použít k nalezení velmi malých faktorů a faktorizace eliptické křivky může být efektivní, pokud má faktory střední velikosti. Mezi metody vhodné pro libovolně velká čísla, která nezávisí na velikosti jejich faktorů, patří kvadratické síto a síto obecného číselného pole . Stejně jako u testování primality existují také faktorizační algoritmy, které vyžadují, aby jejich vstup měl speciální formu, včetně speciálního číselného pole síta . Od prosince 2019 je největším známým číslem, které bylo faktorizováno pomocí univerzálního algoritmu, RSA-240 , který má 240 dekadických číslic (795 bitů) a je součinem dvou velkých prvočísel.

Shorův algoritmus může na kvantovém počítači zohlednit jakékoli celé číslo v polynomickém počtu kroků . Současná technologie však může spustit tento algoritmus pouze pro velmi malá čísla. V říjnu 2012 bylo největší číslo, které bylo faktorováno kvantovým počítačem se Shorovým algoritmem, 21.

Další výpočetní aplikace

Několik kryptografie veřejných klíčů algoritmů, jako jsou RSA a Diffie-Hellman , jsou založeny na velkých prvočísel (2048- bitových prvočísla jsou časté). RSA se opírá o předpoklad, že je mnohem snazší (tj. efektivnější) provést násobení dvou (velkých) čísel a než počítat a (za předpokladu coprime ), pokud je znám pouze součin . Výměna klíčů Diffie–Hellman spoléhá na skutečnost, že existují účinné algoritmy pro modulární umocňování (výpočet ), zatímco zpětná operace ( diskrétní logaritmus ) je považována za obtížný problém.

Prvočísla se často používají pro hashovací tabulky . Například původní metoda Cartera a Wegmana pro univerzální hašování byla založena na výpočtu hašovacích funkcí výběrem náhodných lineárních funkcí modulo velkých prvočísel. Carter a Wegman zobecnili tuto metodu na -nezávislé hašování pomocí polynomů vyšších stupňů, opět modulo velkých prvočísel. Stejně jako v hašovací funkci se pro velikost hašovací tabulky v hašovacích tabulkách založených na kvadratickém sondování používají prvočísla, aby se zajistilo, že sekvence sondy pokryje celou tabulku.

Některé metody kontrolního součtu jsou založeny na matematice prvočísel. Například kontrolní součty používané v mezinárodních standardních knižních číslech jsou definovány tak, že se vezme zbytek čísla modulo 11, prvočíslo. Protože 11 je prvočíslo, může tato metoda detekovat jak jednociferné chyby, tak transpozice sousedních číslic. Další metoda kontrolního součtu, Adler-32 , používá aritmetické modulo 65521, největší prvočíslo menší než . Prvočísla se také používají v generátorech pseudonáhodných čísel včetně lineárních kongruenciálních generátorů a Mersenne Twister .

Jiné aplikace

Prvočísla mají ústřední význam pro teorii čísel, ale mají také mnoho aplikací v jiných oblastech matematiky, včetně abstraktní algebry a elementární geometrie. Například je možné umístit prvočísla bodů do dvourozměrné mřížky tak, aby žádná tři nebyla v přímce nebo aby každý trojúhelník tvořený třemi body měl velkou plochu . Dalším příkladem je Eisensteinovo kritérium , test, zda je polynom neredukovatelný na základě dělitelnosti jeho koeficientů prvočíslem a jeho druhou mocninou.

Součet dvou hlavních uzlů

Pojem prvočísla je tak důležitý, že byl zobecněn různými způsoby v různých odvětvích matematiky. Obecně „první“ označuje minimalizaci nebo nerozložitelnost ve vhodném smyslu. Například prvočíslo daného pole je jeho nejmenší podpole, které obsahuje 0 i 1. Je to buď těleso racionálních čísel, nebo konečné těleso s prvočíslem prvků, odkud pochází název. Často je zamýšlen druhý, dodatečný význam použitím slova prvočíslo, totiž že jakýkoli předmět lze v podstatě jednoznačně rozložit na jeho primární složky. Například v teorii uzlu , je primární uzel je uzel , který je indecomposable v tom smyslu, že nemůže být zapsána jako připojené součtu dvou netriviálních uzlů. Jakýkoli uzel lze jednoznačně vyjádřit jako spojený součet prvotřídních uzlů. Prime rozklad 3-variet je dalším příkladem tohoto typu.

Kromě matematiky a výpočetní techniky mají prvočísla potenciální spojení s kvantovou mechanikou a byla metaforicky používána v umění a literatuře. Byly také použity v evoluční biologii k vysvětlení životních cyklů cikád .

Sestavitelné polygony a polygonové oddíly

Konstrukce pravidelného pětiúhelníku pomocí pravítka a kružítka
Konstrukce pravidelného pětiúhelníku pomocí pravítka a kružítka. To je možné pouze proto, že 5 je Fermatovo prvočíslo .

Fermatova prvočísla jsou prvočísla formy

s je nezáporné celé číslo . Jsou pojmenována po Pierru de Fermat , který se domníval, že všechna taková čísla jsou prvočísla. Prvních pět z těchto čísel – 3, 5, 17, 257 a 65 537 – je prvočíslo, ale je složené, stejně jako všechna ostatní Fermatova čísla, která byla ověřena od roku 2017. Pravidelný -gon lze sestavit pomocí pravítka a kružítka, pokud a pouze v případě, že liché prvočísla (pokud existují) jsou odlišná Fermatova prvočísla. Stejně tak pravidelný -gon může být konstruován pomocí pravítka, kružítka a úhlového trisektoru tehdy a pouze tehdy, jsou-li prvočísla libovolného počtu kopií 2 nebo 3 spolu s (možná prázdnou) sadou odlišných Pierpontových prvočísel , prvočísel formulář .

Je možné rozdělit jakýkoli konvexní mnohoúhelník na menší konvexní mnohoúhelníky o stejné ploše a stejném obvodu, kde je mocnina prvočísla , ale u jiných hodnot to není známo .

Kvantová mechanika

Počínaje prací Hugha Montgomeryho a Freemana Dysona v 70. letech 20. století matematici a fyzici spekulovali, že nuly Riemannovy zeta funkce jsou spojeny s energetickými hladinami kvantových systémů . Prvočísla jsou také významná v kvantové informační vědě , a to díky matematickým strukturám, jako jsou vzájemně nezaujaté základy a symetrické informačně kompletní míry pozitivního operátora .

Biologie

Evoluční strategie používaná cikády rodu Magicicada využívá prvočísel. Tento hmyz tráví většinu svého života jako hlupáci pod zemí. Po 7, 13 nebo 17 letech se pouze zakuklí a vylézají ze svých nor, v tomto okamžiku létají, rozmnožují se a pak maximálně po několika týdnech umírají. Biologové se domnívají, že tyto délky rozmnožovacích cyklů s prvočíslem se vyvinuly, aby zabránily predátorům synchronizovat se s těmito cykly. Naproti tomu víceletá období mezi kvetením u rostlin bambusu jsou předpokládána jako hladká čísla , která mají ve faktorizaci pouze malá prvočísla.

Umění a literatura

Prvočísla ovlivnila mnoho umělců a spisovatelů. Francouzský skladatel Olivier Messiaen použil prvočísla k vytvoření ametrické hudby prostřednictvím „přírodních jevů“. V dílech jako La Nativité du Seigneur (1935) a Quatre études de rythme (1949–50) využívá současně motivy s délkami danými různými prvočísly k vytvoření nepředvídatelných rytmů: prvočísla 41, 43, 47 a 53 se objevují v třetí etuda, „Neumes rythmiques“. Podle Messiaena byl tento způsob skládání „inspirován pohyby přírody, pohyby volného a nestejného trvání“.

Vědec Carl Sagan ve svém vědecko-fantastickém románu Contact navrhl, že prvočíselná faktorizace by mohla být použita jako prostředek k vytvoření dvourozměrných obrazových rovin při komunikaci s mimozemšťany, což je myšlenka, kterou poprvé neformálně rozvinul s americkým astronomem Frankem Drakem v roce 1975. románu The Curious Incident of the Dog in the Night-Time od Marka Haddona , vypravěč uspořádá úseky příběhu podle po sobě jdoucích prvočísel, aby tak vyjádřil duševní stav jeho hlavní postavy, matematicky nadaného teenagera s Aspergerovým syndromem . Prvočísla jsou použita jako metafora pro osamělost a izolaci v románu Paola Giordana Osamělost prvočísel , ve kterém jsou zobrazena jako „outsideři“ mezi celými čísly.

Poznámky

Reference

externí odkazy

Generátory a kalkulačky