Array ( [0] => 14661404 [id] => 14661404 [1] => cswiki [site] => cswiki [2] => Prvočíslo [uri] => Prvočíslo [3] => [img] => [4] => [day_avg] => [5] => [day_diff] => [6] => [day_last] => [7] => [day_prev_last] => [8] => Prvočíslo je přirozené číslo větší než jedna, které nemá žádné dělitele kromě jedničky a sebe sama. Prvočísla jsou základní stavební jednotkou pro celočíselné faktorizace, tedy rozklad celých čísel na jejich prvočíselné složky. V českém číslování se k prvním číslům počítá i číslo dva, které je jediným sudým prvočíslem. Existuje nekonečně mnoho prvočísel, jak bylo dokázáno Eukleidovým důkazem, a každé přirozené číslo větší než jedna lze jednoznačně faktorizovat na součin prvočísel. Prvočísla mají důležitou roli v matematice a v různých aplikacích, jako je kryptografie, kde jsou využívána při tvorbě bezpečných šifer. Existují také algoritmy na nalezení prvočísel, ale vzhledem k jejich náhodné distribuci není možné jejich výskyt předpovědět. [oai] => Prvočíslo je přirozené číslo větší než jedna, které nemá žádné dělitele kromě jedničky a sebe sama. Prvočísla jsou základní stavební jednotkou pro celočíselné faktorizace, tedy rozklad celých čísel na jejich prvočíselné složky. V českém číslování se k prvním číslům počítá i číslo dva, které je jediným sudým prvočíslem. Existuje nekonečně mnoho prvočísel, jak bylo dokázáno Eukleidovým důkazem, a každé přirozené číslo větší než jedna lze jednoznačně faktorizovat na součin prvočísel. Prvočísla mají důležitou roli v matematice a v různých aplikacích, jako je kryptografie, kde jsou využívána při tvorbě bezpečných šifer. Existují také algoritmy na nalezení prvočísel, ale vzhledem k jejich náhodné distribuci není možné jejich výskyt předpovědět. [9] => [is_good] => [10] => [object_type] => [11] => 0 [has_content] => 0 [12] => [oai_cs_optimisticky] => ) Array ( [0] => '''Prvočíslo''' je [[přirozené číslo]] větší než 1, které je beze zbytku [[dělitelnost|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é číslo|složená čísla]]. Prvním prvočíslem je číslo 2, které je jediným sudým prvočíslem. [1] => [2] => == Formální definice == [3] => Číslo n \in \mathbb{N} je prvočíslem právě když platí: n > 1 \land \forall k \in \mathbb{N} : \left(k | n \implies (k = 1 \lor k = n)\right) nebo ekvivalentně \left|\{k : k\in \mathbb{N}, k | n\}\right| = 2. [4] => [5] => == Příklad == [6] => Čí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. [7] => [8] => Číslo 24 je dělitelné čísly 1, 2, 3, 4, 6, 8, 12, 24. Není proto prvočíslem, ale složeným číslem. [9] => [10] => == Prvočíselnost jedničky == [11] => 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činitel]]i, zatímco jednička patří mezi takzvané [[jednotka (teorie okruhů)|jednotky]]. [12] => [13] => == Vlastnosti == [14] => * 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. [15] => * Každé složené číslo lze jednoznačně vyjádřit jako součin prvočísel. Proces rozkladu čísla na jeho prvočíselné [[činitel]]e (prvočinitele) se nazývá [[faktorizace]]. Např. 24 = 2^3\cdot 3. [16] => * [[Okruh (algebra)|Okruh]] \mathbb{Z}/n{\mathbb{Z}} (viz [[množina zbytkových tříd]]) je [[těleso (algebra)|těleso]], právě když n je prvočíslo. Jinak vyjádřeno: n je prvočíslo, právě když \varphi(n) = n - 1, kde \varphi(n) je [[Eulerova funkce|počet invertovatelných prvků]] v \mathbb{Z}/n{\mathbb{Z}}. [17] => * Pokud p je prvočíslo a 0 < a < p je celé číslo, pak a^{p} - a je dělitelné p. ([[Malá Fermatova věta]]) [18] => * Pokud n je kladné celé číslo větší než jedna, existuje prvočíslo p tak, že n < p < 2n. ([[Bertrandův postulát]]) [19] => * Číslo p větší než jedna je prvočíslo, právě když (p-1)!\ \equiv\ -1 \pmod p. ([[Wilsonova věta]]) [20] => * Pokud G je konečná [[grupa]] a p^n je nejvyšší mocnina prvočísla p, která dělí [[řád grupy]] G, má grupa G [[podgrupa|podgrupu]] řádu p^n. [21] => * Pokud p je prvočíslo a G je grupa s p^n prvky, obsahuje G prvek řádu p. [22] => * Prvočísel je nekonečně mnoho. (Viz níže.) [23] => * Suma převrácených hodnot prvočísel diverguje. [24] => * Hustota prvočísel je asymptoticky 1/\ln(n), kde \ln(n) je [[logaritmus|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. [25] => * Největší dnes (prosinec 2018) známé prvočíslo je 282 589 933 − 1, má 24 862 048 dekadických cifer.[https://www.mersenne.org/primes/?press=M82589933 GIMPS Discovers Largest Known Prime Number: 282,589,933-1], [[GIMPS]], 21. 12. 2018 Je to 51. známé [[Mersennovo prvočíslo]], označované jako M82589933. Bylo nalezeno [[7. prosinec|7. prosince]] [[2018]]. [26] => [27] => Zkoumáním vlastností prvočísel se zabývá [[teorie čísel]]. Zobecněním prvočísel jsou v [[abstraktní algebra|abstraktní algebře]] [[prvočinitel]]é. [28] => [29] => == Výskyt prvočísel == [30] => Prvočísel je nekonečně mnoho. ([[Důkaz sporem]]: Nechť existuje jen konečně mnoho prvočísel. Označme je p_1, p_2, \ldots, p_n. Potom číslo x = p_1 p_2 \cdots 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]].) [31] => [32] => Podle [[Bertrandův postulát|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. (I z této věty lze dovodit, že prvočísel je nekonečně mnoho.) [33] => [34] => 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, \ldots, (k+1)!+k+1 obsahuje k složených čísel. Tato čísla jsou totiž po řadě dělitelná dvěma, třemi, …, k+1. [35] => [36] => 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íž [[matematický důkaz|důkaz]] je vypsána odměna milion dolarů. [37] => [38] => === Speciální prvočísla === [39] => Některá prvočísla lze vyjádřit v některé z několika matematicky zajímavých podob. Patří sem například: [40] => * [[Fermatovo číslo|Fermatova čísla]]: Prvočísly je prvních pět čísel ve formě 2^{(2^n)} + 1. [41] => * [[Mersennovo prvočíslo|Mersennova prvočísla]]: Prvočíslo ve formě 2^p - 1, kde p je jiné prvočíslo. Mersennovými prvočísly je mnoho z největších známých prvočísel. [42] => * Některá prvočísla lze vyjádřit ve formě 1 + 2 \cdot 6^n.[https://oeis.org/A205776 A205776: Primes of the form 2*6^n+1]. [[OEIS]] [43] => [44] => == Využití == [45] => Velký praktický význam mají prvočísla v [[kryptografie|kryptografii]], například v šifrovacích systémech jako je [[RSA]]. [46] => [47] => Pro vytvoření seznamu prvočísel existují různé [[algoritmus|algoritmy]], např. [[Eratosthenovo síto]]. [48] => [49] => == Testování prvočíselnosti == [50] => Otestovat, zda je číslo prvočíslem, tedy [[testování prvočíselnosti|testovat prvočíselnost]] je možné [[asymptotická složitost|asymptoticky]] v [[polynomiální algoritmus|polynomiálním čase]] [[algoritmus AKS|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í algoritmus|pravděpodobnostních algoritmů]], například [[Millerův-Rabinův test prvočíselnosti|Millerova-Rabinova algoritmu]]. [51] => [52] => Testování prvočíselnosti pomocí algoritmu využívajícího vlastností eliptických křivek ([[ECPP]]) je nejrychlejší známý algoritmus.{{en}}[http://primes.utm.edu/ The prime pages], primes.utm.edu [53] => [54] => === Příklad testovacího algoritmu === [55] => 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. [56] => [57] => public static bool IsPrvocislo(int num) [58] => { [59] => if (num == 1) [60] => return false; [61] => [62] => int odmocnina = (int) floor(sqrt(num)); [63] => [64] => for (int i = 2; i <= odmocnina; i++) [65] => { [66] => if (num % i == 0) [67] => return false; [68] => } [69] => [70] => return true; [71] => } [72] => [73] => [74] => == Prvočísla menší než 1000 == [75] => 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 [76] => [77] => == Největší známé prvočíslo == [78] => Největší známé prvočíslo je 282 589 933 − 1. Jedná se o [[číslo]], které má 24 862 048 [[Číslice|číslic]] v [[Desítková soustava|desítkové soustavě]]. Číslo bylo objeveno v rámci projektu [[Great Internet Mersenne Prime Search|GIMPS]] v prosinci 2018.{{Citace elektronického periodika [79] => | titul = 51st Known Mersenne Prime Discovered [80] => | url = https://www.mersenne.org/primes/press/M82589933.html [81] => | periodikum = www.mersenne.org [82] => | datum přístupu = 2019-08-26 [83] => | jazyk = en [84] => }} Jeho přesná podoba je uvedena níže, kde je pro zjednodušení zobrazeno pouze prvních a posledních 120 číslic.
148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560 ... [85] => [86] => (mezitím je 24 861 808 dalších číslic) [87] => [88] => ... 062107557947958297531595208807192693676521782184472526640076912114355308311969487633766457823695074037951210325217902591
[89] => [90] => == Odkazy == [91] => === Reference === [92] => [93] => [94] => === Související články === [95] => * [[Eratosthenovo síto]] [96] => * [[Mersennovo prvočíslo]] [97] => * [[Emirp]] [98] => * [[Prvočíselný rozklad]] [99] => * [[Prvočíselná dvojice]] [100] => * [[Wieferichovo prvočíslo]] [101] => * [[Ulamova spirála]] [102] => * [[2147483647]] [103] => * [[Ilegální prvočíslo]] [104] => * [[Poloprvočíslo]] [105] => [106] => === Externí odkazy === [107] => * {{Commonscat}} [108] => * {{Wikislovník|heslo=prvočíslo}} [109] => * {{Wikiverzita|kurs=Prvočísla}} [110] => * {{en}} [http://primes.utm.edu/ The Primes Pages] – přehledové i aktuální informace o výzkumu prvočísel [111] => * {{en}} [http://www.prime-numbers.org/ www.prime-numbers.org] – seznam prvočísel do 10 miliard [112] => * {{en}} [https://web.archive.org/web/20110317082045/http://www.walter-fendt.de/m14e/primes.htm Prvočísla do jednoho bilionu] [113] => {{Autoritní data}} [114] => [115] => [[Kategorie:Čísla]] [116] => [[Kategorie:Prvočísla|*]] [117] => [[Kategorie:Teorie čísel]] [] => )
good wiki

Prvočíslo

More about us

About

Expert Team

Vivamus eget neque lacus. Pellentesque egauris ex.

Award winning agency

Lorem ipsum, dolor sit amet consectetur elitorceat .

10 Year Exp.

Pellen tesque eget, mauris lorem iupsum neque lacus.

You might be interested in

,'Mersennovo prvočíslo','Eratosthenovo síto','Bertrandův postulát','prvočinitel','Great Internet Mersenne Prime Search','2147483647','C++','Prvočíselný rozklad','dělení','Malá Fermatova věta','Číslice','Důkaz sporem'

2147483647

C++

Číslice

Dělení

Prvočinitel