Prvočíslo: Prirodzené číslo, ktoré je väčšie ako 1 a ktorého jedinými deliteľmi sú 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, ...

• 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 a^p − 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 pⁿ je najvyššia mocnina prvočísla p, ktorá delí rád grupy G, potom má grupa G podgrupu rádu pⁿ.
• 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 p₁, p₂, …, p_n. Potom číslo x = p₁ · p₂ ··· p_n + 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 p₁...p_n. To znamená, že množina prvočísel p₁...p_n 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.

Istou skupinou prvočísel sú takzvané Mersennove prvočísla. Takéto prvočíslo sa dá zapísať v tvare 2^p-1, kde p je tiež prvočíslo. Príkladmi na Mersennove prvočísla môžu byť prvočíslo 3=2²-1 alebo 7=2³-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 2^{82 589 933}-1.

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

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