Số nguyên tố là một số nguyên $p>1$ mà các ước dương duy nhất của nó là $1$ và chính $p$; mọi số nguyên $n>1$ không nguyên tố đều là hợp số, nghĩa là nó tách thành $n=a\cdot b$ với $1<a,b<n$. Mục tiêu của Mệnh đề 20, Quyển IX trong Cơ bản của Euclid (khoảng 300 TCN) — theo bản dịch Heath, 'Các số nguyên tố nhiều hơn bất kỳ tập hữu hạn số nguyên tố nào được chỉ định' — là chỉ ra rằng tập $\mathbb{P}=\{2,3,5,7,11,\dots\}$ không thể bị vét cạn bởi một danh sách hữu hạn.

Để ý dạng logic trong phát biểu của chính Euclid: nó không nói 'có vô hạn số nguyên tố' mà là một phép dựng — đưa tôi một tập số nguyên tố bất kỳ đã chỉ định, tôi sẽ chỉ ra một số nguyên tố không nằm trong đó. Vô hạn chỉ xuất hiện dưới dạng sự bất khả của tính đầy đủ cho danh sách hữu hạn, đúng cách toán học Hy Lạp cổ đại tiếp cận vô hạn.

Chứng minh tựa trên hai trụ đã được xây sẵn trong Cơ bản: mọi số nguyên lớn hơn $1$ đều có ước nguyên tố (Quyển VII, Mệnh đề 31), và sự kiện sơ cấp rằng ước của hai số cũng chia hết hiệu của chúng — động cơ đằng sau mẹo '+1' ở Bước 3.