Prvočíslo

V matematice je prvočíslo přirozené číslo, které má pouze dva dělitele: 1 a samo sebe. Prvních 25 prvočísel:

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

Číslo 1 není prvočíslo. Studium prvočísel je součástí teorie čísel, odvětví matematiky, které zahrnuje i studium přirozených čísel. Přestože prvočísla byla a jsou předmětem intenzivního výzkumu, nepodařilo se vyřešit některé otázky týkající se prvočísel (např. Riemannova hypotéza nebo Goldbachova hypotéza).

Historie prvočísel

Existují důkazy, že už Egypťané znali prvočísla, ale první studie prvočísel pochází z Antického Řecka. Matematik Euklidus napsal knihu, která obsahovala důležité teorie prvočísel včetně například toho, že řada prvočísel je nekonečná. Eratosthenovo síto je jednoduchá metoda, pomocí které se dají jednoduše určovat prvočísla (počítače, které generují vysoká prvočísla používají jinou metodu).

Další studie prvočísel pocházejí až ze 17 století. V roce 1640 ustanovil Pierre de Fermat Malou Fermatovu větu (důkaz této věty našli později matematici Leibniz a Euler). Některé speciální případy Fermatovy věty mohli být objevené daleko dříve v Číně. Fermat předpokládal, že čísla 22n+1 jsou prvočísla (nazývají se Fermatova čísla) a tuto větu potvrdil až do n=4. Nicméně později matematik Euler dokázal, že další Fermatovo číslo není prvočíslo: 225+1. Není známo další Fermatovo číslo, které by bylo prvočíslo. Francouzský mnich Marin Mersene hledal prvočísla pomocí vzorce 2p-1, kde p je prvočíslo. Tato čísla se na jeho počest nazývají Mersenova prvočísla.

Dlouho se předpokládalo, že prvočísla nemají žádný praktický význam mimo matematiku. Toto se změnilo v roce 1970 kdy byly položeny základy dnešní kryptografie (jedním z prvním algoritmů byl šifrovací algoritmus RSA).

Od roku 1951 byli všechny vysoká prvočísla nalezená pomocí počítače. Hledání vyšších prvočísel vyvolalo zájem i v jiných kruzích než matematických. Společnosti jako The Great Internet Mersenne Prime Search vynaložily velké úsilí o nalezení vysokých prvočísel.

Prvočíselný rozklad

Základní věta aritmetiky ustanovuje, že každé číslo větší než jedna se da zapsat jako součin jednoho nebo více prvočísel (každé číslo se dá zapsat pouze jedním způsobem). Jednotlivá prvočísla se v prvočíselném rozkladu ale mohou opakovat. Prvočísla se díky tomuto mohou nazývat jako základní kámen přirozených čísel.

Například číslo 23244 můžeme rozepsat jako:

23244 = 22 * 3 * 13 * 149

Více v článku Prvočíselný rozklad.

Počet prvočísel

Existuje nekonečně mnoho prvočísel.

Nejstarší známý důkaz ustanovující to, že prvočísel je nekonečně mnoho byl nalezen řeckým matematikem Euklidem. Jeho důkaz je zní asi takto:

Mějme nějakou konečnou množinu prvočísel. Vynásobme je všechny dohromady a přičtěme jedničku. Výsledné číslo není dělitelné ani jedním prvočíslem z uvažované množiny, protože dělením jakýmkoliv z daných prvočísel získáme zbytek jedna. Protože všechna čísla, která nejsou prvočísla, mohou být rozložena na součin prvočísel je výsledek buď prvočíslo, nebo je výsledek možno rozložit pomocí nějakého prvočísla/prvočísel, které není v uvažované množině prvočísel. Tak nebo tak, vždy existuje minimálně jedno další prvočíslo, které není v uvažované množině. Tento fakt platí bez ohledu na to, jakou množinou začneme. Proto je řada prvočísel nekonečná.

