Prvočíslo má přesně dva dělitele: 1 a samo sebe. První prvočísla jsou 2, 3, 5, 7, 11, 13. Číslo 2 je jediné sudé prvočíslo. Číslo 1 není prvočíslo, protože má pouze jednoho dělitele.

Prvočísla jsou stavebními kameny celých čísel. Každé celé číslo větší než 1 se jednoznačně rozkládá na prvočísla, což se nazývá základní věta aritmetiky. Euklid dokázal, že prvočísel existuje nekonečně mnoho. Jejich rozdělení zůstává hlubokou záhadou a je spojeno s Riemannovou hypotézou.

Prvočísla jsou v kryptografii nezbytná. Šifrování RSA se spoléhá na obtížnost rozkladu velkých čísel na prvočísla. Testování prvočísel a generování prvočísel jsou aktivními oblastmi výpočetní teorie čísel. Navzdory své jednoduché definici prvočísla skrývají některá z nejhlubších tajemství matematiky.

• Přirozené číslo větší než 1 s přesně dvěma děliteli
• 2 je jediné sudé prvočíslo
• Nekonečně mnoho prvočísel (Euklid)
• Ústřední bod pro šifrování RSA