ユークリッドは、「原論」で素数（1と自身以外に約数をもたない2以上の自然数）が無限に存在することを証明した。その証明は以下のように背理法を使う。
もし、素数が有限個であったとする。その素数がp₁，p₂，p₃，……，p_nで、これらが素数のすべてとする。このとき、これらの素数よりも大きい数、(p₁×p₂×p₃×……×p_n)＋1は、p₁，p₂，p₃，……，p_nのどの数で割っても1余る。つまり、p₁，p₂，p₃，……，p_nで割り切れないのだから、これも素数でなければならない。これは、p₁，p₂，p₃，……，p_nが素数のすべてとするという仮定に反する。
よって、素数が有限個という仮定がおかしいことがわかる。
このユークリッドの素数の無限性の証明方法を用いれば、桁の大きい素数を探すことも考られるが、現在ではあまり用いられない。