Tento důkaz bývá někdy nesprávně pochopen, a někteří čtenáři mohou si mohou myslet, že P+1 (kde P je součin prvočísel) je vždy prvočíslo. Toto se objevuje zejména, pokud pracujete s malými prvočísly. Nejmenší příklad, kdy P+1 není prvočíslo je 30031:

(2*3*5*7*11*13)+1 = 30031
59*509 = 30031

Rozmístění prvočísel

Problém rozmístění prvočísel je populárním objektem výzkumu. Prvočísla jsou obklopena přirozenými čísly v nepředpovídaným způsobem. Přesto se zdá, že nějaké zákony řídí jejich rozmístění. Leonhard Euler to komentoval následovně:

Matematici se marně pokoušejí objevit nějaký zákon v rozmístění prvočísel, ale máme důvod se domnívat, že do tohoto problému naše mysl nikdy nepronikne.

V roce 1975 tento problém komentoval Don Zagier:

Existují dvě fakta ohledně rozmístění prvočísel, které vás, jak doufám, uchvátí tak, že budou navždy vryta ve vašich srdcích. První je to, že navzdory jejich jednoduché definici a jejich roli jako stavebních kamenů přirozených čísel, se prvočísla objevují okolo přirozených čísel, aniž by se řídila nějakým zákonem, tudíž nikdo nemůže předpokládat, kde se další prvočíslo objeví. Druhý fakt je ještě více udivující, kvůli tomu, že vyjadřuje přesný opak prvního faktu: výskyt prvočísel ukazuje omračující pravidelnost a jistě existují nějaké zákony, které určují, kde bude další prvočíslo.

Předchozí obrázek s 2310 sloupci ukazuje rozmístění prvočísel od čísla 1 do čísla 76800. Bílé pixely představují přirozená čísla zatímco černé pixely označují prvočísla.

Ulamova spirála

Ulamova spirála je jednoduchá metoda, pomocí které se prvočísla zobrazí v pravidelných obrazcích. Tato metoda byla objevena matematikem Stanisławem Ulamem v roce 1963 když během nějaké nudné konference načrtl číselnou řadu ve tvaru spirály s jedničkou uprostřed.

Poté co zakroužkoval prvočísla, dostal překvapující obrázek:

Zakroužkovaná čísla tvoří diagonální čáry. Lépe to uvidíte na větším obrázku. Následující obrázek je Ulamova spirála o velikosti 200 × 200.

Goldbachova hypotéza

Jedná se o jeden z nejstarších zatím nevyřešených problémů teorie čísel. Tato hypotéza stanovuje: Každé sudé číslo větší než dva může být zapsáno jako součet dvou prvočísel.

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
14 = 3 + 11 = 7 + 7

Pro malá čísla lze být tato hypotéza ověřena. V roce 1938 N. Popping potvrdil tuto hypotézu pro čísla n ≤ 105. Později, s pomocí počítačů byla ověřena další čísla → byla potvrzena čísla n ≤ 1018.

Tato hypotéza nestanovuje, že existuje pouze jeden unikátní způsob, jak lze vyjádřit dané číslo. V tomto článku jste již viděli, že například číslo 14 lze vyjádřit dvěma způsoby. Čím větší číslo, tím více existuje způsobů, jak dané číslo zapsat pomocí součtu dvou prvočísel.

Předchozí obrázek ukazoval počet způsobů jak zapsat čísla v intervalu n ≤ 1000. Následující obrázek ukazuje čísla v intervalu n ≤ 1000000.

Lemoinoiva hypotéza

Tato hypotéza stanovuje, že každé liché číslo větší než 5 se dá zapsat jako součet prvočísla a čísla, které je součinem dvou prvočísel. Daná hypotéza vypadá asi takto: (2n+1)=p+2*q, kde p, q jsou prvočísla a n > 2.

47 = 13 + 2 × 17 = 37 + 2 × 5 = 41 + 2 × 3 = 43 + 2 × 2
59 = 53 + 2*3
...

