Prvočíslo

Prvočíslo je přirozené číslo, které je beze zbytku dělitelné právě dvěma různými přirozenými čísly, a to číslem jedna a sebou samým (tedy 1 není prvočíslo). Přirozená čísla různá od jedné, která nejsou prvočísla, se nazývají složená čísla.

První prvočísla jsou:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31…

Příklad

Číslo 13 má při dělení dvěma zbytek 1, při dělení 3 zbytek 1, při dělení pěti zbytek 3 atd. Beze zbytku je dělitelné pouze 1 a 13. Proto je 13 prvočíslo.

Číslo 24 je dělitelné čísly 1, 2, 3, 4, 6, 8, 12, 24 – proto není prvočíslem.

Vlastnosti

• Pokud je p prvočíslo a p dělí součin čísel a a b, pak p dělí a nebo p dělí b.
• 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ř. $24 = 2^3\cdot 3$.
• Okruh Z/nZ (viz množina zbytkových tříd) je těleso, právě když n je prvočíslo. Jinak vyjádřeno: n je prvočíslo, právě když φ(n) = n − 1, kde φ(n) je počet invertovatelných prvků v Z/nZ.
• Pokud p je prvočíslo a 0<a<p je celé číslo, pak $a^{p}-a$ je dělitelné p. (Malá Fermatova věta)
• Pokud n je kladné celé číslo větší než jedna, existuje prvočíslo p tak, že n < p < 2n. (Bertrandův postulát)
• P je prvočíslo, právě když $(p-1)! \equiv -1 \pmod p$. (Wilsonova věta)
• Pokud G je konečná grupa a $p^n$ je nejvyšší mocnina prvočísla p, která dělí řád grupy G, má grupa G podgrupu řádu $p^n$.
• Pokud p je prvočíslo a G je grupa s $p^n$ prvky, obsahuje G prvek řádu p.
• Prvočísel je nekonečně mnoho. (Důkaz sporem: Nechť existuje jen konečně mnoho prvočísel. Označme je p₁, p₂, …, p_n. Potom číslo x = p₁ · p₂ ··· p_n + 1 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 x 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.
• Suma převrácených hodnot prvočísel diverguje.
• Hustota prvočísel je asymptoticky $1/\ln(n)$, kde $\ln(n)$ je přirozený logaritmus n. Přesněji, $\pi(n)\simeq n/\ln(n)$, kde prvočíselná funkce $\pi(n)$ vyjadřuje počet prvočísel menších než n.
• Největší dnes (2008) známé prvočíslo je 2^43 112 609 − 1, má 12 978 189 dekadických cifer. Je to 47. známé Mersennovo prvočíslo, označované jako M_43112609. Bylo nalezeno 23. srpna 2008.

Zkoumáním vlastností prvočísel se zabývá teorie čísel.

Výskyt prvočísel

Podle Bertrandova postulátu lze nalézt vždy alespoň jedno prvočíslo mezi čísly n a 2n pro n > 1. Ve skutečnosti jich však existuje pro vyšší n daleko více. Z této věty ihned také plyne nekonečný počet prvočísel.

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

Mnoho hypotéz o rozložení prvočísel je dodnes nevyřešených. K nejznámějším patří otázka, zda je nekonečně mnoho prvočíselných dvojčat, tj. dvojic prvočísel lišících se o 2 (např 5,7 nebo 41,43). Jiný 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ů.

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.

Prvních sto 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, 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.

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: $n=a\cdot{}b$ pro $a,b\in\mathbb{N}, a, b>1$. Pokud by nestačilo testovat do odmocniny, znamenalo by to, že $a > \sqrt{n}$ a současně $b > \sqrt{n}$, vynásobíme-li ale tyto dva vztahy, máme $a\cdot{}b > n$, což je spor.

bool isPrime(int number) {
    if (number < 2) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;
 
    int max = (int) sqrt(number);
 
    for (int i = 3; i <= max; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
 
    return true;
}

Odkazy

Související články

• Mersennovo prvočíslo
• Emirp
• Prvočíselný rozklad
• Prvočíselná dvojice
• Wieferichovo prvočíslo
• Ulamova spirála
• 2147483647
• Ilegální prvočíslo

Externí odkazy

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