Chứng minh rằng tồn tại vô hạn các số nguyên tố.

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ố.