Vlastnosti prvočísel

Prvočísla majú veľa zaujímavých vlastností:

• Prvočísel je nekonečne veľa. Dôkaz: predpokladajme, že existuje konečný zoznam všetkých prvočísel. Vynásobme všetky navzájom a pripočítame 1. Toto číslo nemôže byť deliteľné žiadnym prvočíslom zo zoznamu (pri delení každým prvočíslom zo zoznamu vznikne zvyšok 1), ale musí byť deliteľné nejakým prvočíslom, takže musí existovať prvočíslo mimo zoznamu. Lenže v našom zozname mali byť všetky prvočísla, a preto nemalo existovať žiadne prvočíslo mimo neho. Takže nemôže existovať konečný zoznam všetkých prvočísel, a preto musí byť prvočísel nekonečne veľa.
• Pre každé celé číslo väčšie ako jedna existuje rozklad na súčin prvočísel (čo je nájdenie takých prvočísel, aby bol ich súčin rovný pôvodnému číslu); tento rozklad je jednoznačný (Základná veta aritmetiky).
• Je možné nájsť ľubovoľne veľkú (konečnú) postupnosť čísel, ktoré idú po sebe, bez prvočísel, a to kvôli tomu, že medzi číslami X! (faktoriál) + 2 až X! + X nie je prvočíslo (X! + n pre n ≤ X je deliteľné n).
• Každé prvočíslo okrem 2 sa dá zapísať buď ako 4n+1, alebo ako 4n-1; tie v tvare 4n+1 sa vždy dajú rozložiť na súčet dvoch druhých mocnín, tie v tvare 4n-1 sa takýmto spôsobom nikdy rozložiť nedajú.
• Pre akúkoľvek kladnú celú hodnotu čísla n existuje prvočíslo ležiace medzi n a 2n vrátane týchto čísel (Bertrandov postulát).
• Vždy, keď je p prvočíslo a a je kladné celé číslo, tak musí platiť, že a^p – a je deliteľné p (Malá Fermatova veta). To však neznamená, že ak p nie je prvočíslo, tak a^p – a nie je deliteľné a. Čísla p, ktoré spĺňajú to, že a^p – a je deliteľné p, pre ľubovoľné číslo a, a pritom nie sú prvočísla, sa nazývajú Carmichaelove čísla.