Giả sử phản chứng rằng có hữu hạn số nguyên tố, cụ thể là các số nguyên tố $p_1, p_2, \dots, p_n$.

Tiếp theo, ta sẽ xây dựng một số nguyên tố mới từ các số nguyên tố đã có.

Ta chọn

$P = p_1 . p_2 . \dots . p_n + 1$

Ta thấy rằng $P$ chia cho $p_1, \dots, p_n$ đều dư $1$.

Do đó $P$ là một số nguyên tố nếu $P \neq 1$.

Tuy nhiên, do các số nguyên tố lớn hơn hoặc bằng 2, nên tập hợp $p_i$ là ko rỗng. Suy ra $P$ lớn hơn 1 và từ đó $P$ có ít nhất 2 ước là $1$ và $P$.

Từ định nghĩa của $P$ ta cũng có thể thấy rằng $P$ lớn hơn mọi số nguyên tố $p_1, \dots, p_n$. Điều này mâu thuẫn với việc có hữu hạn số nguyên tố.

Vậy có vô hạn số nguyên tố.

Định lý Eculid: Tập hợp số nguyên tố là vô hạn

Chứng minh: Giả sử có hữu hạn số nguyên tố là `p_1,p_2,...,p_n`

Xét `A=p_1p_2....p_n+1` thì A không trùng với số nào trong các `p_1,p_2,...,p_n` nên `A` là hợp số

Do đó `A` có ước nguyên tố là `p`

Vì chỉ có hữu hạn số nguyên tố là `p_1,p_2,...,p_n` nên `p∈{p_1,p_2,...,p_n}`

Như vậy

`A\vdotsp`

`p_1p_2...p_n\vdotsp`

`→1\vdotsp` (vô lý)