Prosti broj: razlika između inačica

'''Prosti brojevi''' ili '''primbrojevi''' su svi [[prirodni brojevi]] veći od 1 koji su bez [[Modularna aritmetika|ostatka]] [[djelitelj|djeljivi]] samo s [[jedan|brojem 1]] i sami sa sobom. Prirodni brojevi veći od 1 koji nisu prosti brojevi nazivaju se [[složen broj|složenim brojevima]].<ref name=":0">{{Citiranje knjige |title=Uvod u teoriju brojeva |author=Andrej Dujella |authorlink=Andrej Dujella |year=2008 |url=https://web.archive.org/web/20210407155741/https://www.mathos.unios.hr/images/homepages/mirela/UUTB/utblink.pdf |format=PDF |publisher=Prirodoslovno-matematički fakultet |location=Zagreb |access-date=7. travnja 2021. |archive-date=7. travnja 2021. |archive-url=https://web.archive.org/web/20210407155741/https://www.mathos.unios.hr/images/homepages/mirela/UUTB/utblink.pdf |url-status=bot: unknown }}</ref>{{Is|6}} Na primjer, broj 5 je prost jer je djeljiv samo s 1 i 5, dok je 6 složen jer se osim s 1 i 6 može podijeliti i brojevima 2 i 3.

pa <math>N</math> nije djeljiv ni s jednim od njih. No prema [[Osnovni stavak aritmetike|Osnovnom stavku aritmetike]] svaki bi se broj morao moći zapisati kao umnožak konačno mnogo prostih brojeva,<ref>{{Citiranje knjige |title=Uvod u teoriju brojeva |author=Ivan Matić |year=2013 |url=https://www.mathos.unios.hr/images/homepages/mirela/UUTB/uvod_u_teoriju_brojeva.pdf |format=PDF |pages=11 |location=Osijek |access-date=7. travnja 2021. |archive-date=7. travnja 2021. |archive-url=https://web.archive.org/web/20210407155723/https://www.mathos.unios.hr/images/homepages/mirela/UUTB/uvod_u_teoriju_brojeva.pdf |formaturl-status=PDFbot: |pages=11unknown |location=Osijek}}</ref> a za ovakav <math>N</math> to ne može biti nijedan broj iz skupa <math> P </math>. Očito postoje prosti brojevi izvan tog skupa, čime se početna tvrdnja dovodi u kontradikciju.