Prvočíslo: Rozdiel medzi revíziami

z Wikipédie, slobodnej encyklopédie
Smazaný obsah Přidaný obsah
Mirec (diskusia | príspevky)
opravený odkaz na 'Eratosthenovo sito'
AtonX (diskusia | príspevky)
Riadok 23: Riadok 23:


== Hľadanie prvočísel==
== Hľadanie prvočísel==
Na vytvorenie zoznamu prvočísel existujú rôzne [[algoritmus|algoritmy]], napr. [[Eratosthenovo sito|Eratosthenovo sito]].
Na vytvorenie zoznamu prvočísel existujú rôzne [[algoritmus|algoritmy]], napr. [[Eratostenovo sito]].


== Využitie ==
== Využitie ==

Verzia z 11:57, 20. november 2005

Prvočíslo je prirodzené číslo, ktorého jedinými deliteľmi sú 1 a ono samo. Prirodzené čísla, ktoré nie sú prvočíslami sa s výnimkou čísla 1 nazývajú zložené čísla.

Čísla 0 a 1 nie sú považované ani za prvočísla ani za zložené čísla. Každé prirodzené číslo väčšie ako 1 je buď prvočíslom, alebo zloženým číslom. Skúmaním vlastností prvočísel sa zaoberá teória čísel.

Začiatok radu prvočísel:

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

Vlastnosti

  • Ak p je prvočíslo a p delí súčin čísel a a b, potom p delí a alebo p delí b.
  • Ak p je prvočíslo a a je ľubovolné celé číslo, potom je ap − a delitelné p.
  • Ak n je kladné celé číslo, existuje prvočíslo p také, že platí n < p ≤ 2n.
  • Pre každé prvočíslo p > 2 existuje prirodzené číslo n také, že platí p = 4n ± 1.
  • Pre každé prvočíslo p > 3 existuje prirodzené číslo n také, že platí p = 6n ± 1.
  • Ak p je prvočíslo iné ako 2 a 5, potom 1/p má v desiatkovej číselnej sústave nekonečný desatinný rozvoj.
  • Každé zložené číslo sa dá jednoznačne vyjadriť ako súčin prvočísel. Proces rozkladu čísla na jeho prvočíselné činitele (prvočinitele) sa nazýva faktorizácia. Napr. 24 = 2³ ⋅ 3.
  • Ak p je prvočíslo a G je grupa s pn prvkami, potom G obsahuje prvok rádu p.
  • Ak G je konečná grupa a pn je najvyššia mocnina prvočísla p, ktorá delí rád grupy G, potom má grupa G podgrupu rádu pn.
  • Okruh Z/nZ je teleso, práve vtedy, keď n je prvočíslo. Inak povedané: n je prvočíslo, práve vtedy keď φ(n) = n − 1.
  • Prvočísel je nekonečne veľa. Dôkaz sporom: Nech existuje iba konečne veľa prvočísel. Označme ich p1, p2, …, pn. Potom číslo x = p1 · p2 ··· pn + 1 nie je deliteľné žiadnym z týchto prvočísel, pretože pri delení dostaneme vždy zvyšok 1. Teda číslo x musí byt buď prvočíslo, alebo musí byt deliteľné nejakým iným prvočíslom. To ale znamená, že množina prvočísel zo začiatku dôkazu nebola úplná, čo je spor s predpokladom.)

Mersennove prvočísla

Istou skupinou prvočísel sú takzvané Mersennove prvočísla. Takéto prvočíslo sa dá zapísať v tvare 2p-1, kde p je tiež prvočíslo. Čo je na nich také zaujímavé je skutočnosť, že takýchto prvočísel je zatiaľ odhalených veľmi málo (presne 42 - zatiaľ posledné objavené sa skladá z 7 816 230 číslic). Príkladmi na Mersennove prvočísla môžu byť prvočíslo 3 (22-1) alebo 7 (23-1).

Hľadanie prvočísel

Na vytvorenie zoznamu prvočísel existujú rôzne algoritmy, napr. Eratostenovo sito.

Využitie

Veľký praktický význam majú prvočísla v Kryptológii.

Externe odkazy