Tato hypotéza zatím byla potvrzena pro čísla až do 109.

Nejvyšší prvočíslo

Nejvyšší známé prvočíslo k červnu 2008 je 232582657-1 (toto číslo má 9808358 číslic). Toto číslo je 44 Mersenovo prvočíslo. 32582657 bylo objeveno 4 září 2006 Curtisem Cooperem a Stevenem Boonem, profesory University v Missouri a členy organizace GIMPS. Toto číslo hledalo 700 počítačů 9 let.

Další dvě nejvyšší prvočísla jsou také Mersenova prvočísla: M30402457 =230402457-1 (43 známé Mersenovo prvočíslo o délce 9 152 052 číslic) a M25964951 =225964951-1 (42 známé Mersenovo prvočíslo o délce 7 816 230 číslic).

Nejvyšší známé prvočíslo, které není Mersenovo prvočíslo je 19249*2213018586+1. Toto číslo má délku 3918990 číslic a je to také sedmé nejvyšší prvočíslo obecně.

Eratosthenovo síto

Eratosthenovo síto je jednoduchý algoritmus pro nalezení všech prvočísel menších než zadaná horní mez. Je pojmenován po řeckém matematikovi Eratosthenovi z Kyrény, který žil v letech 276–194 př. n. l.

Algoritmus je založen na proséváním seznamu čísel. Na počátku jsou čísla 2, 3, 4, 5, ..., zadané maximum. Nyní musíme vyjmout první číslo ze seznamu - jedná se o prvočíslo. Dále ze seznamu odstraníme všechny násobky daného čísla a celý postup opakujeme do té doby, dokud než je seznam prázdný nebo do té doby, než je jako prvočíslo označeno číslo vyšší než odmocnina nejvyššího čísla seznamu (zbývající čísla jsou prvočísla).

Na předchozím obrázku si můžete prohlédnout animaci toho, jak lze pomocí Eratosthenova síta nalézt prvočísla do čísla 120. My si tady můžeme rozepsat, jak by se hledali prvočísla do čísla 30:

• Máme řadu 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30. Označíme 2 jako prvočíslo a ze seznamu vyškrtneme všechny jeho násobky.
  Prvočísla: 2.
• Máme řadu 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29. Označíme 3 jako prvočíslo a ze seznamu vyškrtneme všechny jeho násobky.
  Prvočísla: 2, 3.
• Máme řadu 5, 7, 11, 13, 17, 19, 23, 25, 29. Označíme 5 jako prvočíslo a ze seznamu vyškrtneme všechny jeho násobky.
  Prvočísla: 2, 3, 5.
• Máme řadu 7, 11, 13, 17, 19, 23, 29. Odmocnina z 29 je přibližně 5.3 → 5.3 < 7 → Ukončíme hledání; zbylá čísla jsou prvočísla.
  Prvočísla: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Emirp

Všímavější čtenáři si jistě všimli, že emirp je obráceně prime (anglický výraz pro prvočísla). Emirp je typ prvočísla, které když napíšeme pozpátku, dostaneme opět prvočíslo. Následuje začátek řady takových prvočísel:

13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, ...

Nejvyšší známé prvočíslo, které je emirp, je 1010006+941992101×104999+1.

Prvočíselná dvojice

Jak už název napovídá, jedná se o dvojici prvočísel, jež se liší o číslo 2. Musí tedy platit (p, p+2), kde p je prvočíslo. Jedná se o nejmenší možnou vzdálenost mezi prvočísly (kromě dvojice prvočísel (2, 3)).

Nejvyšší známá dvojice prvočísel je 2003663613 · 2195000 ± 1 byla objevena roku 2007 Francouzem Ericem Vautierem.

Zatím neexistuje důkaz, který by potvrdil, že existuje nekonečně mnoho prvočíselných dvojic, ale předpokládá se, že tomu tak je.