Dokaz da postoji beskonačno mnogo prostih brojeva

 Pozdrav svima. Danas ćemo dokazati da postoji beskonačno mnogo prostih brojeva.  Ovaj dokaz je prvi izveo grčki matematičar Euklid.

Teorema: Postoji beskonačno mnogo prostih brojeva.

Dokaz:

Pretpostavimo da postoji konačan broj prostih brojeva. Označimo broj prostih brojeva sa $n$, a same proste brojeve sa $p$ i indeksima $1,2 \ldots, n-1,n$ . Dakle imamo konačan skup prostih brojeva $p_1,p_2,\ldots ,p_{n-1},p_n$.

Sada, konstruišimo broj $q$ na sledeći način:

$$q=p_1 \cdot p_2 \cdot \ldots \cdot p_{n-1}\cdot p_n+1$$

Tada $q$ može biti ili prost ili složen broj. Jasno je da $q$ ne može biti prost broj jer smo pretpostavili da je broj prostih brojeva konačan i da je najveći prost broj broj $p_n$. Dakle, $q$ mora biti složen broj. Ukoliko je $q$ složen broj onda postoji neki prost broj $p$ iz skupa $p_1,p_2,\ldots ,p_{n-1},p_n$ koji ga deli. Označimo sa $P$ proizvod $p_1 \cdot p_2 \cdot \ldots \cdot p_{n-1}\cdot p_n$. Tada $p$ istovremeno deli i $P$ i $P+1=q$ što znači da $p$ mora da deli i razliku $(P+1)-P$, tj. sledi da $p$ deli broj $1$. Ali kako nijedan prost broj ne deli broj $1$ zaključujemo da $p$ ne može biti u skupu $p_1,p_2,\ldots ,p_{n-1},p_n$. Ovo znači da nezavisno od toga koliki je broj $n$ uvek postoji barem još jedan prost broj van konačnog skupa, stoga postoji beskonačno mnogo prostih brojeva.

$\blacksquare$