Prvočíslo

Prvočíslo je přirozené číslo větší než 1, které je beze zbytku dělitelné jen dvěma děliteli: jedničkou a samo sebou. Jednička není prvočíslo, neboť nemá dva různé dělitele. Přirozená čísla větší než jedna, která nejsou prvočísly, se nazývají složená čísla. Prvním prvočíslem je číslo 2, které je jediným sudým prvočíslem.

Formální definice 
Číslo  je prvočíslem právě když platí:  nebo ekvivalentně .

Příklad 
Číslo 13 má při dělení dvěma zbytek 1, při dělení třemi zbytek 1, při dělení pěti zbytek 3 atd. Říkáme, že je těmito čísly nedělitelné. Pouze při dělení 1 a 13 je zbytek 0 (dělitelné). Proto je 13 prvočíslo.

Číslo 24 je dělitelné čísly 1, 2, 3, 4, 6, 8, 12, 24. Není proto prvočíslem, ale složeným číslem.

Prvočíselnost jedničky 
Jak říká základní věta aritmetiky, každé přirozené číslo je možno rozložit na právě jeden prvočíselný součin (např. 12 = 2×2×3). Pokud by byla jednička zahrnuta do množiny prvočísel, bylo by takových rozkladů vždy nekonečně mnoho (12 = 2×2×3 = 1×2×2×3 = 1×1×2×2×3 = …). Proto se jednička za prvočíslo nepovažuje, přestože podmínku dělitelnosti pouze sebou samým a jedničkou splňuje. V rámci obecnějších teorií jsou prvočísla takzvanými prvočiniteli, zatímco jednička patří mezi takzvané jednotky.

Vlastnosti 
 Pokud je  prvočíslo a  dělí součin čísel  a , pak  dělí  nebo  dělí .
 Každé složené číslo lze jednoznačně vyjádřit jako součin prvočísel. Proces rozkladu čísla na jeho prvočíselné činitele (prvočinitele) se nazývá faktorizace. Např. .
 Okruh  (viz množina zbytkových tříd) je těleso, právě když  je prvočíslo. Jinak vyjádřeno:  je prvočíslo, právě když , kde  je počet invertovatelných prvků v .
 Pokud  je prvočíslo a  je celé číslo, pak  je dělitelné . (Malá Fermatova věta)
 Pokud  je kladné celé číslo větší než jedna, existuje prvočíslo  tak, že . (Bertrandův postulát)
 Číslo  větší než jedna je prvočíslo, právě když . (Wilsonova věta)
 Pokud  je konečná grupa a  je nejvyšší mocnina prvočísla , která dělí řád grupy , má grupa  podgrupu řádu .
 Pokud  je prvočíslo a  je grupa s  prvky, obsahuje  prvek řádu .
 Prvočísel je nekonečně mnoho. (Viz níže.)
 Suma převrácených hodnot prvočísel diverguje.
 Hustota prvočísel je asymptoticky , kde  je přirozený logaritmus n. Přesněji, , kde prvočíselná funkce  vyjadřuje počet prvočísel menších než .
 Největší dnes (prosinec 2018) známé prvočíslo je 282 589 933 − 1, má 24 862 048 dekadických cifer. Je to 51. známé Mersennovo prvočíslo, označované jako M82589933. Bylo nalezeno 7. prosince 2018.

Zkoumáním vlastností prvočísel se zabývá teorie čísel. Zobecněním prvočísel jsou v abstraktní algebře prvočinitelé.

Výskyt prvočísel 
Prvočísel je nekonečně mnoho. (Důkaz sporem: Nechť existuje jen konečně mnoho prvočísel. Označme je . Potom číslo  není dělitelné žádným z těchto prvočísel, jelikož při dělení dostaneme vždy zbytek 1. Tím pádem číslo  musí být buď prvočíslo, nebo musí být dělitelné nějakým jiným prvočíslem. To ale znamená, že množina prvočísel z počátku důkazu nebyla úplná, což je spor s předpokladem. Tento důkaz předvedl Eukleidés.)

