素数の無限性(ユークリッド)

任意の有限な素数のリスト $p_1,\dots,p_n$ が与えられたとき、$N=p_1p_2\cdots p_n+1$ とおく。どの $p_i$ も $N$ を割り切らない($p_i$ で割ると常に余り $1$ が出る)。算術の基本定理により $N$ はある素因数 $q$ を持つ。$q\ne p_i$ がすべての $i$ について成り立つので、$q$ は元のリストにない素数である。したがって、いかなる有限リストもすべての素数を含むことはできない。