Chứng minh của Euclid về vô hạn số nguyên tố

Giả sử, để phản chứng, rằng chỉ có hữu hạn số nguyên tố, và cho $p_1, p_2, \dots, p_n$ là danh sách đầy đủ tất cả chúng.

Xét số $N = p_1 p_2 \cdots p_n + 1$. Vì $N > 1$, nó phải có ít nhất một ước nguyên tố; gọi là $p$ (mọi số nguyên lớn hơn $1$ đều có một ước nguyên tố).

Theo giả thiết, $p_1, \dots, p_n$ là danh sách tất cả số nguyên tố, nên $p$ phải bằng $p_i$ với $i$ nào đó. Đặc biệt, $p$ chia hết tích $p_1 p_2 \cdots p_n$.

Nhưng $p$ cũng chia hết $N = p_1 p_2 \cdots p_n + 1$. Nếu $p$ chia hết cả $p_1 p_2 \cdots p_n$ và $N$, thì $p$ chia hết hiệu của chúng: $p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1$.

Không số nguyên tố nào chia hết $1$, vì mọi số nguyên tố đều lớn hơn $1$. Đây là mâu thuẫn. Do đó giả thiết ban đầu — rằng chỉ có hữu hạn số nguyên tố — phải sai, nên có vô hạn số nguyên tố.