Podle Bertrandova postulátu lze nalézt vždy alespoň jedno prvočíslo mezi čísly  a  pro . Ve skutečnosti jich však existuje pro vyšší  daleko více. (I z této věty lze dovodit, že prvočísel je nekonečně mnoho.)

Naproti tomu lze nalézt libovolně dlouhé intervaly přirozených čísel, kde se nevyskytuje žádné prvočíslo. Například interval  obsahuje  složených čísel. Tato čísla jsou totiž po řadě dělitelná dvěma, třemi, …, .

Mnoho hypotéz o rozložení prvočísel je dodnes nevyřešených. Jeden otevřený problém je tzv. Riemannova hypotéza, která souvisí s pravidelností rozložení prvočísel a za jejíž důkaz je vypsána odměna milion dolarů.

Speciální prvočísla 
Některá prvočísla lze vyjádřit v některé z několika matematicky zajímavých podob. Patří sem například:
 Fermatova čísla: Prvočísly je prvních pět čísel ve formě .
 Mersennova prvočísla: Prvočíslo ve formě , kde  je jiné prvočíslo. Mersennovými prvočísly je mnoho z největších známých prvočísel.
 Některá prvočísla lze vyjádřit ve formě .

Využití 
Velký praktický význam mají prvočísla v kryptografii, například v šifrovacích systémech jako je RSA.

Pro vytvoření seznamu prvočísel existují různé algoritmy, např. Eratosthenovo síto.

Testování prvočíselnosti 
Otestovat, zda je číslo prvočíslem, tedy testovat prvočíselnost je možné asymptoticky v polynomiálním čase algoritmem AKS, nalezeným roku 2002. Asymptoticky rekordní rychlost ovšem neznamená, že se jedná o algoritmus prakticky nejvýhodnější. V praxi bývá častější použití některého z pravděpodobnostních algoritmů, například Millerova-Rabinova algoritmu.

Testování prvočíselnosti pomocí algoritmu využívajícího vlastností eliptických křivek (ECPP) je nejrychlejší známý algoritmus.

Příklad testovacího algoritmu 
Následující jednoduchý algoritmus implementovaný v jazyce C++ zkouší dělit vstup všemi menšími čísly od 2 do jeho odmocniny - pokud nalezne v tomto intervalu dělitele zadaného čísla, je jasné, že zadané číslo není prvočíslo. Testovat stačí pouze do odmocniny, protože pokud n je složené číslo, můžeme psát:  pro . Pokud by nestačilo testovat do odmocniny, znamenalo by to, že  a současně , vynásobíme-li ale tyto dva vztahy, máme , což je spor.
public static bool IsPrvocislo(int num)
{
    if (num == 1)
        return false;
        
    int odmocnina = (int) floor(sqrt(num));
    
    for (int i = 2; i <= odmocnina; i++)
    {
        if (num % i == 0)
            return false;
    }

    return true;
}

Prvočísla menší než 1000 
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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

Největší známé prvočíslo 
Největší známé prvočíslo je 282 589 933 − 1. Jedná se o číslo, které má 24 862 048 číslic v desítkové soustavě. Číslo bylo objeveno v rámci projektu GIMPS v prosinci 2018. Jeho přesná podoba je uvedena níže, kde je pro zjednodušení zobrazeno pouze prvních a posledních 120 číslic.148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560 ...

(mezitím je 24 861 808 dalších číslic)

... 062107557947958297531595208807192693676521782184472526640076912114355308311969487633766457823695074037951210325217902591

Odkazy

Reference

Související články 
 Eratosthenovo síto
 Mersennovo prvočíslo
 Emirp
 Prvočíselný rozklad
 Prvočíselná dvojice
 Wieferichovo prvočíslo
 Ulamova spirála
 2147483647
 Ilegální prvočíslo
 Poloprvočíslo

Externí odkazy 
 
 
 
  The Primes Pages – přehledové i aktuální informace o výzkumu prvočísel
  www.prime-numbers.org – seznam prvočísel do 10 miliard
  Prvočísla do jednoho bilionu

Čísla

Teorie čísel