Praštevila in sestavljena števila

Glede na število deliteljev delimo naravna števila na tri skupine:

• število 1 - le en delitelj,

• praštevila - natanko dva delitelja,

• sestavljena števila - več kot dva delitelja.

Izrek: Praštevil je neskončno mnogo.

Dokaz: Recimo, da je števil končno mnogo: p₁, p₂,…, p_n, tako da je p_n največje praštevilo.
Pomnožimo ta praštevila med seboj in prištejmo 1, tako da je s = p₁• p₂•…• p_n + 1. Število s je praštevilo ali pa sestavljeno število. če je praštevilo, potem p_n ni največje praštevilo. če pa je sestavljeno število, mora biti deljivo z enim izmed praštevil p₁, p₂,…, p_n, vendar ni, saj pri deljenju dobimo ostanek 1. Torej praštevil ni končno.

Osnovni izrek aritmetike: Vsako naravno število lahko na en sam način zapišemo kot produkt

n = p₁^m1• p₂^m2• …• p_k^mk,

kjer so p₁, p₂,…, p_k praštevila in m₁, m₂,…, m_k naravna števila.