Prost broj

#fax #math #ds1 [deo poglavlja "prirodni brojevi" i "celi brojevi"]

Def. Prirodan broj je prost ako su njegovi jedini delioci i . U suprotnom je složen.

Stav. je prost broj i ()
Tada ili

Dokaz:
Iz teoreme sledi

Stav. Za prirodni broj važi da je prost ili proizvod prostih brojeva.

Teorema. Postoji beskonačno mnogo prostih brojeva.

Dokaz: pps ima ih konačno mnogo
Neka su to
Tada mora biti složen (jer )
nijedan od brojeva ne deli je prost (kontradikcija).

Osnovna teorema aritmetike

Teorema. Svaki prirodni broj može se napisati u obliku proizvoda stepena prostih brojeva na jedinstven način (do na redosled faktora).
, su prosti;