Prvočíslo

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 větší než jedna, 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[editovat | editovat zdroj]

Čí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é beze zbytku čísly 1, 2, 3, 4, 6, 8, 12, 24 – proto není prvočíslem, ale složeným číslem.

Vlastnosti[editovat | editovat zdroj]

  • 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 (leden 2016) známé prvočíslo je 274 207 281 − 1, má 22 338 618 dekadických cifer.[1] Je to 49. známé Mersennovo prvočíslo, označované jako M74207281. Bylo nalezeno 17. září 2015.

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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ě .[2]

Využití[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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.[3]

Příklad testovacího algoritmu[editovat | editovat zdroj]

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.

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;
}

Prvočísla menší než 1000[editovat | editovat zdroj]

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.

Odkaz[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1, GIMPS, 7. 1. 2016
  2. A205776: Primes of the form 2*6^n+1. OEIS
  3. (anglicky)The prime pages, primes.utm.edu

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]