Prvočíslo

z Wikipédie, slobodnej encyklopédie

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

Čísla 0 a 1 sa nepovažujú ani za prvočísla ani za zložené čísla. Každé prirodzené číslo, ktoré je väčšie ako 1, je buď prvočíslo alebo zložené číslo. 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, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...
Rozloženie prvočísel nie väčších než 400.

Vlastnosti[upraviť | upraviť zdroj]

  • 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 ľubovoľné celé číslo, potom je ap − a deliteľné p. (Malá Fermatova veta).
  • Ak n je kladné celé číslo, existuje prvočíslo p také, že platí n < p ≤ 2n. (Bertrandov postulát)
  • 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é delitele 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í ľubovoľným z nich dostaneme vždy zvyšok 1. Teda číslo x je buď prvočíslo, alebo je deliteľné nejakým iným prvočíslom, ktoré nebolo medzi p1...pn. To znamená, že množina prvočísel p1...pn nebola úplná, čo je spor s predpokladom.
  • Množina prvočísel je spočítateľná.
  • Množina všetkých prvočísel spolu s reláciou deliteľnosti je príkladom spočítateľného protireťazca.
  • Množina prvočísel obsahuje konečné aritmetické postupnosti ľubovoľnej dĺžky. Toto tvrdenie predstavovalo mnoho rokov odolávajúcu hypotézu. V roku 2004 ju pozitívne zodpovedali Ben Green a Terence Tao.[1]

Mersennove prvočísla[upraviť | upraviť zdroj]

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. Príkladmi na Mersennove prvočísla môžu byť prvočíslo 3=22-1 alebo 7=23-1. Čo je na nich také zaujímavé je skutočnosť, že takýchto prvočísel je zatiaľ odhalených pomerne málo, presne 51. Zatiaľ posledné bolo objavené 21. decembra 2018 a skladá sa z 24 862 048 číslic. Toto číslo je zároveň najvyšším známym prvočíslom. Je výsledkom 282 589 933-1.[2]

Hľadanie prvočísel[upraviť | upraviť zdroj]

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

Využitie[upraviť | upraviť zdroj]

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

Referencie[upraviť | upraviť zdroj]

  1. Prvočísla a zložené čísla [online]. https://www.galeje.sk, [cit. 2019-07-31]. Dostupné online.
  2. Largest Known Prime Number: 282,589,933-1 [online]. mersenne.org, 21.12.2018, rev. 2018-12-21, [cit. 2019-01-04]. Dostupné online. (angličtina)

Externé obrazy[upraviť | upraviť zdroj]